牛客 2024春招冲刺题单 ONT82 腐烂的苹果【中等 BFS Java,Go】

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34

思路

	广度优先搜索。首先找到2坐标集合,然后每次往四周为1的坐标扩展

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param grid int整型ArrayList<ArrayList<>>
     * @return int整型
     */
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        //BFS
        int n = grid.size();
        int m = grid.get(0).size();

        Queue<Integer> q2 = new LinkedList<>();

        int total1 = 0; //正常的苹果个数
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m ; j++) {
                if (grid.get(i).get(j) == 2) {
                    q2.add(i * m + j);
                }
                if (grid.get(i).get(j) == 1) {
                    total1++;
                }
            }
        }


        int[] dirx = {-1, 1, 0, 0};
        int[] diry = {0, 0, -1, 1};
        int deep = 0;
        int change2 = 0; //变为腐烂的苹果的个数
        while (!q2.isEmpty()) {
            int size = q2.size();
            for (int i = 0; i < size ; i++) {
                int xy = q2.poll();
                int x1 = xy / m; //横坐标
                int y1 = xy % m; //纵坐标

                for (int j = 0; j < 4 ; j++) {
                    int x2 = x1 + dirx[j];
                    int y2 = y1 + diry[j];

                    if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && grid.get(x2).get(y2) == 1) {
                        q2.add(x2 * m + y2);
                        change2++;
                        grid.get(x2).set(y2, 2);
                    }
                }
            }

            deep++;
        }


        if (change2 != total1) return -1; //正常的苹果没有全部腐烂,返回-1
        return deep - 1;
    }
}

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param grid int整型二维数组
 * @return int整型
 */
func rotApple(grid [][]int) int {
	// BFS
	n := len(grid)
	m := len(grid[0])
	total1 := 0   //正常的苹果个数
	q2 := []int{} //切片模拟队列

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 2 {
				q2 = append(q2, i*m+j)
			}

			if grid[i][j] == 1 {
				total1++
			}
		}
	}

	change2 := 0 //正常苹果变为腐烂苹果的个数
	deep := 0

	dirx := []int{-1, 1, 0, 0}
	diry := []int{0, 0, -1, 1}
	for len(q2) > 0 {
		size := len(q2)
		q2new := []int{}
		for i := 0; i < size; i++ {
			xy := q2[i]
			x1 := xy / m //xy对应的 横坐标
			y1 := xy % m //xy对应的纵坐标

			for j := 0; j < 4; j++ {
				x2 := x1 + dirx[j]
				y2 := y1 + diry[j]

				if x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && grid[x2][y2] == 1 {
					grid[x2][y2] = 2
					change2++
					q2new = append(q2new, x2*m+y2)
				}
			}
		}
		q2 = q2new
		deep++
	}

	if change2 != total1 {
		return -1
	}

	return deep - 1
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

RAG基础知识及应用

简单介绍下RAG的基础知识和RAG开源应用 “茴香豆" 一. RAG 基础知识 1. RAG工作原理 RAG是将向量数据库和大模型问答能力的有效结合&#xff0c;从而达到让大模型的知识能力增加的目的。首先将知识源存储在向量数据库中&#xff0c;当提出问题时&#xff0c;去向量数据库…

客户案例丨拓数派向量计算引擎PieCloudVector助力东吴证券AIGC应用升级

1.项目背景 随着人工智能技术的不断创新和应用&#xff0c;我们可以看到人工智能在各个领域的应用越来越广泛。深度学习技术在图像识别、语音识别、自然语言处理等领域表现出色。机器学习算法的改进将解决更多实际问题&#xff0c;如增强学习、迁移学习和联合学习等&#xff…

学生用什么品牌的台灯好,学生护眼台灯推荐品牌

在童年的岁月里&#xff0c;我们常常无知于如何正确地使用眼睛&#xff0c;对于何种光线最有益眼睛健康也缺乏了解。这些年轻时的疏忽&#xff0c;如今在我的眼镜度数上得到了反映&#xff0c;近视已接近千度&#xff0c;这是许多同样经历的视友都能共鸣的体验。随着时间的推移…

MoonBit 最新动态:MoonBit 引入实验性的测试覆盖率统计工具

MoonBit更新 支持 array.iter intrinsic 并且已经对标准库中的函数进行标注&#xff0c;从而可以在特定情况下将循环进行内联&#xff0c;以提升运行效率 /// intrinsic %array.iter pub fn iter[T](self : Array[T], f : (T) -> Unit) -> Unit {for i 0; i < self…

pymilvus创建IVF_FLAT向量索引

索引简介 索引的作用是加速大型数据集上的查询。 目前&#xff0c;向量字段仅支持一种索引类型&#xff0c;即只能创建一个索引。 milvus支持的向量索引类型大部分使用近似最近邻搜索算法(ANNS,approximate nearest neighbors search) 。ANNS 的核心思想不再局限于返回最准确…

棋牌室计时吧台计费收费灯控管理系统软件操作流程

棋牌室计时吧台计费收费灯控管理系统软件操作流程 一、前言 以下软件操作教程以&#xff0c;佳易王棋牌桌球计时计费管理系统软件灯控版V17.87为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 该计时计费软件可以是棋牌和桌球混合同时计时计费 …

