【Cracking the Code Interview(5th edition)】一、数组与字符串(C++)

1.1 实现一个算法，确定一个字符串的所有字符是否全都不同。不允许使用额外的数据结构。

解答：这里假定字符集为ASCII码，可以与面试官沟通确认字符串使用的字符集。由于字符集是有限的，建立一个数组模拟的Hash表记录每个字符是否出现，线性扫描一次字符串即可，复杂度O(len(s)).如果字符集较大，需要考虑空间开销，则可以用bitset来实现。

 1 bool isUnique(string s) {
 2 　　bool record[256];
 3 　　memset(record, 0, sizeof(record));
 4 　　size_t size = s.size();
 5 　　for(size_t i = 0; i < size; ++i) {
 6 　　　　if (record[s[i]] == true)
 7 　　　　　　return false;
 8 　　　　else
 9 　　　　　　record[s[i]] = false;
10 　　}
11 　　return true;
12 }

可以加一个剪枝：如果字符串的大小大于字符集的大小了，那么该字符串肯定是存在重复字符的。

 1 bool isUnique(string s) {
 2     size_t size = s.size();
 3     if (size > 256) 
 4             return false;
 5 　　 bool record[256];
 6 　　 memset(record, 0, sizeof(record));
 7 　　 for(size_t i = 0; i < size; ++i) {
 8 　　　　 if (record[s[i]] == true)
 9 　　　　　 　return false;
10 　　　　 else
11 　　　　　 　record[s[i]] = false;
12 　　 }
13 　　 return true;
14 }

补充：假设对空间开销非常严苛，可以考虑先对字符串中的字符排序，然后进行一次线性扫描；如果还不允许改变字符串原有的内容，那么就只能暴力搜查了吧。

1.2 用C或C++实现void reverse(char * str)函数，即反转一个‘’结尾的字符串。

解答：

 1 void reverse(char *str) {
 2     if (str == nullptr) return;
 3     size_t length = strlen(str);
 4     for (size_t i = 0; i < length / 2; ++i) {
 5         // swap str[i] and str[length - 1 - i];
 6         char temp = str[i];
 7         str[i] = str[length - 1 - i];
 8         str[length - 1 - i] = temp;
 9     }
10 }

1.3 给定两个字符串，请写程序，确定其中一个字符串的重新排列后，能否变成另一个字符串。

解答：这里同样假定字符集是ASCII码，假定判断字符串相等时，大小写是区分的。在开始时通过检查两个字符串长度是否相等进行剪枝，然后，用一个数组记录第一个字符串中每个字符出现的次数，然后判断第二个字符串中每个字符出现的次数是否与第一个字符串相等即可。

 1 bool canConvert(string s1, string s2) {
 2     if (s1.size() != s2.size())
 3         return false;
 4     int record[256];
 5     memset(record, 0, sizeof(record));
 6     for (auto &c : s1) {
 7         ++record[c];
 8     }
 9     for (auto &c : s2) {
10         if (--record[c] < 0)
11             return false;
12     }
13     return true;
14 }

1.4 编写一个方法，将字符串中的空格全部替换为"%20".假定字符串尾部有足够的空间存放新增字符，并且知道字符串的真实长度。示例：

输入: "Mr John Smith"

输出: "Mr%20John%20Smith"

解答：需要改变字符串长度的问题，通常从尾部开始处理比较高效，因为可以避免字符的重复移动。

 1 void replaceSpace(char str[], int length) {
 2     //length为字符串实际长度，不包括结尾的''
 3     if(length <= 0) return;
 4     int space_cnt = 0;
 5     for (int i = 0; i < length; ++i) {
 6         if (str[i] == ' ') {
 7             ++space_cnt;
 8         }
 9     }
10     if (space_cnt > 0) {
11         int j = length + space_cnt * 2;
12         str[j] = '';
13         for (int i = length - 1; i >= 0; --i) {
14             if (str[i] == ' ') {
15                 //用"%20"替换空格
16                 str[--j] = '0';
17                 str[--j] = '2';
18                 str[--j] = '%';
19             } else {
20                 str[--j] = str[i];
21             }
22         }
23     }      
24 }

1.5 利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如：字符串"aabbcccccaaa"会变为"a2b1c5a3".若压缩后的字符串没有变短，则返回原先的字符串。

解答：重复长度编码(run length encoding, RLE).按照题述模拟即可，但要注意细节实现。(其中to_string(int)函数为C++11新增)

 1 string compress(string s) {
 2     string ret;
 3     int length = s.size();
 4     if (length > 0) {
 5         char buf = s[0];
 6         int cnt = 1;
 7         for (size_t i = 1; i < length; ++i) {
 8             if (s[i] != buf) {
 9                 ret = ret + buf + to_string(cnt);
10                 buf = s[i];
11                 cnt = 1;
12             }
13             else {
14                 ++cnt;
15             }
16         }
17         //开始忘记了加这一句，导致最后一组计数结果没有加入ret
18         ret = ret + buf + to_string(cnt);
19     }
20     //注意这里要加等号
21     return ret.size() >= s.size() ? s : ret;
22 }

1.6 给定一副NxN矩阵表示的图像，其中每个图像的大小为4字节，编写一个方法，将图像旋转90°。不占用额外空间能否做到？

解答：常见的问题了，有很多旋转的方式，这里就用最常用的由外向内逐层旋转的方法吧。

