精华内容
下载资源
问答
  • leetcode 60题 排列序列(康拓展开)
    2021-08-14 19:47:03

    题目

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

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

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

    示例 1:

    输入:n = 3, k = 3
    输出:“213”

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/permutation-sequence

    思路

    这个题思考了半天还是没有理清楚最终的解法。虽然想到了应该是按照全排列的数量去从高到低的推测每一位数字,但是公式确实有点复杂。

    官方给出的思路非常清晰,最终参考其思路写出了代码。官方解法链接

    根据LeetCode上的评论,发现这个其实是一个很有名的数据数学方法,叫做康托展开。康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。本题就可以通过逆康托展开来解决。

    关于康托展开,有一篇很好的文章可以参考,很容易理解。

    更多相关内容
  • 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.第k个排列

    题目描述

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

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

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

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

    说明:

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

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

    示例 1:

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

    示例 2:

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

    解题思路

    本题可以选择使用回溯法解题,但是时间复杂度太高,使用数学的思维去解题,下面分享一下解题思路。

    给定一个数字n和一个数字k,那么如果可以直接求出所有的组合,那么直接就可以使用下标索引的方式直接找到第k个排列,那么又是是如何找到所有的排序的。即首先固定第一位,有n种可能;固定第二位有n-1中可能;…;第n位有1种可能。那么说了那么多如何直接计算第k个呢?首先,如果固定了第一位的数字,那么剩下的没有排列的n-1位,可以有(n-1)!种排列方式,如果在固定第一位的基础上固定第二位,那么剩下的未排列的n-2位就有(n-2)!种排列方式。通过这样的计算,给定一个k之后,就可以确定每一个位对应什么数字。这样说可能不是很明白,那么以题中的示例2举例,直接计算出第k个排列

    例子: n = 4, k = 9

    • 首先计算第一位,第一位可以选择1、2、3、4四个数,选定以后每一个数字对应的是(n-1)!种排列,由于是按照顺序排列的,如果第一位选择1,那么排完1就可以产生6个排列,即第六个就是最有一个以1作为开头的排序,同理排完2,就会产生12个排列,那么给定一个数字k,就可以确定第一位是对应的数字了。例题中给的k=9,那么 9/6 = 1.5,这里如果不是整除,直接向上取整。即9/6=2;那么第一位对应的数字就是2
    • 然后是确定第二位,由于数字2已经使用了,所有要把它删除,第二位可以使用的数字是1、3、4。这时的k也是需要改变的,确定了第一个数字以后,可以知道目标排列就在以数字2开头的排列中,由于是顺序排列的所以,需要减去数字1开头的排序,k = k-((n-1)!) * num,这里的num是指的第几个数字,这里是数字1,那么如果我们的目标是3开头的排序,就需要减去1、2开头的所有排列,即 k = k-((n-1)!) * 2. 所有k = 9 - 1*((4-1)!) = 3,此时n=3,第二位数字是3/((3-1)!) = 2,这时未排序的数组中只有1、3、4,所以第二个数字是3
    • 第三个数字参考上面两步,先计算现在的k = 3 - 1*((3-1)!) = 1, 此时的n = 2 ,第三个数字的下标是 1/((2-1)!) = 1,此时数组里面的数字是1、4,所以第三个数字是1
    • 第四个数字,其实已经拍完了,就剩一个数字4了。同样的我们继续按照上面的方式计算一下,k = 1- 0*((2-1)!),此时的n=1; 我们定义 数字0的阶乘等于1,所以第四个数字为 1/((1-1)!) = 1,此时数组里面只有数字4
    • 所以第9个排列是 2314
    class Solution {
    public:
        string getPermutation(int n, int k) {
            string str = "123456789";
            string res = "";
    
            while(n){
                int num = 0; // 用于表示计算对应位,应该选择哪一个数字
                if(k%factorial(n-1)){
                    num = k/factorial(n-1) +1; 
                }
                else{
                    num = k/factorial(n-1);
                }
                
                res += str[num-1];  // 添加到字符串
                str.erase(str.begin()+num-1); // 使用过的字符串从待定的字符串中删除
                
                k -= factorial(n-1)*(num-1); // 计算新的k
                n--;                         // 确定了一位数字以后,n的数量要减少1
            }
    
            return res;
        }
    
        // 阶乘
        int factorial(int n){
            if(n == 0){
                return 1;
            }
            else{
                return n*factorial(n-1);
            }
        }
    };
    

    欢迎大家关注我的个人公众号,同样的也是和该博客账号一样,专注分享技术问题,我们一起学习进步
    在这里插入图片描述

    展开全文
  • 还是根据排列组合基本问题全排列 II中给的两种方法改编。 代码1(朴素直接修改原来的模板): int all=-1; int f(int nums,vector n,int c,int k,vector& v) {//该往c位置放了 if(c==n.size()-1){ all++; if(all=...
  • leetcode优美的排列

    2021-01-20 02:13:30
    假设有从 1 到 NN 整数,如果从这 N 数字中成功构造出一数组,使得数组的 i 位 (1 <= i <= N) 满足如下两条件中的一,我们就称这数组为一优美的排列。条件:   i 位的数字能被 i 整除 ...
  • 你总共有 n 枚硬币,你需要将它们摆成一阶梯形状, k 行就必须正好有 k 枚硬币。 给定一数字 n,找出可形成完整阶梯行的总行数。 n 是一非负整数,并且在32位有符号整型的范围内。 示例 1: n = 5 硬币可排列...
  • 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
    展开全文
  • 给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n = 3, k = 3 输出: "213" 示例 2: 输入: n = 4, k = 9 输出: "2314" 链接:https:

    题目

    给出集合 [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"
    

    链接:https://leetcode-cn.com/problems/permutation-sequence

    解题记录

    • 其实是一道数学题
    • 由于是从上到下进行排序,那么就通过给的k进行判断其区域
    • n==3时,一共3*2*1种情况,第一个数字每种情况3*2*1/3=2*1,那么k/2的商就是第几个数
    • k==3时,3/2=1..1那么第一个数,因为0是第一个,1就是第二个,就是2
    • 还有一个问题就是这里给的k是第几个,而不是index需要k-1来表示第几个数
    /**
     * @author: ffzs
     * @Date: 2020/9/5 上午8:39
     */
    public class Solution {
    
        public String getPermutation(int n, int k) {
            if (n==1) return "1";
            List<Integer> tmp = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                tmp.add(i);
            }
            int total = factorial(n - 1);
            int index, remain=k-1;
            StringBuilder res = new StringBuilder();
            for (int i = n - 1; i > 1; --i) {
                index = remain/total;
                remain = remain%total;
                total = total/i;
                res.append(tmp.remove(index));
            }
            res.append(tmp.remove(remain));
            res.append(tmp.get(0));
            return res.toString();
        }
    
        private int factorial(int n) {
            if (n < 1) return -1;
            else if (n == 1) return 1;
            else return factorial(n - 1) * n;
        }
    }
    
    class Test {
        public static void main(String[] args) {
            Solution solution = new Solution();
            System.out.println(solution.getPermutation(3,3));
        }
    }
    

    在这里插入图片描述

    展开全文
  • Leetcode441. 排列硬币

    2021-01-07 16:26:06
    你总共有 n 枚硬币,你需要将它们摆成一阶梯形状, k 行就必须正好有 k 枚硬币。 给定一数字 n,找出可形成完整阶梯行的总行数。 n 是一非负整数,并且在32位有符号整型的范围内。 示例 1: n = 5 硬币可排列...
  • 描述 给出集合 [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...
  • 你总共有 n 枚硬币,并计划将它们按阶梯状排列。对于一由 k 行组成的阶梯,其 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。 给你一数字 n ,计算并返回可形成 完整阶梯行 的总行数。 示例 1: ...
  • leetcode 排列组合系列

    2020-08-21 16:27:11
    下面总结一下leetcode中的排列组合问题。 排列 排列问题一般是对原数组进行交换,然后维护一全局变量的结果集合,每当符合要求将当前状态下的原数组加入到结果集合之中。 题目: 46 全排列 vector<vector<...
  • 参考了这篇文章,原来是道数学题。。。题干:给出集合 [1,2,3,…,n],其所有元素共有 n!...给定 n 和 k,返回 k 个排列。说明:给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1:输入: n = 3, 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 51——N皇后

    2022-04-02 10:43:33
    每日刷题计划,leetcode 51题,n皇后
  • 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一更大的排列。 如果不存在下一更大的排列,则将数字重新排列成最小的排列(即升序排列)。 必须原地修改,只允许使用额外常数空间。 ...
  • 关于《31. 下一个排列》问题的分析及具体实现算法的主要内容
  • 觉得知道题有必要,我二次...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):
  • LeetCode:下一个排列

    2020-10-01 22:41:09
    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一更大的排列。 如果不存在下一更大的排列,则将数字重新排列成最小的排列(即升序排列)。 必须原地修改,只允许使用额外常数空间。 ...
  • leetcode迷宫问题 leetcode by 没有感情的刷题机器 主要根据《挑战程序设计竞赛》的章节,结合leetcode加强...下一个排列 k 个排列 组合总和:无重复元素的数组candidates和一目标数target,可重复使用 组合总
  • Java实现排列A(m,n) 对于递归的关键代码: /** * * @param prefix 拼接结果前缀 * @param total 需要从N个数中取total数 * @param list 含有N个数的集合 */ public void ...
  • 296 章 使用 Javascript 的 LeetCode 解决方案 var :smiling_face_with_sunglasses: ...下一个排列 32 :fearful_face: 最长有效括号 33 :fearful_face: 在旋转排序数组中搜索 34 :neutral_face: 搜
  • LeetCode 60.k个排列 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1,...
  • leetcode 60. k个排列

    2019-03-03 16:38:18
    leetcode 60. k个排列 给出集合 [1,2,3,…,n]...“123” “132” “213” “231” “312” “321” 给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1: 输入: n...
  • 我的LeetCode代码仓:https://github.com/617076674/LeetCode 原题链接:...思路一:求出所有的排列,取k个排列(在LeetCode中提交会超时) 该思路之所以超时,是因为求解了许多...
  • 给定两n 和 k ,让我们求 1 ~ nk全排列。 首先,对于 n 数的全排列来说,我们先来看数确定之后,之后的全排列的个数: 以 1 开头的全排列的个数为: (n-1)! 以 2 开头的全排列的个数为: (n-1)!...
  • 题目描述 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。...给定 n 和 k,返回 k 个排列。 说明: 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例: 输入: n = 3, k = 3 输出: ...
  • LeetCode算法题31:下一个排列解析

    千次阅读 2018-12-04 21:24:53
    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一更大的排列。 如果不存在下一更大的排列,则将数字重新排列成最小的排列(即升序排列)。 必须原地修改,只允许使用额外常数空间。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,413
精华内容 13,365
关键字:

leetcode 第n个排列