第二章 面试需要的基础知识

1. 数组

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

• 排序后扫描复杂度O(nlogn)

• 哈希表，空间复杂度O(n)，时间复杂度O(n)

  原地哈希：有的元素多次重复，有的元素确实，使用原地哈希，其中某个正确元素一定在合适位置，那么遍历时每次比较当前元素是否与 合适位置重复，如果没有重复，就把它放到合适位置。

  时间复杂度O(n)，空间复杂度O(1)

    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0;i < nums.size(); ++i){//从头到尾扫描
            if(nums[i] == i) continue;//如果nums[i]在合适的位置，继续向前扫描
            else{//如果不在合适位置
                if(nums[i] == nums[ nums[i] ]) return nums[i];//比较当前元素是否与合适位置的元素重复
                else swap(nums[i],nums[nums[i]]);//如果不重复，就把当前元素放到合适位置
            }
        }
        return 0;
    }

变形题：不修改数组找出重复数字

1. 创建一个长度为n+1的辅助数组，逐一把原数组的元素m复制到新数组对应下标为m的位置，如果该位置已经被修改，那么该数字重复。空间复杂度O(n)。
2. 二分法：以0 ~ n-1的中点m为界，小于m的数如果超过了m个，则说明前m个数中有重复的，相反则证明后m个数有重复。再以0~m-1为界，继续缩小范围，继续缩小范围，则能找到该重复的数。空间复杂度为O(1)，时间复杂度为O(nlogn)。以时间换空间。

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。给定 target = 20，返回 false。

**解决一个复杂问题，通过分析简单具体的例子，试图寻找普遍规律。**发现从右上角开始分析作为突破口。

//从右上角遍历，比target小，就向下走，比target大，就往左走
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        int n = matrix.size(),m = matrix[0].size();
        int i = 0,j = m-1;
        while(i < n && j >= 0){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] < target){
                ++i;
            }else{
                --j;
            }
        }
        return false;
    }

2. 字符串

每个字符串都以字符‘\0’结尾，所以要注意越界。

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

输入：s = "We are happy."
输出："We%20are%20happy."

• 第一种：在原来字符的基础上进行修改，那么就有可能覆盖修改该字符后面的内容。所以需要把空格后面的所有字符都后移2字节。因为每个空格后面的所有字符都要移动，所以时间复杂度是O(n^2)
• 第二种：创建一个新的足够多的字符串，在新的字符串上进行复制。建立双指针，从后往前，旧指针指向旧字符串末尾，新指针指向新字符串末尾，碰到空格，旧指针-1，新指针-3；碰到字符，将对应字符复制到新字符串处。

是否高度警惕内存覆盖

    string replaceSpace(string str) {
        if(str.empty()) return "";
        int count = 0;//统计空格的个数
        for(auto & s:str){
            if(s == ' ') ++count;
        }
        int last = str.size()-1,newlast = str.size()+2*count-1;//last指向原数组末尾，newlast指向新数组末尾
        stri