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

LeetCode1706

LeetCode1706

目录

  • LeetCode1706
    • 题目描述
    • 示例
    • 题目理解
      • 问题描述
    • 示例分析
    • 思路分析
      • 问题核心
    • 代码段
    • 代码逐行讲解
      • 1. 获取网格的列数
      • 2. 初始化结果数组
      • 3. 遍历每个球
      • 4. 逐行模拟下落过程
      • 5. 检查是否卡住
      • 6. 记录结果
      • 7. 返回结果数组
    • 复杂度分析
      • 时间复杂度
      • 空间复杂度
    • 总结的知识点
      • 1. 二维数组的遍历
      • 2. 边界检查
      • 3. 条件判断
      • 4. 模拟过程
      • 5. 结果记录
    • 整合
    • 总结

题目描述

用一个大小为 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]
解释:
- 球0从第0列开始下落,最终落在第1列。
- 球1从第1列开始下落,卡在第1列和第2列之间。
- 球2从第2列开始下落,卡在第2列和第3列之间。
- 球3从第3列开始下落,卡在第3列和第4列之间。
- 球4从第4列开始下落,卡在第4列。

示例 2:

输入: grid = [[-1]]
输出: [-1]
解释:
- 球0从第0列开始下落,卡在第0列。

好的,我们将对 力扣 1706 题(球会落何处) 进行全面细致的分析,包括题目理解、解题思路、代码实现、复杂度分析以及涉及的知识点总结。通过这种方式,我们可以更深入地理解这道题目的核心逻辑和实现细节。


题目理解

问题描述

我们有一个大小为 m x n 的二维网格 grid,其中每个单元格的值可以是 1-1

  • 1 表示单元格的右上方和左下方有对角线,球会向右移动。
  • -1 表示单元格的左上方和右下方有对角线,球会向左移动。

球从网格的顶部开始下落,每个球会从第一行的某个列开始下落。球在移动过程中会遵循以下规则:

  1. 如果球碰到 1,它会向右移动。
  2. 如果球碰到 -1,它会向左移动。
  3. 如果球移动时碰到边界或者移动方向与相邻单元格的对角线方向不一致,球会卡住。

我们需要返回一个大小为 n 的数组,表示每个球最终会落在哪个列。如果球卡住了,则对应位置为 -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]

解释

  • 球 0 从第 0 列开始下落,最终落在第 1 列。
  • 球 1 从第 1 列开始下落,卡在第 1 列和第 2 列之间。
  • 球 2 从第 2 列开始下落,卡在第 2 列和第 3 列之间。
  • 球 3 从第 3 列开始下落,卡在第 3 列和第 4 列之间。
  • 球 4 从第 4 列开始下落,卡在第 4 列。

思路分析

问题核心

我们需要模拟每个球在网格中的下落过程,并确定它们最终会落在哪个列。网格中的每个单元格的值可以是 1-1

  • 1 表示单元格的右上方和左下方有对角线,球会向右移动。
  • -1 表示单元格的左上方和右下方有对角线,球会向左移动。

球的下落过程需要遵循以下规则:

  1. 如果球碰到 1,它会向右移动。
  2. 如果球碰到 -1,它会向左移动。
  3. 如果球移动时碰到边界或者移动方向与相邻单元格的对角线方向不一致,球会卡住。

思路拆解后的重点: 模拟每个球的下落和移动方向的计算


代码段

class Solution {public int[] findBall(int[][] grid) {int len = grid[0].length;int[] ans = new int[len];for (int i = 0; i < len; i++) {int k = i;for (int[] row : grid) {int d = row[k];k += d;if (k < 0 || k == len || row[k] != d) {k = -1;break;}}ans[i] = k;}return ans;}
}

在这里插入图片描述

代码逐行讲解

下面有整合

1. 获取网格的列数

int len = grid[0].length;
  • grid 是一个二维数组,表示网格。
  • grid[0].length 获取网格的列数 len

2. 初始化结果数组

int[] ans = new int[len];
  • ans 是一个大小为 len 的数组,用于存储每个球的最终位置。

3. 遍历每个球

