Leetcode 695 Max Area of Island

embedded/2025/1/14 5:12:37/

题意

给定一个二维矩阵,矩阵中包含0和1,所有相连的1被视为一个岛屿,求这些所有岛屿的最大区域是多少

题目链接

https://leetcode.com/problems/max-area-of-island/description/

题解

遍历二维矩阵,当遇到没有被访问过的1时,开始进行dfs,记此时的1坐标为x,y。 dfs返回从(x,y)出发,能到达的所有岛屿格的数量。

class Solution {
public:int m;int n;int maxAreaOfIsland(vector<vector<int>>& grid) {int res = 0;m = grid.size();n = grid[0].size();vector<vector<bool>> vis(m, vector<bool>(n, false));for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1 && !vis[i][j]) {res = max(res, dfs(grid, vis, i, j));}}}return res;}int dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {vis[x][y] = true;int dk[] = {-1, 0, 1, 0, -1};int area = 1;for(int i = 0; i < 4; i++) {int nx = x + dk[i];int ny = y + dk[i+1];if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && grid[nx][ny] == 1) {area += dfs(grid, vis, nx, ny);}}return area;}
};

时间复杂度: O ( m n ) O(mn) O(mn) m,n是二维矩阵的长宽
空间复杂度: O ( m n ) O(mn) O(mn) m,n是二维矩阵的长宽

疑问

为什么area += dfs(grid, vis, nx, ny);, 而不是return 1+dfs(grid, vis, nx, ny),你需要统计4个方向的答案再返回


http://www.ppmy.cn/embedded/148880.html

相关文章

【Linux进程】进程信号

目录 1. 信号 2. 信号的产生 2.1 终端按键 自定义信号处理 2.2 系统调用 kill raise abort 2.3 硬件异常 2.4 软件条件产生 思考 总结 1. 信号 在Linux中存在着一种通信的方式&#xff0c;与管道和System V IPC不同&#xff0c;更准确的说是一种通知机制&#xff0c;…

如何查看flink错误信息

flink出错时&#xff0c;可以通过以下步骤查看flink错误信息&#xff1a; 1.打开flink webui界面 2.进入overview或running jobs页面 3.点击出错的job name&#xff0c;出错的jobname一般后面的status会变红 4.在job 详情页面&#xff0c;点击exception&#xff0c;即可查看错…

eth_type_trans 函数

eth_type_trans 是 Linux 内核网络子系统中的一个函数,它主要用于确定接收到的以太网数据包(Ethernet frame)的协议类型,并设置相应的 sk_buff 结构体的协议字段。以下是关于 eth_type_trans 的详细解释: 功能 eth_type_trans 函数的主要功能是根据以太网数据包的目的 M…

Flink中并行度和slot的关系——任务和任务槽

一、任务槽&#xff08;task slots) Flink的每一个TaskManager是一个JVM进程&#xff0c;在其上可以运行多个线程&#xff08;任务task&#xff09;&#xff0c;那么每个线程可以拥有多少进程资源呢&#xff1f;任务槽就是这样一个概念&#xff0c;对taskManager上每个任务运行…

w118共享汽车管理系统

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…

LightGBM分类算法在医疗数据挖掘中的深度探索与应用创新(上)

一、引言 1.1 医疗数据挖掘的重要性与挑战 在当今数字化医疗时代,医疗数据呈爆炸式增长,这些数据蕴含着丰富的信息,对医疗决策具有极为重要的意义。通过对医疗数据的深入挖掘,可以发现潜在的疾病模式、治疗效果关联以及患者的健康风险因素,从而为精准医疗、个性化治疗方…

Elasticsearch 国产化替代方案之一 Easysearch 的介绍与部署指南

一、前言 在国内数字化转型浪潮和 信创 大背景下&#xff0c;“替代进口”成为许多企业级应用所需要面对的重要课题&#xff0c;搜索领域也不例外。 Elasticsearch&#xff08;简称 ES&#xff09;作为一款业界领先的全文搜索和分析引擎&#xff0c;虽然功能强大&#xff0c;但…

[实战]Docker应用自动重启

场景 Java应用&#xff0c;在凌晨定时任开始时运行一段时间后&#xff0c;会自动重启&#xff0c;导致定时任务失败。该应用使用Docker部署 分析 Docker应用运行一段时间自动重启可能的原因为容器分配的资源&#xff08;如CPU、内存&#xff09;不足&#xff0c;系统可能会杀…