当前位置: 首页 > news >正文

华为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’&#xff08;空地&#xff09;、’1’&#xff08;银矿&#xff09;、’2’&#xff08;金矿&#xff09;组成的的地图&#xff0c; 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿…...

Java Maven 项目读取项目版本号

java读取 pom.xml 文件中设置的版本号 1. 在 src/main/resources/下新建 app.properties 文件&#xff1a; app.version${project.version} 2. 在pom.xml 中增加 <build> <resources> <resource> <directory>src/main/resources</di…...

Lesson4-1:OpenCV图像特征提取与描述---角点特征

学习目标 理解图像的特征知道图像的角点 1 图像的特征 大多数人都玩过拼图游戏。首先拿到完整图像的碎片&#xff0c;然后把这些碎片以正确的方式排列起来从而重建这幅图像。如果把拼图游戏的原理写成计算机程序&#xff0c;那计算机就也会玩拼图游戏了。 在拼图时&#xff…...

C++ 基础(一)题目练习

一、使用输出运算符输出一个长方形&#xff0c; 如下图所示&#xff1a; #include <iostream> using namespace std; int main() {cout << "*******" << endl;cout << "*******" << endl;cout << "*******"…...

Webpack5入门到原理

Webpack5学习 尚硅谷Webpack5新版视频教程 B站直达&#xff1a;https://www.bilibili.com/video/BV14T4y1z7sw 百度网盘&#xff1a;https://pan.baidu.com/s/114lJRGua2uHBdLq_iVLOOQ 提取码&#xff1a;yyds 阿里云盘&#xff1a;https://www.aliyundrive.com/s/UMkmCzdWsGh&…...

地形有通挂支隘险远六种情况

地形有通、挂、支、隘、险、远六种情况 【安志强趣讲《孙子兵法》第34讲】 第十一篇&#xff1a;地形篇 【全文大白话】 地形有各种情况&#xff0c;行军有各种情况&#xff0c;用好地形获得交战的主动权。 【原文】 孙子曰&#xff1a;地形有通者&#xff0c;有挂者&#xff0…...

C++多态案例-设计计算器类

1.前置知识点 多态是面向对象的三大特性之一 多态分为两类 静态多态&#xff1a;函数重载和运算符重载都属于静态多态&#xff0c;复用函数名动态多态&#xff1a;派生类和虚函数实现运行时多态 静态多态和动态多态的区别 静态多态的函数地址早绑定-----编译阶段确定函数地…...

复制tr的一行数据或者复制数据使用,使用jq和php

效果图&#xff1a; 2.Html <!--复制的tr数据&#xff0c;s----------------------------------------------------------------------------------------------->{foreach from$arrs keykk itemvv} <tr><td style"text-align:center;" >1</t…...

软件测试的基础(1)

程序员(开发) :编写程序代码(实现产品需求) 产品:收集并设计需求-需求文档(根据用户需求进行产品设计) UI设计师:设计界面,向外展示的形态 前端:用代码实现页面的显示 DBA:数据库设计(系统数据之间的关联) 运维:版本控制和发布、升级迭代,环境搭建和维护 客服:客户支持,…...

基于Java+SpringBoot+Vue前后端分离库存管理系统设计和实现

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专…...

Secrets in Kubernetes (K8s)

摘要 在Kubernetes&#xff08;K8s&#xff09;中&#xff0c;Secrets是一种用于存储敏感数据的资源对象。它可以用于存储密码、API密钥、数据库凭证等敏感信息&#xff0c;以便在应用程序中使用。 设计实现说明如下&#xff1a; 加密存储&#xff1a;Kubernetes使用Base64编…...

模板测试和深度测试在cocoscreator中的应用

模板测试(Stencil Test)&#xff1a; 当片段着色器处理完一个片段之后&#xff0c;模板测试(Stencil Test)会开始执行&#xff0c;和深度测试一样&#xff0c;它也可能会丢弃片段。接下来&#xff0c;被保留的片段会进入深度测试&#xff0c;它可能会丢弃更多的片段。模板测试…...

手机便签功能在哪里?如何在便签里添加文字图片视频?

手机已成为我们生活中不可或缺的工具&#xff0c;而在使用手机的过程中&#xff0c;我们经常需要随手记录一些重要的事情。那么&#xff0c;如何高效便捷地记录这些事情呢&#xff1f;答案就是使用手机便签软件。但是&#xff0c;有很多人不知道手机便签功能在哪里&#xff1f;…...

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设置&#xff08;增删改查&#xff09; 四.github与git连接——本地Git仓库4.1 建本地的版本库4.2 源代码放入本地仓库4.3提交仓库 五、github与git的连接——远程连接5.1 创建SSH Key5.2…...

【瑞萨零基础入门】瑞萨MCU零基础入门系列教程(更新连载中)

瑞萨MCU零基础入门系列教程 前言 得益于瑞萨强大的MCU、强大的软件开发工具(e studio)&#xff0c;也得益于瑞萨和RA生态工作室提供的支持&#xff0c;我们团队编写了《ARM嵌入式系统中面向对象的模块编程方法》&#xff0c;全书37章&#xff0c;将近500页: 讲解面向对象编程…...

Bean 的生命周期总结

目录 一、Bean生命周期的五个阶段 Bean的初始化 二、PostConstruct 和 PreDestroy 各自的效果 三、 实例化和初始化的区别 四、为什么要先设置属性在进⾏初始化呢&#xff1f; 一、Bean生命周期的五个阶段 Java 中的公共类称之为 Bean 或 Java Bean&#xff0c;而 Spring 中的…...

【Python】环境的搭建

前言 要想能够进行 Python 开发, 就需要搭建好 Python 的环境. 需要安装的环境主要是两个部分: 运行环境: Python开发环境: PyCharm 一、安装 Python 1.找到官方网站 官网&#xff1a;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 大意&#xff1a;给出一条线段 &#xff0c; 一个人从线段的起点走到线段的终点 &#xff0c; 线段的一侧有若干风车 &#xff0c; 当前的人在线段上的每一个位置观察风车都会得到一个顺…...

SpringCloudAlibaba Gateway(一)简单集成

SpringCloudAlibaba Gateway(一)简单集成 随着服务模块的增加&#xff0c;一定会产生多个接口地址&#xff0c;那么客户端调用多个接口只能使用多个地址&#xff0c;维护多个地址是很不方便的&#xff0c;这个时候就需要统一服务地址。同时也可以进行统一认证鉴权的需求。那么服…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...