• <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>

            coreBugZJ

            此 blog 已棄。

            生成全排列的非回溯方法(TopCoder SRM 591 DIV 2)

            問題來自 TopCoder SRM 591 DIV 2 的第二題:

            Problem Statement
               
            Let X and Y be two strings of equal length, consisting of uppercase English letters only. The two strings are called convertible if there is a permutation P of the English alphabet with the following property: if each character c in the string X is replaced by the character P(c), we obtain the string Y. (In other words, X and Y are convertible iff the following holds: whenever two letters of X are equal, the corresponding two letters of Y must be equal, and vice versa.)  For example, consider the string "ABCA". We can choose to replace each 'A' by a 'F', each 'B' by a 'B', and each 'C' by a 'G', obtaining the string "FBGF". Thus the strings "ABCA" and "FBGF" are convertible. The strings "ABCA" and "EFGH" are not convertible, because the two 'A's in the first string must correspond to the same letter in the second string. The strings "ABCA" and "EEEE" are not convertible, because different letters in the first string must correspond to different letters in the second string.  You are given two strings A and B of the same length. These strings only contain English letters from 'A' to 'I', inclusive. (That is, only the first 9 letters of the alphabet are used.)  You want to change A and B into two strings that are convertible. The only allowed change is to choose some indices (possibly none) and to remove the characters at those indices from each of the strings. (I.e., the removed characters must be at the same positions in both strings. For example, it is not allowed to only remove character 0 of A and character 3 of B.) For example, if A="ABAC", B="AHHA" and the chosen indices are 0 and 2, then the resulting strings will be "BC" and "HA". Our goal is to choose as few indices as possible, given that after the erasing we want to obtain two convertible strings. Compute and return the smallest possible number of chosen indices.
            Definition
               
            Class:
            ConvertibleStrings
            Method:
            leastRemovals
            Parameters:
            string, string
            Returns:
            int
            Method signature:
            int leastRemovals(string A, string B)
            (be sure your method is public)
               

            Constraints
            -
            A will contain between 1 and 50 characters, inclusive.
            -
            A and B will be of the same length.
            -
            A will contain characters from 'A' to 'I' only.
            -
            B will contain characters from 'A' to 'I' only.

            我的思路是窮舉A中字母與B中字母的對(duì)應(yīng)關(guān)系,看哪種對(duì)應(yīng)需要?jiǎng)h除的字母最少,這一最少值即是答案。
            窮舉對(duì)應(yīng)關(guān)系,就是生成全排列。
            我生成全排列的方式是回溯。

            之后看其他人的代碼,發(fā)現(xiàn)一個(gè)由給定排列求出其下一個(gè)排列的函數(shù),于是學(xué)習(xí)一下,自己實(shí)現(xiàn)如下:

            // 生成下一字典序排列
            // 假設(shè)a中元素互不相同
            // 若已經(jīng)是最后一個(gè)字典序排列,則返回0,否則返回1
            int next_permutation( int a[], int n ) {
                    
            int i, j;
                    
            for ( i = n-1; (0 < i) && (a[i-1> a[i]); --i ) {
                    }
                    
            if ( 0 >= i ) {
                            
            return 0;
                    }
                    
            for ( j = n-1; j >= i; --j ) {
                            
            if ( a[ j ] > a[ i-1 ] ) {
                                    
            int tmp = a[ i-1 ];
                                    a[ i
            -1 ] = a[ j ];
                                    a[ j ] 
            = tmp;
                                    j 
            = n - 1;
                                    
            while ( i < j ) {
                                            tmp 
            = a[ i ];
                                            a[ i ] 
            = a[ j ];
                                            a[ j ] 
            = tmp;
                                            
            ++i; --j;
                                    }
                                    
            break;
                            }
                    }
                    
            return 1;
            }

            還有人使用的是C++的 <algorithm> 中 next_permutation 函數(shù),功能一樣。


            posted on 2013-09-28 17:03 coreBugZJ 閱讀(910) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm

            亚洲AV成人无码久久精品老人 | 亚洲一区二区三区日本久久九| 欧美性大战久久久久久| 久久久国产精品福利免费| 天堂久久天堂AV色综合| 亚洲精品乱码久久久久久蜜桃图片 | 久久伊人五月丁香狠狠色| 久久精品国产只有精品66| 久久99精品久久久久久秒播| 久久精品综合一区二区三区| 久久精品国产精品亜洲毛片| 国产巨作麻豆欧美亚洲综合久久 | 久久国产精品77777| 国产人久久人人人人爽| 久久精品成人免费看| 91久久香蕉国产熟女线看| 久久久WWW成人| 久久人人爽人人人人爽AV| 无码国内精品久久人妻| 国产91久久精品一区二区| 亚洲国产精品热久久| 久久久久99这里有精品10| 色诱久久久久综合网ywww| 欧美亚洲国产精品久久蜜芽| 久久久99精品一区二区| 亚洲国产精品无码久久久不卡| 久久精品国产精品青草app| 久久久国产精华液| 人妻少妇久久中文字幕一区二区| 国产精品天天影视久久综合网| 久久一区二区三区免费| 久久精品夜夜夜夜夜久久| 国产精品久久久天天影视香蕉 | 久久久久99这里有精品10 | 91精品国产91久久久久久青草| 久久丝袜精品中文字幕| 久久久无码人妻精品无码| 午夜精品久久久久久影视777| 亚洲中文字幕无码久久2020| 精品乱码久久久久久夜夜嗨| 日韩av无码久久精品免费|