前言
之前刷過(guò)一些leetcode的題目，這學(xué)期修了組合數(shù)學(xué)這門課，讓我感受頗多。課程上更關(guān)注的是數(shù)學(xué)上的解法，并沒(méi)有講到具體的用某種語(yǔ)言實(shí)現(xiàn)，并沒(méi)有深入地講為什么這樣做就是對(duì)的。結(jié)合我的經(jīng)驗(yàn)，想分享一下我的理解。
leetcode 31.下一個(gè)全排列
2個(gè)關(guān)鍵點(diǎn):
下一個(gè)全排列比當(dāng)前的大(字典序)
增量要是最小的
一些例子:
1243 -> 1324,要使1243更大，從右往左看，43已經(jīng)是最大的了,所以下一個(gè)肯定是13開(kāi)頭，故交換2,3得到1342,后2位42肯定無(wú)法保證增量最小，故翻轉(zhuǎn)42，得到1324,即為所求
4321 -> 1234,從右往左看，全部遞增，故這是最后一個(gè)序列了，翻轉(zhuǎn)整個(gè)序列，得到1234,符合題目的要求
class Solution {
public void nextPermutation(int[] nums) {
if(nums == null || nums.length == 1) return;
//從右向左，找到破壞遞增規(guī)律的第一個(gè)數(shù)
int n = nums.length;
int index = -1;
for(int i = n-2; i >= 0; i--){
if(nums[i] < nums[i+1]){
index = i;
break;
}
}
//找到比nums[index]大的第一個(gè)數(shù)
//交換nums[index]與這個(gè)nums[i]
if(index != -1){
for(int i = n-1; i>= 0; i--){
if(nums[i] > nums[index]){
int tmp = nums[i];
nums[i] = nums[index];
nums[index] = tmp;
break;
}
}
}
//翻轉(zhuǎn)數(shù)組，范圍為[index+1,n-1]，這樣便使增量最小
//如果是最后一個(gè)排列，如[3,2,1],index為-1，翻轉(zhuǎn)整個(gè)序列
reverseArray(nums, index+1, n-1);
}
public void reverseArray(int[] nums,int start,int end){
for(int i = start, j = end;i <= j; i++,j--){
//交換nums[i]與nums[j]
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
leetcode 60.第k個(gè)全排列
n=3時(shí)，共有3!個(gè)排列
123
132
213
231
312
321
關(guān)鍵:
每2個(gè)看成一組，每一組內(nèi)第一位都是相同的,如123,132
即每n-1個(gè)看成一組，總共有n組(n!=n*(n-1))
若第0位已確定，剩下就是n-1個(gè)數(shù)的排列，可分成n-1組，每個(gè)組內(nèi)(n-2)!個(gè)
以n=3,k=4為例:
為了跟程序里的小標(biāo)對(duì)應(yīng),從0開(kāi)始，k=k-1=3
3/2!=1余1,說(shuō)明第0位是[1,2,3]中下標(biāo)為1的數(shù),即2
余數(shù)為1，剩下2個(gè)數(shù),1/1!=1余0,[1,3]中下標(biāo)為1的數(shù)即3
只剩下1,故結(jié)果是231
這其實(shí)可以歸納出一個(gè)數(shù)學(xué)公式，康托展開(kāi)與逆展開(kāi)
class Solution {
public String getPermutation(int n, int k) {
//需要用到一點(diǎn)數(shù)學(xué)知識(shí)，康托展開(kāi)
StringBuilder sb = new StringBuilder();
List<Integer> info = new ArrayList<Integer>();
for(int i=1;i<=n;i++){
info.add(i);
}
int factor=1;
k=k-1;
//計(jì)算出(k-1)!
for(int i = 2;i<=n-1;i++){
factor *= i;
}
for(int i=n-1;i>=1;i--){
int p = k/factor;//商
k = k%factor;//余數(shù)
sb.append(info.get(p));
//移除
info.remove(p);
//更新
factor /= i;
}
sb.append(info.get(0));//最后info中只剩下一個(gè)
return sb.toString();
}
}
已知全排列求k
給出231,求k
如果真的理解了上面的分組，很容易就可以列出式子:
因?yàn)槲覀冃?biāo)從0開(kāi)始，最后再加1即可
理解一下這個(gè)式子的含義:就是求比231小的排列有多少個(gè)
只有這幾種可能{1, ,}(以1開(kāi)頭的排列,共有2個(gè))
{2,1,}(以2,1,開(kāi)頭的排列,只有1個(gè))
所以231是排在第4的
