【综合算法学习】(第十五篇)

目录

图像渲染(medium)

题目解析

讲解算法原理

编写代码

岛屿数量(medium)

题目解析

讲解算法原理

编写代码


图像渲染(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

有⼀幅以mxn的⼆维整数数组表⽰的图画image,其中image[i][j]表⽰该图画的像素值⼤⼩。
你也被给予三个整数sr,sc和newColor。你应该从像素image[sr][sc]开始对图像进⾏上⾊填充。
为了完成上⾊⼯作,从初始像素开始,记录初始坐标的上下左右四个⽅向上像素值与初始坐标相同的相连像素点,接着再记录这四个⽅向上符合条件的像素点与他们对应四个⽅向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜⾊值改为newColor。
最后返回经过上⾊渲染后的图像。
⽰例1:


输⼊:image=[[1,1,1],[1,1,0],[1,0,1]],sr=1,sc=1,newColor=2输出:[[2,2,2],[2,2,0],[2,0,1]]
解析:在图像的正中间,(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜⾊都被更改成2。
注意,右下⻆的像素没有更改为2,因为它不是在上下左右四个⽅向上与初始点相连的像素点。
⽰例2:
输⼊:image=[[0,0,0],[0,0,0]],sr=0,sc=0,newColor=2输出:[[2,2,2],[2,2,2]]

讲解算法原理

算法思路:

可以利⽤「深搜」或者「宽搜」,遍历到与该点相连的所有「像素相同的点」,然后将其修改成指定
的像素即可。递归函数设计:• 参数:
a. 原始矩阵;
b. 当前所在的位置;
c. 需要修改成的颜⾊。
• 函数体:
a. 先将该位置的颜⾊改成指定颜⾊(因为我们的判断,保证每次进⼊递归的位置都是需要修改的
位置);
b. 遍历四个⽅向上的位置:
▪ 如果当前位置合法,并且与初试颜⾊相同,就递归进去。

编写代码

c++算法代码:

class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int prev;
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, 
int color) {if(image[sr][sc] == color) return image;m = image.size(), n = image[0].size();prev = image[sr][sc];dfs(image, sr, sc, color);return image;}void dfs(vector<vector<int>>& image, int i, int j, int color){image[i][j] = color;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){dfs(image, x, y, color);}}}
};

java算法代码:

class Solution
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;int prev;public int[][] floodFill(int[][] image, int sr, int sc, int color) {if(image[sr][sc] == color) return image;m = image.length; n = image[0].length;prev = image[sr][sc];dfs(image, sr, sc, color);return image;}public void dfs(int[][] image, int i, int j, int color){image[i][j] = color;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){dfs(image, x, y, color);}}}
}

岛屿数量(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

给你⼀个由'1'(陆地)和'0'(⽔)组成的的⼆维⽹格,请你计算⽹格中岛屿的数量。岛屿总是被⽔包围,并且每座岛屿只能由⽔平⽅向和/或竖直⽅向上相邻的陆地连接形成。此外,你可以假设该⽹格的四条边均被⽔包围。
⽰例1:输⼊:grid=[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
输出:1
⽰例2:输⼊:grid=[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
输出:3

提⽰:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为'0'或'1'

讲解算法原理

算法思路:
遍历整个矩阵,每次找到「⼀块陆地」的时候:• 说明找到「⼀个岛屿」,记录到最终结果 ret ⾥⾯;

• 并且将这个陆地相连的所有陆地,也就是这块「岛屿」,全部「变成海洋」。这样的话,我们下次
遍历到这块岛屿的时候,它「已经是海洋」了,不会影响最终结果。

• 其中「变成海洋」的操作,可以利⽤「深搜」和「宽搜」解决,其实就是733.图像渲染这道题
这样,当我们,遍历完全部的矩阵的时候, ret 存的就是最终结果。
解法(dfs):
算法流程:

1. 初始化 ret = 0 ,记录⽬前找到的岛屿数量;2. 双重循环遍历⼆维⽹格,每当遇到⼀块陆地,标记这是⼀个新的岛屿,然后将这块陆地相连的陆地全部变成海洋。
递归函数的设计:
1. 把当前格⼦标记为⽔;
2. 向上、下、左、右四格递归寻找陆地,只有在下标位置合理的情况下,才会进⼊递归:
a. 下⼀个位置的坐标合理;
b. 并且下⼀个位置是陆地

编写代码

c++算法代码:

class Solution
{vector<vector<bool>> vis;int m, n;
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();vis = vector<vector<bool>>(m, vector<bool>(n));int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == '1'){ret++;dfs(grid, i, j);}}return ret;}int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};void dfs(vector<vector<char>>& grid, int i, int j){vis[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] 
== '1'){dfs(grid, x, y);}}}
};

