备案控制台
探索云世界
开发者社区 人工智能 文章 正文

leetcode第40题

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

总

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

文章标签：
算法
白月光永恒
目录
相关文章
菊头蝙蝠
|
3月前
leetcode-1447：最简分数
leetcode-1447：最简分数
菊头蝙蝠
33 0
想当开心果哦
|
3月前
|
消息中间件 Kubernetes NoSQL
LeetCode 1359、1360
LeetCode 1359、1360
想当开心果哦
18 0
freesan44
|
Python
LeetCode 1904. 你完成的完整对局数
一款新的在线电子游戏在近期发布，在该电子游戏中，以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着，在 HH:00、HH:15、HH:30 和 HH:45 ，将会开始一个新的对局，其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ，所以一天中最早的时间是 00:00 ，最晚的时间是 23:59 。
freesan44
79 0
ruicore
|
存储 Python
LeetCode 66. Plus One
给定表示非负整数的非空数字数组，加上整数的1。 存储数字使得最高有效数字位于列表的开头，并且数组中的每个元素包含单个数字。 您可以假设整数不包含任何前导零，除了数字0本身。
ruicore
67 0
LeetCode 66. Plus One
三寸艺术家
leetcode
在排序数组中查找元素的第一个和最后一个位置
三寸艺术家
58 0
白月光永恒
leetcode第53题
解法一和解法二的动态规划，只是在定义的时候一个表示以 i 开头的子数组，一个表示以 i 结尾的子数组，却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和，不如解法二直接，只保存最大的和。
白月光永恒
51 0
leetcode第53题
白月光永恒
|
存储 算法
leetcode第43题
个位乘个位，得出一个数，然后个位乘十位，全部乘完以后，就再用十位乘以各个位。然后百位乘以各个位，最后将每次得出的数相加。十位的结果要补 1 个 0 ，百位的结果要补两个 0 。相加的话我们可以直接用之前的大数相加。直接看代码吧。
白月光永恒
65 0
leetcode第43题
白月光永恒
leetcode第44题
时间复杂度：text 长度是 T，pattern 长度是 P，那么就是 O（TP）。 空间复杂度：O（TP）。 同样的，和第10题一样，可以优化空间复杂度。
白月光永恒
63 0
leetcode第44题
白月光永恒
leetcode第36题
一个 9 * 9 的数独的棋盘。判断已经写入数字的棋盘是不是合法。需要满足下边三点， • 每一行的数字不能重复 • 每一列的数字不能重复 • 9 个 3 * 3 的小棋盘中的数字也不能重复。 只能是 1 - 9 中的数字，不需要考虑数独最后能不能填满
白月光永恒
64 0
leetcode第36题
白月光永恒
leetcode第46题
这是自己开始想到的一个方法，考虑的思路是，先考虑小问题怎么解决，然后再利用小问题去解决大问题。没错，就是递归的思路。比如说， 如果只有 1 个数字 [ 1 ]，那么很简单，直接返回 [ [ 1 ] ] 就 OK 了。 如果加了 1 个数字 2， [ 1 2 ] 该怎么办呢？我们只需要在上边的情况里，在 1 的空隙，也就是左边右边插入 2 就够了。变成 [ [ 2 1 ], [ 1 2 ] ]。
白月光永恒
50 0
leetcode第46题

热门文章

最新文章

  • 1
    理解事务的4种隔离级别
  • 2
    疑犯追踪第一季/全集Person Of Interest迅雷下载
  • 3
    简单实用的数据建模工具PDManer
  • 4
    详细讲解！Canal+Kafka实现MySQL与Redis数据同步！
  • 5
    71.7. Script for automatic startup on boot
  • 6
    关于Oracle客户端显示乱码问题
  • 7
    PHPWAMP站点管理的“域名模式”和“端口模式”详解、均支持自定义
  • 8
    jsHelper
  • 9
    学校里学不到的东西(一)
  • 10
    Python 3 教程一:入门
  • 1
    Python的装饰器
    34
  • 2
    R语言用潜类别混合效应模型(Latent Class Mixed Model ,LCMM)分析老年痴呆年龄数据
    20
  • 3
    数据分享|R语言用logistic逻辑回归和AFRIMA、ARIMA时间序列模型预测世界人口
    16
  • 4
    【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享（下）
    21
  • 5
    【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享（上）
    27
  • 6
    数据分享|数据探索电商平台用户行为流失可视化分析
    29
  • 7
    电商平台数据可视化分析网红零食销量
    18
  • 8
    R语言线性回归模型拟合诊断异常值分析家庭燃气消耗量和卡路里实例带自测题
    16
  • 9
    数据分享|R语言GLM广义线性模型：逻辑回归、泊松回归拟合小鼠临床试验数据（剂量和反应）示例和自测题
    12
  • 10
    数据分享|R语言逻辑回归、线性判别分析LDA、GAM、MARS、KNN、QDA、决策树、随机森林、SVM分类葡萄酒交叉验证ROC（下）
    17

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）