【leetcode刷题之路】剑指Offer（4）——分治+排序算法+动态规划

8 分治算法

8.1 【递归】剑指 Offer 07 - 重建二叉树

https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

  前序遍历是根左右，中序遍历是左根右，这也就意味着前序遍历的第一个节点是整棵树的根节点，顺着这个节点找到它在中序遍历中的位置，即为in_root，那么in_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 {
private:unordered_map<int,int> hash_table;
public:TreeNode* subTree(vector<int>& preorder, vector<int>& inorder, int pre_l, int pre_r, int in_l, int in_r){if(pre_l > pre_r) return nullptr;//找到根节点，计算左子树的节点数int pre_root = pre_l;int in_root = hash_table[preorder[pre_l]];int sub_l = in_root - in_l;//开始生成rootTreeNode* root = new TreeNode(preorder[pre_l]);//对于左子树而言，前序遍历的[左边界+1，左边界+左子树节点数]即为中序遍历的[左边界，根节点-1]root->left = subTree(preorder, inorder, pre_l+1, pre_l+sub_l, in_l, in_root-1);//对于右子树而言，前序遍历的[左边界+左子树节点数+1，右边界]即为中序遍历的[根节点+1，右边界]root->right = subTree(preorder, inorder, pre_l+sub_l+1, pre_r, in_root+1, in_r);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = inorder.size();for(int i=0;i<n;i++){hash_table[inorder[i]] = i;}return subTree(preorder, inorder, 0, n-1, 0, n-1);}
};

8.2 【递归】【快速幂】剑指 Offer 16 - 数值的整数次方

https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/description/

  这道题可以用快速幂来解决，具体思路就是把幂次按照二进制拆开，分别计算，下面举个例子： 假设我要计算$x^{10}$，因为10的二进制表示为1010，那么$x^{10}=x^{2^0\ast 0}\ast x^{2^1\ast 1}\ast x^{2^2\ast 0}\ast x^{2^3\ast 1}$，可以看作按照x的2次方依次递增，只需要看这一个次方对应的二进制是否为1。

class Solution {
public:double myPow(double x, int n) {if(x==1 || n==0) return 1;if(x==0) return 0;double ans = 1;long num = n;if(n<0){num = -num;x = 1/x;}while(num){if(num & 1) ans *= x;x *= x;num >>= 1;}return ans;}
};

8.3 【递归】剑指 Offer 33 - 二叉搜索树的后序遍历序列

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

  后序遍历的特点就是先访问左子树再访问右子树最后访问根节点，所以最后一个元素一定根节点，而二叉搜索树的特点就是左子树<根节点<右子树，所以我们可以根据根节点的值把数组分为两部分，然后分别判断是否符合二叉搜索树的特点，重复上述过程直到所有情况都判断完为止。

class Solution {
public:bool dfs(vector<int>& postorder, int left, int right){if(left >= right) return true;int i = left;while(postorder[i]<postorder[right]){i++;}int mid = i;while(postorder[i]>postorder[right]){i++;}return i==right & dfs(postorder,left,mid-1) & dfs(postorder,mid,right-1);}bool verifyPostorder(vector<int>& postorder){return dfs(postorder,0,postorder.size()-1);}
};

8.4 【递归】【分治】剑指 Offer 17 - 打印从1到最大的n位数

https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof

  这道题目由于指定了数组是int型，所以不用考虑大整数问题，直接暴力就可以解决，但如果是大整数的话，需要采用分治递归的思想，主要如下：

（1）第一层遍历，为n，分别考虑到生成的数字是1位数、2位数、3位数…n位数；

（2）第二层遍历，分别遍历每一位数是几，除了第一位是1-9之外，其余都是0-9。

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

8.5 【归并排序】【分治】剑指 Offer 51 - 数组中的逆序对

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof

  这位大佬写的很好！（https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h）

class Solution {
public:int merge_sort(int left, int right, vector<int>& nums, vector<int>& tmp){if(left >= right) return 0;int mid = (left + right) / 2;int res = merge_sort(left, mid, nums, tmp) + merge_sort(mid+1, right, nums, tmp);int i = left, j = mid + 1;for(int k=left;k<=right;k++){tmp[k] = nums[k];}for(int k=left;k<=right;k++){ if(i == mid+1) nums[k] = tmp[j++];else if(j == right+1 || tmp[i] <= tmp[j]) nums[k] = tmp[i++];else{nums[k] = tmp[j++];res += mid - i + 1;}}return res;}int reversePairs(vector<int>& nums){vector<int> tmp(nums.size());return merge_sort(0, nums.size()-1, nums, tmp);}
};

9 排序

9.1 【冒泡排序】剑指 Offer 45 - 把数组排成最小的数

https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof

  这题可以看作是冒泡排序，只不过针对的对象是字符串，我们需要找到里面表示最大的字符串，然后把它放到字符串的最后即可，例如“32”和“3”，因为“323”<“332”，所以“32”<“3”，所以应该把“3”放在“32”后面，借助这种排序思路来解题。

class Solution {
public:string minNumber(vector<int>& nums) {for(int i=nums.size()-1;i>0;i--){for(int j=0;j<i;j++){if(string_sort(nums[j],nums[j+1])){swap(nums[j],nums[j+1]);}}}string ans = "";for(int i=0;i<nums.size();i++){ans += to_string(nums[i]);}return ans;}bool string_sort(int num1, int num2){string s1 = to_string(num1) + to_string(num2);string s2 = to_string(num2) + to_string(num1);if(s1>s2) return true;else return false;}
};

9.2 【排序】剑指 Offer 61 - 扑克牌中的顺子

https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof

  这道题不难，想清楚顺子的判断条件即可，主要为以下几个方面：

（1）五个数中除了0以外不能有其他的重复数字，否则肯定不是顺子；

（2）找出五个数中的最大值和最小值，看看这两个数之间缺的数的个数是多少，记为gap，然后计算五个数中0的个数，记为zero_num，如果gap<=zero_num，说明0的个数可以补全缺的数，否则就肯定不是顺子。

class Solution {
public:bool isStraight(vector<int>& nums) {int arr[14] = {0};int max_num = 0, min_num = 14, zero_num = 0;for(int i=0;i<5;i++){if(nums[i]==0) zero_num++;else{if(arr[nums[i]]) return false;else{arr[nums[i]] = 1;min_num = min(min_num, nums[i]);max_num = max(max_num, nums[i]);}}}int gap = 0;for(int i=min_num;i<max_num;i++){if(arr[i]!=1) gap++;}if(gap <= zero_num) return true;else return false;}
};

9.3 【堆排序】剑指 Offer 40 - 最小的k个数

https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof

  方法一：直接用sort排序，然后选前k个数就好了。

  方法二：用堆排序，堆排序，采用大根堆，首先把前k个数字存入大根堆中，之后的数字依次和大根堆的top比较，如果比top小就更新大根堆，最后把大根堆中的数字存入vector中作为答案返回。

//方法一：直接排序
class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {sort(arr.begin(),arr.end());vector<int> ans;for(int i=0;i<k;i++){ans.push_back(arr[i]);}return ans;}
};
//方法二：堆排序
class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> ans;if(k == 0) return ans;priority_queue<int, vector<int>, less<int>> max_stack;//把前k个数字存入大根堆for(int i=0;i<k;i++){max_stack.push(arr[i]);}//依次和大根堆的top比较，如果比top小就更新大根堆for(int j=k;j<arr.size();j++){if(arr[j] < max_stack.top()){max_stack.pop();max_stack.push(arr[j]);}}//把大根堆中的数字存入vector中作为答案返回while(k--){ans.push_back(max_stack.top());max_stack.pop();}return ans;}
};

