面试题 16.19. 水域大小
题目链接
面试题 16.19. 水域大小 mid
题目描述
你有一个用于表示一片土地的整数矩阵 land,该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。
池塘的大小是指相连接的水域的个数。
编写一个方法来计算矩阵中所有池塘的大小,返回值需要从小到大排序。
示例:
输入:
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出: [1,2,4]
提示:
- 0<len(land)<=10000 < len(land) <= 10000<len(land)<=1000
- 0<len(land[i])<=10000 < len(land[i]) <= 10000<len(land[i])<=1000
解法:bfs
对于每一块池塘,我们都用 dfs 计算其大小 ttt,接着再将 ttt 存入答案数组 ansansans 中,最后将 ansansans 排序后再返回。
时间复杂度:O(mn)O(mn)O(mn)
C++代码:
const int dx[8] = {-1,-1,-1,0,1,1,1,0};
const int dy[8] = {-1,0,1,1,1,0,-1,-1};class Solution {
public:vector<int> pondSizes(vector<vector<int>>& g) {int m = g.size() , n = g[0].size();bool st[m][n];memset(st,false,sizeof st);vector<int> ans;function<int(int,int)> dfs = [&](int i,int j) -> int{if(i < 0 || i >= m || j < 0 || j >= n || st[i][j] || g[i][j] != 0) return 0;st[i][j] = true;int sum = 1;for(int k = 0;k < 8;k++) sum += dfs(i + dx[k] , j + dy[k]);return sum;};for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(!st[i][j] && g[i][j] == 0){int t = dfs(i,j);ans.push_back(t);}}}sort(ans.begin(),ans.end());return ans;}
};相关文章:
面试题 16.19. 水域大小
题目链接 面试题 16.19. 水域大小 mid 题目描述 你有一个用于表示一片土地的整数矩阵 land,该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。 池塘的大小是指相连接的水域的个数。 编写一个方法来计算矩阵…...
在vscode中切换分支,显示已经删除的远程分支
运行命令:修剪远程分支 git remote prune origin 然后远程的已经删除的分支就不见了。...
森林督查违法图斑内业报告高效制作实践技术
Python已成为最热门的编程语言之一,与arcpy、geopandas等行业软件包相结合,能极大程度地减轻森林督查违法图斑内业报告制作的工作量,显著提升工作效率。为了提升广大从业人员在森林违法图斑内业报告制作等方面的技能,内容主要包括…...
华为OD机试-日志限流-2022Q4 A卷-Py/Java/JS
某软件系统会在运行过程中持续产生日志,系统每天运行N单位时间,运行期间每单位时间产生的日志条数保行在数组 records中。records[i]表示第i单位时间内产生日志条数。 由于系统磁盘空间限制,每天可记录保存的日志总数上限为total条。 如果一天…...
ChatGPT能胜任高级程序员吗?
与开发人员信任的其他软件开发工具不同,AI工具在训练、构建、托管和使用方式等方面都存在一些独特的风险。 自2022年底ChatGPT发布以来,互联网上便充斥着对其几乎相同比例的支持和怀疑的论调。不管你是否喜欢它,AI正在逐步进入你的开发组织。…...
effective c++ item 25-29
item25:自定义swap函数 namespace std{template<typename T>void swap(T& a, T& b){T temp(a); // T要满足拷贝构造和拷贝赋值a b;b temp; } }1、Pimpl 2、自定义swap item26:尽可能延后变量的定义 case 1: temp j; for(int i 0; i < n; …...
MasterCAM实体旋转命令相关几个问题:曲线相交于边缘等
MasterCAM版本:2022 目的:通过旋转画杯子边缘主体 内外环直径分别是:56、60mm 命令:实体 - 旋转 问题: 一、处理实体期间错误parasolid(r) kernel 界面错误PK 错误代码:942-曲线相交于边缘 对应参数&a…...
p标签需要设置宽高吗?不用
Dusk: # 引用补丁,开头必须以 -javaagent: 开头,后面跟着补丁的绝对路径(可根据你实际的位置进行修改),注意路径一定要填写正确,且不能包含中文,否则会导致 IDEA 无法启动-javaagent:D:/ja-netfilter/ja-ne…...
Andorid 事件分发机制案例实操与解析
文章目录为什么要理解Android事件分发机制?滑动冲突类问题我们以什么开始?代码如下:activity xml 代码:Activity代码:item_user.xml代码修改后代码如下:Activity xmlactivity代码item_gift.xml问题出现了An…...
Git 版本控制/项目迭代
一、Git的作用/为什么要进行版本控制? 什么是项目迭代? 搞开发的时候我们不是一次性就做好平台的所有功能,而是先上线一个功能差不多的版本让用户用着,然后不断迭代、修改,上线新的版本,所以一个项目就会…...
智慧农业大数据项目建设方案
智慧农业大数据项目建设方案 目录 项目概述.................................... 6...
【数据结构专栏】动态扩容顺序栈详解
💌 博客内容:顺序栈的原理详解 😀 作 者:陈大大陈 🚀 个人简介:一个正在努力学技术的准前段,专注基础和实战分享 ,欢迎私信! 💖 欢迎大家:这…...
Linux命令·ifconfig
许多windows非常熟悉ipconfig命令行工具,它被用来获取网络接口配置信息并对此进行修改。Linux系统拥有一个类似的工具,也就是ifconfig(interfaces config)。通常需要以root身份登录或使用sudo以便在Linux机器上使用ifconfig工具。依赖于ifconfig命令中使…...
大器晚成我服刘邦,48岁才开始创业
读史使人明智,周末放下手机,静下心来读点人文历史。大器晚成我最佩服刘邦,48岁才开始创业 。在此之前,他是一个出身平凡的农民,早年曾多次失败和受挫。刘邦最后能够战胜项羽,常常让人觉得匪夷所思ÿ…...
AndroidStudio快捷键
动态演示:https://blog.csdn.net/weixin_67276852/article/details/124159843?spm1000.2115.3001.6382&utm_mediumdistribute.pc_feed_v2.none-task-blog-hot-11.pc_personrec&depth_1-utm_sourcedistribute.pc_feed_v2.none-task-blog-hot-11.pc_personre…...
机械硬盘的工作原理
每个磁盘的表面都有高速扫过的记录磁头。 每个磁盘上都覆盖着一层薄薄的微小的磁化金属粒。 数据以一种肉眼无法分辨的形式存在。很多组微小颗粒形成的磁化图案记录形成了数据。每一组,又称之为比特(bit)。 所有微粒都按照自身的磁性排列…...
掌握TypeScript:10个最佳实践提高代码质量
TypeScript 是一种强类型的 JavaScript 超集,提供了很多优秀的工具和语言特性,可以帮助开发者提高代码质量和开发效率。在本文中,我们将介绍 10 个 TypeScript 最佳实践,帮助初级和中级的 Web 前端开发工程师更好地使用 TypeScrip…...
【面试】Kafka面试题
文章目录1、Kafka是什么?2、partition的数据文件(offffset,MessageSize,data)3、数据文件分段 segment(顺序读写、分段命令、二分查找)4、负载均衡(partition会均衡分布到不同broker…...
【C++学习】map和set的使用
🐱作者:一只大喵咪1201 🐱专栏:《C学习》 🔥格言:你只管努力,剩下的交给时间! map和set的使用🌈关联式容器⚡键对值🌈set⚡构造函数⚡增删查改🌈…...
企业电子招投标采购系统——功能模块功能描述+数字化采购管理 采购招投标
功能模块: 待办消息,招标公告,中标公告,信息发布 描述: 全过程数字化采购管理,打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力,为外…...
AI写论文实用宝典,4款AI论文生成工具搞定各类论文写作!
在2025年的学术写作智能化浪潮中,越来越多的人开始依赖AI写论文工具进行创作。尽管这些工具的使用越来越普遍,但在撰写硕士、博士论文等较长篇幅的学术文章时,许多AI论文写作工具往往陷入缺乏理论深度和逻辑性不强的问题。普通的AI写专著或AI…...
Bladed 4.3 软件安装与学习研究环境搭建指南
1. Bladed 4.3软件简介与学习用途说明 Bladed是风力发电行业广泛使用的专业仿真软件,由英国Garrad Hassan公司开发(现属DNV集团)。它能够模拟风力发电机组的动态性能、载荷计算和控制系统设计,是风电工程师和研究人员的核心工具之…...
高效管理惠普OMEN游戏本:OmenSuperHub全面解析与实战指南
高效管理惠普OMEN游戏本:OmenSuperHub全面解析与实战指南 【免费下载链接】OmenSuperHub 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub OmenSuperHub是一款专为惠普OMEN系列游戏本设计的轻量级系统管理工具,它通过替代原厂Omen Ga…...
Oracle数据库架构入门概述
本文分为四个部分简单概述 一、入门概述 二、数据库实例简述 三、数据库物理存储和逻辑存储结构简述 四、网络体系结构概述 入门概述 Oracle 数据库服务器包括一个数据库和至少一个数据库实例 (通常是指只有一个实例)。 因为实例和数据库关联紧密&#x…...
5分钟完成专业级黑苹果配置:OpCore Simplify终极简化指南
5分钟完成专业级黑苹果配置:OpCore Simplify终极简化指南 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 你是否曾经为黑苹果配置的复杂性…...
Bitahub算力上新 RTX3080 10G重磅登场
针对当前 AI 开发与科研场景中算力成本高、配置复杂的痛点,Bitahub 平台推出了 RTX3080 10G 显卡算力服务。该显卡具备 10GB 显存,能够满足模型训练、推理等多场景算力需求,同时平台定价极具竞争力:单卡低至 0.82 元 / 小时&#…...
nli-distilroberta-base代码实例:Python调用DistilRoBERTa实现Entailment识别
nli-distilroberta-base代码实例:Python调用DistilRoBERTa实现Entailment识别 1. 项目概述 自然语言推理(Natural Language Inference, NLI)是自然语言处理中的一项重要任务,用于判断两个句子之间的逻辑关系。nli-distilroberta-base是基于DistilRoBER…...
零基础玩转OpenClaw:Qwen3-32B-Chat镜像云端体验指南
零基础玩转OpenClaw:Qwen3-32B-Chat镜像云端体验指南 1. 为什么选择云端体验OpenClaw? 第一次听说OpenClaw时,我正被各种本地部署的依赖项折磨得焦头烂额。作为一个习惯在MacBook上写代码的开发者,光是配置CUDA环境就让我望而却…...
RAG深度解析一:从参数化知识到检索增强的范式重构
【内容定位】深度技术原理【文章日期】2026-03-27【场景引入】进入2026年3月,一场围绕大语言模型“可信性”的讨论在技术社区再度升温。开发者们早已不再争论模型参数量,而是转向一个更实际的问题:如何让动辄千亿参数的大模型,在回…...
嵌入式开发工具选择与效率提升实践
1. 嵌入式开发者的工作状态与开发工具选择1.1 程序员工作场景分析嵌入式开发者在家庭办公环境中往往表现出独特的工作状态。通过观察典型的工作场景,我们可以总结出几个关键特征:专注度提升:家庭环境减少了办公室干扰,开发者更容易…...