java算法代码:

class Solution
{boolean[][] vis;int m, n;int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};public int numIslands(char[][] grid) {m = grid.length; n = grid[0].length;vis = new boolean[m][n];int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == '1'){ret++;dfs(grid, i, j);}}return ret;}public void dfs(char[][] grid, int i, int j){vis[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] 
== '1'){dfs(grid, x, y);}}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463063.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

教育技术革新:SpringBoot在线试题库系统开发

2 相关技术 2.1 Spring Boot框架简介 Spring Boot是由Pivotal团队提供的全新框架&#xff0c;其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置。通过这种方式&#xff0c;Sprin…

OTFS延迟多普勒信道模型(信道模型代码)

一、信道模型公式 1、延迟多普勒域信道模型 在一个M*N维的延迟多普勒域中&#xff0c;定义M为子载波数&#xff0c;子载波间隔为 对应倒数时隙长度为&#xff0c;信号总长度为,L-1表示最大径数。 公式中冲激响应延迟域移动的分辨率&#xff0c;如下图中Delay轴的一格也就是即,多…

Failed to search for file: Cannot update read-only repo

今天在读《Linux就该这么学》并上机操作RedHat Linux 8。结果在执行指令时却出现了问题: 我明明已经是root权限了&#xff0c;我于是上网去找&#xff0c;但也没看到合适的解答。为什么会和书上的操作结果不一样。 后来我突然意识到是不是我打了不该打的空格&#xff0c;于是…

Android中SurfaceView与GLSurfaceView 的关系

SurfaceView 与 GLSurfaceView 的关系 在 Android 开发中&#xff0c;SurfaceView 和 GLSurfaceView 是实现自定义渲染效果的关键组件。它们提供了不同的渲染方式&#xff0c;适用于不同的应用场景。我们将通过以下几个方面详细说明 SurfaceView 和 GLSurfaceView 的特点及实现…

游戏引擎中的颜色科学

游戏引擎中的渲染组件的作用是生成一个二维图片&#xff0c;在特定的时间从给定的视点观察的方向看到的一个三维空间的状态。他们的生成每一张图片都会被称为帧&#xff0c;他们生成的速度称为帧率。 像素 在每一帧中&#xff0c;游戏引擎的视觉输出基本上是一大堆彩色像素&a…

计算机网络-以太网小结

前导码与帧开始分界符有什么区别? 前导码--解决帧同步/时钟同步问题 帧开始分界符-解决帧对界问题 集线器 集线器通过双绞线连接终端, 学校机房的里面就有集线器 这种方式仍然属于共享式以太网, 传播方式依然是广播 网桥: 工作特点: 1.如果转发表中存在数据接收方的端口信息…

D56【python 接口自动化学习】- python基础之异常

day56 异常的产生与分类 学习日期&#xff1a;20241102 学习目标&#xff1a;模块与标准库 -- 72 初始异常&#xff1a;异常的产生与分类 学习笔记&#xff1a; 什么是异常 异常的分类 总结 引发异常时&#xff0c;代码会进行中断exception-所有内置的非系统退出类异常都派…

轴承性能对步进电机的影响

步进电机作为一种重要的电动机类型&#xff0c;在工业自动化、机器人技术以及各种机械设备中得到了广泛应用。步进电机的性能直接关系到其控制精度、响应速度和可靠性&#xff0c;而其中一个关键的组成部分——轴承&#xff0c;往往被认为是影响步进电机性能的一个重要因素。 一…

Java项目实战II基于Spring Boot的个人云盘管理系统设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 基于Spring Boot的个人云盘管理系统设计…

Java类和对象(上篇)

