华为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(一)简单集成 随着服务模块的增加,一定会产生多个接口地址,那么客户端调用多个接口只能使用多个地址,维护多个地址是很不方便的,这个时候就需要统一服务地址。同时也可以进行统一认证鉴权的需求。那么服…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
