首页 > 编程语言 >【综合算法学习】(第十五篇)

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

时间:2024-11-03 12:44:53浏览次数:7  
标签:int sr image dfs 学习 算法 grid && 第十五

目录

图像渲染(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);
 }
 }
 }
}

标签:int,sr,image,dfs,学习,算法,grid,&&,第十五
From: https://blog.csdn.net/weixin_73861555/article/details/143429179

相关文章

  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程,解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录106.从中序与后序遍历序列构造二叉树根据一棵树的中序遍历与后序遍历构造二叉树,假设树中没有重复的元素。提供参数:中序遍历数组inorder,后序遍历数组postorder主要操作:递归三要素1......
  • 蓝桥算法
    1.https://www.lanqiao.cn/problems/19954/learning/?contest_id=214这道题用快速幂直接秒,而快速幂就是求一个数的次方很大的时候,我们可以把指数分解为二进制的形式,再有a的b*c次方等于a的b次方乘以a的c次方,在用一个数存储一下即可。代码如下:defqui(x,y):res=1whiley:if......
  • 51单片机——蜂鸣器播放提示音(学习记录)
    踩过的坑!!!红外接收模块输出接口和独立按键k3共用的p32引脚,所以有红外的时候单片机会误以为按了k3按键,测试的时候要把红外接收拔掉,蜂鸣器连接的IO口是P25(江科的是P15),之前学习的时候看弹幕说型号选stc89c51rc2(但我这里的代码没改),就一直选的这个,蜂鸣器也能正常播放提示音,但到后......
  • 【算法-选择排序】挑挑拣拣,排出顺序——选择排序入门
    什么是选择排序?选择排序是一种比较简单直接的排序方式。想象你在打散一副牌,想按照大小顺序从小到大排列这些牌。你会怎么做?可能会先找出最小的那张,放在最前面,然后在剩下的牌里找第二小的,依次类推,这就是选择排序的基本思路!在程序中,选择排序的操作流程也类似:它逐步将未排序......
  • 《AI 算法的突破与挑战:探寻人工智能的核心驱动力》
    在当今科技飞速发展的时代,AI算法无疑是人工智能领域的核心驱动力,它的不断演进和突破正在重塑我们的世界。从简单的代码到如今令人惊叹的“智能大脑”,AI算法经历了漫长的发展历程,取得了诸多令人瞩目的成就,但同时也面临着一系列的挑战。一、AI算法的辉煌成就精度超越......
  • 布谷鸟优化算法:原理、案例与代码实现
    一、引言在优化算法的领域中,布谷鸟优化算法(CuckooSearchAlgorithm)以其独特的原理和高效的性能受到了广泛关注。它模拟了布谷鸟的繁殖行为和Levy飞行模式,为解决复杂的优化问题提供了一种新颖的途径。二、布谷鸟优化算法原理(一)布谷鸟繁殖行为模拟在自然界中,布谷鸟将......
  • 算法-图论-拓扑排序
    1.拓扑排序(卡码网117)fromcollectionsimportdeque,defaultdictdefmain():num_node,num_edge=map(int,input().split())inDegrees=[0for_inrange(num_node)]edges=defaultdict(list)for_inrange(num_edge):source,target=......
  • 2024-2025-1 20241412 《计算机基础与程序设计》第六周学习总结
    学期(如2024-2025-5)学号(如:20241404)《计算机基础与程序设计》第5周学习总结作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/homework/13276这个作......
  • floyed算法模板
    #include<bits/stdc++.h>#include<vector>usingnamespacestd;intlj[1010][1010];//邻接矩阵//可以换成链式前向星之类的巴拉巴拉,这里用邻接矩阵演示比较清楚intn,m;intflyd[1001][1001];intmain(){ cin>>n>>m; for(inti=1;i<=m;i++){ intu,v,w; cin>>u>>......