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

深藏阁楼爱情的钟 2022-09-26 04:54 192阅读 0赞

**Android 技术人，希望让你看到程序猿不同的一面，除了分享 Coding，，还有职场心得，面试经验，学习心得，人生感悟等等。希望通过该公众号，我们不只会敲代码，我们还会。。。。。。**

![Android 技术人][Android]

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

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

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

**[例子源码下载地址：][Link 2] [http://download.csdn.net/detail/gdutxiaoxu/9635393][Link 2]**

## KMP算法 ##

关于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);
    
    	}
    
    	/** * 注意这里为了保持保持一致性 ，第一个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-1)表示前缀字符 ，c.charAt(behind-1)表示后缀字符 */
    		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;
    	}
    
    	/** * 注意这里为了保持保持一致性 ，第一个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-1)表示前缀字符 c.charAt(behind-1)表示后缀字符 */
    		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、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；  
4、每个单词最长20个字母；

第一种方法

### 思路解析 ###

*  1.我们可以采用正则表达式把字符串分隔成为字符串数组
 *  2.接着我们再倒序输出字符串数组
 *  3.在注意最后一个字符串数组，可能是空格

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的元素就是最后一个要输出的元素，末尾不要再加空格
    			if (strArray[0].length() == 0)
    				System.out.println(strArray[1]);
    			else
    				System.out.println(strArray[1] + ' ' + strArray[0]);
    		}
    	}
    
    }

第二种方法

### 思路解析 ###

*  对输入的字符串进行分析，去掉非法字符，如中文字符，多个空格只保留一个空格等
 *  对字符串进行分组
 *  倒序输出

### 代码如下 ###

/** * 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();
    	}
    }

--------------------

## 字符串全排列 ##

### 思路分析 ###

可以采用递归的形式

*  从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，
 *  从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例：
 *  固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
 *  固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到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

--------------------

## 全组合 ##

### 第一种方法 ###

#### 思路解析 ####

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

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

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

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

对应输出组合结果为：

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

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

public static  void Combination( ) { 
            /*基本思路：求全组合，则假设原有元素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的十进制数 * ****************************************************************** * * * */
            String[] str = { "a" , "b" ,"c"};
            int n = str.length;                                  //元素个数。
            //求出位图全组合的结果个数：2^n
            int nbit = 1<<n;                                     // “<<” 表示 左移:各二进位全部左移若干位，高位丢弃，低位补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++) {                         //每个数二进制最多可以左移n次，即遍历完所有可能的变化新二进制数值了
                    int tmp = 1<<j ;        
                    if((tmp & i)!=0) {                             //& 表示与。两个位都为1时，结果才为1
                        System.out.print(str[j]);
                    }
                }
                System.out.println();
            }
        }

### 第二种方法 ###

#### 思路解析 ####

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

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

*  1.  选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可;
 *  1.  如果不包含5, 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可;
 *  1.  如果也不包含4, 直接选取3, 那么再在前2个里面选取2个, 刚好只有两个.
 *  纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m.
 *  横向看, 该问题为一个前i-1个中选m-1的递归.

### 代码如下 ###

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-1个里面选取m-1个. 如: 1, 2, 3, 4, * 5 中选取3个元素. 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可; 2) 如果不包含5, * 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可; 3) 如果也不包含4, 直接选取3, * 那么再在前2个里面选取2个, 刚好只有两个. 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m. 横向看, * 该问题为一个前i-1个中选m-1的递归. */
    	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) {  // 从后往前依次选定一个
    				subchars[m - 1] = chars[i - 1]; // 选定一个后
    				combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
    			}
    		}
    	}
    
    	/** 数组元素的全排列 */
    	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) {  // 只剩最后一个字符时为出口
    			for (int i = 0; i < chars.length; ++i) { 
    				System.out.print(chars[i]);
    			}
    			System.out.println();
    		} else { 
    			for (int i = begin; i <= end; ++i) {  // 每个字符依次固定到数组或子数组的第一个
    				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多天没更新博客了，主要是因为家里有事，回家了十来天，最近又在校招，有时候参加宣讲会与招聘，有时候在准备笔试和面试的东西。
 *  现在还没有拿到offer，也是感觉挺可惜的。
 *  接下来更新博客的频率可能会比较不稳定

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

**[例子源码下载地址：][Link 2] [http://download.csdn.net/detail/gdutxiaoxu/9635393][Link 2]**

![Android 技术人][Android]

[Android]: /images/20220717/5b290f1d82424045ac473c400bc7fc21.png
[Link 1]: http://blog.csdn.net/gdutxiaoxu/article/details/52602327
[Link 2]: http://download.csdn.net/detail/gdutxiaoxu/9635393
[KMP]: http://blog.csdn.net/v_july_v/article/details/7041827