AI 助理
备案控制台
开发者社区 云计算 文章 正文

leetcode第39题

2022-09-26 98
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 对回溯法又有了更深的了解，一般的架构就是一个大的 for 循环，然后先 add，接着利用递归进行向前遍历，然后再 remove ，继续循环。而解法二的动态规划就是一定要找到递进的规则，开始的时候就想偏了，导致迟迟想不出来。

image.png

给几个数字，一个目标值，输出所有和等于目标值的组合。

解法一 回溯法

参考这里) ，就是先向前列举所有情况，得到一个解或者走不通的时候就回溯。和37题有异曲同工之处，也算是回溯法很典型的应用，直接看代码吧。

publicList<List<Integer>>combinationSum(int[] nums, inttarget) {
List<List<Integer>>list=newArrayList<>();
backtrack(list, newArrayList<>(), nums, target, 0);
returnlist;
}
privatevoidbacktrack(List<List<Integer>>list, List<Integer>tempList, int [] nums, intremain, intstart){
if(remain<0) return;
elseif(remain==0) list.add(newArrayList<>(tempList));
else{ 
for(inti=start; i<nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain-nums[i], i); 
//找到了一个解或者 remain < 0 了，将当前数字移除，然后继续尝试tempList.remove(tempList.size() -1);
        }
    }
}

时间复杂度：

空间复杂度：

解法二 动态规划

参考这里。动态规划的关键就是找到递进关系，看到了下边的评论想通的。

image.png我们用一个 opt 的 list，然后依次求出 opt [ 0 ]，opt [ 1 ] ... opt [ target ]。

opt[0]，表示和为 0 的所有情况的组合。

opt[1]，表示和为 1 的所有情况的组合。

opt[2]，表示和为 2 的所有情况的组合。

...

opt[target]，表示和为 target 的所有情况的组合，也就是题目所要求的。

递进关系就是，sum 代表要求的和，如果想求 opt [ sum ] ，就遍历给定的数组 nums，然后分两种情况。

  • 如果 sum 刚好等于 nums [ i ]，那么就直接把 nums [ i ] 加到 list 里，算作一种情况。
    例如 nums = [ 2, 3, 6, 7 ] , target = 7。
    当求 sum = 3 的时候，也就是求 opt [ 3 ] 的时候，此时当遍历到 nums [ 1 ]，此时 nums [ 1 ] == sum == 3，所以此时 opt [ 3 ] = [ [ 3 ] ]。
  • 如果 sum 大于 nums [ i ]，那么我们就把 opt [ sum - nums [ i ] ] 的所有情况都加上 nums [ i ] 然后作为 opt [ sum ] 。
    例如 nums = [ 1, 2, 3, 6, 7 ] , target = 7。
    当 sum 等于 5 的时候，也就是求 opt [ 5 ] 的时候，此时当遍历到 nums [ 1 ]，此时 nums [ 1 ] = 2 < sum。然后，就看 opt [ sum - nums [ i ] ] = opt [ 5 - 2 ] = opt [ 3 ]，而 opt [ 3 ] 在之前已经求好了，opt [ 3 ] = [ [ 1, 2 ], [ 3 ] ]，然后把 opt [ 3 ] 中的每一种情况都加上 nums [ 1 ] ，也就是 2，就变成了 [ [ 1, 2, 2 ], [ 3, 2 ] ]，这个就是遍历到 nums [ 1 ] 时候的 opt [ 5 ]了。

上边的想法看起来没什么问题，但跑了下遇到一个问题。

比如求 nums = [ 2, 3, 6, 7 ] , target = 7 的时候。

求 opt [ 5 ]，然后遍历到 nums [ 0 ] = 2 的时候，就把 opt [ 3 ] = [ [ 3 ] ] 的所有情况加上 2，也就是[ 3 2 ] 加到 opt [ 5 ] 上。接着遍历到 nums [ 2 ] = 3 的时候，就把 opt [ 2 ] = [ [ 2 ] ] 的所有情况加上 3，然后 [ 2 3 ] 这种情况加到 opt [ 5 ] 上，此时 opt [ 5 ] = [ [ 3 2]，[ 2 3 ] ]。这样出现了重复的情况，需要解决一下。

这样就相当于二维数组去重，也就是 [ [ 3 2 ]，[ 2 3 ] , [ 1 ] ] 这样的列表去重变成 [ [ 2 3 ] , [ 1 ] ] 。最普通的想法就是两个 for 循环然后一个一个比对，把重复的去掉。但这样实在是太麻烦了，因为比对的时候又要比对列表是否相等，比对列表是否相等又比较麻烦。

