现在的位置: 首页 > 综合 > 正文

Crack The Code Interview第一章Arrays & Strings读书笔记

2018年02月17日 ⁄ 综合 ⁄ 共 3986字 ⁄ 字号 评论关闭

问题一: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;
    } else {
      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;
		} else {
			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 anagram(string str1, string str2)
{
    int letters[256];
    int num_chars = 0;
    int num_completed = 0;

    for(int i = 0; i < 256; i++)
    {
        letters[i] = 0;
    }

    int size1 = str1.size();
    int size2 = str2.size();

    for(int i = 0; i < size1; i++)
    {
        if(letters[ str1[i] ] == 0)
            num_chars++;
        letters[ str1[i] ]++;
    }

    for(int i = 0; i < size1; i++)
    {
        if(letters[ str2[i] ] == 0)
            return false;
        letters[ str2[i] ] --;
        if(letters[ str2[i] ] == 0)
        {
            num_completed++;
            if(num_chars == num_completed)
            {
                return i == size1-1;
            }
        }
    }
}

算法时间复杂度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;
    } else {
      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");

这一章的例子都不难,但是要给出来一个比较完美的解答还是需要很多思考。要写出“正确”的代码就更需要细心。

 

 

抱歉!评论已关闭.