} } }

    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);

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



    原来,再大的房子,再大的床,没有相爱的人陪伴,都只是冰冷的物质。而如果身边有爱人陪伴,即使房子小,床小,也觉得无关紧要,因为这些物质上面有了爱的温度,成了家的元素。—— 何珞《婚房》#书摘#
    分享到: