字符串相关高频面试题算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了字符串相关高频面试题算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、字符串

java：String内置类型，不可更改。（如需更改可考虑：StringBuffer, StringBuilder,char[]等）

二、归类

　字符串涉及到的相关题型通常会是以下几个方面：

概念理解：字典序
简单操作：插入删除字符、旋转
规则判断（罗马数字转换是否是合法的整数、浮点数）
数字运算（大数加法，二进制加法）
排序、交换
字符计数：变位词
匹配（正则表达式、全串匹配、KMP、周期判断）
动态规划（LCS、编辑距离、最长回文子串）
搜索（单词变换、排列组合）

三、例题

1、交换：把一个只包含01的串排序，可交换任意两个数的位置，最少需要多少次交换？

　　思路：从两头往中间扫荡，扫荡过程中在左边遇到1就和右边遇到的0交换位置，直接到左有下标相遇时结束。具体代码如下：

 1 public static void main(String[] strs) {
 2         int count = 0;
 3         int[] arrays = new int[] {0, 0, 1, 1, 1, 0, 1, 0, 0, 1};
 4         int left = 0;
 5         int right = arrays.length - 1;
 6         while (true) {
 7             while (arrays[left] == 0) {
 8                 left++;
 9             }
10             while (arrays[right] == 1) {
11                 right--;
12             }
13             if (left >= right) {
14                 break;
15             } else {
16                 int temp = arrays[left];
17                 arrays[left] = arrays[right];
18                 arrays[right] = temp;
19                 count++;
20             }
21         }
22         Logger.println("交换次数：" + count);
23         for (int array : arrays) {
24             Logger.print(array + ", ");
25         }
26 }

复制

清晰起见，交换次数和排序后的的字符串输出如下：

交换次数：3
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,

复制

2、字符串替换和复制：删除一个字符串所有的a，并且复制所有的b（字符数组足够大）

　　思路：详细思路见代码注释

 1 public static void main(String[] strs) {
 2         char[] input = new char[]{'a', 'b', 'c', 'd', 'a', 'f', 'a', 'b', 'c', 'd', 'b', 'b', 'a', 'b'};
 3         char[] chars = new char[50];
 4         for (int j = 0; j < input.length; j++) {
 5             chars[j] = input[j];
 6         }
 7         Logger.println("操作前：");
 8         for (char c:chars
 9                 ) {
10             Logger.print(c + ", ");
11         }
12         int n = 0;
13         int countB = 0;
14         // 1、删除a，用n当做新下标，循环遍历数组，凡是不是a的元素都放到新下标的位置，由于新n增长慢，老下标i增长快，所以元素不会被覆盖。
15         // 并且在删除a时顺便记录b的数量，以便下一步复制b时可以提前确定数组最终的最大的下标。
16         for (int i = 0; chars[i] != '\u0000' && i < chars.length; i++) {
17             if (chars[i] != 'a') {
18                 chars[n++] = chars[i];
19             }
20             if (chars[i] == 'b') {
21                 countB++;
22             }
23         }
24 
25         // 2、复制b，由于在第一步中就已经知道了字符串中b的个数，这里就能确定最终字符串的最大下标，从最打下表开始倒着复制原字符串，碰到b时复制即可。
26         int newMaxIndex = n + countB - 1;
27         for (int k = n - 1; k >= 0; k--) {
28             chars[newMaxIndex--] = chars[k];
29             if (chars[k] == 'b') {
30                 chars[newMaxIndex--] = chars[k];
31             }
32         }
33 
34         Logger.println("\n操作后：");
35         for (char c:chars
36                 ) {
37             Logger.print(c + ", ");
38         }
39 }

复制

3、交换星号：一个字符串只包含 * 和数字，请把它的 * 都放在开头。

　　如：1 * 2 * 4 * 3 => * * * 1 2 4 3

方案一：倒着操作，从最大下标开始向前遍历，遇到非 * 号的元素则加入"新"下标中，遍历完毕后，j即代表 * 号的个数，然后将0-j赋值为 * 即可。（操作后，数字的相对位置不变）代码如下：

 1 public static void main(String[] strs) {
 2         char[] chars = new char[]{'1', '*', '4', '3', '*', '5', '*'};
 3         // 方案一（操作后，数字的相对位置不变）
 4         // 倒着操作：从最大下标开始向前遍历，遇到非*号的元素则加入"新"下标中，遍历完毕后，j即代表*号的个数，然后将0-j赋值为*即可。
 5         int j = chars.length - 1;
 6         for (int i = j; i >= 0; i--) {
 7             if (chars[i] != '*') {
 8                 chars[j--] = chars[i];
 9             }
10         }
11         while (j >= 0) {
12             chars[j--] = '*';
13         }
14         for (char c:chars
15                 ) {
16             Logger.print(c + ", ");
17         }
18 }

复制

输出结果如下:

*, *, *, 1, 4, 3, 5,

复制

方案二（操作后，数组的相对位置会变）快排划分，根据循环不变式（每一步循环之后条件都成立）:如本题[0..i-1]是*,[i..j-1]是数字,[j...n-1]未探测，循环时，随着i和j增加，维护此条件依然不变，代码如下:

 1 public static void main(String[] strs) {
 2         char[] chars = new char[]{'1', '*', '4', '3', '*', '5', '*'};
 3         // 方案二（操作后，数组的相对位置会变）
 4         // 快排划分，根据循环不变式（每一步循环之后条件都成立）:如本题[0..i-1]是*,[i..j-1]是数字,[j...n-1]未探测，循环时，随着i和j增加，维护此条件依然不变
 5         for (int i = 0, j = 0; j < chars.length; ++j) {
 6             if (chars[j] == '*') {
 7                 char temp = chars[i];
 8                 chars[i] = chars[j];
 9                 chars[j] = temp;
10                 i++;
11             }
12         }
13         for (char c:chars
14                 ) {
15             Logger.print(c + ", ");
16         }
17 }

复制

输出结果如下：

*, *, *, 3, 1, 5, 4,

复制

4、单词翻转

　　例如：I am a student =》 student a am I

　　思路：

　　1、先将整个字符串翻转：如：I am a student =》 tneduts a ma I

　　2、通过空格判断出每个单词，然后对每个单词进行翻转

　　代码如下:

 1 public static void main(String[] strs) {
 2         String input = "I am a student";
 3         char[] chars = input.toCharArray();
 4         int i = 0;
 5         int j = chars.length - 1;
 6         while (i < j) {
 7             swap(chars, i++, j--);
 8         }
 9         int front = 1;
10         int tail = 0;
11         while (front < chars.length) {
12             if (chars[front] == ' ') {
13                 int frontTemp = front - 1;
14                 while (tail < frontTemp) {
15                     swap(chars, tail++, frontTemp--);
16                 }
17                 tail = front + 1;
18             }
19             front++;
20         }
21         for (char c:chars
22                 ) {
23             Logger.print(c);
24         }
25 }
26 
27 public static void swap(char[] chars, int index1, int index2) {
28         char temp = chars[index1];
29         chars[index1] = chars[index2];
30         chars[index2] = temp;
31 }

复制

输出结果如下: