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

leetcode第40题

2022-09-26 129
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 会发现出现了很多重复的结果，就是因为没有跳过重复的 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天前
|
数据采集 人工智能 安全
阿里云Web应用防火墙市场份额和技术能力双第一
喜报～～
阿里云安全_
1166 1
阿里云安全_
|
13天前
|
云安全 监控 安全
助力企业应对React框架高危漏洞，阿里云多款安全产品限时免费
领取限时免费产品，立即开始防护
阿里云安全_
3100 5
bailiantest1
|
4天前
|
自然语言处理 API
万相 Wan2.6 全新升级发布！人人都能当导演的时代来了
通义万相2.6全新升级，支持文生图、图生视频、文生视频，打造电影级创作体验。智能分镜、角色扮演、音画同步，让创意一键成片，大众也能轻松制作高质量短视频。
bailiantest1
1086 152
modelscope
|
18天前
|
机器学习/深度学习 人工智能 自然语言处理
Z-Image：冲击体验上限的下一代图像生成模型
通义实验室推出全新文生图模型Z-Image，以6B参数实现“快、稳、轻、准”突破。Turbo版本仅需8步亚秒级生成，支持16GB显存设备，中英双语理解与文字渲染尤为出色，真实感和美学表现媲美国际顶尖模型，被誉为“最值得关注的开源生图模型之一”。
modelscope
1752 9
星哥玩云
|
9天前
|
人工智能 自然语言处理 API
一句话生成拓扑图！AI+Draw.io 封神开源组合，工具让你的效率爆炸
一句话生成拓扑图！next-ai-draw-io 结合 AI 与 Draw.io，通过自然语言秒出架构图，支持私有部署、免费大模型接口，彻底解放生产力，绘图效率直接爆炸。
星哥玩云
695 152
阿里云云原生
|
11天前
|
人工智能 安全 前端开发
AgentScope Java v1.0 发布，让 Java 开发者轻松构建企业级 Agentic 应用
AgentScope 重磅发布 Java 版本，拥抱企业开发主流技术栈。
阿里云云原生
660 14
云皓@
|
6天前
|
SQL 自然语言处理 调度
Agent Skills 的一次工程实践
**本文采用 Agent Skills 实现整体智能体**，开发框架采用 AgentScope，模型使用 **qwen3-max**。Agent Skills 是 Anthropic 新推出的一种有别于mcp server的一种开发方式，用于为 AI **引入可共享的专业技能**。经验封装到**可发现、可复用的能力单元**中，每个技能以文件夹形式存在，包含特定任务的指导性说明（SKILL.md 文件）、脚本代码和资源等 。大模型可以根据需要动态加载这些技能，从而扩展自身的功能。目前不少国内外的一些框架也开始支持此种的开发方式,详细介绍如下。
云皓@
439 5