6 一切皆可搜索
6
hh
hh
6.1
6.2
depth-first seachDFS
1 1
->2->4->2 ->1->3->1
-> 1->2->4->3
1 / \
23 /
4
memoization
695. Max Area of Island (Easy)
0-101
Input:
[[1,0,1,1,0,1,0,1], [1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]] Output: 6
6
stack
vector<int> direction{-1, 0, 1, 0, -1};
int maxAreaOfIsland(vector<vector<int>>& grid) { int m = grid.size(), n = m? grid[0].size(): 0, local_area, area = 0, x, y;
for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) {
if (grid[i][j]) { local_area = 1;
grid[i][j] = 0;
stack<pair<int, int>> island;
island.push({i, j});
while (!island.empty()) { auto [r, c] = island.top();
island.pop();
for (int k = 0; k < 4; ++k) { x = r + direction[k], y = c + direction[k+1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 0;
++local_area;
island.push({x, y});
} }
} area = max(area, local_area);
} }
return area;
vector<int> direction{-1, 0, 1, 0, -1};
// int maxAreaOfIsland(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int max_area = 0;
for (int i = 0; i < grid.size(); ++i) { for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) { max_area = max(max_area, dfs(grid, i, j));
} }
} return max_area;
}
// int dfs(vector<vector<int>>& grid, int r, int c) {
if (grid[r][c] == 0) return 0;
grid[r][c] = 0;
int x, y, area = 1;
for (int i = 0; i < 4; ++i) { x = r + direction[i], y = c + direction[i+1];
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) { area += dfs(grid, x, y);
} }
return area;
}
// int maxAreaOfIsland(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int max_area = 0;
for (int i = 0; i < grid.size(); ++i) { for (int j = 0; j < grid[0].size(); ++j) {
max_area = max(max_area, dfs(grid, i, j));
} }
return max_area;
}
// int dfs(vector<vector<int>>& grid, int r, int c) {
if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0) {
return 0;
grid[r][c] = 0;
return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c) + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
}
547. Friend Circles (Medium)
0-1(i, j)1ij abbcac
1
Input:
[[1,1,0], [1,1,0],
[0,0,1]] Output: 2
[1,2][3]
695
695mn4n n1
695
// int findCircleNum(vector<vector<int>>& friends) {
int n = friends.size(), count = 0;
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) { if (!visited[i]) {
dfs(friends, i, visited);
++count;
} }
return count;
// void dfs(vector<vector<int>>& friends, int i, vector<bool>& visited) {
for (int k = 0; k < friends.size(); ++k) { if (friends[i][k] == 1 && !visited[k]) {
dfs(friends, k, visited);
} }
}
417. Pacific Atlantic Water Flow (Medium)
2
Input:
~~~~~
| ~1 | 2 | 2 | 3(5) * |
|---|---|---|---|
| ~3 | 2 | 3(4) (4) * | |
| ~2 | 4(5)3 | 1* | |
| ~ (6) (7) 1 | 4 5* | ||
| ~ (5)1 | 1 | 2 4* | |
| * | * | * | * * |
Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
vector<int> direction{-1, 0, 1, 0, -1};
// vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) { return {};
} vector<vector<int>> ans;
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> can_reach_p(m, vector<bool>(n, false));
vector<vector<bool>> can_reach_a(m, vector<bool>(n, false));
全站分卷索引 · 68 卷
- 11 题目分类
- 22 最易懂的贪心算法
- 32.3 区间问题
- 42.4 练习
- 53 玩转双指针
- 63.2 Two Sum
- 73.4 快慢指针
- 83.5 滑动窗口
- 93.6 练习
- 104 居合斩!二分查找
- 114.3 查找区间
- 124.4 旋转数组查找数字
- 134.5 练习
- 145 千奇百怪的排序算法
- 155.2 快速选择
- 165.3 桶排序
- 175.4 练习
- 186 一切皆可搜索
- 196.3 回溯法
- 206.4 广度优先搜索
- 216.5 练习
- 227 深入浅出动态规划
- 237.3 基本动态规划:二维
- 247.4 分割类型题
- 257.5 子序列问题
- 267.6 背包问题
- 277.7 字符串编辑
- 287.8 股票交易
- 297.9 练习
- 308 化繁为简的分治法
- 318.3 练习
- 329 巧解数学问题
- 339.4 数字处理
- 349.5 随机与取样
- 359.6 练习
- 3610 神奇的位运算
- 3710.3 二进制特性
- 3810.4 练习
- 3911 妙用数据结构
- 4011.2 数组
- 4111.3 栈和队列
- 4211.4 单调栈
- 4311.5 优先队列
- 4411.6 双端队列
- 4511.7 哈希表
- 4611.8 多重集合和映射
- 4711.9 前缀和与积分图
- 4811.10 练习
- 11.10
- 566. Reshape the Matrix (Easy)
- 225. Implement Stack using Queues (Easy)
- 503. Next Greater Element II (Medium)
- 217. Contains Duplicate (Easy)
- 697. Degree of an Array (Easy)
- 594. Longest Harmonious Subsequence (Easy)
- 287. Find the Duplicate Number (Medium)
- 313. Super Ugly Number (Medium)
- 870. Advantage Shuffle (Medium)
- 307. Range Sum Query - Mutable (Medium)
- 4912 令人头大的字符串
- 5012.3 字符串理解
- 5112.4 字符串匹配
- 5212.5 练习
- 5313 指针三剑客之一:链表
- 5413.3 其它链表技巧
- 5513.4 练习
- 5614 指针三剑客之二:树
- 5714.3 层次遍历
- 5814.4 前中后序遍历
- 5914.5 二叉查找树
- 6014.6 字典树
- 6114.7 练习
- 14.7
- 226. Invert Binary Tree (Easy)
- 617. Merge Two Binary Trees (Easy)
- 572. Subtree of Another Tree (Easy)
- 404. Sum of Left Leaves (Easy)
- 513. Find Bottom Left Tree Value (Easy)
- 538. Convert BST to Greater Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Easy)
- 530. Minimum Absolute Difference in BST (Easy)
- 889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 94. Binary Tree Inorder Traversal (Medium)
- 6215 指针三剑客之三:图
- 6315.3 拓扑排序
- 6415.4 练习
- 6516 更加复杂的数据结构
- 6616.3 复合数据结构
- 6716.4 练习
- 6817 后记