力扣(LeetCode)756

Keven 发布于2019-08-16 15:17 / 3152人阅读

摘要：题目地址题目描述给出集合，其所有元素共有种排列。说明给定的范围是。第二种是回溯法求全排列，设置一个全局变量为当前求出的排列数，求出第个全排列，也就是时，停止所有递归否则会超时。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给出集合 [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"

解答：
两种解法：
第一种是利用求下一个排列来求，先排序然后调用k-1次下一个排列。
第二种是回溯法求全排列，设置一个全局变量cur为当前求出的排列数，求出第k个全排列，也就是cur==k时，停止所有递归(否则会超时)。虽然基于交换递归的方法也可以求全排列，但是那种方法求的没有序的关系，所以只能回溯，而不能用递归的方法。我这里采用第二种方法。
java ac代码：

class Solution {
    int cur = 0;
    String ans = "";
    public String getPermutation(int n, int k) {
        int[]nums = new int[n];
        for(int i = 0;i < n;i++){
            nums[i] = i+1;
        }
        backtrack(0,n,k,nums,new int[n],new boolean[n]);
        return ans;
    }
    
    void backtrack(int i,int n,int k,int[] nums,int[] A,boolean[]flag)
    {
        if(cur == k)
            return;
        if(i == n)
        {
            cur++;
            if(cur == k)
            for(int j = 0;j < A.length;j++)
                ans+=A[j];
            return;
        }
        for(int j = 0;j < nums.length;j++)
            if(!flag[j])
            {
                A[i] = nums[j];
                flag[j] = true;
                backtrack(i+1,n,k,nums,A,flag);
                flag[j] = false;
            }
    }
}

GPU云服务器云服务器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73390.html

力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
力扣(LeetCode)452

摘要：对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。解答这是一道区间覆盖问题，不太好说清楚，利用模板即可。题目地址：https://leetcode-cn.com/probl...题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方...

fanux 2019-08-16 15:20 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论0 收藏0