Crack the Code Interview 第一章Strings & Arrays 解
添加时间:2013-7-9 点击量:
题目一:Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures？
若是只是要断定有没有反复的字符，应用一个bool的数组是一个很简单的规划：
bool isUniqueCharStr（string str）{
bool carray[256];
int size = str.size（）;
for（int i = 0; i < size; ++i）{
if（carray[ str[i] ]）{
return false;
}
carray[ str[i] ] = true;
}
}
return true;
}
该算法的时候错杂度和空间错杂度都是O（n）.推敲到题目中请求不应用额外的内存的话，可以以时候换取空间的体式格式，轮回嵌套。
bool isUniqueCharStr_slow（string str）{
int size = str.size（）;
for（int i = 0; i < size - 1; ++i）{
for（int j = i+1; j < size; ++j）{
if（str[j] == str[i]）{
return false;
}
}
}
return true;
}
这种算法是暴力式遍历，时候错杂度达到O（n^2），然则空间错杂度较低O（1）。
2. Write code to reverse a C-Style String. （C-String means that “abcd” is represented as five characters， including the null character.）
这个斗劲简单，首要查核字符串以\0为停止标记，简单写一下代码：
void reverse_c_str（char str）{
int len = strlen（str）;
int i， j;
char tmp;
for（i = 0， j = len-1; i < j; i++， j--）{
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
}
值得重视的是，这里strlen的时候错杂度为O（n），当然，这是不成避免的，全部算法时候O（n），空间O（1）。
3.Design an algorithm and write code to remove the duplicate characters in a stringwithout using any additional buffer. NOTE: One or two additional variables are fine.An extra copy of the array is not
题目难点在于要应用O（1）的空间错杂度。可以把反复的字符标识表记标帜成一个特别字符，在第二遍遍历时删除。
void remove_dup_char2（char str）{
if（ str == NULL） return;
int size = strlen（str）;
if（size <= 2） return;
char flg = str;
for（int i = 0; i < size-1; ++i）{
for（int j = i+1; j < size; ++j）{
if（ str[j] == str[i] ）{
str[j] = flg;
}
}
}
int idx = 1;
for（int i = 1; i < size; ++i）{
if（str[i] == flg）{
continue;
}
str[idx] = str[i];
idx++;
}
}
str[idx] = \0;
}
上方的算法时候错杂度O（n^2），空间错杂度O（1）。
4. Write a method to decide if two strings are anagrams or not.
题目请求断定两个string是不是“变位词”，所谓“变位词”就是指，两个单词中所包含的字母雷同只是次序不合。斗劲直观的办法是对每个string中字符呈现的个数进行统计，然后再进行斗劲。
bool is_anagrams（string str1， string str2）{
int count_char[256];
int size = str1.size（）;
if（str2.size（） != size）{
return false;
}
for（int i = 0; i < size; ++i）{
count_char[ str1[i] ]++;
}
for（int i = 0; i < size; ++i）{
if（count_char[ str1[i] ] == 0）{
return false;
}
}
return true;
}
算法时候错杂度O（n），空间错杂度O（n）。须要重视的是：连个string有可能是多长的字符串？ 如许可以按照字符串的范围拔取count_char的类型。
5. Write a method to replace all spaces in a string with ‘％20’.
这个题目标首要难点在于，转换之后的字符串要比转换之前长很多，并且，书上给出的答案相当诡异，下面是书本上给出的解答：
public static void ReplaceFun（char[] str， int length） {
int spaceCount = 0， newLength， i = 0;
for （i = 0; i < length; i++） {
if （str[i] == ‘ ‘） {
spaceCount++;
}
}
newLength = length + spaceCount 2;
str[newLength] = ‘\0’;
for （i = length - 1; i >= 0; i--） {
if （str[i] == ‘ ‘） {
str[newLength - 1] = ‘0’;
str[newLength - 2] = ‘2’;
str[newLength - 3] = ‘％’;
newLength = newLength - 3;
}
str[newLength - 1] = str[i];
newLength = newLength - 1;
}
}
}
办法本身很轻易懂得，然则，若是str后面的内存是已应用的，那么会造成内存错误。
6 Given an image represented by an NxN matrix， where each pixel in the image is 4 bytes， write a method to rotate the image by 90 degrees. Can you do this in place？
简单懂得为应用O（1）的帮助空间把一个NxN的int类型的矩阵扭转90度。对于这个题，只要找到扭转后的矩阵和扭转前矩阵的坐标关系就okay了。这个并不难，只请求出矩阵的转秩矩阵，然后在对每行（顺时针扭转）或者每列（逆时针扭转）逆序就行了。
void rotate_matrix（int a[10][10]）{
if（a == NULL） return;
int tmp = 0;
for（int i = 0; i < 10; ++i）{
for（int j = 0; j < 10; ++j）{
tmp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = tmp;
}
}
int j，k;
//假设顺时针
for（int i = 0; i < 10; i++）{
for（j = 0， k = 9; j < k; ++j， --k）{
tmp = a[i][j];
a[i][j] = a[i][k];
a[i][k] = tmp;
}
}
}
时候错杂度O（n^2），空间错杂度O（1）。
原书中给出的解答是如许的：
public static void rotate（int[][] matrix， int n） {
for （int layer = 0; layer < n / 2; ++layer） {
int first = layer;
int last = n - 1 - layer;
for（int i = first; i < last; ++i） {
int offset = i - first;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[last-offset][first];
// bottom -> left
matrix[last-offset][first] = matrix[last][last - offset];
// right -> bottom
matrix[last][last - offset] = matrix[i][last];
// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}
8.Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings， s1 and s2， write code to check if s2 is a rotation of s1 using only one call to isSubstring （i.e.， “waterbottle” is a rotation of “erbottlewat”）.
《编程之美》上的老题目了：
char a[] = AABCD;
char b[] = CDAA;
int i， j， res;
char tmp;
int len = strlen（a）;
for（i = 0; i < len; i++）{
tmp = a[0];
for（j = 0; j < len-1; j++）{
a[j] = a[j+1];
}
a[len-1] = tmp;
if（strstr（a，b））{
printf（OK）;
return 0;
}
}
printf（NOT OK）;
这一章的例子都不难，然则要给出来一个斗劲完美的解答还是须要很多思虑。要写出“正确”的代码就更须要细心。
原来，再大的房子，再大的床，没有相爱的人陪伴，都只是冰冷的物质。而如果身边有爱人陪伴，即使房子小，床小，也觉得无关紧要，因为这些物质上面有了爱的温度，成了家的元素。—— 何珞《婚房》#书摘#
题目一:Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures？
若是只是要断定有没有反复的字符，应用一个bool的数组是一个很简单的规划：
bool isUniqueCharStr（string str）{
bool carray[256];
int size = str.size（）;
for（int i = 0; i < size; ++i）{
if（carray[ str[i] ]）{
return false;
}
carray[ str[i] ] = true;
}
}
return true;
}
该算法的时候错杂度和空间错杂度都是O（n）.推敲到题目中请求不应用额外的内存的话，可以以时候换取空间的体式格式，轮回嵌套。
bool isUniqueCharStr_slow（string str）{
int size = str.size（）;
for（int i = 0; i < size - 1; ++i）{
for（int j = i+1; j < size; ++j）{
if（str[j] == str[i]）{
return false;
}
}
}
return true;
}
这种算法是暴力式遍历，时候错杂度达到O（n^2），然则空间错杂度较低O（1）。
2. Write code to reverse a C-Style String. （C-String means that “abcd” is represented as five characters， including the null character.）
这个斗劲简单，首要查核字符串以\0为停止标记，简单写一下代码：
void reverse_c_str（char str）{
int len = strlen（str）;
int i， j;
char tmp;
for（i = 0， j = len-1; i < j; i++， j--）{
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
}
值得重视的是，这里strlen的时候错杂度为O（n），当然，这是不成避免的，全部算法时候O（n），空间O（1）。
3.Design an algorithm and write code to remove the duplicate characters in a stringwithout using any additional buffer. NOTE: One or two additional variables are fine.An extra copy of the array is not
题目难点在于要应用O（1）的空间错杂度。可以把反复的字符标识表记标帜成一个特别字符，在第二遍遍历时删除。
void remove_dup_char2（char str）{
if（ str == NULL） return;
int size = strlen（str）;
if（size <= 2） return;
char flg = str;
for（int i = 0; i < size-1; ++i）{
for（int j = i+1; j < size; ++j）{
if（ str[j] == str[i] ）{
str[j] = flg;
}
}
}
int idx = 1;
for（int i = 1; i < size; ++i）{
if（str[i] == flg）{
continue;
}
str[idx] = str[i];
idx++;
}
}
str[idx] = \0;
}
上方的算法时候错杂度O（n^2），空间错杂度O（1）。
4. Write a method to decide if two strings are anagrams or not.
题目请求断定两个string是不是“变位词”，所谓“变位词”就是指，两个单词中所包含的字母雷同只是次序不合。斗劲直观的办法是对每个string中字符呈现的个数进行统计，然后再进行斗劲。
bool is_anagrams（string str1， string str2）{
int count_char[256];
int size = str1.size（）;
if（str2.size（） != size）{
return false;
}
for（int i = 0; i < size; ++i）{
count_char[ str1[i] ]++;
}
for（int i = 0; i < size; ++i）{
if（count_char[ str1[i] ] == 0）{
return false;
}
}
return true;
}
算法时候错杂度O（n），空间错杂度O（n）。须要重视的是：连个string有可能是多长的字符串？ 如许可以按照字符串的范围拔取count_char的类型。
5. Write a method to replace all spaces in a string with ‘％20’.
这个题目标首要难点在于，转换之后的字符串要比转换之前长很多，并且，书上给出的答案相当诡异，下面是书本上给出的解答：
public static void ReplaceFun（char[] str， int length） {
int spaceCount = 0， newLength， i = 0;
for （i = 0; i < length; i++） {
if （str[i] == ‘ ‘） {
spaceCount++;
}
}
newLength = length + spaceCount 2;
str[newLength] = ‘\0’;
for （i = length - 1; i >= 0; i--） {
if （str[i] == ‘ ‘） {
str[newLength - 1] = ‘0’;
str[newLength - 2] = ‘2’;
str[newLength - 3] = ‘％’;
newLength = newLength - 3;
}
str[newLength - 1] = str[i];
newLength = newLength - 1;
}
}
}
办法本身很轻易懂得，然则，若是str后面的内存是已应用的，那么会造成内存错误。
6 Given an image represented by an NxN matrix， where each pixel in the image is 4 bytes， write a method to rotate the image by 90 degrees. Can you do this in place？
简单懂得为应用O（1）的帮助空间把一个NxN的int类型的矩阵扭转90度。对于这个题，只要找到扭转后的矩阵和扭转前矩阵的坐标关系就okay了。这个并不难，只请求出矩阵的转秩矩阵，然后在对每行（顺时针扭转）或者每列（逆时针扭转）逆序就行了。
void rotate_matrix（int a[10][10]）{
if（a == NULL） return;
int tmp = 0;
for（int i = 0; i < 10; ++i）{
for（int j = 0; j < 10; ++j）{
tmp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = tmp;
}
}
int j，k;
//假设顺时针
for（int i = 0; i < 10; i++）{
for（j = 0， k = 9; j < k; ++j， --k）{
tmp = a[i][j];
a[i][j] = a[i][k];
a[i][k] = tmp;
}
}
}
时候错杂度O（n^2），空间错杂度O（1）。
原书中给出的解答是如许的：
public static void rotate（int[][] matrix， int n） {
for （int layer = 0; layer < n / 2; ++layer） {
int first = layer;
int last = n - 1 - layer;
for（int i = first; i < last; ++i） {
int offset = i - first;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[last-offset][first];
// bottom -> left
matrix[last-offset][first] = matrix[last][last - offset];
// right -> bottom
matrix[last][last - offset] = matrix[i][last];
// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}
8.Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings， s1 and s2， write code to check if s2 is a rotation of s1 using only one call to isSubstring （i.e.， “waterbottle” is a rotation of “erbottlewat”）.
《编程之美》上的老题目了：
char a[] = AABCD;
char b[] = CDAA;
int i， j， res;
char tmp;
int len = strlen（a）;
for（i = 0; i < len; i++）{
tmp = a[0];
for（j = 0; j < len-1; j++）{
a[j] = a[j+1];
}
a[len-1] = tmp;
if（strstr（a，b））{
printf（OK）;
return 0;
}
}
printf（NOT OK）;
这一章的例子都不难，然则要给出来一个斗劲完美的解答还是须要很多思虑。要写出“正确”的代码就更须要细心。
原来，再大的房子，再大的床，没有相爱的人陪伴，都只是冰冷的物质。而如果身边有爱人陪伴，即使房子小，床小，也觉得无关紧要，因为这些物质上面有了爱的温度，成了家的元素。—— 何珞《婚房》#书摘#
