当前位置: 首页 > news >正文

408算法题leetcode--第22天

200. 岛屿数量

  • 200. 岛屿数量
  • 时间:O(mn);空间:O(min(m, n)),队列最大入队个数,可以想象从左上到右下,第一次入队1个,第二次出队1,入队2,第三次出队2,入队3…
class Solution {
public:int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 右,下,左,上int count = 0;int row;int column;void bfs(vector<vector<char>>& grid, int x, int y){queue<pair<int, int>>q;q.push({x, y});while(!q.empty()){auto t = q.front();q.pop();for(int i = 0; i < 4; i++){int new_x = t.first + dir[i][0], new_y = t.second + dir[i][1];if(new_x < 0 || new_x >= row || new_y < 0 || new_y >= column){continue;}if(grid[new_x][new_y] != '1'){continue;}grid[new_x][new_y] = '0';  // 访问q.push({new_x, new_y});}}}int numIslands(vector<vector<char>>& grid) {// bfsrow = grid.size(), column = grid[0].size();for(int i = 0; i < row; i++){for(int j = 0; j < column; j++){if(grid[i][j] == '1'){bfs(grid, i, j);++count;}}}return count;}
};

695. 岛屿的最大面积

  • 695. 岛屿的最大面积
  • 同上,bfs
class Solution {
public:int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 右,下,左,上int ret = 0;int row;int column;int bfs(vector<vector<int>>& grid, int x, int y){grid[x][y] = 0;queue<pair<int, int>>q;q.push({x, y});int square = 1;while(!q.empty()){auto t = q.front();q.pop();for(int i = 0; i < 4; i++){int new_x = t.first + dir[i][0], new_y = t.second + dir[i][1];if(new_x < 0 || new_x >= row || new_y < 0 || new_y >= column){continue;}if(grid[new_x][new_y] != 1){continue;}grid[new_x][new_y] = 0;  // 访问++square;q.push({new_x, new_y});}}return square;}int maxAreaOfIsland(vector<vector<int>>& grid) {// bfsrow = grid.size(), column = grid[0].size();for(int i = 0; i < row; i++){for(int j = 0; j < column; j++){if(grid[i][j] == 1){int temp = bfs(grid, i, j);ret = max(ret, temp);}}}return ret;}
};

547. 省份数量

  • 547. 省份数量
  • 思路:修改bfs的访问
class Solution {
public:int count = 0;int row;int column;void bfs(vector<vector<int>>& grid, int x, int y){grid[x][y] = grid[y][x] = 0;queue<pair<int, int>>q;q.push({x, y});while(!q.empty()){auto t = q.front();q.pop();int new_x = t.first;for(int i = 0; i < column; i++){if(grid[new_x][i] == 0){continue;}grid[new_x][i] = grid[i][new_x] = 0;  // 访问q.push({i, new_x});}}}int findCircleNum(vector<vector<int>>& isConnected) {// bfsrow = isConnected.size(), column = isConnected[0].size();for(int i = 0; i < row; i++){for(int j = 0; j < column; j++){if(isConnected[i][j] == 1){bfs(isConnected, i, j);++count;}}}return count;}
};

相关文章:

408算法题leetcode--第22天

200. 岛屿数量 200. 岛屿数量时间&#xff1a;O(mn)&#xff1b;空间&#xff1a;O(min(m, n))&#xff0c;队列最大入队个数&#xff0c;可以想象从左上到右下&#xff0c;第一次入队1个&#xff0c;第二次出队1&#xff0c;入队2&#xff0c;第三次出队2&#xff0c;入队3……...

dubbo微服务

一.启动nacos和redis 1.虚拟机查看是否开启nacos和redis docker ps2.查看是否安装nacos和redis docker ps -a3.启动nacos和redis docker start nacos docker start redis-6379 docker ps二.创建三个idea的maven项目 1.第一个项目dubboapidemo 2.1.1向pom.xml里添加依赖 …...

如何在 DAX 中计算多个周期的移动平均线

在 DAX 中计算移动聚合很容易。但是&#xff0c;计算一段时间内的移动平均值时会有一些陷阱。由于其中一些陷阱是定义问题&#xff0c;因此我们必须小心&#xff0c;不要选择错误的方法。让我们看看细节。欢迎来到雲闪世界。 添加图片注释&#xff0c;不超过 140 字&#xff08…...

微信小程序 图片的上传

错误示范 /*从相册中选择文件 微信小程序*/chooseImage(){wx.chooseMedia({count: 9,mediaType: [image],sourceType: [album],success(res) {wx.request({url:"发送的端口占位符",data:res.tempFiles[0].tempFilePath,method:POST,success(res){//请求成功后应该返…...

软件测试人员发现更多程序bug

软件测试人员发现更多程序bug 1. 理解需求和业务&#xff0c;需求评审时候发现bug 熟悉了产品的业务流程、才能迅速找出软件中存在的一些重要的缺陷&#xff0c;发现的软件缺陷才是有价值的。否则即使你能找到一些软件缺陷&#xff0c;那也是纯软件的缺陷&#xff0c;价值不大…...

Nagle 算法:优化 TCP 网络中小数据包的传输

1. 前言 在网络通信中&#xff0c;TCP&#xff08;传输控制协议&#xff09;是最常用的协议之一&#xff0c;广泛应用于各种网络应用&#xff0c;如网页浏览、文件传输和在线游戏等。然而&#xff0c;随着互联网的普及&#xff0c;小数据包的频繁传输成为一个不容忽视的问题。…...

C#入门教程

目录 1.if分支语句 2.面向对象 3.static简单说明 1.if分支语句 我们的这个C#里面的if语句以及这个if-else语句和C语言里面没有区别&#xff0c;就是打这个输出上面的方式不一样&#xff0c;c#里面使用的是这个console.writeline这个指令&#xff0c;其他的这个判断逻辑都是一…...

【MySQL报错】---Data truncated for column ‘age‘ at row...

目录 一、前言二、问题分析三、解决办法 一、前言 欢迎大家来到权权的博客~欢迎大家对我的博客进行指导&#xff0c;有什么不对的地方&#xff0c;我会及时改进哦~ 博客主页链接点这里–>&#xff1a;权权的博客主页链接 二、问题分析 问题一修改表结构 XXX 为 not n…...

Go基础学习08-并发安全型类型-通道(chan)深入研究

文章目录 chan基础使用和理解通道模型&#xff1a;单通道、双通道双向通道单向通道单向通道的作用 缓冲通道和非缓冲通道数据发送和接收过程缓冲通道非缓冲通道 通道基本特性通道何时触发panicChannel和Select结合使用Select语句和通道的关系Select语句的分支选择规则有那些Sel…...

some 蓝桥杯题

12.反异或01串 - 蓝桥云课 (lanqiao.cn) #include "bits/stdc.h" #define int long long using namespace std; char c[10000000]; char s[10000000]; int cnt,Ans,mr,mid; int maxi; int p[10000000],pre[10000000]; signed main() {ios::sync_with_stdio(0);cin.t…...

[linux 驱动]input输入子系统详解与实战

目录 1 描述 2 结构体 2.1 input_class 2.2 input_dev 2.4 input_event 2.4 input_dev_type 3 input接口 3.1 input_allocate_device 3.2 input_free_device 3.3 input_register_device 3.4 input_unregister_device 3.5 input_event 3.6 input_sync 3.7 input_se…...

2023_Spark_实验十:Centos_Spark Local模式部署

参考这篇博客&#xff1a;【Centos8_配置单节点伪分布式Spark环境】_centos8伪分布式环境搭建-CSDN博客...

pyecharts-快速入门

pyecharts文档&#xff1a;渲染图表 - pyecharts - A Python Echarts Plotting Library built with love. pyecharts-gallery文档&#xff1a;中文简介 - Document (pyecharts.org) 一、快速入门案例 from pyecharts.charts import Barbar Bar() bar.add_xaxis(["衬衫…...

vue3打包疯狂报错

打包的时候报错很多Cannot find name ‘xxx‘ 。 但是npm run dev 是运行正常的。 解决方法&#xff1a;package.json中的vue-tsc --noEmit 删掉就可以了。 例如&#xff1a; 这是原来的 {"scripts": {"dev": "vite","build": &quo…...

STM32 软件触发ADC采集

0.91寸OLED屏幕大小的音频频谱&#xff0c;炫酷&#xff01; STM32另一个很少人知道的的功能——时钟监测 晶振与软件的关系&#xff08;深度理解&#xff09; STM32单片机一种另类的IO初始化方法 ADC是一个十分重要的功能&#xff0c;几乎任何一款单片机都会包含这个功能&a…...

Android SystemUI组件(08)睡眠灭屏 锁屏处理流程

该系列文章总纲链接&#xff1a;专题分纲目录 Android SystemUI组件 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节持续迭代之前章节的思维导图&#xff0c;主要关注左侧上方锁屏分析部分 睡眠灭屏 即可。 Power按键的处理逻辑最终是由PhoneWindowManager来完…...

C# 表达式与运算符

本课要点&#xff1a; 1、表达式的基本概念 2、常用的几种运算符 3、运算符的优先级 4、常见问题 一 表达式 表达式是由运算符和操作数组成的。、-、*和/等都是运算符&#xff0c;操作数包括文本、常量、变量和表达式等。 二 算术运算符 2.1 算术运算符的使用 三 常见错误 …...

SpringBoot--最大连接数和最大并发数

原文网址&#xff1a;SpringBoot--最大连接数和最大并发数-CSDN博客 简介 本文介绍SpringBoot的最大连接数和最大并发数。 配置 SpringBoot默认使用tomcat处理请求。tomcat可以指定连接数、线程数等配置。 server:tomcat:# 请求处理线程都在使用中时&#xff0c;新连接请求…...

CF687D Dividing Kingdom II 题解

Description 给定一个 n n n 个点、 m m m 条边的图&#xff0c;有 q q q 次询问&#xff0c;每次询问一个 [ l , r ] [l,r] [l,r] 的区间&#xff0c;求将 n n n 个点分为两个部分后&#xff0c;编号在 [ l , r ] [l,r] [l,r] 内的边中&#xff0c;两端点属于同一部分的…...

高空抛物AI检测算法:精准防控,技术革新守护城市安全

近年来&#xff0c;随着城市化进程的加速&#xff0c;高楼大厦如雨后春笋般涌现&#xff0c;但随之而来的高空抛物问题却成为城市管理的一大难题。高空抛物不仅严重威胁行人的安全&#xff0c;还可能引发法律纠纷和社会问题。为了有效预防和减少高空抛物事件的发生&#xff0c;…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...