2.6#
平衡二叉树 (掌握程度：中)#
难度不大，毕竟是个简单题，但是平衡二叉树不知道是啥，看到题解之后立马就知道了
/**
* 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 isBalanced(TreeNode* root) {
return dfs(root) != -1;
}
int dfs(TreeNode* node) {
if (node == nullptr) return 0;
int left = dfs(node->left);
if (left == -1) return -1;
int right = dfs(node->right);
if (right == -1) return -1;
if (abs(left - right) > 1) return -1;
return max(left, right) + 1;
}
};岛屿的最大面积 (掌握程度：中)#
跟岛屿数量差不多的解法，只不过岛屿数量没有返回值，这个有
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
ans = max(ans, dfs(grid, m, n, i, j));
}
}
}
return ans;
}
int dfs(vector<vector<int>>& grid, int m, int n, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return 0;
grid[i][j] = 0; // 标记已访问
int area = dfs(grid, m, n, i + 1, j) +
dfs(grid, m, n, i - 1, j) +
dfs(grid, m, n, i, j + 1) +
dfs(grid, m, n, i, j - 1) + 1;
return area;
}
};另一种 dfs 的写法
class Solution {
public:
int dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return 0;
int area = 1;
grid[i][j] = 0;
for (auto& d : dirs) {
int x = i + d[0];
int y = j + d[1];
area += dfs(grid, x, y, m, n);
}
return area;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
ans = max(ans, dfs(grid, i, j, m, n));
}
}
}
return ans;
}
};二叉树的前序遍历 (掌握程度：高)#
这种 X 序遍历题，现在拿给小学生说不定都会
/**
* 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> ans;
void dfs(TreeNode* node) {
if (node == nullptr) return;
ans.push_back(node->val);
dfs(node->left);
dfs(node->right);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};最大正方形 (掌握程度：低)#
只知道是dp 但是具体实现一个都不知道啊
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int maxLen = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = min({
dp[i-1][j],
dp[i][j-1],
dp[i-1][j-1]
}) + 1;
}
maxLen = max(maxLen, dp[i][j]);
}
}
}
return maxLen * maxLen;
}
};回文链表 (掌握程度：高)#
数组存值之后再判断是否为回文
另一种写法是找中点，之后反转链表再一个节点一个节点比较
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
vals.push_back(cur->val);
}
int n = vals.size();
int left = 0, right = n - 1;
while (left <= right) {
if (vals[left] != vals[right]) return false;
left++;
right--;
}
return true;
}
};买卖股票的最佳时机 II (掌握程度：低)#
最优解的贪心，这道题是可以无限买，假设每次都买了第二天卖。只要赚了就是赚了，亏了就不进行买卖
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int ans = 0;
for (int i = 1; i < n; i++) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
};验证二叉搜索树 (掌握程度：中)#
中序遍历验证二叉搜索树，但是有点还是忘记了
/**
* 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:
long pre = LONG_MIN;
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
if (!isValidBST(root->left)) return false;
if (root->val <= pre) return false;
pre = root->val;
return isValidBST(root->right);
}
};旋转图像 (掌握程度：中)#
先交换后行倒转，就是顺时针，后面行的倒转有点忘记怎么写了
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};先行倒转，再交换就是逆时针
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};最长公共前缀 (掌握程度：低)#
是真的有点没见过的题，不过看了题解之后，才发现难度其实也还好，就是
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
for (int i = 0; i < strs[0].size(); i++) {
char c = strs[0][i];
for (int j = 1; j < strs.size(); j++) {
if (i == strs[j].size() || strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
};搜索二维矩阵 II (掌握程度：中)#
收缩排除法，因为从左到右，从上到下都是递增，只要元素不符合行/列可以直接排除
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] < target) i++;
else j--;
}
return false;
}
};