[关闭]
@xujun94 2016-09-21T11:51:40.000000Z 字数 7694 阅读 1651

笔试题—字符串常见的算法题集锦

本篇博客主要讲解一下四个问题

转载请注明原博客地址： http://blog.csdn.net/gdutxiaoxu/article/details/52602327

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

KMP算法

关于KMP算法的分析，这里就不讲解了，有兴趣的可以参考这篇博客：从头到尾彻底理解KMP

代码如下

  1. package com.xujun.stringfind;
  3. public class KMPFind {
  5.     public static void main(String[] args) {
  6.         String s = "abcbb2abcabx";
  7.         String c = "abca";
  8.         int[] next = new int[s.length() + 1];
  9.         next = getNext(c);
  10.         for (int i = 0; i < next.length; i++) {
  11.             System.out.println("=" + next[i]);
  12.         }
  13.         int find = matchNext(s, c, 0);
  14.         System.out.println("find=" + find);
  16.         int[] nextVal = getNextVal(c);
  18.         for (int i = 0; i < nextVal.length; i++) {
  19.             System.out.println("=" + nextVal[i]);
  20.         }
  21.         int matchNextVal = matchNextVal(s, c, 0);
  22.         System.out.println("matchNextVal=" + matchNextVal);
  24.     }
  26.     /**
  27.      * 注意这里为了保持保持一致性 ，第一个next[0]没有用到
  28.      * 
  29.      * @param c
  30.      * @return
  31.      */
  32.     private static int[] getNextVal(String c) {
  33.         int[] nextVal = new int[c.length() + 1];
  34.         int front = 0;
  35.         int behind = 1;
  36.         nextVal[1] = 0;
  37.         /**
  38.          * c.charAt(front-1)表示前缀字符 ，c.charAt(behind-1)表示后缀字符
  39.          */
  40.         while (behind < c.length()) {
  41.             if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
  42.                 ++front;
  43.                 ++behind;
  44.                 if (c.charAt(front - 1) != c.charAt(behind - 1)) {
  45.                     nextVal[behind] = front;
  46.                 } else {
  47.                     nextVal[behind] = nextVal[front];
  48.                 }
  49.             } else {
  50.                 // 前缀索引回溯
  51.                 front = nextVal[front];
  52.             }
  53.         }
  55.         return nextVal;
  56.     }
  58.     /**
  59.      * 注意这里为了保持保持一致性 ，第一个next[0]没有用到
  60.      * 
  61.      * @param c
  62.      * @return
  63.      */
  64.     private static int[] getNext(String c) {
  65.         int[] next = new int[c.length() + 1];
  66.         int front = 0;
  67.         int behind = 1;
  68.         next[1] = 0;
  69.         /**
  70.          * c.charAt(front-1)表示前缀字符 c.charAt(behind-1)表示后缀字符
  71.          */
  72.         while (behind < c.length()) {
  73.             if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
  74.                 ++front;
  75.                 ++behind;
  76.                 next[behind] = front;
  77.             } else {
  78.                 // 前缀 索引回溯
  79.                 front = next[front];
  80.             }
  81.         }
  83.         return next;
  84.     }
  86.     public static int matchNextVal(String source, String c, int pos) {
  88.         int i;
  89.         int[] nextVal = getNextVal(c);
  90.         if (pos < 1) {
  91.             i = 1;
  92.         } else {
  93.             i = pos + 1;
  94.         }
  95.         int j = 1; // i控制S,j控制T;
  96.         while (i <= source.length() && j <= c.length()) {
  97.             if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
  98.                 ++i;
  99.                 ++j;
  100.             } else {
  101.                 j = nextVal[j]; // j退回合适的位置，i值不变
  102.             }
  103.         }
  104.         if (j > c.length())
  105.             return i - c.length() - 1;
  106.         else
  107.             return -1;
  108.     }
  110.     public static int matchNext(String source, String c, int pos) {
  112.         int i;
  113.         int[] next = getNext(c);
  114.         if (pos < 1) {
  115.             i = 1;
  116.         } else {
  117.             i = pos + 1;
  118.         }
  119.         int j = 1; // i控制S,j控制T;
  120.         while (i <= source.length() && j <= c.length()) {
  121.             if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
  122.                 ++i;
  123.                 ++j;
  124.             } else {
  125.                 j = next[j]; // j退回合适的位置，i值不变
  126.             }
  127.         }
  128.         if (j > c.length())
  129.             return i - c.length() - 1;
  130.         else
  131.             return -1;
  132.     }
  134. }

字符串倒序输出，单词不倒序

题目
对字符串中的所有单词进行倒排。
说明：
1、每个单词是以26个大写或小写英文字母构成，可能含有非法字符
2、非构成单词的字符均视为单词间隔符；
3、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
4、每个单词最长20个字母；

