【华为OD机考B卷 | 100分】统计监控、需要打开多少监控器(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 < m, n <= 20
(那不就是一个二维数组嘛) - 每个车位上方都有一个监控器(所以,整个停车场总共有
m * n
个监控器) - 监控需要打开的条件:【当前停车位有车】或者【前后左右至少有一辆车】时
代码示例
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;}
}
代码解读:
整体代码都很简单,我相信看我上面的代码估计也知道啥意思了。有一些需要特别声明的点:
- 我新增了一个二维数组
AROUND
用来快速锚定当前位置的【前后左右】位置的坐标,并且为此改变了长宽条件变量MAX_COUNT
的值(20 -> 20 + 1 + 1
,下面我会解释为什么我要这么写) - 我在读取数据的
for
循环区间是[1, m]
而不是[0, m)
,这是为了方便索引(相当于把坐标整体往右下角移动了)。毕竟停车场边缘是坐标周围的坐标不好索引,需要做额外判断。这也是为什么,我要在MAX_COUNT = 20 + 1 + 1
的原因。其中,20
表示条件中说的长、宽范围;后面的1 + 1
表示的语义如下:- 第一个
1
:整体往右下角移动 - 第二个
1
:则是为了避免过多的安全判断。使当前节点周围节点可以索引。如果没有这个的话,那么在判断停车场边缘节点(即:数组边缘)的时候,为了防止数组越界,需要做额外的安全判断
- 第一个
相关文章:

【华为OD机考B卷 | 100分】统计监控、需要打开多少监控器(JAVA题解——也许是全网最详)
前言 本人是算法小白,甚至也没有做过Leetcode。所以,我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。 题干 OD,B 卷 100 分题目【OD 统一考试(B 卷)】 1. 题目描述 某长方形停车场每个车位上方都有一个监控…...

Python Django 详解(基础)
文章目录 1 概述1.1 安装 django1.2 创建 django 项目1.3 创建 app 2 启动 Django2.1 settings.py:注册 app2.2 view.py:URL和视图对应2.3 启动 Django2.4 访问 3 快速上手3.1 templates:html 模板3.2 static:静态文件3.3 模板语法…...

C语言内存函数
目录 memcpy(Copy block of memory)使用和模拟实现memcpy的模拟实现 memmove(Move block of memory)使用和模拟实现memmove的模拟实现: memset(Fill block of memory)函数的使用扩展 memcmp(Compare two blocks of memory)函数的使用 感谢各位大佬对我的支持,如果我的文章对你有…...
【Docker】Docker-compose及Consul多容器编排工具
使用一个Dockerfile模版文件可以定义一个单独的应用容器,当需要定义多个容器时就需要编排 docker swarm(管理跨节点) 编排工具——docker compose Dockerfile可以让用户管理一个单独的应用容器;而Compose则允许用户在一个模板&…...
Unity网络同步方案帧同步和状态同步
网络同步方案 介绍开始我们使用的状态同步(实时状态同步)后来采用的帧同步 状态同步优点缺点 帧同步顺序执行追帧重连优点缺点 总结 这两年做的都是帧同步和状态同步的项目,正好最近有时间总结一下什么是帧同步和状态同步,之前在做…...

【Monorepo实战】pnpm+turbo+vitepress构建公共组件库文档系统
Monorepo架构可以把多个独立的系统放到一起联调,本文记录基于pnpm > workspace功能,如何构建将vitepress和组件库进行联调,并且使用turbo进行任务顺序编排。 技术栈清单: pnpm 、vitepress 、turbo 一、需求分析 1、最终目标…...

CentOS 编译安装Redis
一、编译配置hiredis.h C来操作redis数据库。通过hiredis接口来实现,目前只能在Linux环境使用。 下载hiredis.h hiredis的下载地址为:https://github.com/redis/hiredis 解压并编译hiredis [rootlocalhost source_code]# pwd /usr/local/source_…...

