leetcode第一刷_Permutations II

leetcode第一刷_Permutations II

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

leetcode第一刷_Permutations II此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

当有反复元素的时候呢?

不用拍脑袋都会想到一种方法,也是全部有反复元素时的通用处理方法,维护一个set,假设这个元素没增加过就增加,增加过了的忽略掉。可是,在这道题上这个通用方法竟然超时了!

怎么办?想一下为什么会这样,如果我们要排列的数字是1111112,当当前的排列中没有1时,取哪个1生成一遍,都是一样的。仅仅有当前面的1都用过了,必须轮到这个1出场的时候,它才会有价值。更明白一点说,如果我们要在生成的排列中放两个1,那么这两个1是原来的哪两个根本无所谓,不断的选,终于的结果肯定一样,可是当我们要在排列中放3个1的时候,再选择的1一定是新的了,是有意义的。

用算法的语言描写叙述就是,先把全部的候选数字排一下序,同样的数字会挨在一起,对于同样的数字,都先取第一个增加排列,后面的同样的数字想增加排列,必须保证它前面的同样数字已经在排列中了,这样避免了不断生成反复的排列。

class Solution {
public:
    set<vector<int> > vis;
    void getPerm(vector<int> &num, vector<int> &tpres, vector<vector<int> > &res, int len, int n, bool *visited){
        if(len == n){
            if(vis.find(tpres) == vis.end()){
                vis.insert(tpres);
                res.push_back(tpres);
            }
            return;
        }
        for(int i=0;i<n;i++){
            if(!visited[i]){
                if(i!=0&&num[i] == num[i-1]&&!visited[i-1])
                    continue;
                visited[i] = 1;
                tpres.push_back(num[i]);
                getPerm(num, tpres, res, len+1, n, visited);
                visited[i] = 0;
                tpres.pop_back();
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        vector<int> tpres;
        int msize = num.size();
        if(msize<=0)    return res;
        bool visited[msize];
        memset(visited, 0, sizeof(visited));
        sort(num.begin(), num.end());
        getPerm(num, tpres, res, 0, msize, visited);
        return res;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118003.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • DLL注入

    DLL注入DLL注入DLL注入原理dll注入实现过程功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML图表FLowchart流程图导出与导入导出导入DLL注入原理在Windows操作系统中,运行的每一个进程都生活在自己的程序空间中(保护模式),每一个进程都认为自己拥有整个机器的控制权,

  • MySQL时间戳与日期时间转换

    MySQL时间戳与日期时间转换MySQL日期转时间戳:UNIX_TIMESTAMP(日期时间)MySQL时间戳转日期:FROM_UNIXTIME(时间戳,日期时间格式);

  • php mysql 经纬度_mysql,php和js根据经纬度计算距离

    php mysql 经纬度_mysql,php和js根据经纬度计算距离根据经纬度计算距离公式图片来自互联网对上面的公式解释如下:Lung1Lat1表示A点经纬度,Lung2Lat2表示B点经纬度;a=Lat1–Lat2为两点纬度之差b=Lung1-Lung2为两点经度之差;6378.137为地球半径,单位为千米;计算出来的结果单位为千米,若将半径改为米为单位则计算的结果单位为米。计算精度与谷歌地图的距离精度差不多,相差范围在0.2米以下。参数说明…

  • activity启动FLAG之FLAG_ACTIVITY_CLEAR_TASK「建议收藏」

    activity启动FLAG之FLAG_ACTIVITY_CLEAR_TASK「建议收藏」随时随地阅读更多技术实战干货,获取项目源码、学习资料,请关注源代码社区公众号(ydmsq666)官方文档解释:IfsetinanIntentpassedtoContext.startActivity(),thisflagwillcauseanyexistingtaskthat…

  • LayUI树形表格treetable使用详解[通俗易懂]

    LayUI树形表格treetable使用详解[通俗易懂]LayUI是现在比较流行的一款前端框架,也有很多人基于LayUI开发了很多不错的组件,比如treetable树形表格。因为treetable是第三方基于LayUI开发的,所以需要先用Layui引入一下文件。layui.config({base:’static/layui/’}).extend({treetable:’treetable-lay/treetab…

  • MVC三层架构各层含义[通俗易懂]

    MVC三层架构各层含义[通俗易懂]1.模拟架构图:2.Action/Service/DAO简介:Action是管理业务(Service)调度和管理跳转的。Service是管理具体的功能的。Action只负责管理,而Service负责实施。DAO只完成增删改查,虽然可以1-n,n-n,1-1关联,模糊、动态、子查询都可以。但是无论多么复杂的查询,dao只是封装增删改查。至于增删查改如何去实现一个功能,dao是不管…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号