小編給大家分享一下LeetCode如何解決第k個(gè)排列問(wèn)題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

鹽津網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,鹽津網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為鹽津近1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營(yíng)銷網(wǎng)站建設(shè)要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的鹽津做網(wǎng)站的公司定做！

題目

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

按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng) n = 3 時(shí), 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

給定 n 和 k，返回第 k 個(gè)排列。

說(shuō)明：

給定 n 的范圍是 [1, 9]。
給定 k 的范圍是[1,  n!]。

示例 1:

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

示例 2:

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

思路

深度優(yōu)先搜索（DFS）+ 剪枝

深度優(yōu)先搜索： 可以理解為暴力法遍歷矩陣中所有字符串可能性。DFS 通過(guò)遞歸，先朝一個(gè)方向搜到底，再回溯至上個(gè)節(jié)點(diǎn)，沿另一個(gè)方向搜索，以此類推。

剪枝： 在搜索中，遇到 這條路不可能和目標(biāo)字符串匹配成功 的情況（例如：此矩陣元素和目標(biāo)字符不同、此元素已被訪問(wèn)），則應(yīng)立即返回，稱之為 可行性剪枝 。

步驟

如果 kk 大于這一個(gè)分支將要產(chǎn)生的葉子結(jié)點(diǎn)數(shù)，直接跳過(guò)這個(gè)分支，這個(gè)操作叫「剪枝」

如果 kk 小于等于這一個(gè)分支將要產(chǎn)生的葉子結(jié)點(diǎn)數(shù)，那說(shuō)明所求的全排列一定在這一個(gè)分支將要產(chǎn)生的葉子結(jié)點(diǎn)里，需要遞歸求解

代碼

class Solution {
    public String getPermutation(int n, int k) {
        //初始化階乘數(shù)組
        int[] factorial = new int[n+1];
        calculateFactorial(factorial,n);
        //查找全排列的布爾數(shù)組
        boolean[] temp = new boolean[n+1];
        Arrays.fill(temp,false);
        //動(dòng)態(tài)字符串
        StringBuilder path = new StringBuilder();
        dfs(temp,factorial,0,path,k,n);
        return path.toString();
    }

    private void dfs(boolean[] temp,int factorial[],int index,StringBuilder path,int k,int n){
        if(index == n){
            return;
        }
        //全排列個(gè)數(shù)
        int cnt = factorial[n-1-index];
        for(int i = 1; i <= n; i++){
            if(temp[i]){
                continue;
            }
            //當(dāng)時(shí)全排列個(gè)數(shù)
            if(cnt < k){
                k -= cnt;
                continue;
            }
            path.append(i);
            temp[i] = true;
            dfs(temp,factorial,index+1,path,k,n);
            return;
        }
    }

    //計(jì)算階乘數(shù)組
    private void calculateFactorial(int[] factorial, int n){
        factorial[0] = 1;
        for(int i = 1; i <= n; i++){
            factorial[i] = factorial[i-1]*i;
        }
    }
}

以上是“LeetCode如何解決第k個(gè)排列問(wèn)題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

新聞標(biāo)題：LeetCode如何解決第k個(gè)排列問(wèn)題
分享地址：http://sd-ha.com/article20/jjsoco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、品牌網(wǎng)站設(shè)計(jì)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站策劃、營(yíng)銷型網(wǎng)站建設(shè)、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)