for (int i = 0; i < len; i++) {int k = i; // 当前球的起始列
  • 使用 for 循环遍历每个球,i 表示球的起始列。
  • k 是当前球的列位置,初始化为起始列 i

4. 逐行模拟下落过程

for (int[] row : grid) {int d = row[k]; // 当前单元格的值(1 或 -1)k += d; // 计算下一列
  • 使用增强的 for 循环遍历每一行 row
  • d 是当前单元格的值,可以是 1-1
  • k += d 计算球的下一列位置:
    • 如果 d = 1,球向右移动,k 增加 1。
    • 如果 d = -1,球向左移动,k 减少 1。

5. 检查是否卡住

if (k < 0 || k == len || row[k] != d) {k = -1; // 球卡住break;
}
  • 边界检查
    • 如果 k < 0,球移动到左边界外。
    • 如果 k == len,球移动到右边界外。
  • 方向一致性检查
    • 如果 row[k] != d,球的移动方向与相邻单元格的对角线方向不一致。
  • 如果球卡住,将 k 设置为 -1,并跳出循环。

6. 记录结果

ans[i] = k; // 记录结果
  • 将每个球的最终位置 k 记录到结果数组 ans 中。

7. 返回结果数组

return ans; // 返回结果数组
  • 返回结果数组 ans,其中每个元素表示对应球的最终位置。

复杂度分析

时间复杂度

  • 对于每个球,我们需要逐行模拟下落过程,最多需要遍历 m 行。
  • 总共有 n 个球,因此总时间复杂度为 O(m * n)

空间复杂度

  • 我们只需要一个大小为 n 的数组来存储结果,因此空间复杂度为 O(n)

总结的知识点

1. 二维数组的遍历

  • 使用增强的 for 循环遍历二维数组 grid
  • 外层循环遍历列,内层循环遍历行。

2. 边界检查

  • 使用条件判断检查球是否移动到网格的边界外。

3. 条件判断

  • 使用 if 语句判断球是否卡住。

4. 模拟过程

  • 通过逐行模拟球的下落过程,实时更新球的位置。

5. 结果记录

  • 使用数组 ans 记录每个球的最终位置。

整合

class Solution {public int[] findBall(int[][] grid) {int len = grid[0].length; // 获取网格的列数int[] ans = new int[len]; // 初始化结果数组// 遍历每个球for (int i = 0; i < len; i++) {int k = i; // 当前球的起始列// 逐行模拟下落过程for (int[] row : grid) {int d = row[k]; // 当前单元格的值(1 或 -1)k += d; // 计算下一列// 检查是否卡住if (k < 0 || k == len || row[k] != d) {k = -1; // 球卡住break;}}ans[i] = k; // 记录结果}return ans; // 返回结果数组}
}

总结

我认为整体上还是简洁高效,逐行模拟球的下落过程,并实时检查是否卡住,来进行判断并解决问题。

相关文章:

LeetCode1706

LeetCode1706 目录 LeetCode1706题目描述示例题目理解问题描述 示例分析思路分析问题核心 代码段代码逐行讲解1. 获取网格的列数2. 初始化结果数组3. 遍历每个球4. 逐行模拟下落过程5. 检查是否卡住6. 记录结果7. 返回结果数组 复杂度分析时间复杂度空间复杂度 总结的知识点1. …...

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

2517. 礼盒的最大甜蜜度&#xff08;Maximum Tastiness of Candy Box&#xff09; 问题描述 给定一个正整数数组 price&#xff0c;其中 price[i] 表示第 i 类糖果的价格&#xff0c;另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖…...

Golang 的字符编码与 regexp

前言 最近在使用 Golang 的 regexp 对网络流量做正则匹配时&#xff0c;发现有些情况无法正确进行匹配&#xff0c;找到资料发现 regexp 内部以 UTF-8 编码的方式来处理正则表达式&#xff0c;而网络流量是字节序列&#xff0c;由其中的非 UTF-8 字符造成的问题。 我们这里从 G…...

利用ollama 与deepseek r1大模型搭建本地知识库

1.安装运行ollama ollama下载 https://ollama.com/download/windows 验证ollama是否安装成功 ollama --version 访问ollama本地地址&#xff1a; http://localhost:11434/ 出现如下界面 ollama运行模型 ollama run llama3.2 ollama常用操作命令 启动 Ollama 服务&#xf…...

Java短信验证功能简单使用

注册登录阿里云官网&#xff1a;https://www.aliyun.com/ 搜索短信服务 自己一步步申请就可以了 开发文档&#xff1a; https://next.api.aliyun.com/api-tools/sdk/Dysmsapi?version2017-05-25&languagejava-tea&tabprimer-doc 1.引入依赖 <dependency>…...

CAS单点登录(第7版)21.可接受的使用政策

如有疑问&#xff0c;请看视频&#xff1a;CAS单点登录&#xff08;第7版&#xff09; 可接受的使用政策 概述 可接受的使用政策 CAS 也称为使用条款或 EULA&#xff0c;它允许用户在继续应用程序之前接受使用策略。此功能的生产级部署需要修改流&#xff0c;以便通过外部存…...

53倍性能提升!TiDB 全局索引如何优化分区表查询?

作者&#xff1a; Defined2014 原文来源&#xff1a; https://tidb.net/blog/7077577f 什么是 TiDB 全局索引 在 TiDB 中&#xff0c;全局索引是一种定义在分区表上的索引类型&#xff0c;它允许索引分区与表分区之间建立一对多的映射关系&#xff0c;即一个索引分区可以对…...

Pythong 解决Pycharm 运行太慢

Pythong 解决Pycharm 运行太慢 官方给Pycharm自身占用的最大内存设低估了限制,我的Pycharm刚开始默认是256mb。 首先找到自己的Pycharm安装目录 根据合适自己的改 保存&#xff0c;重启Pycharm...

库里存储的数据有大量回车时,该如何进行存取

如图&#xff0c;打印模板存了很多坐标性的字段数据&#xff1a; 大量带换行的文本数据存到库里之后取出&#xff0c;前端需要做非空、合法校验&#xff0c; 然后在循环中&#xff0c;使用eval 函数接收每一句字符串&#xff0c;去执行这句 JavaScript 代码。 let arrStr tem…...

【devops】Github Actions Secrets | 如何在Github中设置CI的Secret供CI的yaml使用

一、Github Actions 1、ci.yml name: CIon: [ push ]jobs:build:runs-on: ubuntu-lateststeps:- name: Checkout codeuses: actions/checkoutv3- name: Set up Gouses: actions/setup-gov4with:go-version: 1.23.0- name: Cache Go modulesuses: actions/cachev3with:path: |…...

体验 DeepSeek-R1:解密 1.5B、7B、8B 版本的强大性能与应用

文章目录 &#x1f34b;引言&#x1f34b;DeepSeek 模型简介&#x1f34b;版本更新&#xff1a;1.5B、7B、8B 的区别与特点&#x1f34b;模型评估&#x1f34b;体验 DeepSeek 的过程&#x1f34b;总结 &#x1f34b;引言 随着大规模语言模型的持续发展&#xff0c;许多模型在性…...

一文说清楚什么是Token以及项目中使用Token延伸的问题

首先可以参考我的往期文章&#xff0c;我这里说清楚了Cookie&#xff0c;Seesion&#xff0c;Token以及JWT是什么 其实Token你就可以理解成这是一个认证令牌就好了 详细分清Session&#xff0c;Cookie和Token之间的区别&#xff0c;以及JWT是什么东西_还分不清 cookie、sessi…...

大模型-Tool call、检索增强

大模型 Tool call 心知天气&#xff1a;https://www.seniverse.com/ 例子&#xff1a;调用天气接口 API from openai import OpenAI import requests import json """ ##### 天气接口 API 密钥获取&#xff1a;https://www.free-api.com/doc/558 ##### &quo…...

【算法】【区间和】acwing算法基础 802. 区间和 【有点复杂,但思路简单】

题目 假定有一个无限长的数轴&#xff0c;数轴上每个坐标上的数都是 0。 现在&#xff0c;我们首先进行 n 次操作&#xff0c;每次操作将某一位置 x 上的数加 c。 接下来&#xff0c;进行 m 次询问&#xff0c;每个询问包含两个整数 l 和 r&#xff0c;你需要求出在区间 [l,r] …...

Ubuntu22.04通过Docker部署Jeecgboot

程序发布环境包括docker、mysql、redis、maven、nodejs、npm等。 一、安装docker 1、用如下命令卸载旧Docker: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done 2、安装APT环境依赖包…...

HTML4

HTML 初体验 1.鼠标右键 > 新建 > 文本文档 > 输入以下内容&#xff0c;并保存 2.修改后缀为 .html &#xff0c;然后双击打开即可 这里的后缀名&#xff0c;使用 .htm 也可以&#xff0c;但推荐使用更标准的 .html <marquee>尚硅谷&#xff0c;让天下没有难…...

STM32F10X 启动文件完整分析

最近在准备面试相关 顺便复盘总结一下之前的内容 启动文件在基于ARM的芯片是很重要的组成部分&#xff0c;它主要负责完成芯片上电启动时的一系列初始化工作和各种异常及中断的入口地址。 也是理解bootloader自举的关键点&#xff0c;所以需要理解一下 1. 向量表定义 启动文件…...

typescript快速入门之安装与运行

安装 安装ts环境&#xff0c;最好全局安装&#xff0c;这样就不需要开一个项目又安装 npm i -g typescript初始化 可以运行初始化配置文件&#xff0c;也可以手动生成&#xff1b;不生成的话会运行默认配置 使用默认配置 把ts文件转成js文件使用的是es3语言&#xff0c;语…...

React源码解读

配置React源码本地调试环境 本次环境构建采用了node版本为16、react-scripts 版本号为 3.4.4&#xff0c;源码下载地址 react源码调试: react源码调试环境 使用 create-react-app 脚手架创建项目 npx create-react-app react-test 进入刚刚下载的目录&#xff0c;弹射 crea…...

【DeepSeek-R1】 API申请(火山方舟联网版)

DeepSeek-R1 API申请&#xff08;火山方舟联网版&#xff09; 1、新建联网版应用2、开通信息增强服务3、开启联网内容插件4、创建接入点5、获取模型名称6、获取API Key 如果第一次注册账号&#xff0c;请先按照文章《【Deepseek-R1】 API申请&#xff08;火山方舟&#xff09;》…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...