【LeetCode 热题 HOT 100】题解笔记 —— Day04

❤ 作者主页：欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉

一、颜色分类

1. 题目描述

---

2. 思路分析

这道题的思路很难可以想到。

如图所示, $[0,j-1]$ 维护的是全是 $0$ 的区间，$[j,i-1]$ 维护的是全是 $1$ 的区间，$[k+1,n-1]$ 维护的是全是 $2$ 的区间，而 $[i,k]$ 区间的元素是还没放的数。

枚举整个数组，若当前枚举到的位置是 $i$：

1. 若 nums[i] == 0，则交换 $i$ 和 $j$ 的位置的元素，由于nums[i] == 0且nums[j] == 1，因此交换后 $i$ 和 $j$ 同时往后移动1位；
2. 若nums[i] == 1，则直接 i ++；
3. 若 nums[i] == 2，则交换 $i$ 和 $k$ 位置的元素，由于 nums[i] == 2，因此填入到 $k$ 位置时，$k$ 的元素就是2，因此 $k$ 需要往前移动1位，而交换过来可能是2 也可能是0 而i的元素未知，不做移动。

---

3. 代码实现

class Solution {
public:void sortColors(vector<int>& 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:vector<vector<int>> res;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return res;}void dfs(vector<int> 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(vector<vector<char>>& 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(vector<vector<char>>& 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. 思路分析

单调栈

1. 此题的本质是找到每个柱形条左边和右边最近的比自己低的矩形条，然后用宽度乘上当前柱形条的高度作为备选答案。
2. 解决此类问题的经典做法是单调栈，维护一个单调递增的栈，如果当前柱形条 $i$ 的高度比栈顶要低，则栈顶元素 $cur$ 出栈。出栈后，$cur$ 右边第一个比它低的柱形条就是 i，左边第一个比它低的柱形条是当前栈中的 $top$。不断出栈直到栈为空或者柱形条 $i$ 不再比 $top$ 低。
3. 满足 操作2 之后，当前矩形条 $i$ 进栈。

---

3. 代码实现

class Solution {
public:int largestRectangleArea(vector<int>& h) {int n = h.size();vector<int> left(n), right(n);stack<int> 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 = stack<int>();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:vector<int> res;vector<int> 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$ 个节点的 BST，除去根节点有 $n-1$ 个节点，将这 $n-1$ 个节点分配在根节点的两侧，即可构造出所有的方案。

状态表示： $f[n]$ 表示 $n$ 个节点的二叉搜索树共有多少种。
状态转移： 左子树可以有 $0,1,...,n-1$ 个节点，对应的右子树有 $n-1,n-2,...,0$ 个节点，$f[n]$ 是所有这些情况的总和，即 $f[n]=f[0]\ast f[n-1]+f[1]\ast f[n-2]+\dots +f[n-1]\ast f[0]$

---

3. 代码实现

class Solution {
public:int numTrees(int n) {vector<int> 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++中的引用来专递。
对于当前节点，我们先遍历它的左子树，判断左子树是否合法，同时判断左子树的最大值是否小于当前节点的值；然后遍历右子树，判断右子树是否合法，同时判断右子树的最小值是否大于当前节点的值。
如果条件均满足，说明以当前节点为根的子树是一棵合法的二叉搜索树，返回 $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. 思路分析

递归判断两个子树是否互为镜像。

两个子树互为镜像当且仅当：

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！！！