文章目录
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) {}
* };
*/classSolution{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)returnnullptr;//找到根节点，计算左子树的节点数int pre_root = pre_l;int in_root = hash_table[preorder[pre_l]];int sub_l = in_root - in_l;//开始生成root
TreeNode* root =newTreeNode(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;}returnsubTree(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
x^{10}
x10，因为10的二进制表示为1010，那么
x
10
=
x
2
0
∗
0
∗
x
2
1
∗
1
∗
x
2
2
∗
0
∗
x
2
3
∗
1
x^{10}=x^{2^0*0}*x^{2^1*1}*x^{2^2*0}*x^{2^3*1}
x10=x20∗0∗x21∗1∗x22∗0∗x23∗1，可以看作按照x的2次方依次递增，只需要看这一个次方对应的二进制是否为1。
classSolution{public:doublemyPow(double x,int n){if(x==1|| n==0)return1;if(x==0)return0;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
后序遍历的特点就是先访问左子树再访问右子树最后访问根节点，所以最后一个元素一定根节点，而二叉搜索树的特点就是左子树<根节点<右子树，所以我们可以根据根节点的值把数组分为两部分，然后分别判断是否符合二叉搜索树的特点，重复上述过程直到所有情况都判断完为止。
classSolution{public:booldfs(vector<int>& postorder,int left,int right){if(left >= right)returntrue;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);}boolverifyPostorder(vector<int>& postorder){returndfs(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。
classSolution{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
classSolution{public:intmerge_sort(int left,int right, vector<int>& nums, vector<int>& tmp){if(left >= right)return0;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++];elseif(j == right+1|| tmp[i]<= tmp[j]) nums[k]= tmp[i++];else{
nums[k]= tmp[j++];
res += mid - i +1;}}return res;}intreversePairs(vector<int>& nums){
vector<int>tmp(nums.size());returnmerge_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”后面，借助这种排序思路来解题。
classSolution{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;}boolstring_sort(int num1,int num2){
string s1 =to_string(num1)+to_string(num2);
string s2 =to_string(num2)+to_string(num1);if(s1>s2)returntrue;elsereturnfalse;}};
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的个数可以补全缺的数，否则就肯定不是顺子。
classSolution{public:boolisStraight(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]])returnfalse;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)returntrue;elsereturnfalse;}};
9.3 【堆排序】剑指 Offer 40 - 最小的k个数
https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof
方法一：直接用sort排序，然后选前k个数就好了。
方法二：用堆排序，堆排序，采用大根堆，首先把前k个数字存入大根堆中，之后的数字依次和大根堆的top比较，如果比top小就更新大根堆，最后把大根堆中的数字存入vector中作为答案返回。
//方法一：直接排序classSolution{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;}};//方法二：堆排序classSolution{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。
classMedianFinder{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(){}voidaddNum(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元素相加取平均，如果不相等，那么中位数就是小根堆的topdoublefindMedian(){if(min_stack.size()== max_stack.size()){return(max_stack.top()+ min_stack.top())/2.0;}elsereturn 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，主要是因为在计算过程中会有一些数被反复计算，所以我们在这里采用哈希表来存放已经被计算过的数，这样在之后再次被计算时直接用就好了。
classSolution{public:
unordered_map<int,int> hash_table;intdfs(int n){if(n ==0)return0;elseif(n ==1)return1;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];}}}intfib(int n){returndfs(n);}};
10.2 【动态规划】【哈希表】【DFS】剑指 Offer 10- II - 青蛙跳台阶问题
https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
这道题目就是变形的斐波那契数列，在这里采用哈希表来存放已经被计算过的数，这样在之后再次被计算时直接用就好了。
classSolution{public:
unordered_map<int,int> hash_table;intdfs(int n){if(n ==0)return1;elseif(n ==1)return1;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];}}}intnumWays(int n){returndfs(n);}};
10.3 【动态规划】剑指 Offer 63 - 股票的最大利润
https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof
动态规划类题目的解题主要是找到状态转移方程就好了，对于这道题目的状态转移就在于某一天有无股票，我们以此为分界来定义状态转移方程dp[i][2]：
（1）前i天未持有股票
d
p
[
i
]
[
0
]
=
m
a
x
(
d
p
[
i
−
1
]
[
0
]
,
d
p
[
i
−
1
]
[
1
]
+
p
r
i
c
e
s
[
i
]
)
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])
（2）前i天持有股票
d
p
[
i
]
[
1
]
=
m
a
x
(
d
p
[
i
−
1
]
[
1
]
,
0
−
p
r
i
c
e
s
[
i
]
)
dp[i][1] = max(dp[i-1][1], 0 - prices[i])
dp[i][1]=max(dp[i−1][1],0−prices[i])
同时还要预判一下prices为空的情况，此时返回0，因为dp的两个元素在反复调用，所以在代码中也是直接用两个变量来进行代替了。
classSolution{public:intmaxProfit(vector<int>& prices){if(!prices.size())return0;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
n
n，连续子数组的最大和为
f
(
n
)
f(n)
f(n)，那么
f
(
n
)
=
m
a
x
(
f
(
n
−
1
)
+
n
u
m
s
[
i
]
,
n
u
m
[
i
]
)
f(n)=max(f(n-1)+nums[i],num[i])
f(n)=max(f(n−1)+nums[i],num[i])，也就意味着最大和要么是前
n
−
1
n-1
n−1个数的最大和加上第
i
i
i个数，要么就是第
i
i
i个数本身，如果是第
i
i
i个数本身的话，就要从这里开始重新找到连续子数组了，在这个过程中记录下最大值即可。
classSolution{public:intmaxSubArray(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
其实每个地方的最大值只与两个状态有关，假设目前要求的是
v
a
l
u
e
[
i
]
[
j
]
value[i][j]
value[i][j]的最大值，那么
v
a
l
u
e
[
i
]
[
j
]
=
m
a
x
(
v
a
l
u
e
[
i
]
[
j
−
1
]
,
v
a
l
u
e
[
i
−
1
]
[
j
]
)
+
g
r
i
d
[
i
]
[
j
]
value[i][j] = max(value[i][j-1],value[i-1][j]) + grid[i][j]
value[i][j]=max(value[i][j−1],value[i−1][j])+grid[i][j]，这里为了方便初始化，把初始数组的大小设置为
(
m
+
1
)
∗
(
n
+
1
)
(m+1)*(n+1)
(m+1)∗(n+1)。
classSolution{public:intmaxValue(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];}};
版权归原作者 小天才才 所有， 如有侵权，请联系我们删除。