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

            99久久中文字幕| 一本久道久久综合狠狠爱| 久久青草国产精品一区| 亚洲国产精品婷婷久久| 久久综合九色欧美综合狠狠| 欧美亚洲国产精品久久| 色偷偷偷久久伊人大杳蕉| 久久国产免费| AV色综合久久天堂AV色综合在 | 伊人久久成人成综合网222| 色天使久久综合网天天| 91精品国产9l久久久久| 无码八A片人妻少妇久久| 久久夜色精品国产亚洲| 日韩人妻无码一区二区三区久久 | 久久青青草视频| 日韩精品久久久久久| 午夜欧美精品久久久久久久| 久久精品国产清自在天天线| av国内精品久久久久影院| 伊人情人综合成人久久网小说 | 亚洲人成网站999久久久综合| 97久久精品国产精品青草| 欧美亚洲国产精品久久高清| 国产L精品国产亚洲区久久| 日本强好片久久久久久AAA| 久久精品国产AV一区二区三区| 一级女性全黄久久生活片免费| 国产精品成人无码久久久久久| 久久久久国产精品熟女影院| 久久精品国产AV一区二区三区| 中文成人无码精品久久久不卡 | 久久久精品人妻一区二区三区蜜桃 | 国内精品伊人久久久久影院对白| 久久er99热精品一区二区| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 久久精品www| 免费国产99久久久香蕉| 国产日产久久高清欧美一区| 日韩精品久久久久久| 国产精品免费看久久久香蕉|