MongoDB Angular ipv4 powershell cordova plot LimeJS springboot单点登录 当前线程等待5秒 java数据分析 office2016修复 solr索引 lora开发 mysql新增用户和权限 python语言 python包 python开发界面 python获取字典的值 java基础框架 java对象序列化 java网课 java安装与配置 java注释规范 rewritebase 怪物猎人ol捏脸数据 win10长期服务版 销售清单打印软件 键盘宏软件 主板排名天梯图 影视后期软件 反转颜色 云管家 电脑基础 摩斯密码翻译器 博途v14安装教程 pp安卓助手 氤氲之息哪里爆率高 dns劫持怎么解决 xfce4 win10画图在哪里
当前位置: 首页 > 学习教程  > 编程语言

Dat Seventeen

2021/1/28 23:19:59 文章标签:

算法 来源:力扣(LeetCode)90. 子集 II 给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 示例: 输入: [1,2,2] 输出: [ [2], [1], …

算法

来源:力扣(LeetCode)90. 子集 II
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。

示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

解题思路
这题和昨天那题的区别就在于会包含重复的元素,也就是说[A,B,C] 产生的子集[[],[A],[B],[C],[A,B],[A,C],[C,B],[A,B,C]] 如果B=C 那么[A,C]=[A,B] 题目要求解集不能有重复的元素,那么我们就用set存储结果,就能得到答案了吗?让我们来看这个例子,[2,1,2,2] 产生的子集其中有 [1,2,2] 和[2,1,2] 这两种子集,虽然顺序不同,我们直观就能看出这两个子集是相同的,但是set集合不会认为是相同的。所以为了解决这一问题,我们让初始的集合排序也就是变成[1,2,2,2] 那么接下来产生的子集 就只会是[1,2,2],这样我们就能得到答案了。
昨天的代码我还是不能理解为啥能那样做,虽然直到这样做能得到答案,按我的思路应该是:
在这里插入图片描述
放入set集合就好,重复元素一排除就会是结果。但是看上图很巧的是都是树的左节点保留,右节点可以舍去。很巧的是把所有的黄色节点左移填充就会得到昨天的图。很可惜智力不够,尚不能理解透。
在这里插入图片描述

代码

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,result,item,res_set);
        return result;
    }
private:
    void generate(int i,vector<int>& nums,vector<vector<int>> &result,
        vector<int> &item,set<vector<int>> &res_set){
            if(i>=nums.size()){
                return;
            }
            item.push_back(nums[i]);
            if(res_set.find(item)==res_set.end()){
                result.push_back(item);
                res_set.insert(item); 
            }
            generate(i+1,nums,result,item,res_set);
            item.pop_back();
            generate(i+1,nums,result,item,res_set);
        }
};

来源:力扣(LeetCode)40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

解题思路
这题解题思路和上题大同小异,最主要的一点就是剪枝,减少遍历的节点。比如1+2+7>8 了这个时候就不用再往下尝试了,或者10>8,这个节点也不需要遍历,当然啦,你也可以在一开始排完数字后,删掉大于target的数。

代码

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        sort(candidates.begin(),candidates.end());
        generate(0,candidates,result,item,res_set,0,target);
        return result;
    }
private:
    void generate(int i,vector<int>& candidates,vector<vector<int>> &result,
        vector<int> &item,set<vector<int>> &res_set,int sum,int target){
            if(sum>=target||i>=candidates.size()||candidates[i]>target){
                return;
            }
            sum+=candidates[i];
            item.push_back(candidates[i]);
            if(sum==target&&res_set.find(item)==res_set.end()){  
                    result.push_back(item);
                    res_set.insert(item);  
            }
            generate(i+1,candidates,result,item,res_set,sum,target);
            sum-=candidates[i];
            item.pop_back();
            generate(i+1,candidates,result,item,res_set,sum,target);
        }
};

最近厌学情绪严重,我慢慢调整下,呜呜呜。


本文链接: http://www.dtmao.cc/news_show_650168.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?