您當(dāng)前位置：首頁 > php開源 > 綜合技術(shù) > 筆試題—字符串常見的算法題集錦

筆試題—字符串常見的算法題集錦

來源：程序員人生發(fā)布時間：2016-09-27 08:43:49 閱讀次數(shù)：2857次

筆試題—字符串常見的算法題集錦

本篇博客主要講授1下4個問題

KMP算法
字母倒序輸出
全排列
全組合

轉(zhuǎn)載請注明原博客地址： http://blog.csdn.net/gdutxiaoxu/article/details/52602327

例子源碼下載地址： http://download.csdn.net/detail/gdutxiaoxu/9635393

KMP算法

關(guān)于KMP算法的分析，這里就不講授了，有興趣的可以參考這篇博客：從頭到尾完全理解KMP

代碼以下

package com.xujun.stringfind;

public class KMPFind {

    public static void main(String[] args) {
        String s = "abcbb2abcabx";
        String c = "abca";
        int[] next = new int[s.length() + 1];
        next = getNext(c);
        for (int i = 0; i < next.length; i++) {
            System.out.println("=" + next[i]);
        }
        int find = matchNext(s, c, 0);
        System.out.println("find=" + find);

        int[] nextVal = getNextVal(c);

        for (int i = 0; i < nextVal.length; i++) {
            System.out.println("=" + nextVal[i]);
        }
        int matchNextVal = matchNextVal(s, c, 0);
        System.out.println("matchNextVal=" + matchNextVal);

    }

    /**
     * 注意這里為了保持保持1致性 ，第1個next[0]沒有用到
     * 
     * @param c
     * @return
     */
    private static int[] getNextVal(String c) {
        int[] nextVal = new int[c.length() + 1];
        int front = 0;
        int behind = 1;
        nextVal[1] = 0;
        /**
         * c.charAt(front⑴)表示前綴字符 ，c.charAt(behind⑴)表示后綴字符
         */
        while (behind < c.length()) {
            if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
                ++front;
                ++behind;
                if (c.charAt(front - 1) != c.charAt(behind - 1)) {
                    nextVal[behind] = front;
                } else {
                    nextVal[behind] = nextVal[front];
                }
            } else {
                // 前綴索引回溯
                front = nextVal[front];
            }
        }

        return nextVal;
    }

    /**
     * 注意這里為了保持保持1致性 ，第1個next[0]沒有用到
     * 
     * @param c
     * @return
     */
    private static int[] getNext(String c) {
        int[] next = new int[c.length() + 1];
        int front = 0;
        int behind = 1;
        next[1] = 0;
        /**
         * c.charAt(front⑴)表示前綴字符 c.charAt(behind⑴)表示后綴字符
         */
        while (behind < c.length()) {
            if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
                ++front;
                ++behind;
                next[behind] = front;
            } else {
                // 前綴 索引回溯
                front = next[front];
            }
        }

        return next;
    }

    public static int matchNextVal(String source, String c, int pos) {

        int i;
        int[] nextVal = getNextVal(c);
        if (pos < 1) {
            i = 1;
        } else {
            i = pos + 1;
        }
        int j = 1; // i控制S,j控制T;
        while (i <= source.length() && j <= c.length()) {
            if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
                ++i;
                ++j;
            } else {
                j = nextVal[j]; // j退回適合的位置，i值不變
            }
        }
        if (j > c.length())
            return i - c.length() - 1;
        else
            return -1;
    }

    public static int matchNext(String source, String c, int pos) {

        int i;
        int[] next = getNext(c);
        if (pos < 1) {
            i = 1;
        } else {
            i = pos + 1;
        }
        int j = 1; // i控制S,j控制T;
        while (i <= source.length() && j <= c.length()) {
            if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
                ++i;
                ++j;
            } else {
                j = next[j]; // j退回適合的位置，i值不變
            }
        }
        if (j > c.length())
            return i - c.length() - 1;
        else
            return -1;
    }

}

字符串倒序輸出，單詞不倒序

題目
對字符串中的所有單詞進(jìn)行倒排。
說明：
1、每一個單詞是以26個大寫或小寫英文字母構(gòu)成，可能含有非法字符
2、非構(gòu)成單詞的字符均視為單詞間隔符；
3、要求倒排后的單詞間隔符以1個空格表示；如果原字符串中相鄰單詞間有多個間隔符時，倒排轉(zhuǎn)換后也只允許出現(xiàn)1個空格間隔符；
4、每一個單詞最長20個字母；

第1種方法

思路解析

1.我們可以采取正則表達(dá)式把字符串分隔成為字符串?dāng)?shù)組
2.接著我們再倒序輸出字符串?dāng)?shù)組
3.在注意最后1個字符串?dāng)?shù)組，多是空格

public class ReverseStr2 {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            String[] strArray = str.split("[^a-zA-Z]+");
            for (int i = strArray.length - 1; i >= 2; i--) {
                System.out.print(strArray[i] + ' ');
            }
            // 如果字符串?dāng)?shù)組的第1個元素是空串，那末下標(biāo)為1的元素就是最后1個要輸出的元素，末尾不要再加空格
            if (strArray[0].length() == 0)
                System.out.println(strArray[1]);
            else
                System.out.println(strArray[1] + ' ' + strArray[0]);
        }
    }

}