这里需要特别注意旋转过程中的循环停止条件和对应的坐标，不小心非常容易出错，用含义清晰的变量名有利于理清思路，避免错误。

 1 void rotate(int **matrix, int n) {
 2     for (int layer = 0; layer < n / 2; ++layer) {
 3         int last = n - 1 - layer;
 4         for (int j = layer; j < last; ++j) {
 5             int offset = j - layer;
 6             //保存上
 7             int temp = matrix[layer][j];
 8             //左->上
 9             matrix[layer][j] = matrix[last - offset][layer];
10             //下->左
11             matrix[last - offset][layer] = matrix[last][last - offset];
12             //右->下
13             matrix[last][last - offset] = matrix[j][last];
14             //上->右
15             matrix[j][last] = temp;
16         }
17     }
18 }

另外关于参数传递的问题，这里需要的是一个可变长的二维数组，C++中我们只能通过传递一个二级指针来实现，这样在函数调用的时候就需要一些处理了：

1 int main(void) {
2     int arr1[] = { 1, 2, 3, 4 };
3     int arr2[] = { 5, 6, 7, 8 };
4     int arr3[] = { 9, 10, 11, 12 };
5     int arr4[] = { 13, 14, 15, 16 };
6     int *matrix[4] = { arr1, arr2, arr3, arr4 };
7     rotate(matrix, 4);
8     return 0;
9 }

C++中不能直接给函数传递二维数组的原因是：“数组名被改写成一个指针参数”规则并不是递归定义的。数组的数组会被改写成“数组的指针”，而不是“指针的指针”。

1.7 编写一个算法，若MxN的矩阵中某个元素为0，则将其所在的行与列都清零。

解答：LeetCode上也有这道题。可以用一个长度为M的数组和一个长度为N的数组分别记录有0的行和列。此外也可以利用矩阵本身的存储空间，用其中的一行一列来记录该结果。以下代码基于后一种方法。

 1 void setZero(int **matrix, int m, int n) {
 2     bool r1_zero = false, c1_zero = false;    //两个变量记录第一行和第一列是否含0
 3     //检查第一行
 4     for (int j = 0; j < n; ++j) {
 5         if (matrix[0][j] == 0) {
 6             r1_zero = true;
 7             break;
 8         }
 9     }
10     //检查第一列
11     for (int i = 0; i < m; ++i) {
12         if (matrix[i][0] == 0) {
13             c1_zero = true;
14             break;
15         }
16     }
17     //检查剩余元素
18     for (int i = 1; i < m; ++i) {
19         for (int j = 1; j < n; ++j) {
20             if (matrix[i][j] == 0) {
21                 //将元素是否为0记录到第一行和第一列
22                 matrix[0][j] = matrix[i][0] = 0;
23             }
24         }
25     }
26     //矩阵按规则置0
27     for (int i = 1; i < m; ++i) {
28         if (matrix[i][0] == 0) {
29             for (int j = 1; j < n; ++j) {
30                 matrix[i][j] = 0;
31             }
32         }
33     }
34     for (int j = 1; j < n; ++j) {
35         if (matrix[0][j] == 0) {
36             for (int i = 0; i < m; ++i) {
37                 matrix[i][j] = 0;
38             }
39         }
40     }
41     if (r1_zero) {
42         for (int j = 0; j < n; ++j) {
43             matrix[0][j] = 0;
44         }
45     }
46     if (c1_zero) {
47         for (int i = 0; i < m; ++i) {
48             matrix[i][0] = 0;
49         }
50     }
51 }

1.8 假定有一个方法isSubstring,可检查一个单词是否为其他字符串的子串。给定两个字符串s1和s2.请编写代码检查s2是否为s1旋转而成，要求只能调用一次isSubstring.(比如：waterbottle是erbottlewat旋转后的字符串)

解答：s2是s1经过一次旋转得到的，那么s1+s1拼成的字符一定把s2包含在其中。可以先判断两个字符串的长度是否相等。

1 bool isSubstring(string s1, string s2);   //s2是s1的子串是为真   
2 
3 bool isRotation(string s1, string s2) {
4     if (s1.size() == s2.size() && isSubstring(s1 + s1, s2) {
5         return true;
6     } else {
7         return false;
8     }
9 }

补充：第四版中的习题

1.3 设计算法并编码实现：在不使用额外缓冲区的情况下去除字符串中的重复字符。设计一些测试用例。

解答：如果允许开辟与字符串长度无关大小的数组，则可以用一个记录字符是否出现过的数组来实现。

 1 void removeDuplicate(char str[]) {
 2     int length = strlen(str);
 3     if (length > 1) {
 4         bool flag[256];
 5         memset(flag, 0, sizeof(flag));
 6         for (int i = 0, j = 0; i < length; ++i) {
 7             if (flag[str[i]] == false) {
 8                 flag[str[i]] = true;
 9                 str[j++] = str[i];
10             }
11         }
12         //不要忘记加上结束标志
13         str[length] = ''; 
14     }
15 }

如果不允许使用额外的数组来记录字符是否出现，那么就只有暴力搜查了。

 1 void removeDuplicate(char str[]) {
 2     int length = strlen(str);
 3     if (length > 1) {
 4         int k = 0;
 5         for (int i = 0; i < length; ++i) {
 6             bool found = false;
 7             for (int j = 0; j < k; ++j) {
 8                 if (str[i] == str[j]) {
 9                     found = true;
10                     break;
11                 }
12             }
13             if (!found) {
14                 str[k++] = str[i];
15             }
16         }
17         //不要忘记结束标记
18         str[k] = '';
19     }
20 }

测试用例如："", "a", "aaa", "abab", "aabb", "abbbb", "abcd"...