9.4 【堆排序】【优先队列】剑指 Offer 41 - 数据流中的中位数

https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof

  这道题如果直接对所有数进行排序的话，最后会runtime，其实只要能找出每一次执行findMedian函数时整个数据流中间的两个数或者一个数就行了，这是我们可以考虑用堆排序，同时维持一个大根堆和一个小根堆，把数据流中的数分为两部分，同时也要保证大根堆中的top要比小根堆中的top小，这样最后的中位数要么是小根堆top，要么就是大根堆和小根堆的top取平均，构造方法如下：

• 如果大根堆和小根堆的size一样，那么此时add的num就加入大根堆，然后把大根堆的top插入到小根堆中，保证大根堆的size<=小根堆的size；
• 如果大根堆和小根堆的size不一样，那么此时add的num就加入小根堆，然后把小根堆的top插入到大根堆中，保证小根堆的size<=大根堆的size；
• 执行findMedian函数时，看看此时大根堆和小根堆的size是否相等，如果相等的话，中位数就是各自取top元素相加取平均，如果不相等，那么中位数就是小根堆的top。

class MedianFinder {
public:/** initialize your data structure here. */priority_queue<int, vector<int>, greater<int>> min_stack;priority_queue<int, vector<int>, less<int>> max_stack;MedianFinder() {}void addNum(int num) {//如果大根堆和小根堆的size一样，那么此时add的num就加入大根堆，然后把大根堆的top插入到小根堆中，保证大根堆的size<=小根堆的sizeif(min_stack.size() == max_stack.size()){max_stack.push(num);min_stack.push(max_stack.top());max_stack.pop();}//如果大根堆和小根堆的size不一样，那么此时add的num就加入小根堆，然后把小根堆的top插入到大根堆中，保证小根堆的size<=大根堆的sizeelse{min_stack.push(num);max_stack.push(min_stack.top());min_stack.pop();}}//执行findMedian函数时，看看此时大根堆和小根堆的size是否相等，如果相等的话，中位数就是各自取top元素相加取平均，如果不相等，那么中位数就是小根堆的topdouble findMedian() {if(min_stack.size() == max_stack.size()){return (max_stack.top() + min_stack.top()) / 2.0;}else return min_stack.top();}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

10 动态规划

10.1 【动态规划】【哈希表】【DFS】剑指 Offer 10- I - 斐波那契数列

https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof

  这道题如果直接用动态规划会runtime，主要是因为在计算过程中会有一些数被反复计算，所以我们在这里采用哈希表来存放已经被计算过的数，这样在之后再次被计算时直接用就好了。

class Solution {
public:unordered_map<int,int> hash_table;int dfs(int n){if(n == 0) return 0;else if(n == 1) return 1;else{if(hash_table.count(n)) return hash_table[n];else{int num1 = dfs(n-1) % 1000000007;int num2 = dfs(n-2) % 1000000007;hash_table[n] = (num1 + num2) % 1000000007;return hash_table[n];}}}int fib(int n) {return dfs(n);}
};

10.2 【动态规划】【哈希表】【DFS】剑指 Offer 10- II - 青蛙跳台阶问题

https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

  这道题目就是变形的斐波那契数列，在这里采用哈希表来存放已经被计算过的数，这样在之后再次被计算时直接用就好了。

class Solution {
public:unordered_map<int,int> hash_table;int dfs(int n){if(n == 0) return 1;else if(n == 1) return 1;else{if(hash_table.count(n)) return hash_table[n];else{int num1 = dfs(n-1) % 1000000007;int num2 = dfs(n-2) % 1000000007;hash_table[n] = (num1 + num2) % 1000000007;return hash_table[n];}}}int numWays(int n) {return dfs(n);}
};

10.3 【动态规划】剑指 Offer 63 - 股票的最大利润

https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof

  动态规划类题目的解题主要是找到状态转移方程就好了，对于这道题目的状态转移就在于某一天有无股票，我们以此为分界来定义状态转移方程dp[i][2]：

（1）前i天未持有股票

$dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])$

