题目描述
这是 LeetCode 上的 1706. 球会落何处 ,难度为 中等。
Tag : 「模拟」
用一个大小为 m x n
的二维网格 gridgrid 表示一个箱子。你有 nn 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。
- 将球导向右侧的挡板跨过左上角和右下角,在网格中用 11 表示。
- 将球导向左侧的挡板跨过右上角和左下角,在网格中用 -1−1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V"
形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。
返回一个大小为 nn 的数组 answeranswer ,其中 answer[i]answer[i] 是球放在顶部的第 ii 列后从底部掉出来的那一列对应的下标,如果球卡在盒子里,则返回 -1−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] 解释:球被卡在箱子左侧边上。 复制代码
示例 3:
输入: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]] 输出:[0,1,2,3,4,-1] 复制代码
提示:
- m == grid.lengthm==grid.length
- n == grid[i].lengthn==grid[i].length
- 1 <= m, n <= 1001<=m,n<=100
- grid[i][j]grid[i][j] 为 11 或 -1−1
模拟
数据范围只有 100100,直接模拟每个球从顶部的某列出发,最终到底底部哪列即可(如果可以到达的话)。
我们使用 r
和 c
表示小球当前所处的位置,受重力影响,在不被卡住的情况下,r
会持续自增,直到到达底部,而 c
的变化,则是取决于当前挡板 grid[r][c]
的方向,若 grid[r][c]
为 11,则小球的下一个位置为 (r + 1, c + 1)(r+1,c+1);若 grid[r][c]
为 -1−1,则下一位置为 (r + 1, c - 1)(r+1,c−1),即可以统一表示为 (r + 1, c + grid[r][c])(r+1,c+grid[r][c])。当且仅当小球在本次移动过程中没被卡住,才能继续移动。即只有 c + grid[r][c]c+grid[r][c] 没有超过矩阵的左右边界(被边界卡住),或者 grid[r][c]grid[r][c] 和 grid[r][c + grid[r][c]]grid[r][c+grid[r][c]] 同向(不形成夹角),小球方能继续移动。
代码:
class Solution { int m, n; int[][] g; public int[] findBall(int[][] grid) { g = grid; m = g.length; n = g[0].length; int[] ans = new int[n]; for (int i = 0; i < n; i++) ans[i] = getVal(i); return ans; } int getVal(int x) { int r = 0, c = x; while (r < m) { int ne = c + g[r][c]; if (ne < 0 || ne >= n) return -1; if (g[r][c] != g[r][ne]) return -1; r++; c = ne; } return c; } } 复制代码
- 时间复杂度:O(m * n)O(m∗n)
- 空间复杂度:O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1706
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。