会员管理网站ASP建设,免费前端模板网站,仪表东莞网站建设,公司注销预审在什么网站做❤ 作者主页#xff1a;欢迎来到我的技术博客#x1f60e; ❀ 个人介绍#xff1a;大家好#xff0c;本人热衷于Java后端开发#xff0c;欢迎来交流学习哦#xff01;(#xffe3;▽#xffe3;)~* #x1f34a; 如果文章对您有帮助#xff0c;记得关注、点赞、收藏、… ❤ 作者主页欢迎来到我的技术博客 ❀ 个人介绍大家好本人热衷于Java后端开发欢迎来交流学习哦(▽)~* 如果文章对您有帮助记得关注、点赞、收藏、评论⭐️⭐️⭐️ 您的支持将是我创作的动力让我们一起加油进步吧 文章目录 一、颜色分类1. 题目描述2. 思路分析3. 代码实现 二、最小覆盖子串1. 题目描述2. 思路分析 三、子集1. 题目描述2. 思路分析3. 代码实现 四、单词搜索1. 题目描述2. 思路分析3. 代码实现 五、柱状图中最大的矩形1. 题目描述2. 思路分析3. 代码实现 六、最大矩阵七、二叉树的中序遍历1. 题目描述2. 思路分析3. 代码实现 八、不同的二叉搜索树1. 题目描述2. 思路分析3. 代码实现 九、验证二叉搜索树1. 题目描述2. 思路分析3. 代码实现 十、对称二叉树1. 题目描述2. 思路分析3. 代码实现 一、颜色分类
1. 题目描述 2. 思路分析
这道题的思路很难可以想到。 如图所示, [ 0 , j − 1 ] [0,j - 1] [0,j−1] 维护的是全是 0 0 0 的区间 [ j , i − 1 ] [j,i - 1] [j,i−1] 维护的是全是 1 1 1 的区间 [ k 1 , n − 1 ] [k 1,n - 1] [k1,n−1] 维护的是全是 2 2 2 的区间而 [ i , k ] [i,k] [i,k] 区间的元素是还没放的数。
枚举整个数组若当前枚举到的位置是 i i i
若 nums[i] 0则交换 i i i 和 j j j 的位置的元素由于nums[i] 0且nums[j] 1因此交换后 i i i 和 j j j 同时往后移动1位若nums[i] 1则直接 i 若 nums[i] 2则交换 i i i 和 k k k 位置的元素由于 nums[i] 2因此填入到 k k k 位置时 k k k 的元素就是2因此 k k k 需要往前移动1位而交换过来可能是2 也可能是0 而i的元素未知不做移动。 3. 代码实现
class Solution {
public:void sortColors(vectorint nums) {for (int i 0, j 0, k nums.size() - 1; i k;) {if (nums[i] 0) swap(nums[i ], nums[j ]);else if (nums[i] 2) swap(nums[i], nums[k --]);else i ;}}
};二、最小覆盖子串
1. 题目描述 2. 思路分析 三、子集
1. 题目描述 2. 思路分析
dfs 和全排列的做法一样当我们走到叶子结点时就把该路径加入方案中。如果还没有走到叶子节点那么对于枚举的当前数我们有两种选择选或不选做出选择再递归到下一层同时记得回溯。 3. 代码实现
class Solution {
public:vectorvectorint res;vectorint path;vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return res;}void dfs(vectorint nums, int u) {if (u nums.size()) {res.push_back(path);return;}dfs(nums, u 1); // 不选当前数递归下一层path.push_back(nums[u]); // 选当前数dfs(nums, u 1); // 递归path.pop_back(); // 回溯}
};四、单词搜索
1. 题目描述 2. 思路分析
(dfs)
在深度优先搜索中最重要的就是考虑好搜索顺序。
我们先枚举单词的起点然后依次枚举单词的每个字母。 过程中需要将已经使用过的字母改成一个特殊字母以避免重复使用字符。 3. 代码实现
class Solution {
public:bool exist(vectorvectorchar board, string word) {for (int i 0; i board.size(); i ) {for (int j 0; j board[i].size(); j ) {if (dfs(board, word, 0, i, j)) return true;}}return false;}int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};bool dfs(vectorvectorchar board, string word, int u, int x, int y) {if (board[x][y] ! word[u]) return false;if (u word.size() - 1) return true;char t board[x][y];board[x][y] .;for ( int i 0; i 4; i ) {int a x dx[i], b y dy[i];if (a 0 || a board.size() || b 0 || b board[0].size() || board[a][b] .) continue;if (dfs(board, word, u 1, a, b)) return true;}board[x][y] t;return false;}
};五、柱状图中最大的矩形
1. 题目描述 2. 思路分析
单调栈
此题的本质是找到每个柱形条左边和右边最近的比自己低的矩形条然后用宽度乘上当前柱形条的高度作为备选答案。解决此类问题的经典做法是单调栈维护一个单调递增的栈如果当前柱形条 i i i 的高度比栈顶要低则栈顶元素 c u r cur cur 出栈。出栈后 c u r cur cur 右边第一个比它低的柱形条就是 i左边第一个比它低的柱形条是当前栈中的 t o p top top。不断出栈直到栈为空或者柱形条 i i i 不再比 t o p top top 低。满足 操作2 之后当前矩形条 i i i 进栈。 3. 代码实现
class Solution {
public:int largestRectangleArea(vectorint h) {int n h.size();vectorint left(n), right(n);stackint stk;for (int i 0; i n; i ) {while (stk.size() h[stk.top()] h[i]) stk.pop();if (stk.empty()) left[i] -1;else left[i] stk.top();stk.push(i);}stk stackint();for (int i n - 1; i 0; i --) {while (stk.size() h[stk.top()] h[i]) stk.pop();if (stk.empty()) right[i] n;else right[i] stk.top();stk.push(i);}int res 0;for (int i 0; i n; i ) {res max(res, h[i] * (right[i] - left[i] - 1));}return res;}
};六、最大矩阵 七、二叉树的中序遍历
1. 题目描述 2. 思路分析
递归算法比较简单就根据中序遍历的过程先遍历左子树再遍历当前根然后遍历右子树。递归函数的中止条件是当前结点为空同时当遍历当前结点时将该点加入遍历数组即可。 3. 代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint res;vectorint inorderTraversal(TreeNode* root) {dfs(root);return res;}void dfs(TreeNode* root) {if (!root) return;dfs(root-left);res.push_back(root-val);dfs(root-right);}
};八、不同的二叉搜索树
1. 题目描述 2. 思路分析
(动态规划) 对于 n n n 个节点的 BST除去根节点有 n − 1 n - 1 n−1 个节点将这 n − 1 n - 1 n−1 个节点分配在根节点的两侧即可构造出所有的方案。
状态表示 f [ n ] f[n] f[n] 表示 n n n 个节点的二叉搜索树共有多少种。 状态转移 左子树可以有 0 , 1 , . . . , n − 1 0,1,...,n - 1 0,1,...,n−1 个节点对应的右子树有 n − 1 , n − 2 , . . . , 0 n - 1, n - 2, ..., 0 n−1,n−2,...,0 个节点 f [ n ] f[n] f[n] 是所有这些情况的总和即 f [ n ] f [ 0 ] ∗ f [ n − 1 ] f [ 1 ] ∗ f [ n − 2 ] … f [ n − 1 ] ∗ f [ 0 ] f[n]f[0]∗f[n−1]f[1]∗f[n−2]…f[n−1]∗f[0] f[n]f[0]∗f[n−1]f[1]∗f[n−2]…f[n−1]∗f[0] 3. 代码实现
class Solution {
public:int numTrees(int n) {vectorint f(n 1);f[0] 1;for (int i 1; i n; i ) for (int j 1; j i; j )f[i] f[j - 1] * f[i - j];return f[n];}
};九、验证二叉搜索树
1. 题目描述 2. 思路分析
深度优先遍历 深度优先遍历整棵子树。 遍历时需要向上传递当前子树中的最小值和最大值这里可以用C中的引用来专递。 对于当前节点我们先遍历它的左子树判断左子树是否合法同时判断左子树的最大值是否小于当前节点的值然后遍历右子树判断右子树是否合法同时判断右子树的最小值是否大于当前节点的值。 如果条件均满足说明以当前节点为根的子树是一棵合法的二叉搜索树返回 t r u e true true。 3. 代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isValidBST(TreeNode* root) {if (!root) return true;int maxv, minv;return dfs(root, maxv, minv);}bool dfs(TreeNode* root, int maxv, int minv) {maxv minv root-val;if (root-left) {int nowMaxv, nowMinv;if (!dfs(root-left, nowMaxv, nowMinv)) return false;if (nowMaxv root-val)return false;maxv max(maxv, nowMaxv);minv min(minv, nowMinv);}if (root-right) {int nowMaxv, nowMinv;if (!dfs(root-right, nowMaxv, nowMinv)) return false;if (nowMinv root-val)return false;maxv max(maxv, nowMaxv);minv min(minv, nowMinv);}return true;}
};十、对称二叉树
1. 题目描述 2. 思路分析
递归判断两个子树是否互为镜像。
两个子树互为镜像当且仅当
两个子树的根节点值相等第一棵子树的左子树和第二棵子树的右子树互为镜像且第一棵子树的右子树和第二棵子树的左子树互为镜像 3. 代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if (!root) return true;return dfs(root-left, root-right);}bool dfs(TreeNode* p, TreeNode* q) {if (!p !q) return true;if (!p || !q || p-val ! q-val) return false;return dfs(p-left, q-right) dfs(p-right, q-left);}
};非常感谢您阅读到这里如果这篇文章对您有帮助希望能留下您的点赞 关注 分享 留言thanks
