2019獨角獸企業重金招聘Python工程師標準>>>

題目描述：

?

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。

?

?

輸入：

?

每個測試案例包括1行。

輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。

?

?

?

輸出：

對應每組數據,按字典序輸出所有排列。

?

?

?

?

樣例輸入： abc BCA

?

樣例輸出： abc acb bac bca cab cba ABC ACB BAC BCA CAB CBA

解題思路：

　　這道題要注意兩個問題：

　　第一個是重復字母，第二個是按字典順序。

　　重復字母我們在進行交換的時候直接跳過就可以了，按字典順序，這個就需要我們進行排列了。

　　排列使用冒泡排序：

void bubbleSort(char *arr,int begin,int length){int i,j;for(i=begin;i<length;i++){for(j=i+1;j<length;j++){if(arr[i]>arr[j]){swap(&arr[i],&arr[j]);}}} }

　　進行交換時，注意忽略掉重復的字符交換：

void Permulation(char *arr,int k,int length){int i;if(k == length){for(i=0;i<length;i++)printf("%c",arr[i]);printf("\n");}else{for(i=k;i<length;i++){if(k != i && arr[k] == arr[i])continue;swap(&arr[k],&arr[i]);bubbleSort(arr,k+1,length);Permulation(arr,k+1,length);bubbleSort(arr,k+1,length);}} }

　　每次在進行交換后，都把剩余的元素進行一次排列。比如字符串abc,在進行最后一次外層交換時變成 cba。

　　此時要進行一次排序，交換cab后，在進行排列。

全部代碼：

#include <stdio.h> #include <stdlib.h> #include <string.h> void bubbleSort(char *arr,int begin,int length); void swap(char *a,char *b); void Permulation(char *arr,int k,int length);int main(){char arr[10];int length;int i;while(gets(arr)){length = strlen(arr);bubbleSort(arr,0,length);Permulation(arr,0,length);}return 0; } void Permulation(char *arr,int k,int length){int i;if(k == length){for(i=0;i<length;i++)printf("%c",arr[i]);printf("\n");}else{for(i=k;i<length;i++){if(k != i && arr[k] == arr[i])continue;swap(&arr[k],&arr[i]);bubbleSort(arr,k+1,length);Permulation(arr,k+1,length);bubbleSort(arr,k+1,length);}} } void swap(char *a,char *b){char c;c = *b;*b = *a;*a = c; } void bubbleSort(char *arr,int begin,int length){int i,j;for(i=begin;i<length;i++){for(j=i+1;j<length;j++){if(arr[i]>arr[j]){swap(&arr[i],&arr[j]);}}} } /**************************************************************Problem: 1369User: xhaloLanguage: CResult: AcceptedTime:470 msMemory:912 kb ****************************************************************/

?

轉載于:https://my.oschina.net/u/204616/blog/545462

總結

以上是生活随笔為你收集整理的剑指OFFER之字符串的排列（九度OJ1369）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。