国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > 笔试题—字符串常见的算法题集锦

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

来源:程序员人生   发布时间:2016-09-27 08:43:49 阅读次数:1207次

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

本篇博客主要讲授1下4个问题

  • KMP算法
  • 字母倒序输出
  • 全排列
  • 全组合

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

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

KMP算法

关于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; } }

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

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

第1种方法

思路解析

  • 1.我们可以采取正则表达式把字符串分隔成为字符串数组
  • 2.接着我们再倒序输出字符串数组
  • 3.在注意最后1个字符串数组,多是空格
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] + ' '); } // 如果字符串数组的第1个元素是空串,那末下标为1的元素就是最后1个要输出的元素,末尾不要再加空格 if (strArray[0].length() == 0) System.out.println(strArray[1]); else System.out.println(strArray[1] + ' ' + strArray[0]); } } }

第2种方法

思路解析

  • 对输入的字符串进行分析,去掉非法字符,如中文字符,多个空格只保存1个空格等
  • 对字符串进行分组
  • 倒序输出

代码以下

/** * 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个元素,然后对剩余的元素进行全排列,如此递归处理,
  • 从而得到所有元素的全排列。以对字符串abc进行全排列为例,我们可以这么做:以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); } }

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

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个,则终究组合结果是2^n个。

缘由是: 用位操作方法:假定元素本来有:a,b,c3个,则1表示取该元素,0表示不取。故去a则是001,取ab则是011.所以1共3位,每一个位上有两个选择0,1.所以是2^n个结果。

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

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

对应输出组合结果为:

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

这个输出顺序恰好跟数字0~2^n结果递增顺序1样,取法的2进制数其实就是从0到2^n⑴的10进制数

public static void Combination( ) { /*基本思路:求全组合,则假定原有元素n个,则终究组合结果是2^n个。缘由是: * 用位操作方法:假定元素本来有:a,b,c3个,则1表示取该元素,0表示不取。故去a则是001,取ab则是011. * 所以1共3位,每一个位上有两个选择0,1.所以是2^n个结果。 * 这些结果的位图值都是0,1,2....2^n。所以可以类似全真表1样,从值0到值2^n顺次输出结果:即: * 000,001,010,011,100,101,110,111 。对应输出组合结果为: 空,a, b ,ab,c,ac,bc,abc. 这个输出顺序恰好跟数字0~2^n结果递增顺序1样 取法的2进制数其实就是从0到2^n⑴的10进制数 * ****************************************************************** * * * */ String[] str = {"a" , "b" ,"c"}; int n = str.length; //元素个数。 //求出位图全组合的结果个数:2^n int nbit = 1<<n; // “<<” 表示 左移:各2进位全部左移若干位,高位抛弃,低位补0。:即求出2^n=2Bit。 System.out.println("全组合结果个数为:"+nbit); for(int i=0 ;i<nbit ; i++) { //结果有nbit个。输出结果从数字小到大输出:即输出0,1,2,3,....2^n。 System.out.print("组合数值 "+i + " 对应编码为: "); for(int j=0; j<n ; j++) { //每一个数2进制最多可以左移n次,即遍历完所有可能的变化新2进制数值了 int tmp = 1<<j ; if((tmp & i)!=0) { //& 表示与。两个位都为1时,结果才为1 System.out.print(str[j]); } } System.out.println(); } }

第2种方法

思路解析

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

从后往前选取, 选定位置i后, 再在前i⑴个里面选取m⑴个.
如: 1, 2, 3, 4, 5 当选取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循环, 初值为5, 终值为m.
    • 横向看, 该问题为1个前i⑴个当选m⑴的递归.

代码以下

package com.xujun.PermutationCombinationHolder; public final class PermutationCombinationHolder { /** 数组元素的全组合 */ static void combination(char[] chars) { char[] subchars = new char[chars.length]; // 存储子组合数据的数组 // 全组合问题就是所有元素(记为n)当选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个元素的组合问题的实现. 原理以下: 从后往前选取, 选定位置i后, 再在前i⑴个里面选取m⑴个. 如: 1, 2, 3, 4, * 5 当选取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循环, 初值为5, 终值为m. 横向看, * 该问题为1个前i⑴个当选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⑴个进行递归 } } } /** 数组元素的全排列 */ static void permutation(char[] chars) { permutation(chars, 0, chars.length - 1); } /** 数组中从索引begin到索引end之间的子数组参与到全排列 */ 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) { // 每一个字符顺次固定到数组或子数组的第1个 if (canSwap(chars, begin, i)) { // 去重 swap(chars, begin, i); // 交换 permutation(chars, begin + 1, end); // 递归求子数组的全排列 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); } }

题外话

  • 已有20多天没更新博客了,主要是由于家里有事,回家了10来天,最近又在校招,有时候参加宣讲会与招聘,有时候在准备笔试和面试的东西。
  • 现在还没有拿到offer,也是感觉挺惋惜的。
  • 接下来更新博客的频率可能会比较不稳定

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

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

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生