网站免费虚拟主机申请,网站关键字 优帮云,好网站建设公司哪家好?,网站代码怎么打开LeetCode1706 目录 LeetCode1706题目描述示例题目理解问题描述 示例分析思路分析问题核心 代码段代码逐行讲解1. 获取网格的列数2. 初始化结果数组3. 遍历每个球4. 逐行模拟下落过程5. 检查是否卡住6. 记录结果7. 返回结果数组 复杂度分析时间复杂度空间复杂度 总结的知识点1. …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它会向左移动。如果球移动时碰到边界或者移动方向与相邻单元格的对角线方向不一致球会卡住。
我们需要返回一个大小为 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它会向左移动。如果球移动时碰到边界或者移动方向与相邻单元格的对角线方向不一致球会卡住。 思路拆解后的重点 模拟每个球的下落和移动方向的计算 代码段
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 或 -1k 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 或 -1k d; // 计算下一列// 检查是否卡住if (k 0 || k len || row[k] ! d) {k -1; // 球卡住break;}}ans[i] k; // 记录结果}return ans; // 返回结果数组}
}总结
我认为整体上还是简洁高效逐行模拟球的下落过程并实时检查是否卡住来进行判断并解决问题。
