小編給大家分享一下LeetCode如何解決第k個排列問題,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
鹽津網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,鹽津網(wǎng)站設(shè)計制作,有大型網(wǎng)站制作公司豐富經(jīng)驗。已為鹽津近1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營銷網(wǎng)站建設(shè)要多少錢,請找那個售后服務(wù)好的鹽津做網(wǎng)站的公司定做!
給出集合 [1,2,3,…,n],其所有元素共有 n! 種排列。
按大小順序列出所有排列情況,并一一標(biāo)記,當(dāng) n = 3 時, 所有排列如下:
"123" "132" "213" "231" "312" "321"
給定 n 和 k,返回第 k 個排列。
給定 n 的范圍是 [1, 9]。 給定 k 的范圍是[1, n!]。
輸入: n = 3, k = 3 輸出: "213"
輸入: n = 4, k = 9 輸出: "2314"
深度優(yōu)先搜索(DFS)+ 剪枝
深度優(yōu)先搜索: 可以理解為暴力法遍歷矩陣中所有字符串可能性。DFS 通過遞歸,先朝一個方向搜到底,再回溯至上個節(jié)點,沿另一個方向搜索,以此類推。
剪枝: 在搜索中,遇到 這條路不可能和目標(biāo)字符串匹配成功 的情況(例如:此矩陣元素和目標(biāo)字符不同、此元素已被訪問),則應(yīng)立即返回,稱之為 可行性剪枝 。
如果 kk 大于這一個分支將要產(chǎn)生的葉子結(jié)點數(shù),直接跳過這個分支,這個操作叫「剪枝」
如果 kk 小于等于這一個分支將要產(chǎn)生的葉子結(jié)點數(shù),那說明所求的全排列一定在這一個分支將要產(chǎn)生的葉子結(jié)點里,需要遞歸求解
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); //動態(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; } //全排列個數(shù) int cnt = factorial[n-1-index]; for(int i = 1; i <= n; i++){ if(temp[i]){ continue; } //當(dāng)時全排列個數(shù) if(cnt < k){ k -= cnt; continue; } path.append(i); temp[i] = true; dfs(temp,factorial,index+1,path,k,n); return; } } //計算階乘數(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個排列問題”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識,歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道!
新聞標(biāo)題:LeetCode如何解決第k個排列問題
分享地址:http://bm7419.com/article20/jjsoco.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供品牌網(wǎng)站制作、品牌網(wǎng)站設(shè)計、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站策劃、營銷型網(wǎng)站建設(shè)、網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)