LeetCode1706

LeetCode1706

题目描述

用一个大小为 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; // 返回结果数组
    }
}

总结

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