这里看到一个方法，就是把每个 list 转成 string，然后利用 HashMap 的 key 是唯一的，把每个 list 当做 key 加入到 HashMap 中，这样就实现了去重，然后再把 string 还原为 list。

privateList<List<Integer>>removeDuplicate(List<List<Integer>>list) {
Map<String, String>ans=newHashMap<String, String>();
for (inti=0; i<list.size(); i++) {
List<Integer>l=list.get(i);
Collections.sort(l);
Stringkey="";
//[ 2 3 4] 转为 "2,3,4"for (intj=0; j<l.size() -1; j++) {
key=key+l.get(j) +",";
        }
key=key+l.get(l.size() -1);
ans.put(key, "");
    }
//根据逗号还原 ListList<List<Integer>>ans_list=newArrayList<List<Integer>>();
for (Stringk : ans.keySet()) {
String[] l=k.split(",");
List<Integer>temp=newArrayList<Integer>();
for (inti=0; i<l.length; i++) {
intc=Integer.parseInt(l[i]);
temp.add(c);
        }
ans_list.add(temp);
    }
returnans_list;
}

然后结合去重的方法，我们的问题就解决了。

publicList<List<Integer>>combinationSum(int[] nums, inttarget) {
List<List<List<Integer>>>ans=newArrayList<>(); //opt 数组Arrays.sort(nums);// 将数组有序，这样可以提现结束循环for (intsum=0; sum<=target; sum++) { // 从 0 到 target 求出每一个 optList<List<Integer>>ans_sum=newArrayList<List<Integer>>();
for (inti=0; i<nums.length; i++) { //遍历 numsif (nums[i] ==sum) { 
List<Integer>temp=newArrayList<Integer>();
temp.add(nums[i]);
ans_sum.add(temp);
            } elseif (nums[i] <sum) {
List<List<Integer>>ans_sub=ans.get(sum-nums[i]);
//每一个加上 nums[i]for (intj=0; j<ans_sub.size(); j++) {
List<Integer>temp=newArrayList<Integer>(ans_sub.get(j));
temp.add(nums[i]);
ans_sum.add(temp);
                }
            } else {
break;
            }
        }
ans.add(sum, ans_sum);
    }
returnremoveDuplicate(ans.get(target));
} 
privateList<List<Integer>>removeDuplicate(List<List<Integer>>list) {
Map<String, String>ans=newHashMap<String, String>();
for (inti=0; i<list.size(); i++) {
List<Integer>l=list.get(i);
Collections.sort(l);
Stringkey="";
//[ 2 3 4 ] 转为 "2,3,4"for (intj=0; j<l.size() -1; j++) {
key=key+l.get(j) +",";
        }
key=key+l.get(l.size() -1);
ans.put(key, "");
    }
//根据逗号还原 ListList<List<Integer>>ans_list=newArrayList<List<Integer>>();
for (Stringk : ans.keySet()) {
String[] l=k.split(",");
List<Integer>temp=newArrayList<Integer>();
for (inti=0; i<l.length; i++) {
intc=Integer.parseInt(l[i]);
temp.add(c);
        }
ans_list.add(temp);
    }
returnans_list;
}

时间复杂度：

空间复杂度：

还有另一种思路可以解决重复的问题。

之前对于 nums = [ 2, 3, 6, 7 ] , target = 7 ，我们用了两层 for 循环，分别对 opt 和 nums 进行遍历。

我们先求 opt [ 0 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]

然后再求 opt [ 1 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]

然后再求 opt [ 2 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]

...

最后再求 opt [ 7 ]，通过遍历 nums [ 0 ]， nums [ 1 ]， nums [ 2 ]， nums [ 3 ]。

求 opt [ 5 ] 的时候，出现了 [ 2 3 ]，[ 3 2 ] 这样重复的情况。

我们可以把两个 for 循环的遍历颠倒一下，外层遍历 nums，内层遍历 opt。

考虑 nums [ 0 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] ... 求出 opt [ 7 ]。

考虑 nums [ 1 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] ... 求出 opt [ 7 ]。

考虑 nums [ 2 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] ... 求出 opt [ 7 ]。

考虑 nums [ 3 ]，求出 opt [ 0 ]，求出 opt [ 1 ]，求出 opt [ 2 ]，求出 opt [ 3 ] ... 求出 opt [ 7 ]。

这样的话，每次循环会更新一次 opt [ 7 ]，最后次更新的 opt [ 7 ] 就是我们想要的了。

这样之前的问题，求 opt [ 5 ] 的时候，出现了 [ 2 3 ]，[ 3 2 ] 这样重复的情况就不会出现了，因为当考虑 nums [ 2 ] 的时候，opt [ 3 ] 里边还没有加入 [ 3 ] 。

