資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目要求假設(shè)按照題中給的排列組合的順序，假設(shè)有個(gè)數(shù)字，返回第個(gè)排列組合的結(jié)果。最后在個(gè)位上，選擇中的第一個(gè)。這時(shí)知道以第位為開(kāi)頭的結(jié)果值有此時(shí)第個(gè)結(jié)果集在該位上的選擇為。依次往后類(lèi)推，直至到最后一位。
題目要求
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): 1."123" 2."132" 3."213" 4."231" 5."312" 6."321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive.
假設(shè)按照題中給的排列組合的順序，假設(shè)有1~n個(gè)數(shù)字，返回第k個(gè)排列組合的結(jié)果。
思路與代碼首先來(lái)整理一下思路。如果有n個(gè)數(shù)組，則能排列組合出n！個(gè)結(jié)果。然后再按照排列組合結(jié)果的各個(gè)位上的數(shù)字選擇來(lái)分析。這里舉一個(gè)具體的例子。就看題中給的例子，此時(shí)n=3。假設(shè)k=5。則在百位上，選擇的數(shù)字為[1，2，3]中的第三個(gè)，這是再看十位上的數(shù)字，選擇了[1,2]中的第一個(gè)數(shù)。最后在個(gè)位上，選擇[1]中的第一個(gè)。
可以總結(jié)出，假設(shè)輸入n，k，則結(jié)果上的從左往右第1位上的數(shù)字為結(jié)果集中第(k-1)/(n-1)!個(gè)數(shù)字。這時(shí)知道以第1位為開(kāi)頭的結(jié)果值有(n-1)!,此時(shí)第k個(gè)結(jié)果集在該位上的選擇為k%factorial[n-1]。依次往后類(lèi)推，直至到最后一位。代碼如下：
public String getPermutation(int n, int k) {
//factorial
int[] factorial = new int[]{1,1,2,6,24,120,720,5040,40320,362880};
//初始化
List numbers = new LinkedList();
for(int i = 0 ; i
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67256.html
摘要：找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成，則第個(gè)全排列的第一位是。然后將得到，這個(gè)就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...
摘要：題目要求類(lèi)似的題目有可以參考這篇博客可以參考這篇博客思路一遞歸還是利用遞歸的方式，在前一種情況的基礎(chǔ)上遍歷下一輪的組合情況。 題目要求 Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subset...
Problem In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a seque...
摘要：做法先把這個(gè)數(shù)放入一個(gè)數(shù)組里，同時(shí)計(jì)算出的階乘。假設(shè)這一組是第組，第一個(gè)數(shù)就是，同時(shí)刪去這個(gè)數(shù)，并讓除以取余作為新的。如此循環(huán)，這樣，下一組的成員數(shù)減少了，要找的位置也更為精確了。 Problem Given n and k, return the k-th permutation sequence. Example For n = 3, all permutations are li...
摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來(lái)判斷結(jié)果中是否有回文。而中心對(duì)稱(chēng)點(diǎn)如果是字符，該字符會(huì)是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...
閱讀 2497·2023-04-25 19:24
閱讀 1716·2021-11-11 16:54
閱讀 2842·2021-11-08 13:19
閱讀 3556·2021-10-25 09:45
閱讀 2563·2021-09-13 10:24
閱讀 3293·2021-09-07 10:15
閱讀 4046·2021-09-07 10:14
閱讀 2962·2019-08-30 15:56
