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)


相关推荐

  • Ubuntu安装与卸载tensorflow

    Ubuntu安装与卸载tensorflow安装sudopipinstalltensorflow-gpu==1.2卸载sudopipuninstalltensorflow-gputensorflow1.2.0配cuda8.0、cudnn5.1

  • APACHE 服务器开启URL REWRITE模块的方法

    APACHE 服务器开启URL REWRITE模块的方法

  • selenium python面试题_selenium面试题

    selenium python面试题_selenium面试题selenium中如何判断元素是否存在?selenium中没有提供原生的方法判断元素是否存在,一般我们可以通过定位元素+异常捕获的方式判断。#判断元素是否存在try:dr.find_element_by_id(‘none’)exceptNoSuchElementException:print’elementdoesnotexist’selenium中hidden或者是display=…

  • idc机房设施运维_软件运维需要掌握的知识

    idc机房设施运维_软件运维需要掌握的知识机房的服务器的维护是机房运维工作的重点,合理的机房环境对于服务器来说是非常的重要的,随着这年经济的发展,机房也在不断的在很多的方面进行调整,今天我们学习IDC机房服务器运维基础知识。1、关于电力(1)定期检测机房内市电及UPS电源是否稳定,并做好记录,UPS巡检记录要落实到个人。确保服务器硬件系统的稳定运转,确保市电中断后服务器正常运转理论值8小时。(2)若遇市电中断,如无特殊事宜,请尽量…

  • ajax 面试题_javascript面试题大全

    ajax 面试题_javascript面试题大全1、什么是AJAX,为什么要使用Ajax(请谈一下你对Ajax的认识)什么是ajax:AJAX是“Asynchronous JavaScript and XML”的缩写。他是指一种创建交互式网页应用的网页开发技术。Ajax包含下列技术:基于web标准(standards-basedpresentation)XHTML+CSS的表示;使用 DOM(Document ObjectM

  • Mysql 慢查询优化实践

    Mysql 慢查询优化实践

发表回复

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

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