剑指 Offer 07. 重建二叉树(重点)

有一个重要的条件就是需要没有重复节点，不然的话就难以构造
根据前序遍历和中序遍历的结果来反推完整的二叉树。要点是通过前序遍历的第一个节点就是根节点，然后再中序遍历里面通过哈希表来查找所在的地方，中序遍历的特点可以帮助获得左右子树的数量。然后进行递归来构建新的子树。

  1. class Solution {
  2. private:
  3.     unordered_map<int, int> index;
  5. public:
  6.     TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
  7.         if (preorder_left > preorder_right) {
  8.             return nullptr;
  9.         }
  11.         // 前序遍历中的第一个节点就是根节点
  12.         int preorder_root = preorder_left;
  13.         // 在中序遍历中定位根节点
  14.         int inorder_root = index[preorder[preorder_root]];
  15.         // 先把根节点建立出来
  16.         TreeNode* root = new TreeNode(preorder[preorder_root]);
  17.         // 得到左子树中的节点数目
  18.         int size_left_subtree = inorder_root - inorder_left;
  19.         // 递归地构造左子树，并连接到根节点
  20.         // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
  21.         root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);//此处都减去了根节点
  22.         // 递归地构造右子树，并连接到根节点
  23.         // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
  24.         root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);//这里代表的意思是区间。
  25.         return root;
  26.     }
  28.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  29.         int n = preorder.size();
  30.         // 构造哈希映射，帮助我们快速定位根节点
  31.         for (int i = 0; i < n; ++i) {
  32.             index[inorder[i]] = i;
  33.         }
  34.         return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);k//这里的是子树的左右边界
  35.     }
  36. };

剑指 Offer 16. 数值的整数次方（重点）

这一题思想非常巧妙，值得反复看。分治的想法就是把大问题转换为小问题，「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x^{64}_x_64，我们可以按照：
image.png
再举一个例子，如果我们要计算 x^{77}_x_77，我们可以按照：
image.png
image.png

  1. class Solution {
  2. public:
  3.     double quickMul(double x, long long N) {
  4.         if (N == 0) {
  5.             return 1.0;
  6.         }
  7.         double y = quickMul(x, N / 2);
  8.         return N % 2 == 0 ? y * y : y * y * x;
  9.     }
  11.     double myPow(double x, int n) {
  12.         long long N = n;
  13.         return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
  14.     }
  15. };

剑指 Offer 33. 二叉搜索树的后序遍历序列(也是有启发性的一题)

每一题的想法都很珍贵，分治的想法在于将一个大问题切割成一个个的小问题，往往回合递归再一起使用，方法很多，不变的是思想。
本题的要点

  • 先确定根节点的位置，因为本题是后序遍历，所以左子树一定小于根节点的值，右子树一定大于根节点的值，根据这个特点来判断左子树与右子树的位置。
  • 判断最大的左子树与右子树之后，往里面递归不停的判断根节点与左右子树的大小关系
  • 这里的思想有一个关键点，怎么设置判断正确与错误的条件呢？ 直接按照正确的要求来判断，就比如这一题递归的条件，假设数组顺序是正确的，将k从左子树开始挪到右子树的第一个节点，然后进行判断。如果通过就代表这一层是正确的。核心思想在于这个根据二叉搜索树的特点而做出的巧妙的判断。

    这个太难看懂了

    1. class Solution {
    2. public:
    3.   vector<int> res;
    4.   bool verifyPostorder(vector<int>& postorder) {
    5.       res = postorder;
    6.       return dfs(0, postorder.size() - 1);
    7.   }
    8.   bool dfs(int l, int r)
    9.   {
    10.       if(l >= r) return true;//退出条件
    11.       int root = res[r];//最后一个点是根结点
    12.       int k = l;//从最左边开始
    13.       while(k < r && res[k] < root) k++;//符合左子树的点
    14.       for(int i = k; i < r; i++)//此时的k是右子树的第一个点
    15.       {
    16.           if(res[i] < root)//如果右子树小于根，说明不符合
    17.           return false;
    18.       }
    19.       return dfs(l, k - 1) && dfs(k, r - 1);//逐步缩小范围
    20.   }
    21. };

    这个简单一点

    ```cpp class Solution { public: bool verifyPostorder(vector& postorder) {
    1.   return helpe(postorder, 0, postorder.size() - 1);
    }

private: bool helpe(vector &postorder, int l, int r) { if (l >= r) return true; int p = l, m = 0; while (postorder[p] < postorder[r]) ++p; m = p; // 切割点 while (postorder[p] > postorder[r]) ++p; return p == r && helpe(postorder, l, m - 1) && helpe(postorder, m, r - 1); } };

<a name="jAgKi"></a>
### [剑指 Offer 17. 打印从1到最大的n位数](https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)
<a name="SOTti"></a>
#### 我的傻逼写法
```shell
class Solution {
public:
    vector<int> printNumbers(int n) {
        if(n == 0) return {};
        int num = 0;
        vector<int> ret;
        while(n){
            num += pow(10, n - 1) * 9;
            n--;
        }
        for(int i = 1; i <= num; i++){
            ret.push_back(i);
        }
        return ret;
    }
};

