数据结构之字符串

时间：2023-01-04 09:03:42

　　第一篇：数据结构之链表

　　第二篇：数据结构之栈和队列

　　第三篇：数据结构之二叉树

　　第四篇：数据结构之排序

 

　　在这篇文章里，我们关注和字符串相关的话题。

　　在谈论到字符串时，通常情况下，我们是在讨论ASCII码范围内的字符串，即它包括256个字符。在设计字符串相关的算法时，我们需要在时间和空间这两者之间进行权衡。

　　下面我们来看相关的题目。

  • 判断字符串里出现的字符是否是唯一的。
    思路：方案一：将字符串转换为字符数组，从第一个字符开始遍历，针对每个字符，判断字符串之前是否出现过该字符，如果出现过，说明该字符在字符串中不是唯一的。对应的空间复杂度O(1)，时间复杂度O(n*n)。
    数据结构之字符串数据结构之字符串判断字符串中的字符是否唯一 
     1 public static boolean Check(String value)
 2 {
 3     if (value == null || value.length() < 2) return true;
 4     char[] arrChars = value.toCharArray();
 5     for (int i = 1; i < arrChars.length; i++)
 6     {
 7         char ch = arrChars[i];
 8         for (int j = 0; j < i; j++)
 9         {
10             if (arrChars[j] == ch) return false;
11         }
12     }
13     
14     return true;
15 }

    方案二：如果字符串中的字符都是ASCII码，那么可以建立一个长度为256的整型flag数组，数组的每个元素初始值是0， 然后遍历字符串，将每个字符对应的ASCII码求出数组中对应位置的元素值，如果为0，说明字符串中暂时还没有出现该字符，将数组对应元素的值设置为1；如果为1，说明字符串中已经出现了该字符，有重复。

    数据结构之字符串数据结构之字符串使用flag数组来判断字符串中字符是否唯一 
     1 public static boolean Check2(String value)
 2 {
 3     if (value == null || value.length() < 2) return true;        
 4     char[] arrChars = value.toCharArray();
 5     int[] arrFlag = new int[256];
 6     for(int flag : arrFlag) flag = 0;
 7     for(char ch : arrChars)
 8     {
 9         if (arrFlag[(int)ch] == 1) return false;
10         arrFlag[(int)ch] = 1;
11     }
12     return true;
13 }

    方案三：如果字符串空字符超出ASCII码，那么可以使用一个hashtable来模拟flag数组，将遍历过的每个字符以键的方式插入到hashtable中。代码略。

  • 反转字符串
    思路：循环替换（0-n/2），需要注意字符串的最后一位是否是'\0'。
    数据结构之字符串数据结构之字符串反转字符串 
     1 public static String reverse(String value)
 2 {
 3     if (value == null || value.length() < 3) return value;
 4     
 5     char[] arrChars = value.toCharArray();
 6     int length = value.length() - 1;
 7     for (int i = 0; i < length/2; i++)
 8     {
 9         char temp = arrChars[i];
10         arrChars[i] = arrChars[length - i];
11         arrChars[length - i] = temp;
12     }
13     arrChars[length] = '0';
14     return arrChars.toString();
15 }
  • 删除字符串中的重复字符
    思路：这个题目，同样有遍历和flag数组两种方式。首先来看遍历方式，时间复杂度是O(n*n)，空间复杂度是O(1)。
    数据结构之字符串数据结构之字符串利用循环删除字符串中的重复字符 
     1 public static void removeDuplicate2(String value)
 2 {
 3     if (value == null || value.length() < 2) return;
 4     char[] arrChars = value.toCharArray();
 5     int current = 0;
 6     for (int i = 1; i < arrChars.length; i++)
 7     {
 8         int j = 0;
 9         for (j = 0; j < i; j++)
10         {
11             if (arrChars[i] == arrChars[j]) break;
12         }
13         if (i == j) 
14         {
15             arrChars[current] = arrChars[i];
16             current++;
17         }
18     }
19     arrChars[current] = '0';
20     value = arrChars.toString();
21 }

    接着是使用flag数组。

    数据结构之字符串数据结构之字符串利用flag数组删除字符串中的重复字符 
     1 public static void removeDuplicate3(String value)
 2 {
 3     if (value == null || value.length() < 2) return;
 4     int[] arrFlag = new int[256];
 5     for(int flag : arrFlag) flag = 0;
 6     char[] arrChars = value.toCharArray();
 7     int current = 0;
 8     for (int i = 0; i < arrChars.length; i++)
 9     {
10         if (arrFlag[(int)arrChars[i]] != 1)
11         {
12             arrChars[current] = arrChars[i];
13             arrFlag[(int)arrChars[i]] = 1;
14             current++;
15         }
16     }
17     arrChars[current] = '0';
18     value = arrChars.toString();
19 }
  • 判断给定的两个字符串是否是变位词（包含的字符相同，但顺序不同）
    思路：方案一：对两个字符串分别进行排序处理，然后比较排序后的两个字符串是否相同。代码略
    方案二：采用flag数组，首先遍历第一个字符串，填充flag数组；然后遍历第二个字符串，同时检查flag数组。
    数据结构之字符串数据结构之字符串利用flag数组判断两个字符串是否是变位词 
     1 public static boolean isAnagram(String value1, String value2)
 2 {
 3     if (value1 == null || value2 == null || value1.length() != value2.length())
 4         return false;
 5     
 6     int[] arrFlag = new int[256];
 7     for(int flag : arrFlag) flag = 0;
 8     char[] arrChars1 = value1.toCharArray();
 9     for(char ch : arrChars1) arrFlag[ch]++;
10     char[] arrChars2 = value2.toCharArray();
11     for(char ch : arrChars2) 
12     {
13         if (arrChars1[ch] == 0)
14             return false;
15         arrChars1[ch]--;
16     }
17     return true;
18 }
  • 将字符串中出现的所有空格替换为'%20'
    思路：由于空格和'%20'长度不一致，这样替换后的字符串长度和原来的长度肯定不一样，对于这种情况，我们需要首先遍历一次字符串，计算出空格的数组，这样也就可以计算出新的字符串的长度，然后从后向前依次替换。
    数据结构之字符串数据结构之字符串替换字符串中的空格为'%20' 
     1 public static void replaceWhitespace(String value)
 2 {
 3     if (value == null)return;
 4     int count = 0;
 5     for(int i = 0; i < value.length(); i++)
 6     {
 7         if (value.charAt(i) == ' ')
 8         {
 9             count++;
10         }
11     }
12     if (count == 0) return;
13     int length = value.length() + 2 * count;
14     int current = length -1;
15     char[] arrChars = new char[length];
16     for (int i = value.length() - 1; i >= 0; i--)
17     {
18         if (value.charAt(i) == ' ')
19         {
20             arrChars[current] = '0';
21             arrChars[current - 1] = '2';
22             arrChars[current - 2] = '%';
23             current = current - 3;
24         }
25         else
26         {
27             arrChars[current] = value.charAt(i);
28             current--;
29         }
30     }
31     
32     value = arrChars.toString();
33 }
  • 将N*N矩阵旋转90度
    思路：我们可以拿3*3矩阵做例子，在旋转完毕后，前后矩阵元素的关系如下：
    　　a[0][0]=>a[0][2]
    　　a[0][1]=>a[1][2]
    　　a[0][2]=>a[2][2]
    　　a[1][0]=>a[0][1]
    　　a[1][1]=>a[1][1]
    　　a[1][2]=>a[2][1]
    　　a[2][0]=>a[0][0]
    　　a[2][1]=>a[1][0]
    　　a[2][2]=>a[2][0]
    我们可以得到以下转换规则：a[x][y]=>a[y][n-x]。
    数据结构之字符串数据结构之字符串将矩阵旋转90度 
     1 public static void rotate(int[][] matrix)
 2 {
 3     if (matrix == null) return;
 4     int length = matrix.length - 1;
 5     for (int i = 0; i < length/2; i++)
 6     {
 7         for (int j = 0; j < length; j++)
 8         {
 9             int temp = matrix[i][j];
10             matrix[i][j] = matrix[j][length - i];
11             matrix[j][length - i] = matrix[length - i][length - j];
12             matrix[length - i][length - j] = matrix[length - j][i];
13             matrix[length - j][i] = temp;
14         }
15     }
16 }
  • 对N*M 矩阵进行处理，如果某个元素为0，则将该元素对应的行与列都设置为0
    思路：不能直接对矩阵进行设置0的处理，因为再设置0后，还需要进行遍历，这样可能导致最终矩阵所有元素都为0，需要先将为0的元素进行保存，然后再处理。
    数据结构之字符串数据结构之字符串对矩阵进行设0处理 
     1 public static void setZeros(int[][] matrix)
 2 {
 3     if (matrix == null) return;
 4     int[] arrX = new int[matrix.length];
 5     int[] arrY = new int[matrix[0].length];
 6     for(int i = 0; i < matrix.length; i++)
 7     {
 8         for (int j = 0; j < matrix[i].length; j++)
 9         {
10             if (matrix[i][j] == 0)
11             {
12                 arrX[i] = 1;
13                 arrY[j] = 1;
14             }
15         }
16     }
17     for (int i = 0; i < matrix.length; i++)
18     {
19         for (int j = 0; j < matrix[i].length; j++)
20         {
21             if (arrX[i] == 1 || arrY[j] == 1)
22             {
23                 matrix[i][j] = 0;
24             }
25         }
26     }
27 }
  • 判断一个字符串是否是另一个字符串经过翻转后得到的结果，例如cdab就是abcd进行翻转后的结果
    思路：将一个字符串拼接到自己后面，然后判断另一个字符串是否是新字符串的子串。
    数据结构之字符串数据结构之字符串判断两个字符串经过翻转后是否一致 
    1 public static boolean isRotation(String value1, String value2)
2 {
3     if (value1 == null || value2 == null || value1.length() != value2.length())
4         return false;
5     String newValue = value1 + value1;
6     return newValue.contains(value2);
7 }



    最后，欢迎大家提出更多和字符串相关的面试题目，我们可以一起讨论。

标签：

相关文章