题目一: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 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;

    } 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）;

这一章的例子都不难，然则要给出来一个斗劲完美的解答还是须要很多思虑。要写出“正确”的代码就更须要细心。