所有的编程练习都在牛客网OJ提交,链接: https://www.nowcoder.com/ta/cracking-the-coding-interview
1.1 实现一个算法,确定一个字符串的所有字符是否全都不相同。假设不允许使用额外的数据结构,又该如何处理?
题解:应该先clarify上面的字符串是 ASCII 还是 unicode,假设是 ASCII,我们可以直接用256个字母表来统计。用个vector<int> st(256, 0)即可。time complexity: O(N)
1 class Different { 2 public: 3 bool checkDifferent(string iniString) { 4 if (iniString.size() > 256) { 5 return false; 6 } 7 vector<int> st(256, 0); 8 for (int i = 0; i < iniString.size(); ++i) { 9 if (st[iniString[i]]) {return false;} 10 st[iniString[i]] = 1; 11 } 12 return true; 13 } 14 };
还可以sort之后,前后相邻的字符比较。time complexity: O(nlogn)
1.2 用C++实现void reverse(char* str) 函数,即反转一个null结尾的字符串。
题解:直接2 pointers。
1 class Reverse { 2 public: 3 string reverseString(string iniString) { 4 int n = iniString.size(); 5 int i = 0, j = n-1; 6 while (i < j) { 7 swap(iniString[i++], iniString[j--]); 8 } 9 return iniString; 10 } 11 };
1.3 给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列之后,能够变成另外一个字符串。
题解:书上给的方法是用一个vector当作字母表,256个字符,统计频次,然后用第二个字符串去减掉。time complexty O(N+M)
也可以排序,或者用个map。
1 #include <unordered_map> 2 class Same { 3 public: 4 bool checkSam(string stringA, string stringB) { 5 const int n1 = stringA.size(), n2 = stringB.size(); 6 if (n1 != n2) {return false;} 7 unordered_map<char, int> mp1; 8 for (auto& c : stringA) { 9 mp1[c]++; 10 } 11 for (auto& c : stringB) { 12 if (mp1.find(c) == mp1.end() || mp1[c] == 0) { 13 return false; 14 } 15 mp1[c]--; 16 } 17 return true; 18 } 19 };
1.4 编写一个方法,将字符串中所有的空格都替换成”%20”。假设该字符串尾部有足够的空间存放新字符,并且知道字符串的真实长度。
题解:先统计空格数量,然后计算出新的总长度,然后从后往前一个一个移动处理。2 pass。
1 class Replacement { 2 public: 3 string replaceSpace(string iniString, int length) { 4 int cntSpace = 0; 5 for (auto c : iniString) { 6 if (c == ‘ ‘) { 7 cntSpace++; 8 } 9 } 10 int newLen = cntSpace * 2 + length; 11 string ret; 12 ret.resize(newLen); 13 int p2 = newLen - 1; 14 for (int i = length-1; i >= 0; --i) { 15 if (iniString[i] == ‘ ‘) { 16 ret[p2--] = ‘0‘; 17 ret[p2--] = ‘2‘; 18 ret[p2--] = ‘%‘; 19 } else { 20 ret[p2--] = iniString[i]; 21 } 22 } 23 return ret; 24 } 25 };
1.5 利用字符重复出现的次数,编写一个方法,实现基本的字符串压缩功能。比如,字符串“aabcccccaaa”会变成“a2b1c5a3”。若“压缩”后的字符串没有变短,则返回原先的字符串。
题解:2 pointers。time complexity: O(N), space complexity: O(N)
1 class Zipper { 2 public: 3 string zipString(string iniString) { 4 const int n = iniString.size(); 5 string ret; 6 if (n == 0) {return ret;} 7 int p1 = 0, p2= 0; 8 while (p2 < n) { 9 while (p2 < n && iniString[p2] == iniString[p1]) { 10 p2++; 11 } 12 int cnt = p2 - p1; 13 ret += string(1, iniString[p1]) + to_string(cnt); 14 p1 = p2; 15 } 16 return ret.size() < iniString.size() ? ret : iniString; 17 } 18 };
1.6 给定一幅由N*N矩阵表示的图像,其中每个像素的大小为4字节,编写一个方法,将图像旋转90度。不占用额外的内存空间能不能做到。48. Rotate Image
1.7 编写一个算法,若 M*N的矩阵中某个元素为0,则将其所在的行和列清零。73. Set Matrix Zeroes
1.8 假定有一个方法 isSubstring, 可检查一个单词是否为其他字符串的子串。给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成,要求只能调用一次isSubstring。(比如,waterbottle 是 erbottlewat旋转后的字符串)。
【读书笔记】Cracking the Code Interview(第五版中文版)
原文:https://www.cnblogs.com/zhangwanying/p/10371495.html