AI 助理
备案控制台
开发者社区 人工智能 文章 正文

leetcode第40题

2022-09-26 62
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 会发现出现了很多重复的结果，就是因为没有跳过重复的 1。在求 opt [ 1 ] 的时候就变成了 [ [ 1 ]，[ 1 ] ] 这样子，由于后边求的时候都是直接在原来每一个列表里加数字，所有后边都是加了两次了。

image.png

和上一道题非常像了，区别在于这里给的数组中有重复的数字，每个数字只能使用一次，然后同样是给出所有和等于 target 的情况。

解法一 回溯法

只需要在上题的基础上改一下就行了。直接看代码吧。

publicList<List<Integer>>combinationSum2(int[] candidates, inttarget) {
List<List<Integer>>ans=newArrayList<>();
getAnswer(ans, newArrayList<>(), candidates, target, 0);
/*************修改的地方*******************/// 如果是 Input: candidates = [2,5,2,1,2], target = 5,// 输出会出现 [2 2 1] [2 1 2] 这样的情况，所以要去重returnremoveDuplicate(ans);
/****************************************/}
privatevoidgetAnswer(List<List<Integer>>ans, ArrayList<Integer>temp, int[] candidates, inttarget, intstart) {
if (target==0) {
ans.add(newArrayList<Integer>(temp));
    } elseif (target<0) {
return;
    } else {
for (inti=start; i<candidates.length; i++) {
temp.add(candidates[i]);
/*************修改的地方*******************///i -> i + 1 ，因为每个数字只能用一次，所以下次遍历的时候不从自己开始getAnswer(ans, temp, candidates, target-candidates[i], i+1);
/****************************************/temp.remove(temp.size() -1);
        }
    }
}
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="";
for (intj=0; j<l.size() -1; j++) {
key=key+l.get(j) +",";
        }
key=key+l.get(l.size() -1);
ans.put(key, "");
    }
List<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>>combinationSum2(int[] candidates, inttarget) {
List<List<Integer>>ans=newArrayList<>();
Arrays.sort(candidates); //排序getAnswer(ans, newArrayList<>(), candidates, target, 0); 
returnans;
}
privatevoidgetAnswer(List<List<Integer>>ans, ArrayList<Integer>temp, int[] candidates, inttarget, intstart) {
if (target==0) {
ans.add(newArrayList<Integer>(temp));
    } elseif (target<0) {
return;
    } else {
for (inti=start; i<candidates.length; i++) {
//跳过重复的数字if(i>start&&candidates[i] ==candidates[i-1]) continue;  
temp.add(candidates[i]);
/*************修改的地方*******************///i -> i + 1 ，因为每个数字只能用一次，所以下次遍历的时候不从自己开始getAnswer(ans, temp, candidates, target-candidates[i], i+1);
/****************************************/temp.remove(temp.size() -1);
        }
    }
}

解法二 动态规划

怎么去更改上题的算法满足本题，暂时没想到，只想到就是再写个函数对答案再过滤一次。先记录给定的 nums 中的每个数字出现的次数，然后判断每个 list 的数字出现的次数是不是满足小于等于给定的 nums 中的每个数字出现的次数，不满足的话就剔除掉。如果大家有直接改之前算法的好办法可以告诉我，谢谢了。

此外，要注意一点就是上题中，给定的 nums 没有重复的，而这题中是有重复的。为了使得和之前一样，所以我们在算法中都得加上

if (i>0&&nums[i] ==nums[i-1]) {
continue;
}

跳过重复的数字，不然是不能 AC 的，至于原因下边分析下。

publicList<List<Integer>>combinationSum2(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++) { //遍历 nums/*******************修改的地方********************/if (i>0&&nums[i] ==nums[i-1]) {
continue;
            }
/***********************************************/if (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);
    }
returnremove(removeDuplicate(ans.get(target)),nums);
} 
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;
}
//过滤不满足答案的情况privateList<List<Integer>>remove(List<List<Integer>>list, int[] nums) {
HashMap<Integer, Integer>nh=newHashMap<Integer, Integer>();
List<List<Integer>>ans=newArrayList<List<Integer>>(list);
//记录每个数字出现的次数for (intn : nums) {
ints=nh.getOrDefault(n, 0);
nh.put(n, s+1);
    }
for (inti=0; i<list.size(); i++) {
List<Integer>l=list.get(i);
HashMap<Integer, Integer>temp=newHashMap<Integer, Integer>();
//记录每个 list 中数字出现的次数for (intn : l) {
ints=temp.getOrDefault(n, 0);
temp.put(n, s+1);
        }
for (intn : l) {
//进行比较if (temp.get(n) >nh.get(n)) {
ans.remove(l);
break;
            }
        }
    }
returnans;
}

如果不加跳过重复的数字的话，下边的样例不会通过。

image.png

这是因为我们求 opt 的时候每个列表的数量在以指数级增加，在上一个 opt 的基础上，每一个列表都增加 5 个 列表。

opt [ 1 ] = [ [ 1 ]，[ 1 ]，[ 1 ]，[ 1 ]，[ 1 ] ] 数量是 5，

