精华内容
下载资源
问答
  • Leetcode K个排列

    2020-01-06 19:48:47
    给出集合[1,2,3,…,n],其所有元素共有n! 种排列。 ...给定n 和k,返回k个排列。 首先,我们先理解清楚全排列的过程。给定n=3,则123的全排列有{123,132,213,231,321,312}; 具体先固定住...

    给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

    按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

    "123"
    "132"
    "213"
    "231"
    "312"
    "321"
    给定 n 和 k,返回第 k 个排列。

     

    首先,我们先理解清楚全排列的过程。给定n=3,则123的全排列有{123,132,213,231,321,312};

    具体先固定住1,对23进行全排序,然后交换1和2的位置,对13进行全排序,再交换1和3的位置,对21进行全排序。

    但这道题目不可采取先递归求全排序所有可能,再取要的答案。因为第5个排列为 312而不是321。所以应考虑从其他角度入手。

    当n=1时,有1种排列,
    当n=2时,有2种排列,
    当n=3时,有6种排列,
    其实n=3时,可以拆分成第一位数和 后两位数,后两位数的排列组合为n=2时的两种,那第一位数可以是三个数种的任意一个,所以总的排列数就是23=6
    所以我们可以知道,当k<=2时,第一位数没有变,那我们就可以确定第一个数是最小数,那就对剩下的后两位数分析,如果k=1那就确定第二位数是最小数,否则则是第二小数
    当2<k<=4时,可以确定第一位数是第二小数,再对后两数分析,如果k=3那第位数就是剩下数里的最小数
    所以以此举例n=4,k=9时,我们对k进行判断k如果是在123到1234之间的话,那说明k至少改变了4位,如果k在123到1232之间,说明第一位肯定是2,未确定是数位[1,3,4]
    那k=k-6=3,那么k是在12 到123之间,说明k改变了3位,且k在12到12*2之间,那第二位就是3, 剩余未排列[1,4]
    k = k-3 = 1,那么说明最后两位k未改变, 那么第三第四位就是1 4

    代码如下:

    class Solution {

    public:

        string getPermutation(int n, int k) {

            string ans="";

            string base="";

            for(int i=1;i<=n;i++)

                base+=char('0'+i);

            if(k==1) return base;

            while(k>1)

            {

                adjust(base,n,k,ans);

            }

            ans+=base;

            return ans;

        }

     

        void adjust(string &s, int &n, int &k,string &ans)

        {

            int cur=jiecheng(n-1);

            int i=0;

            if(k<=cur )

            {

                n--;

                ans+=s[i];

                s.erase(i,1);

                cur=jiecheng(n-1);

            }

            while(k>cur)

                {

                    i++;

                    k-=cur;

                }  

             

            ans+=s[i];

            s.erase(i,1);

            n--;

        }

     

        int jiecheng( int n)

        {

            int val=1;

            for(int i=1;i<=n;i++)

                val*=i;

            return val;

        }

    };

    展开全文
  • leetcode k个排列

    2018-10-09 21:50:20
    给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3

    给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

    按大小顺序列出所有排列情况,并一一标记,当 = 3 时, 所有排列如下:

    1. "123"
    2. "132"
    3. "213"
    4. "231"
    5. "312"
    6. "321"

    给定 n 和 k,返回第 k 个排列。

    说明:

    • 给定 n 的范围是 [1, 9]。
    • 给定 的范围是[1,  n!]。

    示例 1:

    输入: n = 3, k = 3
    输出: "213"
    

    示例 2:

    输入: n = 4, k = 9
    输出: "2314"

     

    class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            mark = [i for i in range(1, n+1)]
            table = [1 for _ in range(n)]
            for i in range(1, n):
                table[i] = i * table[i-1]
            res = ''
            k -= 1
            while n > 0:
                ind, k = divmod(k, table[n-1])
                res += str(mark.pop(ind))
                n -= 1
            return res

     

    展开全文
  • leetcode k个排列 java

    2020-02-15 11:59:21
    题干 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 ...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: ...

    题干

    给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

    按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

    "123"
    "132"
    "213"
    "231"
    "312"
    "321"
    给定 n 和 k,返回第 k 个排列。
    

    说明:

    给定 n 的范围是 [1, 9]。
    给定 k 的范围是[1, n!]。
    示例 1:

    输入: n = 3, k = 3
    输出: "213"
    

    示例 2:

    输入: n = 4, k = 9
    输出: "2314"
    

    想法

    比如n为4 k为3
    我们把n的排列写出来
    会发现
    如果是1开头:

    1 {2,3,4} 其中1开头的个数是234三个的排列,也就是3!

    如果是2开头:

    2 {1,3,4} 其中2开头的个数是134三个的排列,也就是3!

    剩下的同理
    如果我要找第k个数
    那么就要找出它的第一个数在哪一段
    所以用k来➗(n-1)!
    然后去掉首位 继续相同的操作即可
    参考传送门

    Java代码

    代码已经提交到git

    class Solution {
        
            public String getPermutation(int n, int k) {
                k--;
                List<Integer> list = new ArrayList<Integer>();//注意存储1-n
                StringBuilder s = new StringBuilder();
                int times = n-1;
                for(int i=1;i<=n;i++){
                    list.add(i);
                }
                int factorail = 1;//阶乘
                for(int i=2;i<n;i++){//不要×n
                    factorail*=i;
                }
                while(times>=0){
                    int index=k/factorail;
                    s.append(list.get(index));
                    list.remove(index);
                    k=k%factorail;
                    if(times!=0){
                        factorail/=times;
                    }
                    times--;
                }
                return s.toString();
            }
            
        }
    
    展开全文
  • 60. k个排列 题目描述:*给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例...

    60. 第k个排列

    题目描述:*给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
    按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
    “123”
    “132”
    “213”
    “231”
    “312”
    “321”
    给定 n 和 k,返回第 k 个排列。
    说明:
    给定 n 的范围是 [1, 9]。
    给定 k 的范围是[1, n!]。
    示例 1:
    输入: n = 3, k = 3
    输出: “213”
    示例 2:
    输入: n = 4, k = 9
    输出: “2314”*

    1. 暴力法
    可以用递归全排列,将所有的可能都加入到一个列表中,进行排序,找到第K个就行了,这里就不做多述,因为时间复杂度太高了,肯定超时。
    2.权值解法
    有点像海明码的感觉,以n=6,k=100为例,我们来定义一下他们的权值,下面我们来看张图片
    这里写图片描述
    当第六位确定之后,后面五位数最多能组成120个数(5!),也就是说图上6所在的位置,1代表120,2代表240,以此类推。我们定义图上6所在的位置的权值为120,当确定左边两位的时候,剩下四位最大可能组合为24种,我们定义其权值为24,剩下的就不一一说了,看上面的图。
    下面我们来举个例子n=6,k=100;
    首先n=6最大组合数是720,720>100说明6位数的组合数超过100,假定我们确定最高位为1
    剩下的五位数最大组合数为120,120>100同理说明五位数的组合数超过100,同理我们可以判断四位数不行。大家都知道当确定位数后,最高位越小这个数越小,所以证明上面的假定成立,最高位为1。下面就不一一解说了,次高位权值为24,在剩下的数中【2,3,4,5,6】选取6(100/24=4点多,所以取第五位),确定两位后现在我们来确定第三高位,用剩下的(余数)4(100/24=4…..4)继续除以其权值6等于零点几,所以选剩下数列中第一位(2)。再继续用上次的余数4除以第四高位的权值2,等于2正好整除,选取剩下列表中的第二位【3,4,5】4,(正好整除的意思就是说在确定前面的高位的基础上,后面剩余得数选取他们的最大组合数就行了)所以,第五位第六位分别是5,3。最终我们可以得出第一百个数是(k=100)162453。自认说的不是很清楚,第一次写博客,如有疑问或建议欢迎回帖,谢谢。下面直接看代码。
    这个代码的思路较清晰但是在LeetCode不能正常运行不知道是什么原因,我试过了window系统上的python2.X、python3.X和Linux终端都能正常运行。我猜测是取天花那一步出问题了,如果你们有兴趣可以加个if判断,我就懒得写了,之后我再复制一个我好早之前写的代码,有点不清晰,但是能通过用时LeetCode上用时28ms。

    import math
    class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            templist=[]#定义一个列表,用于装放下面取出的数
            temp=[i for i in range(1,n+1)]#定义一个n位的列表1-n
            dicts={1:1,2:1,3:2,4:6,5:24,6:120,7:720,8:5040,9:40320,10:362880}#定义各位的权值
            for i in range(n,0,-1):
                s = math.ceil(k / dicts[i])#计算商值 取其天花
                templist.append(temp.pop(s - 1))#将对应数值,加入到templist中,并删除在temp中取出得数,避免重复取出
                if k%dicts[i]==0:#判断能整除
                    templist.extend(temp[::-1])#将剩余数反转,即最大组合数
                    break
                else:#如果不能整除,即将k值等于其余数
                    k%=dicts[i]
            return ''.join([str(i) for i in templist])#将列表中数字先转化为str`

    代码二

    class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            templist=[]
            temp=[i for i in range(1,n+1)]
            dicts={1:1,2:2,3:6,4:24,5:120,6:720,7:5040,8:40320,9:362880,10:3628800,11:39918600}
            for i in range(n-1,0,-1):
                if k<=dicts[i]:
                    templist+=temp[:len(temp)-i]
                    temp=temp[len(temp)-i:]
                else:
                    if k==dicts[i+1]:
                        templist.append(temp[k//dicts[i]-1])
                        temp.pop(k//dicts[i]-1)
                        templist+=temp[::-1]
                        temp=[]
                        break
                    else:
                        templist.append(temp[k // dicts[i]-1 if k%dicts[i]==0 else k // dicts[i] ])
                        temp.pop(k // dicts[i]-1 if k%dicts[i]==0 else k // dicts[i])
                        k = k % dicts[i]
                        if k==0:
                            templist += temp[::-1]
                            temp = []
                            break
            s1=''
            for s in templist+temp:
                s1+=str(s)
            return s1
    展开全文
  • 描述 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 ...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: ...
  • 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: "21...
  • 觉得知道题有必要,我二次...The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
  • LeetCodek个排列

    2020-09-05 16:31:58
    LeetCodek个排列 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 介绍 60. k个排列 题目 给出集合 [1,2,3,…,n],其所有元素...
  • 题目描述:你总共有 n 枚硬币,你需要将它们摆成一阶梯形状, k 行就必须正好有 k 枚硬币。给定一数字 n,找出可形成完整阶梯行的总行数。 代码: class Solution { public: int arrangeCoins(int n) { int...
  • leetcode 60 k个排列

    2020-09-16 14:53:14
    给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: “213” 示例 2: 输入: n = 4, k = 9 输出: “2314” 一方法超时了:采用swap求...
  • 给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 DFS回溯 会超时,如果能在找到k个时即时退出程序也许可以通过 定位每一位法 从最高位开始,确定每一位的数字 ...
  • Java实现 LeetCode 60 k个排列

    万次阅读 多人点赞 2020-02-15 21:49:01
    60. k个排列 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 ...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = ...
  • LeetCode 60 k个排列

    2019-05-29 23:08:42
    1.问题重述 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输...
  • LeetCode 60 K个排列

    2019-04-12 22:14:00
    题目: 给出集合[1,2,3,…,n],其所有元素共有n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当n= 3...给定n和k,返回k个排列。 说明: 给定n的范围是 [1, 9]。 给定k的范围是[1, n!]。 示例1: ...
  • leetcode 60 K个排列 1.题目描述 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: “123” “132” “213” “231” “312” “321” ...
  • LeetCodeK个排列【60】 题目描述 给出集合[1,2,3,…,n],其所有元素共有n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当n = 3 时, 所有排列如下: "123""132""213""231""312""321" 给定n 和k,...
  • 题目 leetcode 60 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3,...
  • LeetCodek个排列

    2019-05-03 15:13:35
    给出集合[1,2,3,…,n],其所有元素共有n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当...给定n和k,返回k个排列。 说明: 给定n的范围是 [1, 9]。 给定k的范围是[1, n!]。 示例1: 输入: n = 3, k ...
  • 我们不是从低位到高位确定排列,而是反过来,从高位到低位: 最高位有n种填法,余下的是n-1!种填法。 n=3,k=3,n-1! = 2, 所以一位是2,剩下两位是2,1,3, n=4,k=9,n-1!=6, 所以一位是2, ...
  • 原文参考链接:... //k个排列 getPermutation (n, k) { let arr = [], i, j, res = [], temp, result = '' //放入n个数 for (i = 0; i &lt; n; i++)...
  • 题目: 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入:
  • leetcode 60.k个排列

    千次阅读 2020-01-15 12:00:05
    leetcode 60.k个排列 题目描述 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 ...
  • leetcode 60 个排列

    2016-12-19 19:31:01
    he set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123""132""213""231""312"...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,606
精华内容 642
关键字:

leetcode第n个排列