1706. 球会落何处 : 简单模拟题

简介: 1706. 球会落何处 : 简单模拟题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 1706. 球会落何处 ,难度为 中等


Tag : 「模拟」


用一个大小为 m x n 的二维网格 gridgrid 表示一个箱子。你有 nn 颗球。箱子的顶部和底部都是开着的。


箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。


  • 将球导向右侧的挡板跨过左上角和右下角,在网格中用 11 表示。
  • 将球导向左侧的挡板跨过右上角和左下角,在网格中用 -11 表示。


在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。


返回一个大小为 nn 的数组 answeranswer ,其中 answer[i]answer[i] 是球放在顶部的第 ii 列后从底部掉出来的那一列对应的下标,如果球卡在盒子里,则返回 -11


示例 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-11


模拟



数据范围只有 100100,直接模拟每个球从顶部的某列出发,最终到底底部哪列即可(如果可以到达的话)。


我们使用 rc 表示小球当前所处的位置,受重力影响,在不被卡住的情况下,r 会持续自增,直到到达底部,而 c 的变化,则是取决于当前挡板 grid[r][c] 的方向,若 grid[r][c]11,则小球的下一个位置为 (r + 1, c + 1)(r+1,c+1);若 grid[r][c]-11,则下一位置为 (r + 1, c - 1)(r+1,c1),即可以统一表示为 (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(mn)
  • 空间复杂度:O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1706 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
6月前
|
算法 测试技术 C#
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
|
6月前
|
人工智能 BI
经典问题之区间分组
经典问题之区间分组
【图论】【深度优先搜索】【换根法】2858. 可以到达每一个节点的最少边反转次数
【图论】【深度优先搜索】【换根法】2858. 可以到达每一个节点的最少边反转次数
|
6月前
leetcode-1706:球会落何处
leetcode-1706:球会落何处
42 0
|
调度
每日三题-跳跃游戏、根据身高重建队列、任务调度器
每日三题 跳跃游戏 根据身高重建队列 任务调度器
89 0
每日三题-跳跃游戏、根据身高重建队列、任务调度器
用c/c++代码求解时分秒针重合次数
用c/c++代码求解时分秒针重合次数
刷爆力扣之较大分组的位置
刷爆力扣之较大分组的位置
|
定位技术
【CCCC】L3-005 垃圾箱分布 (30分),Dijkstra跑n遍 = 多源最短路
【CCCC】L3-005 垃圾箱分布 (30分),Dijkstra跑n遍 = 多源最短路
143 0