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

leetcode第40题

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

总

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

文章标签：
算法
白月光永恒
目录
相关文章
菊头蝙蝠
|
9月前
leetcode-1518：换酒问题
leetcode-1518：换酒问题
菊头蝙蝠
44 0
菊头蝙蝠
|
9月前
|
C++ Python
leetcode-283:移动零
leetcode-283:移动零
菊头蝙蝠
32 0
Far_Stars
|
存储
leetcode:53.最大字序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
Far_Stars
63 0
允诺@晴天
|
算法
LeetCode——944. 删列造序
LeetCode——944. 删列造序
允诺@晴天
125 0
白月光永恒
|
存储 算法
leetcode第43题
个位乘个位，得出一个数，然后个位乘十位，全部乘完以后，就再用十位乘以各个位。然后百位乘以各个位，最后将每次得出的数相加。十位的结果要补 1 个 0 ，百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。
白月光永恒
102 0
leetcode第43题
白月光永恒
|
人工智能 算法
leetcode第41题
对于这种要求空间复杂度的，我们可以先考虑如果有一个等大的空间，我们可以怎么做。然后再考虑如果直接用原数组怎么做，主要是要保证数组的信息不要丢失。目前遇到的，主要有两种方法就是交换和取相反数。
白月光永恒
103 0
leetcode第41题
白月光永恒
leetcode第39题
对回溯法又有了更深的了解，一般的架构就是一个大的 for 循环，然后先 add，接着利用递归进行向前遍历，然后再 remove ，继续循环。而解法二的动态规划就是一定要找到递进的规则，开始的时候就想偏了，导致迟迟想不出来。
白月光永恒
108 0
leetcode第39题
白月光永恒
leetcode第53题
解法一和解法二的动态规划，只是在定义的时候一个表示以 i 开头的子数组，一个表示以 i 结尾的子数组，却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和，不如解法二直接，只保存最大的和。
白月光永恒
82 0
leetcode第53题
白月光永恒
leetcode第18题
top18 和3Sum类似，只不过是找四个数，使得和为 target，并且不能有重复的序列。 如果之前没有做过3Sum可以先看看，自己在上边的基础上加了一个循环而已。
白月光永恒
101 0
leetcode第18题
白月光永恒
leetcode第14题
我们把原来的数组分成两部分，求出左半部分的最长公共前缀，求出右半部分的最长公共前缀，然后求出的两个结果再求最长公共前缀，就是最后的结果了。 求左半部分的最长公共前缀，我们可以继续把它分成两部分，按照上边的思路接着求。然后一直分成两部分，递归下去。 直到该部分只有 1 个字符串，那么最长公共子串就是它本身了，直接返回就可以了。
白月光永恒
91 0
leetcode第14题

热门文章

最新文章

  • 1
    解决kafka集群由于默认的__consumer_offsets这个topic的默认的副本数为1而存在的单点故障问题
  • 2
    oracle 11g 11204补丁信息
  • 3
    Python 命令行之旅：初探 docopt
  • 4
    时间之箭源于量子纠缠？
  • 5
    输入输出流体系图
  • 6
    Windows Server 2008 R2下部署OCS 2007 R2 边缘服务器
  • 7
    从码农到设计者，从单例模式入手设计代码
  • 8
    瑞典力推储能助太阳能发电计划落实
  • 9
    十张图告诉你互联网发展的八大趋势
  • 10
    第7周-任务3-复数模板类
  • 1
    DeepSeek——DeepSeek模型部署实战
    126
  • 2
    基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
    105
  • 3
    基于电导增量MPPT控制算法的光伏发电系统simulink建模与仿真
    29
  • 4
    基于排队理论的客户结账等待时间MATLAB模拟仿真
    44
  • 5
    3天功能开发→3小时：通义灵码2.0+DEEPSEEK实测报告，单元测试生成准确率92%的秘密
    61
  • 6
    Sentinel监测到了服务，但是实时监控不显示曲线图，应该怎么解决这个问题？
    47
  • 7
    通义灵码 2.0 体验报告：AI 赋能智能研发的新范式
    60
  • 8
    通义灵码 2.0 体验报告：AI 赋能智能研发的新范式
    80
  • 9
    类和对象的简述（c++篇）
    48
  • 10
    模拟实现c++中的vector模版
    38

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型