【华为OD机考】统计监控、需要打开多少监控器(JAVA题解——也许是全网最优)

前言

本人是算法小白,甚至也没有做过Leetcode。所以,我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。

题干

OD,B 卷 100 分题目【OD 统一考试(B 卷)】

1. 题目描述

某长方形停车场每个车位上方都有一个监控器,只有当当前车位或者前后左右四个方向任意一个车位范围停有车时,监控器才需要打开。给定某一时刻停车场的停车分布,请统计最少需要打开多少个监控器。

2. 输入描述

第一行输入m和n,表示停车场的长和宽。满足条件1 < m, n <= 20。
接下来的m行,每行包含n个整数(0或1),表示该行停车位的情况。其中0表示空位,1表示已停车。

3. 输出描述

输出最少需要打开的监控器数量

4. 示例

示例一:
输入:

3 3
0 0 0
0 1 0
0 0 0

输出:

5

示例二:
输入:

3 3
1 0 0
0 1 0
0 0 0

输出:

6

解答

说实在,我刚看到题干的时候是有点懵的,有点读不清楚题目的意思。接着我看了【示例】的输入输出之后,更加懵逼了。就算看了答案,我还是不知所云。后面拿着题干去百度,再反复思考,才理清了其中缘由,哎,其实是我自己想复杂了(有点挫败)。
我自己反思了一下,为什么我会读不清楚题目意思:

  1. 我当时读原题的时候,脑子不自觉就浮现出了停车场模型
  2. 我看原题的时候,那个博主也给了一张停车场鸟瞰图,加深了我的”刻板印象“。看着这张图,我一下子理解不了【每个车位上方都有一个监控器】的意思了(我哭死)
  3. 第一次接触机考,所以我不懂得结合输入、输出描述去理解题干
    在这里插入图片描述

解题思路

大家抛开对停车场的固有印象,也不要去看上面那张鸟瞰图,就用最原始的【面向过程】的想法去看题目。通过读题干,我们可以得到以下条件:

  1. 停车场是长方形的,并且长、宽的限制为1 < m, n <= 20(那不就是一个二维数组嘛)
  2. 每个车位上方都有一个监控器(所以,整个停车场总共有 m * n个监控器)
  3. 监控需要打开的条件:【当前停车位有车】或者【前后左右至少有一辆车】时

代码示例

public class StatisticalMonitors {/*** m、n的范围。 1< m,n <= 20*/static final int MAX_COUNT = 20 + 1 + 1;/*** 【前、后、左、右】的坐标变化量* 用来索引当前节点【前、后、左、右】的目标位置*/static final int AROUND[][] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};public static void main(String[] args) {int row = 0, column = 0;int[][] parkingLot = new int[MAX_COUNT][MAX_COUNT];// 读入数据Scanner scanner = new Scanner(System.in);row = scanner.nextInt();column = scanner.nextInt();for (int r = 1; r <= row; r++) {for (int c = 1; c <= column; c++) {parkingLot[r][c] = scanner.nextInt();}}// 统计数量int monitorCount = 0;for (int r = 1; r <= row; r++) {for (int c = 1; c <= column; c++) {// 当前节点有车,直接返回int status = parkingLot[r][c];if (status == 1) {monitorCount++;continue;}// 没车,看看四周boolean b = checkAround(parkingLot, r, c);if (b) {monitorCount++;}}}System.out.println("停车场至少需要的监控数目:" + monitorCount);}/*** 检查当前四周(前、后、左、右)有没有车停靠** @return true-有车;false-没有车*/private static boolean checkAround(int[][] parkingLot, int curRow, int curColumn) {for (int[] ints : AROUND) {int newRow = curRow + ints[0];int newColumn = curColumn + ints[1];int status = parkingLot[newRow][newColumn];if (status == 1) {return true;}}return false;}
}