第2種方法

思路解析

對輸入的字符串進(jìn)行分析，去掉非法字符，如中文字符，多個空格只保存1個空格等
對字符串進(jìn)行分組
倒序輸出

代碼以下

/**
 * Created by xujun on 2016/9/20
 */
public class ReverseStr {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            StringBuilder sb = new StringBuilder();
            String[] a = filter(sc.nextLine()).split(" ");
            sb.append(a[a.length - 1]);
            for (int i = a.length - 2; i >= 0; i--) {
                sb.append(" " + a[i]);
            }

            System.out.println(sb.toString().trim());
        }
    }

    public static String filter(String s) {
        char[] c = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        boolean isFirstSpace=true;
        for (int i = 0; i < c.length; i++) {
            if ((c[i] >= 'a' && c[i] <= 'z') || (c[i] >= 'A' && c[i] <= 'Z')) {
                sb.append(c[i]);
                isFirstSpace=true;
                continue;
            }
            if(isFirstSpace){
                sb.append(' ');
                isFirstSpace=false;
            }


        }
        return sb.toString();
    }
}

字符串全排列

思路分析

可以采取遞歸的情勢

從集合中順次選出每個元素，作為排列的第1個元素，然后對剩余的元素進(jìn)行全排列，如此遞歸處理，
從而得到所有元素的全排列。以對字符串a(chǎn)bc進(jìn)行全排列為例，我們可以這么做：以abc為例：
固定a，求后面bc的排列：abc，acb，求好后，a和b交換，得到bac
固定b，求后面ac的排列：bac，bca，求好后，c放到第1位置，得到cba
固定c，求后面ba的排列：cba，cab。

public class permutate {  
    public static int total = 0;  
    public static void swap(String[] str, int i, int j)  
    {  
        String temp = new String();  
        temp = str[i];  
        str[i] = str[j];  
        str[j] = temp;  
    }  
    public static void arrange (String[] str, int st, int len)  
    {  
        if (st == len - 1)  
        {  
            for (int i = 0; i < len; i ++)  
            {  
                System.out.print(str[i]+ "  ");  
            }  
            System.out.println();  
            total++;  
        }  
        else  
        {  
            for (int i = st; i < len; i ++)  
            {  
                swap(str, st, i);  
                arrange(str, st + 1, len);  
                swap(str, st, i);  
            }  
        }  

    }  
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
         String str[] = {"a","b","c"};  
         arrange(str, 0, str.length);  
         System.out.println(total);  
    }  
}

運(yùn)行以上代碼，將可以看到以下輸出

a b c d
a b d c
a c b d
a c d b
a d c b
a d b c
b a c d
b a d c
b c a d
b c d a
b d c a
b d a c
c b a d
c b d a
c a b d
c a d b
c d a b
c d b a
d b c a
d b a c
d c b a
d c a b
d a c b
d a b c
24

全組合

第1種方法

思路解析

基本思路：求全組合，則假定原有元素n個，則終究組合結(jié)果是2^n個。

緣由是：用位操作方法：假定元素本來有：a,b,c3個，則1表示取該元素，0表示不取。故去a則是001，取ab則是011.所以1共3位，每一個位上有兩個選擇0,1.所以是2^n個結(jié)果。

這些結(jié)果的位圖值都是0,1,2….2^n。所以可以類似全真表1樣，從值0到值2^n順次輸出結(jié)果：即：

000,001,010,011,100,101,110,111

對應(yīng)輸出組合結(jié)果為：

空,a, b ,ab,c,ac,bc,abc.

這個輸出順序恰好跟數(shù)字0~2^n結(jié)果遞增順序1樣，取法的2進(jìn)制數(shù)其實(shí)就是從0到2^n⑴的10進(jìn)制數(shù)

public static  void Combination( ) {
        /*基本思路：求全組合，則假定原有元素n個，則終究組合結(jié)果是2^n個。緣由是：
         * 用位操作方法：假定元素本來有：a,b,c3個，則1表示取該元素，0表示不取。故去a則是001，取ab則是011.
         * 所以1共3位，每一個位上有兩個選擇0,1.所以是2^n個結(jié)果。
         * 這些結(jié)果的位圖值都是0,1,2....2^n。所以可以類似全真表1樣，從值0到值2^n順次輸出結(jié)果：即：
         * 000,001,010,011,100,101,110,111 。對應(yīng)輸出組合結(jié)果為：
        空,a, b ,ab,c,ac,bc,abc.
        這個輸出順序恰好跟數(shù)字0~2^n結(jié)果遞增順序1樣
        取法的2進(jìn)制數(shù)其實(shí)就是從0到2^n⑴的10進(jìn)制數(shù)
         * ******************************************************************
         * * 
         * */
        String[] str = {"a" , "b" ,"c"};
        int n = str.length;                                  //元素個數(shù)。
        //求出位圖全組合的結(jié)果個數(shù)：2^n
        int nbit = 1<<n;                                     // “<<” 表示 左移:各2進(jìn)位全部左移若干位，高位拋棄，低位補(bǔ)0。:即求出2^n=2Bit。
        System.out.println("全組合結(jié)果個數(shù)為："+nbit);

        for(int i=0 ;i<nbit ; i++) {                        //結(jié)果有nbit個。輸出結(jié)果從數(shù)字小到大輸出：即輸出0,1,2,3,....2^n。
            System.out.print("組合數(shù)值  "+i + " 對應(yīng)編碼為： ");
            for(int j=0; j<n ; j++) {                        //每一個數(shù)2進(jìn)制最多可以左移n次，即遍歷完所有可能的變化新2進(jìn)制數(shù)值了
                int tmp = 1<<j ;        
                if((tmp & i)!=0) {                            //& 表示與。兩個位都為1時，結(jié)果才為1
                    System.out.print(str[j]);
                }
            }
            System.out.println();
        }
    }

