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

灰太狼 2022-10-02 13:56 20阅读 0赞

## 问题一: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");

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