代码解读:
整体代码都很简单,我相信看我上面的代码估计也知道啥意思了。有一些需要特别声明的点:

  1. 我新增了一个二维数组AROUND用来快速锚定当前位置的【前后左右】位置的坐标,并且为此改变了长宽条件变量MAX_COUNT的值(20 -> 20 + 1 + 1,下面我会解释为什么我要这么写)
  2. 我在读取数据的for循环区间是[1, m]而不是[0, m),这是为了方便索引(相当于把坐标整体往右下角移动了)。毕竟停车场边缘是坐标周围的坐标不好索引,需要做额外判断。这也是为什么,我要在MAX_COUNT = 20 + 1 + 1的原因。其中,20表示条件中说的长、宽范围;后面的1 + 1表示的语义如下:
    • 第一个1:整体往右下角移动
    • 第二个1:则是为了避免过多的安全判断。使当前节点周围节点可以索引。如果没有这个的话,那么在判断停车场边缘节点(即:数组边缘)的时候,为了防止数组越界,需要做额外的安全判断
      在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Kafka快速实战以及基本原理详解

这一部分主要是接触 Kafka &#xff0c;并熟悉 Kafka 的使用方式。快速熟练的搭建 kafka 服务&#xff0c;对于快速验证一些基于Kafka 的解决方案&#xff0c;也是非常有用的。 一、 Kafka 介绍 ChatGPT 对于 Apache Kafka 的介绍&#xff1a; 1 、 MQ 的作用 MQ &#xff1a;…

网络原理 - 详解

一&#xff0c;网络通信基础 1.1 IP地址 描述一个设备在网络上的地址&#xff0c;一般使用4个0~255之间的数字&#xff0c;并且使用三给 . 进行分割&#xff0c;如&#xff1a;127.0.0.0 1.2 端口号 端口号是一个2个字节的整数&#xff0c;用来区分一个主机上的不同应用程序…

No168.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

Docker linux 安装

sudo yum update sudo yum clean all sudo yum makecache#安装依赖 sudo yum install -y yum-utils device-mapper-persistent-data lvm2 #添加官方存储库 sudo yum-config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo#安装-跳过一些异常依赖…

阿里云轻量应用服务器有月流量限制吗?

阿里云轻量应用服务器限制流量吗&#xff1f;部分限制&#xff0c;2核2G3M和2核4G4M这两款轻量应用服务器不限制月流量&#xff0c;其他的轻量服务器套餐有月流量限制。 腾讯云轻量应用服务器价格便宜&#xff0c;活动页面&#xff1a;aliyunbaike.com/go/tencent 细心的同学看…

HTML5+CSS3+移动web 前端开发入门笔记(二)HTML标签详解

HTML标签&#xff1a;排版标签 排版标签用于对网页内容进行布局和样式的调整。下面是对常见排版标签的详细介绍&#xff1a; <h1>: 定义一级标题&#xff0c;通常用于标题栏或页面主要内容的标题。<p>: 定义段落&#xff0c;用于将文字分段展示&#xff0c;段落之…

办公技巧:Excel日常高频使用技巧

目录 1. 快速求和&#xff1f;用 “Alt ” 2. 快速选定不连续的单元格 3. 改变数字格式 4. 一键展现所有公式 “CTRL ” 5. 双击实现快速应用函数 6. 快速增加或删除一列 7. 快速调整列宽 8. 双击格式刷 9. 在不同的工作表之间快速切换 10. 用F4锁定单元格 1. 快速求…

CSS学习笔记

目录 1.CSS简介1.什么是CSS2.为什么使用CSS3.CSS作用 2.基本用法1.CSS语法2.CSS应用方式1. 内部样式2.行内样式3.外部样式1.使用 link标签 链接外部样式文件2.import 指令 导入外部样式文件3.使用举例 3.选择器1.基础选择器1.标签选择器2.类选择器3.ID选择器4.使用举例 2.复杂选…

计算机视觉: 基于隐式BRDF自编码器的文生三维技术

论文链接: MATLABER: Material-Aware Text-to-3D via LAtent BRDF auto-EncodeR 背景 得益扩散模型和大量的text - image 成对的图片&#xff0c; 现在文生2D的模型已经比较成熟的框架和模型&#xff0c;主流的技术比如说stable diffusion 和 midjourney 以及工业领域runway 等…