opt [ 2 ] = [

[ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]，

[ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]

[ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]，

[ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]，

[ 1，1 ]， [ 1，1 ]，[ 1，1 ]，[ 1，1 ]，[ 1，1 ]，，

] 数量是 5 * 5。

opt [ 3 ] 数量是 5 * 5 * 5。

到了 opt [ 9 ] 就是 5 的 9 次方，数量是 1953125 内存爆炸了。

另一个算法也可以改一下'

publicList<List<Integer>>combinationSum2(int[] nums, inttarget) {
List<List<List<Integer>>>ans=newArrayList<>();
Arrays.sort(nums);
if (nums[0] >target) {
returnnewArrayList<List<Integer>>();
    }
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++) {
/*******************修改的地方********************/if (i>0&&nums[i] ==nums[i-1]) {
continue;
        }
/***********************************************/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]);
if (sum==nums[i]) {
ArrayList<Integer>temp=newArrayList<Integer>();
temp.add(nums[i]);
ans_sum.add(temp);
            }
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);
                }
            }
        }
    }
returnremove(ans.get(target), nums);
}
privateList<List<Integer>>remove(List<List<Integer>>list, int[] nums) {
HashMap<Integer, Integer>nh=newHashMap<Integer, Integer>();
List<List<Integer>>ans=newArrayList<List<Integer>>(list);
for (intn : nums) {
ints=nh.getOrDefault(n, 0);
nh.put(n, s+1);
    }
for (inti=0; i<list.size(); i++) {
List<Integer>l=list.get(i);
HashMap<Integer, Integer>temp=newHashMap<Integer, Integer>();
for (intn : l) {
ints=temp.getOrDefault(n, 0);
temp.put(n, s+1);
        }
for (intn : l) {
if (temp.get(n) >nh.get(n)) {
ans.remove(l);
break;
            }
        }
    }
returnans;
}

如果不加跳过重复的数字的话，下边的样例不会通过

会发现出现了很多重复的结果，就是因为没有跳过重复的 1。在求 opt [ 1 ] 的时候就变成了 [ [ 1 ]，[ 1 ] ] 这样子，由于后边求的时候都是直接在原来每一个列表里加数字，所有后边都是加了两次了。

总

和上题很像，基本上改一改就好了。排序的来排除重复的情况也很妙。还有就是改算法的时候，要考虑到题的要求的变化之处。

文章标签：
算法
白月光永恒
目录
相关文章
菊头蝙蝠
|
4月前
leetcode-472. 连接词
leetcode-472. 连接词
菊头蝙蝠
41 0
菊头蝙蝠
|
4月前
|
C++ Python
leetcode-283:移动零
leetcode-283:移动零
菊头蝙蝠
26 0
服务端技术栈
|
1月前
|
算法
LeetCode第66题加一
LeetCode第66题"加一"的解题方法，通过遍历数组从后向前处理每一位的加法，并考虑进位情况，最终实现给定数字加一的功能。
服务端技术栈
22 0
LeetCode第66题加一
三哥一起来编程
LeetCode-1219 黄金矿工
LeetCode-1219 黄金矿工
三哥一起来编程
45 0
songwei4615.
leetcode 474一和零
leetcode 474一和零
songwei4615.
90 0
leetcode 474一和零
Ss1Two
|
算法 Java
一和零（LeetCode 474）
一和零（LeetCode 474）
Ss1Two
87 0
白月光永恒
|
存储 算法
leetcode第49题
时间复杂度：两层 for 循环，再加上比较字符串，如果字符串最长为 K，总的时间复杂度就是 O（n²K）。 空间复杂度：O（NK），用来存储结果。 解法一算是比较通用的解法，不管字符串里边是大写字母，小写字母，数字，都可以用这个算法解决。这道题的话，题目告诉我们字符串中只有小写字母，针对这个限制，我们可以再用一些针对性强的算法。 下边的算法本质是，我们只要把一类的字符串用某一种方法唯一的映射到同一个位置就可以。
白月光永恒
144 0
leetcode第49题
白月光永恒
|
人工智能 算法
leetcode第41题
对于这种要求空间复杂度的，我们可以先考虑如果有一个等大的空间，我们可以怎么做。然后再考虑如果直接用原数组怎么做，主要是要保证数组的信息不要丢失。目前遇到的，主要有两种方法就是交换和取相反数。
白月光永恒
83 0
leetcode第41题
白月光永恒
|
算法
leetcode第47题
基本上都是在上道题的基础上改出来了，一些技巧也是经常遇到，比如先排序，然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据，然后再想办法还原。
白月光永恒
74 0
leetcode第47题
白月光永恒
leetcode第34题
从左向右遍历，一旦出现等于 target 的值就结束，保存当前下标。如果从左到右没有找到 target，那么就直接返回 [ -1 , -1 ] 就可以了，因为从左到右没找到，那么从右到左也一定不会找到的。如果找到了，然后再从右到左遍历，一旦出现等于 target 的值就结束，保存当前下标。 时间复杂度是 O（n）并不满足题意，但可以了解下这个思路，从左到右，从右到左之前也遇到过。
白月光永恒
66 0
leetcode第34题