⑩做對了的題目（1）——全排列

5 人贊了文章

這是難度為中等，露米婭自己做出來了的題目~

其實這是全排列問題，應該是很經典的題目，但是露米婭沒接觸過，自己用強行土辦法做出來了……

問題

大家都知道單詞可以按照字典序比較大小吧~就是先按首字元比較，如果首字元相同，再按第二個字元比較，如果第二個字元相同，就按第三個比較，依此類推~

比如說aaa < aab，abz < aca等等，翻一翻字典，看看單詞的排序，大家就會明白了……

那麼，對於一個字元串，將字元串中的字母順序打亂我們就可以得到很多新的字元串。

在這些字元串中，肯定有一些是比原來大的字元串。那麼，你就需要找出它們當中最小的一個，如果不存在這樣的字元串，就返回no awnser。

比如，對於hefg而言，打亂後，有hfeg，hfge，hgef，hgfe，hegf等情況是比原來大的，它們當中最小的是hegf。

HackerRank?

www.hackerrank.com

實現

露米婭是寫了一些情況，才找出規律，想出演算法的……

對於長度為1的，肯定是不存在的。

對於長度為2的，如果第一個字母小於第二個，交換一下就行了，否則，就是不存在，比如ab變ba就可以了，但是對於aa而言，無論怎麼換都是aa，沒有比原來大的情況……

對於長度大於2的，就可以用遞歸的思路了~感覺描述起來有點複雜，就不描述了，大家看我的實現吧~

/*用於qsort*/int comp(const void *a, const void *b){ return *(char *)a - *(char *)b;}/*對於字元串w，找到所有大於ch的字母中，最小的那個字母的指針*/char *findFirstGreater(char *w, int n, char ch){ char min = 127; int min_index = -1; for(int i = 0; i < n; i++){ if(w[i] <= ch) continue; if(w[i] < min){ min = w[i]; min_index = i; } } if(min_index == -1) return NULL; return w + min_index;}/*全排列問題*/char* biggerIsGreater(char* w, int n) { char temp; if(w == NULL) return NULL; if(n < 2) return NULL; if(n == 2){ if(w[0] >= w[1]) return NULL; else { temp = w[0]; w[0] = w[1]; w[1] = temp; return w; } } if(biggerIsGreater(w + 1, n - 1) == NULL){ char *p = findFirstGreater(w+1, n-1, w[0]); if(p == NULL) return NULL; char temp = *w; *w = *p; *p = temp; qsort(w+1, n-1, sizeof(char),comp); } return w;}

這樣就可以了~

題外話

HackerRank會幫你寫好主函數，用於處理輸入輸出，但是主函數有一個問題：

for(int a0 = 0; a0 < T; a0++){ char* w = (char *)malloc(512000 * sizeof(char)); scanf("%s", w); int result_size; char* result = biggerIsGreater(w); printf("%s
", result); }

發現了嗎？調用malloc之後竟然沒有調用free釋放內存……

於是，在一些測試情況中，內存空間被耗盡，導致了段錯誤……

我排查了20分鐘後才發現，我的演算法是沒問題的，問題出在沒有調用free來釋放內存……

於是就AC啦~

如果想要非遞歸的演算法，可以參考