【日常做题】 代码随想录（岛屿最大面积+寻宝）

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者1.#includeiostream #includevector #includealgorithm #includequeue using namespace std; vectorvectorintedge; long long maxn 0; long long cur; int dx[4] { 1,-1,0,0 }; int dy[4] { 0,0,1,-1 }; int N, M; void dfs(int x, int y) { for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { cur; maxn max(maxn, cur); edge[nx][ny] 0; dfs(nx, ny); } } } int main() { cin N M; edge.resize(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) { for (int j 1; j M; j) { cin edge[i][j]; } } for (int i 1; i N; i) { for (int j 1; j M; j) { if (edge[i][j] 1) { edge[i][j] 0; cur 1; maxn max(maxn, cur); dfs(i, j); } } } cout maxn endl; return 0; }从“数岛屿”到“最大岛屿面积”DFS 进阶一篇讲透附代码细节分析很多同学做到“岛屿数量”就停了但其实更经典的一道题是在一个二维网格中求最大连通块的面积你这段代码已经写到了这个进阶版本这篇文章我们就把它彻底讲清楚。一、问题本质给你一个 N × M 的网格1表示陆地0表示水要求找出最大的“岛屿面积”连续的1的数量举个例子1 1 0 1 0 0 0 1 1这里左上角岛面积 3右下角岛面积 2答案3二、核心思路非常重要相比“数岛屿”这里只多了一步每找到一个岛 → 统计它的大小 → 更新最大值三、变量含义解释你的代码中有两个关键变量long long maxn 0; // 最大岛屿面积 long long cur; // 当前岛屿面积四、DFS 核心逻辑来看你的 DFSvoid dfs(int x, int y) { for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { cur; maxn max(maxn, cur); edge[nx][ny] 0; dfs(nx, ny); } } }五、DFS 在干什么一句话总结从一个点出发把整个岛屿遍历一遍同时统计大小执行流程遇到一个新的 1岛屿起点cur 1当前面积从1开始DFS 扩展每找到一个 1 →cur同时更新最大值六、主函数逻辑if (edge[i][j] 1) { edge[i][j] 0; cur 1; maxn max(maxn, cur); dfs(i, j); }逻辑解释发现一个新岛 → 初始化面积 cur 1 → DFS 扩展整个岛 → 更新最大值七、一个关键优化点更推荐写法你现在的写法是cur; maxn max(maxn, cur);其实可以更清晰一点推荐写法DFS返回面积int dfs(int x, int y) { int area 1; // 当前节点算1 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { edge[nx][ny] 0; area dfs(nx, ny); } } return area; }主函数写法if (edge[i][j] 1) { edge[i][j] 0; int area dfs(i, j); maxn max(maxn, area); }为什么更好逻辑更清晰一个函数只干一件事 → 返回面积 避免全局变量混乱 更符合面试写法八、时间复杂度O(N × M)原因每个点最多访问一次九、空间复杂度最坏 O(N × M)原因递归栈可能很深全是1的情况十、常见错误1. 忘记标记访问edge[nx][ny] 0;否则会无限递归。2. cur 没初始化cur 1;3. 起点没处理edge[i][j] 0;必须在 DFS 前做。十一、DFS vs BFS 做这个题方法思路推荐程度DFS递归扩展简单直观BFS队列扩展更稳定防爆栈十二、一句话总结这道题的本质就是用 DFS 找连通块同时统计每个连通块的大小取最大值2.#includeiostream #includevector #includealgorithm using namespace std; typedef struct node { int u, v, w; }node; vectornodeedge; vectorintparent; bool f(node a, node b) { return a.w b.w; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } int main() { int V, E; cin V E; parent.resize(V 1); for (int i 1; i V; i) { parent[i] i; } for (int i 0; i E; i) { int u, v, w; cin u v w; edge.push_back({ u,v,w }); } sort(edge.begin(), edge.end(), f); long long sum 0; long long use 0; for (int i 0; i edge.size(); i) { int u edge[i].u; int v edge[i].v; int w edge[i].w; int rootu find(u); int rootv find(v); if (rootu ! rootv) { parent[rootu] rootv; sum w; use; if (use V-1) break; } } cout sum endl; return 0; }Kruskal算法从入门到实战最小生成树一篇彻底讲明白附完整代码最小生成树MST是图论里非常核心的一块内容而Kruskal算法是最经典、最适合入门的一种解法。你这份代码已经是一个标准模板级写法了这篇文章我帮你整理成一篇可以直接发 CSDN 的高质量版本从思路到代码彻底讲清楚。一、问题背景什么是最小生成树给你一个无向图有 V 个点有 E 条边每条边有权值要求选出若干条边使所有点连通并且总权值最小核心特点1. 必须连通所有点 2. 不能有环 3. 边数一定是 V - 1二、Kruskal算法核心思想一句话理解从小到大选边只要不形成环就加入为什么可行因为每次都选当前最小的边贪心 并用并查集保证不会成环三、代码结构解析我们一步一步拆代码。1. 边结构体typedef struct node { int u, v, w; } node;表示一条边u → v权值 w2. 排序关键一步bool f(node a, node b) { return a.w b.w; }sort(edge.begin(), edge.end(), f);作用按边权从小到大排序3. 并查集初始化parent.resize(V 1); for (int i 1; i V; i) { parent[i] i; }含义每个点一开始是独立集合4. find函数路径压缩int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; }作用查找集合的根节点并压缩路径四、Kruskal核心流程for (int i 0; i edge.size(); i) { int u edge[i].u; int v edge[i].v; int w edge[i].w; int rootu find(u); int rootv find(v); if (rootu ! rootv) { parent[rootu] rootv; sum w; use; if (use V - 1) break; } }逻辑解释情况1不在同一集合可以连 → 不会成环操作合并集合 加入权值情况2在同一集合跳过 → 否则会形成环五、为什么一定是 V - 1 条边树的性质n个点的最小连通结构一定有 n-1 条边所以if (use V - 1) break;这是一个关键优化提前结束避免不必要计算