不考虑大数

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ret;
        for(int i = 1; i <= (pow(10, n)-1); i++ ){
            ret.push_back(i);
        }
        return ret;
    }
};

考虑大数越界情况下的打印

class Solution {
public:
    vector<int> output;
    vector<int> printNumbers(int n) {
        if(n <= 0) return vector<int>(0);
        string s(n, '0');
        for(int i=0; i<=9; ++i)
        {
            s[0] = i + '0';
            permutation(s, s.length(), 1);
        }
        return output;
    }
    void permutation(string& s, int length, int pos)
    {
        // 这个函数的执行机制我想了好久才弄明白，mark一下，对带有循环的递归有时候还挺绕的
        if(pos == length)
        {
           inputNumbers(s);
           return; 
        }
        for(int i=0; i<=9; ++i)
        {
            s[pos] = i + '0';
            permutation(s, length, pos + 1);
        }
    }
    void inputNumbers(string s)
    {
        // 本函数与方法二的同名函数基本一样
        bool isUnwantedZero = true;
        string temp = "";
        for(int i=0; i<s.length(); ++i)
        {
            if(isUnwantedZero && s[i] != '0') isUnwantedZero = false;
            if(!isUnwantedZero) temp += s[i];
        }
        if(temp != "") output.push_back(stoi(temp)); // 如果 s = "000"，则temp会是空，stoi无法执行，会报错
    }
};

剑指 Offer 51. 数组中的逆序对（归并排序）

这一题的要求是给一个数组，要求返回这个数组中有多少个逆序对。逆序对的含义就是两个数字组成，后面的数字比前面的大。

  • 这一题利用了归并排序的特点，在并的过程中，比较左右子数组的大小来并，根据大小来累计逆序对
  • 因为左右两个子数组都是从小到大排序的，如果左边有一个元素p比右边的一个元素q大，那就代表元素p包括后面的所有元素都能与q组成逆序对。数量为m-q
  • 因为归并排序中合的特点，所以不会有重复的情况发生。因为每一层的左右两个子序列都不同。不会出现左子序列与右子序列相同的情况。
    class Solution {
public:
int res = 0;
  int reversePairs(vector<int>& nums) {
      int n = nums.size();
      vector<int> tmp(n);
      merge_sort(nums, 0, n, tmp);
      return res;
  }
  void merge_sort(vector<int>& nums, int l, int r, vector<int>& tmp){
      if(l+1>=r){
          return;
      }
      int m = l + (r-l)/2;
      merge_sort(nums, l, m, tmp);
      merge_sort(nums, m, r, tmp);
      int p = l, q = m, i = l;
      while(p<m||q<r){
          if(q >= r || (p<m&&nums[p] <= nums[q])){
              tmp[i++] = nums[p++];
          } else if(p >= m){
              tmp[i++] = nums[q++];
          } else {
              tmp[i++] = nums[q++];
              res = res + m - p;//此处累加逆序对的数目，此时就是左子数组的一个元素q比右子数组的元素p要大。
          }
      }
      for(i = l; i < r; i++){
          nums[i] = tmp[i];
      }
  }
};