uniapp:Hbuilder没有检测到设备请插入设备或启动模拟器的问题解决

问题 使用模拟器调试运行项目时&#xff0c;出现以下提示&#xff0c;“没有检测到设备&#xff0c;请插入设备或启动模拟器后点击刷新再试”。排查了一天最终找到原因。 解决 已确认模拟器是已经正常启动&#xff0c;并且Hbuilder设置中的adb路径和端口都配置没有问题&#…

123124

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…

如何挂载img镜像以及lvm分区

上一章节&#xff0c;我在win10下利用qemu安装了一个aarch64的 kylin-server-v10的ISO系统镜像包。安装时将系统安装到了虚拟硬盘kylin-server-v10.img 里&#xff0c;现在有个需求&#xff0c;要读出kylin-server-v10.img中文件系统的内容。 通过fdisk命令可以看到 kylin-ser…

element-ui drawer 组件源码分享

今日简单分享 drawer 组件的源码实现&#xff0c;从以下五个方面来分享&#xff1a; 1、drawer 组件页面结构 2、drawer 组件属性 3、drawer 组件 slot 4、drawer 组件方法 5、drawer 组件事件 一、drawer 组件页面结构 二、drawer 组件属性 2.1 append-to-body 属性&am…

vulhub之fastjson篇-1.2.27-rce

一、启动环境 虚拟机:kali靶机:192.168.125.130/172.19.0.1(docker地址:172.19.0.2) 虚拟机:kali攻击机:192.168.125.130/172.19.0.1 本地MAC:172.XX.XX.XX 启动 fastjson 反序列化导致任意命令执行漏洞 环境 1.进入 vulhub 的 Fastjson 1.2.47 路径 cd /../../vulhub/fa…

vue前端项目到后端执行逻辑——自己改的话要怎么改

文章目录 vue前端项目到后端流程——自己改的话要怎么改 vue前端项目到后端流程——自己改的话要怎么改

外部模块介绍(七) 蓝牙HC05

HC05原理图 2. 蓝牙模块的调试 2.1 两种工作模式: HC-05蓝牙串口通讯模块具有两种工作模式:命令响应工作模式和自动连接工作模式。在自动连接工作模式下模块又可分为主(Master)、从(Slave)和回环(Loopback)三种工作角色。 当模块处于自动连接工作模式时,将自动根据事…

深入解析template,掌握C++模板的精髓!

掌握C模板&#xff08;template&#xff09;的优雅之道&#xff01; 一、什么是模板&#xff1f;二、模板如何工作&#xff1f;三、C 中的模板类型3.1、 类模板3.2、 函数模板 四、模板参数推导4.1、模板参数推导示例4.2、函数模板参数推导4.3、类模板参数推导&#xff08;C17 …

Spring 源码学习笔记(二)之Bean标签默认属性的解析

分析调用栈 Spring 通过读取 xml 配置文件注册 bean &#xff0c;通过工厂可以获取注册的 bean&#xff0c;示例代码&#xff1a; XmlBeanFactory beanFactory new XmlBeanFactory(new ClassPathResource("applicationContext.xml")); Object main beanFactory.g…

通过网络api获取日期对应的节假日信息

网络接口获取链接&#xff1a;免费节假日API_原百度节假日API HolidayJudge.h #pragma once#include <QtWidgets/QWidget> #include "ui_HolidayJudge.h"enum DATESTATE {WORK0,//工作日DAYOFF,//休息日HOLIDAY//节假日 };class HolidayJudge : public QWidg…

F5防火墙如何应对恶意攻击?一文搞懂

当前&#xff0c;5G网络模糊了安全防护边界&#xff0c;加速了全球网络攻击升级&#xff0c;攻防对抗变得日益激烈&#xff0c;导致传统网络安全防护措施越来越难以有效预测和应对潜在威胁。面对复杂部署环境&#xff0c;企业的安全团队正在努力寻找一致性的安全防护和可见性策…

谷歌浏览器用不了怎么办?

打开谷歌浏览器点击右上角的三个点 &#xff0c; 点击设置 在搜索引擎里面把这个改成百度 然后越狱登录你的谷歌账号就可以用了 我个人用的越狱软件是r2rayn &#xff0c; 浏览器上面可以搜索的 默认浏览器那里可以设置成谷歌

IP网络对讲广播系统审计

前言 这个系统是前两年在一个内网遇到的&#xff0c;当时顺手试了一个admin登陆之后再没有然后了&#xff0c;最近发现有大佬分享关于这个系统的漏洞&#xff0c;于是就把自己当初看的几个漏洞分享一下&#xff0c;系统比较简单&#xff0c;漏洞点很多&#xff0c;不要做坏事哦…

C++练级之路——类和对象(上)

1、类的定义 class 类名{//成员函数 //成员变量}; class为定义的关键字&#xff0c;{ }内是类的主体&#xff0c;注意后面的 ; 不要忘了 类体中的内容成为类的成员&#xff0c;类中的变量为成员变量或类的属性&#xff0c;类中的函数为成员函数或类的方法&#xff0c; 类的两种…