2020-07-07 刷题5 二叉树，逆序对，数组

63 数组中的逆序对

经典归并排序，divide+merge。在merge时，如果左半边某个元素（i）大于右半边的某个元素，那么左半边后面的元素都大于右半边该元素，逆序对增加mid-i。

class Solution {
public:
    int Divide_Merge(vector<int>& nums, int left, int right){
        if(left + 1 >= right)
            return 0;
        // divide
        int mid = left + (right - left) / 2;
        int left_pair = Divide_Merge(nums, left, mid);
        int right_pair = Divide_Merge(nums, mid, right);
        // merge
        vector<int> tmp;
        int i = left, j = mid, cur_pair = left_pair + right_pair;
        while(i < mid && j < right){
            if(nums[i] <= nums[j]){
                tmp.push_back(nums[i]);
                i++;
            }
            else{
                tmp.push_back(nums[j]);
                cur_pair += (mid - i);
                j++;
            }
        }
        while(i < mid)
            tmp.push_back(nums[i++]);
        while(j < right)
            tmp.push_back(nums[j++]);
        for(int k = 0; k < tmp.size(); k++)
            nums[left + k] = tmp[k];
        return cur_pair;
    }
    int reversePairs(vector<int>& nums) {
        int pairs = Divide_Merge(nums, 0, nums.size());
        return pairs;
    }
};

---

64 求1+2+...+n

不能用if语句，但是可以用？来判断ns是否为0

class Solution {
public:
    int sumNums(int n) {
        return n ? n + sumNums(n - 1) : 0;
    }
};

---

68 二叉搜索树的最近公共节点

因为是二叉搜索树，所以可以通过pq以及root的取值判断，如果pq都小于root，那么最近公共节点在root左子树中；都大于，在右子树中；一个小于一个大于，root就是最近公共节点。如果是面试的时候，需要多考虑一些边界条件，力扣测试数据都没有考虑边界条件。。。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 这里第一需要判断pq以及root是否空
        if((p -> val < root -> val) && (q -> val < root -> val))
            return lowestCommonAncestor(root -> left, p, q);
        if((p -> val > root -> val) && (q -> val > root -> val))
            return lowestCommonAncestor(root -> right, p, q);
        return root;
    }
};

---

68-II 二叉树的最近公共祖先

上一题的升级版，二叉搜索树改成了普通二叉树。这种做法其实跟前面一样，如果左右返回都不为空，说明p和q分别在左右子树中，最近公共祖先就是root；如果其中一个返回为空，另一个不为空，那么pq就在不为空的子树中。对于其中一个是另一个祖先的情况，也可以包含进来，因为只要访问到其中一个节点就不会再深入了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q)
            return root;
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);
        if(left && right)
            return root;
        if(left == nullptr)
            return right;
        return left;
    }
};

---

05 替换空格

原地替换。这个题目如果只是额外分配空间来做，那就没啥意思了。首先需要统计出空格的数目，将字符串后面扩充2*空格数。然后设置ij两个指针，分别指向原字符串末尾和扩充后的字符串末尾，双指针扫描替换，直到两个指针重合，此时前面就没有空格了，也不需要再替换了。

class Solution {
public:
    string replaceSpace(string s) {
        int space_cnt = 0, ori_len = s.size();
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' ')
                space_cnt++;
        }
        for(int i = 0; i < space_cnt; i++)
            s += "  ";
        int i = ori_len - 1, j = s.size() - 1;
        while(i < j){
            if(s[i] != ' ')
                s[j--] = s[i--];
            else{
                s[j--] = '0';
                s[j--] = '2';
                s[j--] = '%';
                i--;
            }
        }
        return s;
    }
};

---

3 数组中重复的数字

第一种时间O(n)且空间O(1)的解法是原地排序，将每个元素放到自己指定的地方，如果同一个位置出现第二个元素，那么该元素就是重复的。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            int j = nums[i];
            while(i != j){
                int tmp = nums[j];
                if(nums[j] == j)
                    return nums[j];
                nums[j] = j;
                j = tmp;
            }
            nums[i] = j;
        }
        return -1;
    }
};

二分解法，1～n-1分成两个区间1～m，m～n-1分别统计两个区间的元素个数，如果左边区间元素多于m，重复元素就在左边区间中；否则在右边区间中，不断缩小区间。但是本题元素范围是0～n-1，所以这种解法不能用，对于[0,0,1,2,4,5,6,7,8,9]是找不到正确解的

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int left = 1, right = nums.size(), left_cnt = 0, right_cnt = 0;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            left_cnt = 0;
            right_cnt = 0;
            for(int i = 0; i < nums.size(); i++){
                if((nums[i] >= left) && (nums[i] < mid))
                    left_cnt++;
                else if((nums[i] >= mid) && (nums[i] < right))
                    right_cnt++;
            }
            if(left_cnt > (mid - left))
                right = mid;
            else
                left = mid;
        }
        return left;
    }
};