• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 200, comments - 8, trackbacks - 0, articles - 0

            第十六章、全排列問題

            53.字符串的排列。
            題目:輸入一個(gè)字符串,打印出該字符串中字符的所有排列。
            例如輸入字符串a(chǎn)bc,則輸出由字符a、b、c 所能排列出來的所有字符串
            abc、acb、bac、bca、cab 和cba。

                分析:此題最初整理于去年的微軟面試100題中第53題,第二次整理于微軟、Google等公司非常好的面試題及解答[第61-70題] 第67題。無獨(dú)有偶,這個(gè)問題今年又出現(xiàn)于今年的2011.10.09百度筆試題中。ok,接下來,咱們先好好分析這個(gè)問題。

            • 一、遞歸實(shí)現(xiàn)
              從集合中依次選出每一個(gè)元素,作為排列的第一個(gè)元素,然后對剩余的元素進(jìn)行全排列,如此遞歸處理,從而得到所有元素的全排列。以對字符串a(chǎn)bc進(jìn)行全排列為例,我們可以這么做:以abc為例
              固定a,求后面bc的排列:abc,acb,求好后,a和b交換,得到bac
              固定b,求后面ac的排列:bac,bca,求好后,c放到第一位置,得到cba
              固定c,求后面ba的排列:cba,cab。代碼可如下編寫所示:
            1. template <typename T>  
            2. void CalcAllPermutation_R(T perm[], int first, int num)  
            3. {  
            4.     if (num <= 1) {  
            5.         return;  
            6.     }  
            7.       
            8.     for (int i = first; i < first + num; ++i) {  
            9.         swap(perm[i], perm[first]);  
            10.         CalcAllPermutation_R(perm, first + 1, num - 1);  
            11.         swap(perm[i], perm[first]);  
            12.     }  
            13. }  
                或者如此編寫,亦可:
            1. void Permutation(char* pStr, char* pBegin);  
            2.   
            3. void Permutation(char* pStr)  
            4. {  
            5.       Permutation(pStr, pStr);  
            6. }  
            7.   
            8. void Permutation(char* pStr, char* pBegin)  
            9. {  
            10.     if(!pStr || !pBegin)  
            11.         return;  
            12.       
            13.     if(*pBegin == '\0')  
            14.     {  
            15.         printf("%s\n", pStr);  
            16.     }  
            17.     else  
            18.     {  
            19.         for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)  
            20.         {  
            21.             // swap pCh and pBegin  
            22.             char temp = *pCh;  
            23.             *pCh = *pBegin;  
            24.             *pBegin = temp;  
            25.               
            26.             Permutation(pStr, pBegin + 1);    
            27.             // restore pCh and pBegin  
            28.             temp = *pCh;  
            29.             *pCh = *pBegin;  
            30.             *pBegin = temp;  
            31.         }  
            32.     }  
            33. }  
            • 二、字典序排列
              把升序的排列(當(dāng)然,也可以實(shí)現(xiàn)為降序)作為當(dāng)前排列開始,然后依次計(jì)算當(dāng)前排列的下一個(gè)字典序排列。
              對當(dāng)前排列從后向前掃描,找到一對為升序的相鄰元素,記為i和j(i < j)。如果不存在這樣一對為升序的相鄰元素,則所有排列均已找到,算法結(jié)束;否則,重新對當(dāng)前排列從后向前掃描,找到第一個(gè)大于i的元素k,交換i和k,然后對從j開始到結(jié)束的子序列反轉(zhuǎn),則此時(shí)得到的新排列就為下一個(gè)字典序排列。這種方式實(shí)現(xiàn)得到的所有排列是按字典序有序的,這也是C++ STL算法next_permutation的思想。算法實(shí)現(xiàn)如下:
            1. template <typename T>  
            2. void CalcAllPermutation(T perm[], int num)  
            3. {  
            4.     if (num < 1)  
            5.         return;  
            6.           
            7.     while (true) {  
            8.         int i;  
            9.         for (i = num - 2; i >= 0; --i) {  
            10.             if (perm[i] < perm[i + 1])  
            11.                 break;  
            12.         }  
            13.           
            14.         if (i < 0)  
            15.             break;  // 已經(jīng)找到所有排列  
            16.       
            17.         int k;  
            18.         for (k = num - 1; k > i; --k) {  
            19.             if (perm[k] > perm[i])  
            20.                 break;  
            21.         }  
            22.           
            23.         swap(perm[i], perm[k]);  
            24.         reverse(perm + i + 1, perm + num);  
            25.          
            26.     }  
            27. }  
              擴(kuò)展:如果不是求字符的所有排列,而是求字符的所有組合,應(yīng)該怎么辦呢?當(dāng)輸入的字符串中含有相同的字符串時(shí),相同的字符交換位置是不同的排列,但是同一個(gè)組合。舉個(gè)例子,如果輸入abc,它的組合有a、b、c、ab、ac、bc、abc

            轉(zhuǎn)自
            http://blog.csdn.net/v_july_v/article/details/6879101

            久久久久高潮毛片免费全部播放| 亚洲一区中文字幕久久| 日韩人妻无码精品久久免费一 | 色偷偷偷久久伊人大杳蕉| 日韩一区二区三区视频久久| 天天综合久久久网| 国产精品伦理久久久久久| 久久这里只有精品久久| 国产精品女同久久久久电影院| 久久久久亚洲精品无码蜜桃 | 香蕉久久夜色精品国产2020| 久久人人妻人人爽人人爽| 九九99精品久久久久久| 国产高潮国产高潮久久久91| 亚洲精品综合久久| 久久久久久久尹人综合网亚洲| 狠狠狠色丁香婷婷综合久久五月| 久久久久久A亚洲欧洲AV冫| 四虎国产精品成人免费久久| www.久久热| 色婷婷久久综合中文久久蜜桃av | 久久天天躁狠狠躁夜夜avapp| 欧美久久综合九色综合| 久久久久人妻一区精品色| 亚洲国产精品无码久久| 久久人人爽人人爽人人片av麻烦 | 狠狠色丁香久久综合婷婷| 久久精品成人免费国产片小草| 99久久www免费人成精品| 国产伊人久久| 成人午夜精品久久久久久久小说| 久久精品国产第一区二区| 久久精品国产清自在天天线| 嫩草影院久久国产精品| 伊人伊成久久人综合网777| 亚洲伊人久久综合影院| 国产精品久久久久9999高清| 久久99亚洲综合精品首页| 日日狠狠久久偷偷色综合0| 久久久老熟女一区二区三区| 久久久久亚洲精品无码蜜桃|