第2種方法

思路解析

n個元素選m個元素的組合問題的實(shí)現(xiàn). 原理以下:

從后往前選取, 選定位置i后, 再在前i⑴個里面選取m⑴個.
如: 1, 2, 3, 4, 5 當(dāng)選取3個元素.

1) 選取5后, 再在前4個里面選取2個, 而前4個里面選取2個又是1個子問題, 遞歸便可;
2) 如果不包括5, 直接選定4, 那末再在前3個里面選取2個, 而前3個里面選取2個又是1個子問題, 遞歸便可;
3) 如果也不包括4, 直接選取3, 那末再在前2個里面選取2個, 恰好只有兩個.
- 縱向看, 1與2與3恰好是1個for循環(huán), 初值為5, 終值為m.
- 橫向看, 該問題為1個前i⑴個當(dāng)選m⑴的遞歸.

代碼以下

package com.xujun.PermutationCombinationHolder;

public final class PermutationCombinationHolder {

    /** 數(shù)組元素的全組合 */
    static void combination(char[] chars) {
        char[] subchars = new char[chars.length]; // 存儲子組合數(shù)據(jù)的數(shù)組
        // 全組合問題就是所有元素(記為n)當(dāng)選1個元素的組合, 加上選2個元素的組合...加
        // 上選n個元素的組合的和
        for (int i = 0; i < chars.length; ++i) {
            final int m = i + 1;
            combination(chars, chars.length, m, subchars, m);
        }
    }

    /**
     * n個元素選m個元素的組合問題的實(shí)現(xiàn). 原理以下: 從后往前選取, 選定位置i后, 再在前i⑴個里面選取m⑴個. 如: 1, 2, 3, 4,
     * 5 當(dāng)選取3個元素. 1) 選取5后, 再在前4個里面選取2個, 而前4個里面選取2個又是1個子問題, 遞歸便可; 2) 如果不包括5,
     * 直接選定4, 那末再在前3個里面選取2個, 而前3個里面選取2個又是1個子問題, 遞歸便可; 3) 如果也不包括4, 直接選取3,
     * 那末再在前2個里面選取2個, 恰好只有兩個. 縱向看, 1與2與3恰好是1個for循環(huán), 初值為5, 終值為m. 橫向看,
     * 該問題為1個前i⑴個當(dāng)選m⑴的遞歸.
     */
    static void combination(char[] chars, int n, int m, char[] subchars,
            int subn) {
        if (m == 0) { // 出口
            for (int i = 0; i < subn; ++i) {
                System.out.print(subchars[i]);
            }
            System.out.println();
        } else {
            for (int i = n; i >= m; --i) { // 從后往前順次選定1個
                subchars[m - 1] = chars[i - 1]; // 選定1個后
                combination(chars, i - 1, m - 1, subchars, subn); // 從前i⑴個里面選取m⑴個進(jìn)行遞歸
            }
        }
    }

    /** 數(shù)組元素的全排列 */
    static void permutation(char[] chars) {
        permutation(chars, 0, chars.length - 1);
    }

    /** 數(shù)組中從索引begin到索引end之間的子數(shù)組參與到全排列 */
    static void permutation(char[] chars, int begin, int end) {
        if (begin == end) { // 只剩最后1個字符時為出口
            for (int i = 0; i < chars.length; ++i) {
                System.out.print(chars[i]);
            }
            System.out.println();
        } else {
            for (int i = begin; i <= end; ++i) { // 每一個字符順次固定到數(shù)組或子數(shù)組的第1個
                if (canSwap(chars, begin, i)) { // 去重
                    swap(chars, begin, i); // 交換
                    permutation(chars, begin + 1, end); // 遞歸求子數(shù)組的全排列
                    swap(chars, begin, i); // 還原
                }
            }
        }
    }

    static void swap(char[] chars, int from, int to) {
        char temp = chars[from];
        chars[from] = chars[to];
        chars[to] = temp;
    }

    static boolean canSwap(char[] chars, int begin, int end) {
        for (int i = begin; i < end; ++i) {
            if (chars[i] == chars[end]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        final char[] chars = new char[] { 'a', 'b', 'c' };
        permutation(chars);
        System.out.println("===================");
        combination(chars);
    }
}