华为OD机试真题【寻找最大价值的矿堆】
1、题目描述
【寻找最大价值的矿堆】
给你一个由 ‘0’(空地)、’1’(银矿)、’2’(金矿)组成的的地图,
矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。
假设银矿价值1 ,金矿价值2,请你找出地图中最大价值的矿堆并输出该矿堆的价值。
**【输入描述】**地图元素信息如下:
22220
00000
00000
11111
地图范围最大 300*300
0<= 地图元素 <= 2
【输出描述】 矿堆的最大价值
8
【输入】
22220
00000
00000
01111
【输出】
8
【输入】
22220
00020
00010
01111
【输出】
15
2、解题思路
此题与【岛屿的最大面试】题类似,可用dfs回溯遍历的方法感染矩阵的位置即将符合题意的方向的1都变成0,统计需要多少次才能将矩阵中所有的值都变成0。
3、参考代码
import java.util.Arrays;
import java.util.Scanner;/*** @Author* @Date 2023/6/11 10:15*/
public class 寻找最大价值的矿堆 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int n = Integer.parseInt(in.nextLine());int[][] array = new int[n][];for (int col = 0; col < n; col++) {array[col] = Arrays.stream(in.nextLine().split("")).mapToInt(Integer::parseInt).toArray();}int maxValue = 0;// int maxSum = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < array[i].length; j++) {if (array[i][j] != 0) {maxValue = Math.max(maxValue, dfs(array, i, j));// maxSum = Math.max(maxSum, dfs(array, i, j, 0));}}}System.out.println(maxValue);//System.out.println(maxSum);}}// 方法一:public static int dfs(int[][] array, int i, int j) {if (i < 0 || j < 0 || i >= array.length || j >= array[i].length || array[i][j] == 0) {return 0;}int sum = array[i][j];array[i][j] = 0;sum += dfs(array, i + 1, j);sum += dfs(array, i - 1, j);sum += dfs(array, i, j + 1);sum += dfs(array, i, j - 1);return sum;}// 方法二:public static int[][] distances = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public static int dfs(int[][] array, int i, int j, int maxSum) {if (i < 0 || j < 0 || i >= array.length || j > array[i].length || array[i][j] == 0) {return maxSum;}maxSum += array[i][j];array[i][j] = 0;for (int[] dis : distances) {int newI = i + dis[0];int newJ = j + dis[1];if (newI < 0 || newJ < 0 || newI >= array.length || newJ >= array[newI].length || array[newI][newJ] == 0) {continue;}maxSum = dfs(array, newI, newJ, maxSum);}return maxSum;}}
4、相似题目
(1)岛屿的面积
//可以看图理解,在加上记住这个模板。public int maxAreaOfIsland(int[][] grid) {//定义一个表示岛屿的面积int max = 0;//这两个for循环是来遍历整张二维格上的所有陆地的。//i 表示行,j表示列for(int i = 0;i<grid.length;i++){for(int j = 0; j<grid[0].length;j++){//陆地的格if(grid[i][j]==1){//取出最大的面积max = Math.max(max,dfs(grid,i,j));} }}//返回最大的陆地面积return max;}public int dfs(int[][] grid,int i,int j){//当超出岛屿边界(上下左右)的时候,就直接退出,特别要加上当遍历到海洋的时候也要退出,if(i<0||j<0 || i>=grid.length || j>= grid[0].length|| grid[i][j]==0) return 0;//定义一个变量表示岛屿的面积,就是包含几个陆地int sum = 1;//将陆地改为海洋,防止重复陆地重复遍历。grid[i][j] =0;//遍历上方元素,每遍历一次陆地就加一sum += dfs(grid,i+1,j);//遍历下方元素sum +=dfs(grid,i-1,j);//遍历右边元素sum +=dfs(grid,i,j+1);//遍历左边元素sum += dfs(grid,i,j-1);return sum;}
相关文章:
华为OD机试真题【寻找最大价值的矿堆】
1、题目描述 【寻找最大价值的矿堆】 给你一个由 ‘0’(空地)、’1’(银矿)、’2’(金矿)组成的的地图, 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿…...
Java Maven 项目读取项目版本号
java读取 pom.xml 文件中设置的版本号 1. 在 src/main/resources/下新建 app.properties 文件: app.version${project.version} 2. 在pom.xml 中增加 <build> <resources> <resource> <directory>src/main/resources</di…...
Lesson4-1:OpenCV图像特征提取与描述---角点特征
学习目标 理解图像的特征知道图像的角点 1 图像的特征 大多数人都玩过拼图游戏。首先拿到完整图像的碎片,然后把这些碎片以正确的方式排列起来从而重建这幅图像。如果把拼图游戏的原理写成计算机程序,那计算机就也会玩拼图游戏了。 在拼图时ÿ…...
C++ 基础(一)题目练习
一、使用输出运算符输出一个长方形, 如下图所示: #include <iostream> using namespace std; int main() {cout << "*******" << endl;cout << "*******" << endl;cout << "*******"…...
Webpack5入门到原理
Webpack5学习 尚硅谷Webpack5新版视频教程 B站直达:https://www.bilibili.com/video/BV14T4y1z7sw 百度网盘:https://pan.baidu.com/s/114lJRGua2uHBdLq_iVLOOQ 提取码:yyds 阿里云盘:https://www.aliyundrive.com/s/UMkmCzdWsGh&…...
地形有通挂支隘险远六种情况
地形有通、挂、支、隘、险、远六种情况 【安志强趣讲《孙子兵法》第34讲】 第十一篇:地形篇 【全文大白话】 地形有各种情况,行军有各种情况,用好地形获得交战的主动权。 【原文】 孙子曰:地形有通者,有挂者࿰…...
C++多态案例-设计计算器类
1.前置知识点 多态是面向对象的三大特性之一 多态分为两类 静态多态:函数重载和运算符重载都属于静态多态,复用函数名动态多态:派生类和虚函数实现运行时多态 静态多态和动态多态的区别 静态多态的函数地址早绑定-----编译阶段确定函数地…...
复制tr的一行数据或者复制数据使用,使用jq和php
效果图: 2.Html <!--复制的tr数据,s----------------------------------------------------------------------------------------------->{foreach from$arrs keykk itemvv} <tr><td style"text-align:center;" >1</t…...
软件测试的基础(1)
程序员(开发) :编写程序代码(实现产品需求) 产品:收集并设计需求-需求文档(根据用户需求进行产品设计) UI设计师:设计界面,向外展示的形态 前端:用代码实现页面的显示 DBA:数据库设计(系统数据之间的关联) 运维:版本控制和发布、升级迭代,环境搭建和维护 客服:客户支持,…...
基于Java+SpringBoot+Vue前后端分离库存管理系统设计和实现
博主介绍:✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专…...
Secrets in Kubernetes (K8s)
摘要 在Kubernetes(K8s)中,Secrets是一种用于存储敏感数据的资源对象。它可以用于存储密码、API密钥、数据库凭证等敏感信息,以便在应用程序中使用。 设计实现说明如下: 加密存储:Kubernetes使用Base64编…...
模板测试和深度测试在cocoscreator中的应用
模板测试(Stencil Test): 当片段着色器处理完一个片段之后,模板测试(Stencil Test)会开始执行,和深度测试一样,它也可能会丢弃片段。接下来,被保留的片段会进入深度测试,它可能会丢弃更多的片段。模板测试…...
手机便签功能在哪里?如何在便签里添加文字图片视频?
手机已成为我们生活中不可或缺的工具,而在使用手机的过程中,我们经常需要随手记录一些重要的事情。那么,如何高效便捷地记录这些事情呢?答案就是使用手机便签软件。但是,有很多人不知道手机便签功能在哪里?…...
Java 中 List 的 7 种遍历方式 及 性能对比
# for i 循环 for (int i 0; i < list.size(); i) {list.get(i); }# 增强for循环 for (int item : list) { }# iterator for 循环 for (Iterator<Integer> iterator list.iterator(); iterator.hasNext(); ) {iterator.next(); }# iterator while 循环 Iterator<…...
【Github】git本地仓库建立与远程连接
文章目录 前言一、git简介二、git下载2.1下载地址 三、git安装3.1安装3.2 配置3.3 config设置(增删改查) 四.github与git连接——本地Git仓库4.1 建本地的版本库4.2 源代码放入本地仓库4.3提交仓库 五、github与git的连接——远程连接5.1 创建SSH Key5.2…...
【瑞萨零基础入门】瑞萨MCU零基础入门系列教程(更新连载中)
瑞萨MCU零基础入门系列教程 前言 得益于瑞萨强大的MCU、强大的软件开发工具(e studio),也得益于瑞萨和RA生态工作室提供的支持,我们团队编写了《ARM嵌入式系统中面向对象的模块编程方法》,全书37章,将近500页: 讲解面向对象编程…...
Bean 的生命周期总结
目录 一、Bean生命周期的五个阶段 Bean的初始化 二、PostConstruct 和 PreDestroy 各自的效果 三、 实例化和初始化的区别 四、为什么要先设置属性在进⾏初始化呢? 一、Bean生命周期的五个阶段 Java 中的公共类称之为 Bean 或 Java Bean,而 Spring 中的…...
【Python】环境的搭建
前言 要想能够进行 Python 开发, 就需要搭建好 Python 的环境. 需要安装的环境主要是两个部分: 运行环境: Python开发环境: PyCharm 一、安装 Python 1.找到官方网站 官网:Welcome to Python.org 2.找到下载页面 点击download中的Windows 3.选择稳定版中的Win…...
2021 ICPC 昆明 I Mr Main and Windmills(直线与线段的交点)
2021 ICPC 昆明 I Mr. Main and Windmills(直线与线段的交点) I Mr. Main and Windmills 大意:给出一条线段 , 一个人从线段的起点走到线段的终点 , 线段的一侧有若干风车 , 当前的人在线段上的每一个位置观察风车都会得到一个顺…...
SpringCloudAlibaba Gateway(一)简单集成
SpringCloudAlibaba Gateway(一)简单集成 随着服务模块的增加,一定会产生多个接口地址,那么客户端调用多个接口只能使用多个地址,维护多个地址是很不方便的,这个时候就需要统一服务地址。同时也可以进行统一认证鉴权的需求。那么服…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
Mac flutter环境搭建
一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
