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);
这一章的例子都不难,然则要给出来一个斗劲完美的解答还是须要很多思虑。要写出“正确”的代码就更须要细心。
原来,再大的房子,再大的床,没有相爱的人陪伴,都只是冰冷的物质。而如果身边有爱人陪伴,即使房子小,床小,也觉得无关紧要,因为这些物质上面有了爱的温度,成了家的元素。—— 何珞《婚房》#书摘#