第一种方法

思路解析

  1. public class ReverseStr2 {
  3.     public static void main(String args[]) {
  4.         Scanner sc = new Scanner(System.in);
  5.         while (sc.hasNext()) {
  6.             String str = sc.nextLine();
  7.             String[] strArray = str.split("[^a-zA-Z]+");
  8.             for (int i = strArray.length - 1; i >= 2; i--) {
  9.                 System.out.print(strArray[i] + ' ');
  10.             }
  11.             // 如果字符串数组的第一个元素是空串，那么下标为1的元素就是最后一个要输出的元素，末尾不要再加空格
  12.             if (strArray[0].length() == 0)
  13.                 System.out.println(strArray[1]);
  14.             else
  15.                 System.out.println(strArray[1] + ' ' + strArray[0]);
  16.         }
  17.     }
  19. }

第二种方法

思路解析

代码如下

  1. /**
  2.  * Created by xujun on 2016/9/20
  3.  */
  4. public class ReverseStr {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         while (sc.hasNext()) {
  8.             StringBuilder sb = new StringBuilder();
  9.             String[] a = filter(sc.nextLine()).split(" ");
  10.             sb.append(a[a.length - 1]);
  11.             for (int i = a.length - 2; i >= 0; i--) {
  12.                 sb.append(" " + a[i]);
  13.             }
  15.             System.out.println(sb.toString().trim());
  16.         }
  17.     }
  19.     public static String filter(String s) {
  20.         char[] c = s.toCharArray();
  21.         StringBuilder sb = new StringBuilder();
  22.         boolean isFirstSpace=true;
  23.         for (int i = 0; i < c.length; i++) {
  24.             if ((c[i] >= 'a' && c[i] <= 'z') || (c[i] >= 'A' && c[i] <= 'Z')) {
  25.                 sb.append(c[i]);
  26.                 isFirstSpace=true;
  27.                 continue;
  28.             }
  29.             if(isFirstSpace){
  30.                 sb.append(' ');
  31.                 isFirstSpace=false;
  32.             }
  35.         }
  36.         return sb.toString();
  37.     }
  38. }

字符串全排列

思路分析

可以采用递归的形式

  1. public class permutate {  
  2.     public static int total = 0;  
  3.     public static void swap(String[] str, int i, int j)  
  4.     {  
  5.         String temp = new String();  
  6.         temp = str[i];  
  7.         str[i] = str[j];  
  8.         str[j] = temp;  
  9.     }  
  10.     public static void arrange (String[] str, int st, int len)  
  11.     {  
  12.         if (st == len - 1)  
  13.         {  
  14.             for (int i = 0; i < len; i ++)  
  15.             {  
  16.                 System.out.print(str[i]+ "  ");  
  17.             }  
  18.             System.out.println();  
  19.             total++;  
  20.         }  
  21.         else  
  22.         {  
  23.             for (int i = st; i < len; i ++)  
  24.             {  
  25.                 swap(str, st, i);  
  26.                 arrange(str, st + 1, len);  
  27.                 swap(str, st, i);  
  28.             }  
  29.         }  
  31.     }  
  32.     /** 
  33.      * @param args 
  34.      */  
  35.     public static void main(String[] args) {  
  36.         // TODO Auto-generated method stub  
  37.          String str[] = {"a","b","c"};  
  38.          arrange(str, 0, str.length);  
  39.          System.out.println(total);  
  40.     }  
  41. }

运行以上代码，将可以看到以下输出

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

全组合

第一种方法

思路解析

基本思路：求全组合，则假设原有元素n个，则最终组合结果是2^n个。

原因是： 用位操作方法：假设元素原本有：a,b,c三个，则1表示取该元素，0表示不取。故去a则是001，取ab则是011.所以一共三位，每个位上有两个选择0,1.所以是2^n个结果。

这些结果的位图值都是0,1,2....2^n。所以可以类似全真表一样，从值0到值2^n依次输出结果：即：

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

对应输出组合结果为：

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

