[100天算法】-球会落何处(day 76)

news/2024/4/20 11:38:30/

题目描述

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。将球导向右侧的挡板跨过左上角和右下角,在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角,在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。返回一个大小为 n 的数组 answer ,其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标,如果球卡在盒子里,则返回 -1 。示例 1:

输入:grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出:[1,-1,-1,-1,-1]
解释:示例如图:
b0 球开始放在第 0 列上,最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上,会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上,会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上,会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上,会卡在第 2、3 列和第 1 行之间的 "V" 形里。
示例 2:输入:grid = [[-1]]
输出:[-1]
解释:球被卡在箱子左侧边上。提示:m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 为 1 或 -1来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/where-will-the-ball-fall
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法1: DFS

思路

用 DFS,模拟小球的运动轨迹就好了。小球可以从三个方向进入一个格子。

具体看代码注释。

复杂度分析

  • 时间复杂度:$O()$。
  • 空间复杂度:$O()$。

代码

JavaScript Code

/*** @param {number[][]} grid* @return {number[]}*/
var findBall = function (grid) {if (!grid || !grid[0]) return [];const cols = grid[0].length;const ans = Array(cols).fill(-1);for (let i = 0; i < cols; i++) {// 一开始所有小球都是从格子上方掉入格子中ans[i] = roll(grid, 0, i, 'TOP');}return ans;// ******************************/*** @param {number[][]} grid* @param {number} x* @param {number} y* @param {string} 表示小球是从哪个方向进入当前格子的*/function roll(grid, x, y, dir) {// 顺利掉到了网格下方的if (x >= grid.length) return y;// 左右边界if (x < 0 || y < 0 || y >= grid[0].length) return -1;// 挡板let board = grid[x][y];let res = -1;// 从上方掉落的,看挡板方向,小球只能滚向左侧或者右侧if (dir === 'TOP') {if (board === 1) res = roll(grid, x, y + 1, 'LEFT');else if (board === -1) res = roll(grid, x, y - 1, 'RIGHT');}// 从左右两侧进入的,看挡板方向,小球只能卡在当前格子或者往下掉else if ((dir === 'LEFT' && board === -1) ||(dir === 'RIGHT' && board === 1))res = -1;else res = roll(grid, x + 1, y, 'TOP');return res;}
};

http://www.ppmy.cn/news/1215713.html

相关文章

【Spring Boot】034-Spring Boot 整合 JUnit

【Spring Boot】034-Spring Boot 整合 JUnit 文章目录 【Spring Boot】034-Spring Boot 整合 JUnit一、单元测试1、什么是单元2、什么是单元测试3、为什么要单元测试 二、JUnit1、概述简介特点 2、JUnit4概述基本用法 3、JUnit5概述组成 4、JUnit5 与 JUnit4 的常用注解对比 三…

[100天算法】-不同路径 III(day 75)

题目描述 在二维网格 grid 上&#xff0c;有 4 种类型的方格&#xff1a;1 表示起始方格。且只有一个起始方格。 2 表示结束方格&#xff0c;且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向&#xff08;上、下、左、右&#…

海上船舶交通事故VR模拟体验低成本高效率-深圳华锐视点

在海上运输行业&#xff0c;安全事故的防范和应对能力是企业安全教育的重中之重。针对这一问题&#xff0c;海上运输事故VR模拟逃生演练成为了一种创新且高效的教育手段。通过这种演练&#xff0c;企业能够在提升员工安全意识和技能方面获得多方面的帮助。 在VR船舶搜救演练中&…

【C语言】深入解开指针(二)

&#x1f308;write in front :&#x1f50d;个人主页 &#xff1a; 啊森要自信的主页 &#x1f308;作者寄语 &#x1f308;&#xff1a; 小菜鸟的力量不在于它的体型&#xff0c;而在于它内心的勇气和无限的潜能&#xff0c;只要你有决心&#xff0c;就没有什么事情是不可能的…

设计模式-备忘录模式(Memento)

设计模式-备忘录模式&#xff08;Memento&#xff09; 一、备忘录模式概述1.1 什么是备忘录模式1.2 简单实现备忘录模式1.3 使用备忘录模式的注意事项 二、备忘录模式的用途三、备忘录模式实现方式3.1 基于数组的备忘录实现方式3.2 基于集合的备忘录实现方式3.3 基于HashMap的备…

眼科动态图像处理系统使用说明(2023-8-11 ccc)

眼科动态图像处理系统使用说明 2023-8-11 ccc 动态眼科图像捕捉存贮分析与传输系统&#xff0c;是由计算机软件工程师和医学专家组结合&#xff0c;为满足医院临床工作的需要&#xff0c;在2000年开发的专门用于各类眼科图像自动化分析、处理和传输的软件系统。该系统可以和各…

拆位线段树 E. XOR on Segment

Problem - E - Codeforces 区间求和&#xff0c;区间异或的操作跟线段树的区间求和、区间相见相似&#xff0c;考虑用线段树。 发现数组初始值最多是1e6&#xff0c;有不到25位&#xff0c;可以知道异或最大值是这些位数全是1的情况。 发现可以对每一位进行运算就和。 我们开…

【PyTorch教程】如何使用PyTorch分布式并行模块DistributedDataParallel(DDP)进行多卡训练

本期目录 1. 导入核心库2. 初始化分布式进程组3. 包装模型4. 分发输入数据5. 保存模型参数6. 运行分布式训练7. DDP完整训练代码 本章的重点是学习如何使用 PyTorch 中的 Distributed Data Parallel (DDP) 库进行高效的分布式并行训练。以提高模型的训练速度。 1. 导入核心库 D…

SharePoint-连接Excel

Power Automate和Power Apps想要连接Excel表格的话&#xff0c;可以在OneDrive或SharePoint网站的文档中创建Excel文件&#xff0c;然后把Excel转换成table表格 以SharePoint为例&#xff0c;在文档中点击新建&#xff0c;选择Excel工作簿 填写内容&#xff0c;然后全选选中 在…

ChatGPT重磅升级 奢侈品VERTU推出双模型AI手机

2023年11月7日,OpenAI举办了首届开发者大会,CEO Sam Altman(山姆奥尔特曼)展示了号称“史上最强”AI的GPT-4 Turbo。它支持长达约10万汉字的输入,具备前所未有的长文本处理能力,使更复杂的互动成为可能。此外,GPT-4 Turbo还引入了跨模态API支持,可以同时处理图片、视频和声音,从…

wpf devexpress项目中添加GridControl绑定数据

本教程讲解了如何添加GridControl到wpf项目中并且绑定数据 原文地址Lesson 1 - Add a GridControl to a Project and Bind it to Data | WPF Controls | DevExpress Documentation 1、使用 DevExpress Template Gallery创建一个新的空白mvvm应用程序&#xff0c;这个项目包括了…

java学习part02一些特性

17-Java语言概述-Java语言的特点和JVM的功能_哔哩哔哩_bilibili 1.java优点 跨平台性 在jvm上运行 2.jvm 2.1实现跨平台性 不需要对每一种指令集编写编译器&#xff0c;只需要针对jvm编程&#xff0c;jvm会自动转换 2.2内存回收 内存溢出&#xff1a;用的内存太多已经占满了&…

JVM及其垃圾回收机制(GC)

目录 一.JVM内存区域划分 二.JVM类加载机制 类加载过程 类加载的时机 双亲委派模型 三.JVM垃圾回收机制&#xff08;GC) GC工作过程 1.找到垃圾/判断垃圾 &#xff08;1&#xff09;引用计数【python/PHP】 &#xff08;2&#xff09;可达性分析【Java】 2.对象释放…

Xilinx Artix7-100T低端FPGA解码MIPI视频,基于MIPI CSI-2 RX Subsystem架构实现,提供工程源码和技术支持

目录 1、前言免责声明 2、我这里已有的 MIPI 编解码方案3、本 MIPI CSI2 模块性能及其优缺点4、详细设计方案设计原理框图OV5640及其配置权电阻硬件方案MIPI CSI-2 RX SubsystemSensor Demosaic图像格式转换Gammer LUT伽马校正VDMA图像缓存AXI4-Stream toVideo OutHDMI输出 5、…

Django路由层

路由层&#xff08;urls&#xff09; Django的路由层是负责将用户请求映射到相应的视图函数的一层。在Django的MVT架构中&#xff0c;路由层负责处理用户的请求&#xff0c;然后将请求交给相应的视图函数进行处理&#xff0c;最后将处理结果返回给用户。 在Django中&#xff0c…

Ubuntu上使用SSH连接到CentOS系统

确保CentOS系统上的SSH服务器已安装并正在运行&#xff1a; 在CentOS上&#xff0c;默认情况下&#xff0c;SSH服务器&#xff08;sshd&#xff09;应该已安装并正在运行。如果不确定&#xff0c;可以通过以下方式检查&#xff1a; sudo systemctl status sshd如果未安装&…

P6入门:项目初始化7-项目详情之代码/分类码Code

前言 使用项目详细信息查看和编辑有关所选项目的详细信息&#xff0c;在项目创建完成后&#xff0c;初始化项目是一项非常重要的工作&#xff0c;涉及需要设置的内容包括项目名&#xff0c;ID,责任人&#xff0c;日历&#xff0c;预算&#xff0c;资金&#xff0c;分类码等等&…

Clickhouse学习笔记(13)—— Materialize MySQL引擎

该引擎用于监听 binlog 事件&#xff0c;类似于canal、Maxwell等组件 ClickHouse 20.8.2.3 版本新增加了 MaterializeMySQL 的 database 引擎&#xff0c;该 database 能映射到 MySQL中的某个database &#xff0c;并自动在ClickHouse中创建对应ReplacingMergeTree。 ClickHous…

TensorFlow学习笔记--(3)张量的常用运算函数

损失函数及求偏导 通过 tf.GradientTape 函数来指定损失函数的变量以及表达式 最后通过 gradient(%损失函数%,%偏导对象%) 来获取求偏导的结果 独热编码 给出一组特征值 来对图像进行分类 可以用独热编码 0的概率是第0种 1的概率是第1种 0的概率是第二种 tf.one_hot(%某标签…

情侣游戏情侣飞行棋小程序系统:智能化互动,增添情感交流

随着科技的不断发展&#xff0c;智能化已经成为我们生活中不可或缺的一部分。在情侣互动游戏中&#xff0c;智能化互动也为情侣们带来了更加丰富、便捷的交流方式。本文将介绍情侣飞行棋小程序系统的智能化互动特点及其为情侣情感交流带来的益处。 一、情侣飞行棋小程序系统的…