杭州四喜做网站建设么,ja.wordpress.org,想建设个网站怎么赚钱,学技术的培训机构文章目录 8 分治算法8.1 【递归】剑指 Offer 07 - 重建二叉树8.2 【递归】【快速幂】剑指 Offer 16 - 数值的整数次方8.3 【递归】剑指 Offer 33 - 二叉搜索树的后序遍历序列8.4 【递归】【分治】剑指 Offer 17 - 打印从1到最大的n位数8.5 【归并排序】【分治】剑指 Offer 51 -… 文章目录 8 分治算法8.1 【递归】剑指 Offer 07 - 重建二叉树8.2 【递归】【快速幂】剑指 Offer 16 - 数值的整数次方8.3 【递归】剑指 Offer 33 - 二叉搜索树的后序遍历序列8.4 【递归】【分治】剑指 Offer 17 - 打印从1到最大的n位数8.5 【归并排序】【分治】剑指 Offer 51 - 数组中的逆序对 9 排序9.1 【冒泡排序】剑指 Offer 45 - 把数组排成最小的数9.2 【排序】剑指 Offer 61 - 扑克牌中的顺子9.3 【堆排序】剑指 Offer 40 - 最小的k个数9.4 【堆排序】【优先队列】剑指 Offer 41 - 数据流中的中位数 10 动态规划10.1 【动态规划】【哈希表】【DFS】剑指 Offer 10- I - 斐波那契数列10.2 【动态规划】【哈希表】【DFS】剑指 Offer 10- II - 青蛙跳台阶问题10.3 【动态规划】剑指 Offer 63 - 股票的最大利润10.4 【动态规划】【分治】剑指 Offer 42 - 连续子数组的最大和10.5 【动态规划】剑指 Offer 47 - 礼物的最大价值 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_mapint,int hash_table;
public:TreeNode* subTree(vectorint preorder, vectorint 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_l1, pre_lsub_l, in_l, in_root-1);//对于右子树而言前序遍历的[左边界左子树节点数1右边界]即为中序遍历的[根节点1右边界]root-right subTree(preorder, inorder, pre_lsub_l1, pre_r, in_root1, in_r);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int n inorder.size();for(int i0;in;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 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} x10x20∗0∗x21∗1∗x22∗0∗x23∗1可以看作按照x的2次方依次递增只需要看这一个次方对应的二进制是否为1。
class Solution {
public:double myPow(double x, int n) {if(x1 || n0) return 1;if(x0) return 0;double ans 1;long num n;if(n0){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(vectorint 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 iright dfs(postorder,left,mid-1) dfs(postorder,mid,right-1);}bool verifyPostorder(vectorint 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:vectorint printNumbers(int n) {int cnt pow(10,n);vectorint ans;for(int i1;icnt;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, vectorint nums, vectorint tmp){if(left right) return 0;int mid (left right) / 2;int res merge_sort(left, mid, nums, tmp) merge_sort(mid1, right, nums, tmp);int i left, j mid 1;for(int kleft;kright;k){tmp[k] nums[k];}for(int kleft;kright;k){ if(i mid1) nums[k] tmp[j];else if(j right1 || tmp[i] tmp[j]) nums[k] tmp[i];else{nums[k] tmp[j];res mid - i 1;}}return res;}int reversePairs(vectorint nums){vectorint 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(vectorint nums) {for(int inums.size()-1;i0;i--){for(int j0;ji;j){if(string_sort(nums[j],nums[j1])){swap(nums[j],nums[j1]);}}}string ans ;for(int i0;inums.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(s1s2) 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如果gapzero_num说明0的个数可以补全缺的数否则就肯定不是顺子。
class Solution {
public:bool isStraight(vectorint nums) {int arr[14] {0};int max_num 0, min_num 14, zero_num 0;for(int i0;i5;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 imin_num;imax_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:vectorint getLeastNumbers(vectorint arr, int k) {sort(arr.begin(),arr.end());vectorint ans;for(int i0;ik;i){ans.push_back(arr[i]);}return ans;}
};
//方法二堆排序
class Solution {
public:vectorint getLeastNumbers(vectorint arr, int k) {vectorint ans;if(k 0) return ans;priority_queueint, vectorint, lessint max_stack;//把前k个数字存入大根堆for(int i0;ik;i){max_stack.push(arr[i]);}//依次和大根堆的top比较如果比top小就更新大根堆for(int jk;jarr.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_queueint, vectorint, greaterint min_stack;priority_queueint, vectorint, lessint 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_mapint,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_mapint,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天未持有股票 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的两个元素在反复调用所以在代码中也是直接用两个变量来进行代替了。
class Solution {
public:int maxProfit(vectorint prices) {if(!prices.size()) return 0;int dp_0 0, dp_1 -prices[0];for(int i1;iprices.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个数本身的话就要从这里开始重新找到连续子数组了在这个过程中记录下最大值即可。
class Solution {
public:int maxSubArray(vectorint nums) {int pre 0, max_seqsum nums[0];for(int i0;inums.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 ) (m1)*(n1) (m1)∗(n1)。
class Solution {
public:int maxValue(vectorvectorint grid) {int m grid.size(), n grid[0].size();int value[m1][n1];memset(value,0,sizeof(value));for(int i0;im;i){for(int j0;jn;j){value[i1][j1] max(value[i1][j],value[i][j1]) grid[i][j];}}return value[m][n];}
};
