算法学习记录(一)

前言
留一小段给《算法》
去年曾花了近两个月学习《算法》红皮书，完成了有一大半，记录都存在本本上，如今忘记也有大半，还好部分有些印象；
这本书比较基础，对于每一道算法学习过程，异常的详尽，感慨作者严谨求实的探究精神，科学家的魅力总是能在某一刹那征服你，是算法入门的超级好书。

---

半年过去，算法水平并没有本质的提高，还是太缺练了，有什么好办法吗？
自己找题练习，不求快，务必找出问题的本质，提升编程思维能力。
听闻《剑指offer》算法题非常实用，面试命中率70%，粗看了几道感觉确实挺经典的，用这本书来再次学习算法，希望能提升一点儿应试能力。
<刷LeetCode也可以，这本书讲得更详细，最重要得是坚持>
时间安排：
争取每天一题，总共五十来道题，不到两个月就差不多了
题目记录：

---

1. 找出有序二维数组(从上到下有序，从左到右有序)中指定位置的数字
   思路：每次从数组的右上角(或者左下角)取值，这样一次就可以过滤掉一行；因为数组有序，所以若a比右上角值小，则排除右上角所在列；若a比右上角值大，则排除右上角所在行；以此类推，直到找到该值，或者数组遍历完毕
   分析：二维数组只需要一次遍历，时间复杂度o(n)
   核心代码：

    int rows = metrix.count;
    int columns = [metrix.firstObject count];
    int row = 0;
    int column = columns - 1;
    while (row < rows && column > 0) {
        int tempValue = [[metrix[row] objectAtIndex:column] intValue];
        if(tempValue == value){
            NSLog(@"value %d:row=%d,column=%d",value,row,column);
            return @[@(row),@(column)];
        }else if(value < tempValue){
            column--;
        }else{
            row++;
        }
    }
    
    return nil;

数组问题基本都是遍历相关，平时习惯了锚点在左上角，对于有序数组，学会从尾部考虑问题，好多问题可能就迎刃而解

2. 用%20替换字符串中的空格
   思路：
   解法一：由于字符串中的空格占一个字符，%20占3个字符，若从前往后遍历，遇到一个空格做替换，每次替换空格后边的字符全部都要后移n次，n个空格，时间复杂度为o(n2)
   解法二：可以考虑从后往前遍历，先找出空格的个数，那么新的字符串长度就是原长度n+2空格个数；那么可以用两个指针p1,p2，第一个指向原字符串末尾，第二个指向新字符串末尾，开始遍历，将p1指向的内容copy到p2指向的位置，若遇到一个空格，将%20拷贝到p2,并将p2向前移动3个位置；遇到第二个也是同样操作；当p1,*p2指向相同时，则处理完毕。

    int newStrLength = strLength + 2 * blankNum;
    while (strLength > 0 && newStrLength > strLength) {
        // 如果不是空格
        strLength--;
        newStrLength--;
        if(string[strLength] !=' '){
            string[newStrLength] = string[strLength];
        }else{
            string[newStrLength--] = '0';
            string[newStrLength--] = '2';
            string[newStrLength] = '%';
        }
    }

字符串也可以理解成字符数组，这个其实也是倒序遍历的思想，要注意的是字符串边界问题：

1. NULL/空字符串
2. 非法字符等

2.1 此题扩展
合并两个有序数组，其中一个数组较大
分析：若两个数组都从头到尾遍历的话，每遍历一次，指定位置后边的数字都要移动n次，n次遍历时间复杂度为o(n^2)，更好的思路依然是从数组尾部遍历，用两个指针i,j分别指向两个数组a[],b[]的尾部，第一次若a[i] < b[j]，说明b[j]是合并之后的最大值，应该放在合并后数组的i+j位置，然后j向前移动一位，若a[i] > b[j]，则a[i]应该是最大值，放在totalLength-1位置，i指针向前移动一位；如此比较直到，i==0,j==0，则合并完毕，由于每次遍历，只移动数组中的一个元素，没有重复移动，所以n次遍历，时间复杂度为o(n)。
代码如下：

void mergeTwoSortArray(int a1[], int length1, int a2[], int length2){
    int totalLength = length1 + length2;
    int temp = totalLength;
    while (length1 >= 0 && length2 >= 0) {
        if(a1[length1-1] > a2[length2-1]){
            a1[--totalLength] = a1[--length1];
        }else if(a1[length1 - 1] < a2[length2 - 1]){
            a1[--totalLength] = a2[--length2];
        }else if(a1[length1 - 1] == a2[length2 - 1]){
            a1[--totalLength] = a1[--length1];
            length2--;
            totalLength--;//此时需要多减1
        }
    }
}