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

8 分治算法

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

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

  前序遍历是根左右，中序遍历是左根右，这也就意味着前序遍历的第一个节点是整棵树的根节点，顺着这个节点找到它在中序遍历中的位置，即为in_root，那么in_root左边的都在左子树，右边的都在右子树，这样就可以知道左子树一共有多少个节点，然后去前序遍历中找到左右子树的分界点，分成左右两部分，分别重复上述过程，找到各自部分的第一个根节点，然后再依次往下进行，直到最后左右子树的边界发生重合，此时二叉树重建完毕。

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;        //开始生成root        TreeNode* 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:        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<=小根堆的size        if(min_stack.size() == max_stack.size())        {            max_stack.push(num);            min_stack.push(max_stack.top());            max_stack.pop();        }        //如果大根堆和小根堆的size不一样，那么此时add的num就加入小根堆，然后把小根堆的top插入到大根堆中，保证小根堆的size<=大根堆的size        else        {            min_stack.push(num);            max_stack.push(min_stack.top());            min_stack.pop();        }    }    //执行findMedian函数时，看看此时大根堆和小根堆的size是否相等，如果相等的话，中位数就是各自取top元素相加取平均，如果不相等，那么中位数就是小根堆的top    double findMedian() {        if(min_stack.size() == max_stack.size())        {            return (max_stack.top() + min_stack.top()) / 2.0;        }        else return min_stack.top();    }};

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];    }};

来源地址：https://blog.csdn.net/qq_44528283/article/details/132571866