1.24#
二叉树的层序遍历 (掌握程度：中)#
边界的处理还是有些许的问题，但是大体的方向是没有问题的
/**
* 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<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
vector<int> vals;
for (int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
vals.push_back(node->val);
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
ans.push_back(vals);
}
return ans;
}
};搜索旋转排序数组 (掌握程度：低)#
想起来了他是要根据判断target是在前面有序区域还是后续有序区域，再进行二分的，但是边界处理还是记得不太清楚，后续还是要好好熟络一下
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
};岛屿数量 (掌握程度： 高)#
典型的dfs了
class Solution {
public:
int numIslands(vector<vector<char>>& 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') {
dfs(grid, m, n, i, j);
ans++;
}
}
}
return ans;
}
void dfs(vector<vector<char>>& grid, int m, int n, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
grid[i][j] = '0';
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);
}
};两数之和 (掌握程度：中)#
这个简单题我已经不熟很久了，总是忘记一些循环内的东西，但是好歹大致方向没啥问题
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> pos;
int n = nums.size();
for (int i = 0; i < n; i++) {
int x = nums[i];
if (pos.count(target - x)) {
return {pos[target - x], i};
}
pos[x] = i;
}
return {};
}
};全排列 (掌握程度：高)#
简单的回溯
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<bool> used;
void dfs(vector<int>& nums, int n, int i) {
if (i == n) {
ans.push_back(path);
return;
}
for (int j = 0; j < n; j++) {
if (used[j] == true) continue;
used[j] = true;
path.push_back(nums[j]);
dfs(nums, n, i + 1);
path.pop_back();
used[j] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
used = vector<bool>(n, false);
dfs(nums, n, 0);
return ans;
}
};