思路就是上边说的了，但是写代码的时候遇到不少坑，大家也可以先尝试写一下。

publicList<List<Integer>>combinationSum(int[] nums, inttarget) {
List<List<List<Integer>>>ans=newArrayList<>();
Arrays.sort(nums);
if (nums[0] >target) {
returnnewArrayList<List<Integer>>();
    }
// 先初始化 ans[0] 到 ans[target]，因为每次循环是更新 ans,会用到 ans.get() 函数，如果不初始化会报错for (inti=0; i<=target; i++) {
List<List<Integer>>ans_i=newArrayList<List<Integer>>();
ans.add(i, ans_i);
    }
for (inti=0; i<nums.length; i++) {
for (intsum=nums[i]; sum<=target; sum++) {
List<List<Integer>>ans_sum=ans.get(sum);
List<List<Integer>>ans_sub=ans.get(sum-nums[i]);
//刚开始 ans_sub 的大小是 0，所以单独考虑一下这种情况if (sum==nums[i]) {
ArrayList<Integer>temp=newArrayList<Integer>();
temp.add(nums[i]);
ans_sum.add(temp);
            }
//如果 ans.get(sum - nums[i])大小不等于 0，就可以按之前的想法更新了。//每个 ans_sub[j] 都加上 nums[i]if (ans_sub.size() >0) {
for (intj=0; j<ans_sub.size(); j++) {
ArrayList<Integer>temp=newArrayList<Integer>(ans_sub.get(j));
temp.add(nums[i]);
ans_sum.add(temp);
                }
            }
        }
    }
returnans.get(target);
}

总

对回溯法又有了更深的了解，一般的架构就是一个大的 for 循环，然后先 add，接着利用递归进行向前遍历，然后再 remove ，继续循环。而解法二的动态规划就是一定要找到递进的规则，开始的时候就想偏了，导致迟迟想不出来。

白月光永恒
目录
相关文章
菊头蝙蝠
|
7月前
leetcode-472. 连接词
leetcode-472. 连接词
菊头蝙蝠
51 0
想当开心果哦
|
7月前
|
消息中间件 Kubernetes NoSQL
LeetCode 3、28、1351
LeetCode 3、28、1351
想当开心果哦
46 0
Cache_1024
单链表反转 LeetCode 206
单链表反转 LeetCode 206
Cache_1024
75 0
在下小吉.
顺手牵羊（LeetCode844.)
好多同学说这是双指针法，但是我认为叫它顺手牵羊法更合适
在下小吉.
82 0
ruicore
|
算法 Python
LeetCode 386. Lexicographical Numbers
给定一个整数 n, 返回从 1 到 n 的字典顺序。
ruicore
88 0
LeetCode 386. Lexicographical Numbers
白月光永恒
leetcode第53题
解法一和解法二的动态规划，只是在定义的时候一个表示以 i 开头的子数组，一个表示以 i 结尾的子数组，却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和，不如解法二直接，只保存最大的和。
白月光永恒
73 0
leetcode第53题
白月光永恒
|
算法
leetcode第45题
时间复杂度：O（n）。 空间复杂度：O（1）。 这里要注意一个细节，就是 for 循环中，i < nums.length - 1，少了末尾。因为开始的时候边界是第 0 个位置，steps 已经加 1 了。如下图，如果最后一步刚好跳到了末尾，此时 steps 其实不用加 1 了。如果是 i < nums.length，i 遍历到最后的时候，会进入 if 语句中，steps 会多加 1 。
白月光永恒
109 0
leetcode第45题
白月光永恒
leetcode第51题
较经典的回溯问题了，我们需要做的就是先在第一行放一个皇后，然后进入回溯，放下一行皇后的位置，一直走下去，如果已经放的皇后的数目等于 n 了，就加到最后的结果中。然后再回到上一行，变化皇后的位置，然后去找其他的解。 期间如果遇到当前行所有的位置都不能放皇后了，就再回到上一行，然后变化皇后的位置。再返回到下一行。 说起来可能还费力些，直接看代码吧。
白月光永恒
85 0
leetcode第51题
白月光永恒
|
算法
leetcode第40题
会发现出现了很多重复的结果，就是因为没有跳过重复的 1。在求 opt [ 1 ] 的时候就变成了 [ [ 1 ]，[ 1 ] ] 这样子，由于后边求的时候都是直接在原来每一个列表里加数字，所有后边都是加了两次了。
白月光永恒
69 0
leetcode第40题
白月光永恒
leetcode第28题
返回一个字符串 needle 在另一个字符串 haystack 中开始的位置，如果不存在就返回 -1 ，如果 needle 长度是 0 ，就返回 0 。 就是一一比较就好，看下代码吧。
白月光永恒
77 0
leetcode第28题