今天学习Java的类【认识类&#xff0c;并学习有关类的操作&#xff08;1.定义和使用 2.实例化 3. this引用 4.构造对象和初始化对象&#xff09;】 目录 1. 初步认知面向对象1.1 面向对象的概念1.1 面向对象和面向过程 2. 类定义和使用2.1 认识类2.2 类的定义格式2.3 练习2.3.1…

【路径——Dijkstra】

题目 代码 #include <bits/stdc.h> using namespace std; #define x first #define y second typedef pair<int, int> PII; const int N 2025, M N * N; int h[N], e[M], ne[M], w[M], idx; int dist[N]; int n 2021; void add(int a, int b, int c) {w[idx] …

ubuntu安装与配置Nginx(1)

在 Ubuntu 上安装和配置 Nginx 是相对简单的。以下是一个逐步指南&#xff1a; 1. 更新系统包 首先&#xff0c;确保你的系统是最新的。打开终端并运行&#xff1a; sudo apt update sudo apt upgrade2. 安装 Nginx 使用以下命令安装 Nginx&#xff1a; sudo apt install …

基于XSS的flash钓鱼上线Cobalt strike

题记 学习网安真是让人愉快啊&#xff0c;天天晚上睡觉之前都要想点技术问题&#xff0c;我是不是快魔怔了&#xff0c;今天打算搞XSS的flash钓鱼&#xff0c;完成一下写毕业论文的时候没有完成的事情。学习最有趣的地方就是在学习过程中发现新的不会的出现&#xff0c;下一个…

10.30.2024刷华为OD

文章目录 HJ20 密码验证合格程序&#xff08;难过全部例子 list取数左开有闭 [0,3) &#xff09;HJ21 简单密码HJ22 汽水瓶 (数学游戏...)HJ23 (dic就是map&#xff0c;注意怎么用&#xff0c; 善用values()和keys()函数返回list)语法知识记录 (留意转换的字符怎么拼接) HJ20 密…

安卓设备adb执行AT指令控制电话卡

文章目录 AT指令起源与发展&#xff1a;基本格式&#xff1a;常见应用领域及功能&#xff1a;不同设备中的应用&#xff1a; 安卓获取modem设备输入符入口安卓设备输入AT指令 AT指令 AT 指令是 Attention 的缩写&#xff0c;是一种用于控制调制解调器等通信设备的指令集。 起…

明日周刊-第26期

在昨晚的英雄联盟总决赛上&#xff0c;遗憾落败。少年终究还是没翻过最高的山&#xff0c;最长的河。虽然失败总是贯穿人生始终&#xff0c;但是你们还年轻&#xff0c;继续加油吧。 文章目录 1. 科技短讯OpenAI推出ChatGPT网络搜索Gemini AI接入谷歌地图&#x1f4f1;科技大厂…

(实战)WebApi第9讲:EFCore性能优化(IQueryable延迟查询、取消跟踪机制)

一、例子是第8讲的四、6&#xff08;EFCore的静态化处理 &#xff09;&#xff1a;分析ToList() ToList()在下图绿色框内。 二、在没有最终取数据的时候&#xff0c;使用 IQueryable<T> 延迟执行查询 &#xff08;1&#xff09;在没有最终取数据的时候&#xff0c;不要使…

三周精通FastAPI:29 定义在返回响应后运行的后台任务

官方文档&#xff1a;https://fastapi.tiangolo.com/zh/tutorial/background-tasks/ 后台任务 你可以定义在返回响应后运行的后台任务。 这对需要在请求之后执行的操作很有用&#xff0c;但客户端不必在接收响应之前等待操作完成。 包括这些例子&#xff1a; 执行操作后发…

Rust的enum枚举的强大用法

在Rust中&#xff0c;enum&#xff08;枚举&#xff09;是一种非常强大的类型&#xff0c;它可以包含多个变体&#xff08;variants&#xff09;&#xff0c;每个变体可以是不同的类型&#xff0c;包括复杂类型。这使得enum在Rust中不仅用于表示简单的状态或选项集合&#xff0…

Python世界:自动化办公Word之批量替换文本生成副本

Python世界&#xff1a;自动化办公Word之批量替换文本生成副本 任务背景编码思路代码实现相关参考 任务背景 为提高办公效率&#xff0c;用python试手了一个word任务&#xff0c;要求如下&#xff1a; 给你一个基础word文档A&#xff0c;格式为docx&#xff0c;名字为&#xf…