（2）前i天持有股票

$dp[i][1]=max(dp[i-1][1],0-prices[i])$

  同时还要预判一下prices为空的情况，此时返回0，因为dp的两个元素在反复调用，所以在代码中也是直接用两个变量来进行代替了。

class Solution {
public:int maxProfit(vector<int>& prices) {if(!prices.size()) return 0;int dp_0 = 0, dp_1 = -prices[0];for(int i=1;i<prices.size();i++){dp_0 = max(dp_0, dp_1 + prices[i]);dp_1 = max(dp_1, 0 - prices[i]);}return dp_0;}
};

10.4 【动态规划】【分治】剑指 Offer 42 - 连续子数组的最大和

https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

  这道题用到一点点分治的思想，假设现在数组长度为$n$，连续子数组的最大和为$f(n)$，那么$f(n)=max(f(n-1)+nums[i],num[i])$，也就意味着最大和要么是前$n-1$个数的最大和加上第$i$个数，要么就是第$i$个数本身，如果是第$i$个数本身的话，就要从这里开始重新找到连续子数组了，在这个过程中记录下最大值即可。

class Solution {
public:int maxSubArray(vector<int>& nums) {int pre = 0, max_seqsum = nums[0];for(int i=0;i<nums.size();i++){pre = max(pre + nums[i], nums[i]);max_seqsum = max(max_seqsum, pre);}return max_seqsum;}
};

10.5 【动态规划】剑指 Offer 47 - 礼物的最大价值

https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof

  其实每个地方的最大值只与两个状态有关，假设目前要求的是$value[i][j]$的最大值，那么$value[i][j]=max(value[i][j-1],value[i-1][j])+grid[i][j]$，这里为了方便初始化，把初始数组的大小设置为$(m+1)\ast (n+1)$。

class Solution {
public:int maxValue(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();int value[m+1][n+1];memset(value,0,sizeof(value));for(int i=0;i<m;i++){for(int j=0;j<n;j++){value[i+1][j+1] = max(value[i+1][j],value[i][j+1]) + grid[i][j];}}return value[m][n];}
};