ElasticSearch环境准备

Elasticsearch 是一个基于 Apache Lucene™ 的开源搜索引擎。不仅仅是一个全文搜索引擎&#xff0c;它还是一个分布式的搜索和分析引擎&#xff0c;可扩展并能够实时处理大数据。以下是关于 Elasticsearch 的一些主要特点和说明&#xff1a; 1.实时分析&#xff1a;Elasticsear…

反爬虫机制与反爬虫技术(一)

反爬虫机制与反爬虫技术一 1、网络爬虫的法律与道德问题2、反爬虫机制与反爬虫技术2.1、User-Agent伪装2.2、代理IP2.3、请求频率控制2.4、动态页面处理2.5、验证码识别3、反爬虫案例:豆瓣电影Top250爬取3.1、爬取目标3.2、库(模块)简介3.3、翻页分析3.4、发送请求3.5、数据…

【Solidity】智能合约案例——①食品溯源合约

目录 一、合约源码分析&#xff1a; 二、合约整体流程&#xff1a; 1.部署合约 2.管理角色 3.食品信息管理 4.食品溯源管理 一、合约源码分析&#xff1a; Producer.sol:生产者角色的管理合约&#xff0c;功能为&#xff1a;添加新的生产者地址、移除生产者地址、判断角色地址…

基于支持向量机SVM和MLP多层感知神经网络的数据预测matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 一、支持向量机&#xff08;SVM&#xff09; 二、多层感知器&#xff08;MLP&#xff09; 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 .…

vue3前端开发-flex布局篇

文章目录 1.传统布局与flex布局优缺点传统布局flex布局建议 2. flex布局原理2.1 布局原理 3. flex常见属性3.1 父项常见属性3.2 子项常见属性 4.案例实战(携程网首页) 1.传统布局与flex布局优缺点 传统布局 兼容性好布局繁琐局限性&#xff0c;不能再移动端很好的布局 flex布…

C++深入学习part_1

Linux下编译C程序 安装g命令&#xff1a;sudo apt install g 编译命令&#xff1a;$ g *.cc 或者 *.cpp -o fileName; hellworld 编译程序可以看到&#xff1a; namespace命名空间 首先&#xff0c;命名空间的提出是为了防止变量重名冲突而设置的。 浅浅试一下&#xff1…

漏洞复现-易思无人值守智能物流文件上传

免责声明&#xff1a; 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直…

STC89C51基础及项目第10天:LCD显示字符(非标协议外设)

1. 初识LCD1602&#xff08;233.79&#xff09; 非标协议外设 LCD1602显示 LCD1602&#xff08;Liquid Crystal Display&#xff09;是一种工业字符型液晶&#xff0c;能够同时显示 1602 即 32 字符(16列两行) 引脚说明 第 1 脚&#xff1a; VSS 为电源地第 2 脚&#xff1…

Unity AI Sentis 基础教程

Unity AI Sentis基础教程 Unity AI Sentis基础教程Unity AI 内测资格申请Unity 项目Package Manager开始尝试模型下载识别图片完整代码代码搭载运行 射线绘画 URP&#xff08;扩展&#xff09;射线绘画脚本脚本搭载效果 Sentis 是 AI 模型的本地推理引擎&#xff0c;它利用最终…

3D孪生场景搭建:模拟仿真

前面几期文章介绍如何使用NSDT 编辑器 搭建3D应用场景&#xff0c;本期介绍下孪生场景中一个一个非常重要的功能&#xff1a;模拟仿真。 1、什么是模拟仿真 模拟仿真是一种用于描述、分析和模拟现实世界中系统、过程或事件的计算机模型和程序。仿真通过输入各种参数和条件&am…

【iOS】——仿写计算器

文章目录 一、实现思路二、实现方法三、判错处理 一、实现思路 先搭建好MVC框架&#xff0c;接着在各个模块中实现各自的任务。首先要创建好UI界面&#xff0c;接着根据UI界面的元素来与数据进行互动&#xff0c;其中创建UI界面需要用到Masonry布局。 二、实现方法 在calcu…