可拓展的低代码全栈框架
尽管现在越来越多的人开始对低代码开发感兴趣,但已有低代码方案的局限性仍然让大家有所保留。其中最常见的担忧莫过于低代码缺乏灵活性以及容易被厂商锁定。 显然这样的担忧是合理的,因为大家都不希望在实现特定功能的时候才发现低代码平台无法支持&…...
C++11 智能指针
目录 智能指针 异常导致执行流乱跳 智能指针解决问题 auto_ptr unique_ptr sharded_ptr weak_ptr 智能指针 由于C11引入异常之后,执行流乱跳,所以导致之前 malloc/new 的空间很容易没有被释放,导致内存泄露问题。 所以这时候&#x…...

二、WebGPU阶段间变量(inter-stage variables)
二、WebGPU阶段间变量(inter-stage variables) 在上一篇文章中,我们介绍了一些关于WebGPU的基础知识。在本文中,我们将介绍阶段变量(inter-stage variables)的基础知识。 阶段变量在顶点着色器和片段着色…...
【Linux】31个普通信号
文章目录 1.每种信号的含义2.两种不能被忽略的信号3.两种不能被捕捉的信号 1.每种信号的含义 信号编号信号名信号含义1SIGHUP如果终端接口检测到一个连接断开,则会将此信号发送给与该终端相关的控制进程,该信号的默认处理动作是终止进程。2SIGINT当用户…...

Mac电脑交互式原型设计 Axure RP 8汉化最新 for mac
Axure RP 8是一款专业且快速的原型设计工具,主要用于定义需求、规格、设计功能和界面。这款工具主要适用于用户体验设计师、交互设计师、业务分析师、信息架构师、可用性专家和产品经理等职业。 Axure RP 8的主要特性包括能够快速设计出应用软件或Web网站的线框图、…...

在线免费无时长限制录屏工具 - 录猎在线版
需要录屏的小伙伴注意啦,想要长时间录制又不想花钱的,可以看下这款在线版录屏软件 —— 录猎在线版,一个录屏软件所需要的基本功能它都有,设置录制范围、录制的声音来源、摄像头也能录制的。同时它是支持Windows和Mac系统的&#…...

c语言文件操作详解:fgetc,fputc,fgets,fputs,fscanf,,fprintf,fread,fwrite的使用和区别
前言:在对于c语言的学习中,我们为了持续使用一些数据,为了让我们的数据可以在程序退出后仍然保存并且可以使用,我们引入了文件的概念和操作,本文旨在为大家分享在文件操作中常用的输入输出函数的使用方式和技巧&#x…...
Harmony装饰器
1、装饰器 装饰器是用于装饰类、结构、方法以及变量,并赋予其特殊的含义。如: Component表示自定义组件Entry表示该自定义组件为入口组件State表示组件中的状态变量,状态变量变化会触发UI刷新。 2 、语法范式 Builder/BuilderParam&#…...

如何加快Chrome谷歌浏览器下载速度?
用Chrome打开chrome://flags/...

使用kubectl连接远程Kubernetes(k8s)集群
使用kubectl连接远程Kubernetes集群 环境准备下载kubectl下载地址 安装kubectl并处理配置文件Windows的安装配置安装kubectl拉取配置文件安装kubectl拉取配置文件kubectl命令自动补全 Linux的安装配置安装kubectl拉取配置文件kubectl命令自动补全 环境准备 你需要准备一个Kube…...

Kubernetes革命:云原生时代的应用编排和自动化
文章目录 什么是Kubernetes以及为何它备受欢迎?云原生应用和K8s的关系Kubernetes的核心概念:Pods、Services、ReplicaSets等部署、扩展和管理应用程序的自动化容器编排的演进:Docker到Kubernetes实际用例:企业如何受益于K8s的应用…...
mysql.mongoDb,neo4j数据库对比
#Mysql与MongoDb和Neo4j的一些对比 主要区别 MySQL: 1.MySQL是一种关系型数据库管理系统(RDBMS),广泛用于处理结构化数据。 2.它支持SQL语言,具备成熟的事务处理和数据一致性能力。 3.MySQL适用于大多数传统的基于表…...

unity使用UniStorm 5.1.0.unitypackage增加天气
添加天天气组件unistorm 然后添加一个player 导入包会报错,需要修改代码 using UnityEngine; using UnityEngine.PostProcessing;namespace UnityEditor.PostProcessing {[CustomPropertyDrawer(typeof(UnityEngine.PostProcessing.MinAttribute))]sealed class MinDrawer : …...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...