signed

QiShunwang

“诚信为本、客户至上”

leetcode 解题2021/3/21

2021/3/21 0:39:04   来源:

leetcode 150 逆波兰式 中等
Integer.parseInt(str);

leetcode 45 跳跃游戏 中等
每个可达元素的优先级=下标+值,最后一格最高优先级

leetcode 49 字母异位词分组 中等
题解1 将字母对应成质数 质数的乘积解析结果唯一 存在问题 字符过长乘积溢出
题解2 将单词中的字母顺序排列 比较是否相同

map.put(key, value) 
map.keySet().contains(key)==map.containsKey(key)  map.containsValue() 
map.remove(key);

String.valueOf(char数组) 
Arrays.sort(数组) 
new ArrayList<>(Arrays.asList(数组))

leetcode 44 通配符匹配 困难
思路1 递归 首先处理string或pattern为空的情况
比较s和p的首字母 如果有*(匹配空字符串、任意字符串)进行分情况递归讨论
存在问题 超时
思路2 动态规划 dp[i][j]表示s前i和p前j个字符是否匹配
实现代码》》边界问题

boolean dp[][] = new boolean[s.length()][p.length()];
dp[0][0] = true;
for(int i=0;i<=s.length();i++){
	for(int j=0;j<=p.length();j++){
		if(p.charAt(j-1)=='*'){ //j-1 对应第j个字符
			dp[i][j] = dp[i][j-1]; //匹配空字符串
			if(i>0&&dp[i-1][j]){ //匹配非空字符串  i>0满足dp[i-1][*]
				dp[i][j] = true;
		... ...
		else{
			if(i>0&&dp[i-1][j-1]&&(p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='?'){
				dp[i][j] = true;
			… …
return dp[s.length()][p.length()];

竞赛 构造连续值的最大数目
给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。
请返回从 0 开始(包括 0 ),你最多能 构造 出多少个连续整数。

思路好牛逼啊
public int getMaximumConsecutive(int[] coins) {
	Arrays.sort(coins);
    if(coins[0]!=1)
        return 1;
    int result = 1;
    for(int i=1;i<coins.length;i++){
    	if(coins[i]<=result+1){
			result += coins[i];
		}
		else{
			break;
		}
    }
    return result+1;
}

竞赛 N次操作后的最大分数和
给你 nums ,它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
在第 i 次操作时(操作编号从 1 开始),你需要:
1、选择两个元素 x 和 y 。
2、获得分数 i * gcd(x, y) 。
3、将 x 和 y 从 nums 中删除。
请你返回 n 次操作后你能获得的分数和最大为多少。
函数 gcd(x, y) 是 x 和 y 的最大公约数。