这个输出顺序刚好跟数字0~2^n结果递增顺序一样，取法的二进制数其实就是从0到2^n-1的十进制数

  1. public static  void Combination( ) {
  2.         /*基本思路：求全组合，则假设原有元素n个，则最终组合结果是2^n个。原因是：
  3.          * 用位操作方法：假设元素原本有：a,b,c三个，则1表示取该元素，0表示不取。故去a则是001，取ab则是011.
  4.          * 所以一共三位，每个位上有两个选择0,1.所以是2^n个结果。
  5.          * 这些结果的位图值都是0,1,2....2^n。所以可以类似全真表一样，从值0到值2^n依次输出结果：即：
  6.          * 000,001,010,011,100,101,110,111 。对应输出组合结果为：
  7.         空,a, b ,ab,c,ac,bc,abc.
  8.         这个输出顺序刚好跟数字0~2^n结果递增顺序一样
  9.         取法的二进制数其实就是从0到2^n-1的十进制数
  10.          * ******************************************************************
  11.          * * 
  12.          * */
  13.         String[] str = {"a" , "b" ,"c"};
  14.         int n = str.length;                                  //元素个数。
  15.         //求出位图全组合的结果个数：2^n
  16.         int nbit = 1<<n;                                     // “<<” 表示 左移:各二进位全部左移若干位，高位丢弃，低位补0。:即求出2^n=2Bit。
  17.         System.out.println("全组合结果个数为："+nbit);
  19.         for(int i=0 ;i<nbit ; i++) {                        //结果有nbit个。输出结果从数字小到大输出：即输出0,1,2,3,....2^n。
  20.             System.out.print("组合数值  "+i + " 对应编码为： ");
  21.             for(int j=0; j<n ; j++) {                        //每个数二进制最多可以左移n次，即遍历完所有可能的变化新二进制数值了
  22.                 int tmp = 1<<j ;        
  23.                 if((tmp & i)!=0) {                            //& 表示与。两个位都为1时，结果才为1
  24.                     System.out.print(str[j]);
  25.                 }
  26.             }
  27.             System.out.println();
  28.         }
  29.     }

第二种方法

思路解析

n个元素选m个元素的组合问题的实现. 原理如下:

从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个.
如: 1, 2, 3, 4, 5 中选取3个元素.

代码如下

  1. package com.xujun.PermutationCombinationHolder;
  3. public final class PermutationCombinationHolder {
  5.     /** 数组元素的全组合 */
  6.     static void combination(char[] chars) {
  7.         char[] subchars = new char[chars.length]; // 存储子组合数据的数组
  8.         // 全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加
  9.         // 上选n个元素的组合的和
  10.         for (int i = 0; i < chars.length; ++i) {
  11.             final int m = i + 1;
  12.             combination(chars, chars.length, m, subchars, m);
  13.         }
  14.     }
  16.     /**
  17.      * n个元素选m个元素的组合问题的实现. 原理如下: 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个. 如: 1, 2, 3, 4,
  18.      * 5 中选取3个元素. 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可; 2) 如果不包含5,
  19.      * 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可; 3) 如果也不包含4, 直接选取3,
  20.      * 那么再在前2个里面选取2个, 刚好只有两个. 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m. 横向看,
  21.      * 该问题为一个前i-1个中选m-1的递归.
  22.      */
  23.     static void combination(char[] chars, int n, int m, char[] subchars,
  24.             int subn) {
  25.         if (m == 0) { // 出口
  26.             for (int i = 0; i < subn; ++i) {
  27.                 System.out.print(subchars[i]);
  28.             }
  29.             System.out.println();
  30.         } else {
  31.             for (int i = n; i >= m; --i) { // 从后往前依次选定一个
  32.                 subchars[m - 1] = chars[i - 1]; // 选定一个后
  33.                 combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
  34.             }
  35.         }
  36.     }
  38.     /** 数组元素的全排列 */
  39.     static void permutation(char[] chars) {
  40.         permutation(chars, 0, chars.length - 1);
  41.     }
  43.     /** 数组中从索引begin到索引end之间的子数组参与到全排列 */
  44.     static void permutation(char[] chars, int begin, int end) {
  45.         if (begin == end) { // 只剩最后一个字符时为出口
  46.             for (int i = 0; i < chars.length; ++i) {
  47.                 System.out.print(chars[i]);
  48.             }
  49.             System.out.println();
  50.         } else {
  51.             for (int i = begin; i <= end; ++i) { // 每个字符依次固定到数组或子数组的第一个
  52.                 if (canSwap(chars, begin, i)) { // 去重
  53.                     swap(chars, begin, i); // 交换
  54.                     permutation(chars, begin + 1, end); // 递归求子数组的全排列
  55.                     swap(chars, begin, i); // 还原
  56.                 }
  57.             }
  58.         }
  59.     }
  61.     static void swap(char[] chars, int from, int to) {
  62.         char temp = chars[from];
  63.         chars[from] = chars[to];
  64.         chars[to] = temp;
  65.     }
  67.     static boolean canSwap(char[] chars, int begin, int end) {
  68.         for (int i = begin; i < end; ++i) {
  69.             if (chars[i] == chars[end]) {
  70.                 return false;
  71.             }
  72.         }
  73.         return true;
  74.     }
  76.     public static void main(String[] args) {
  77.         final char[] chars = new char[] { 'a', 'b', 'c' };
  78.         permutation(chars);
  79.         System.out.println("===================");
  80.         combination(chars);
  81.     }
  82. }

题外话

转载请注明原博客地址： http://blog.csdn.net/gdutxiaoxu/article/details/52602327

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

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注