1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int[] findBall(int[][] grid) {
int[] ans = new int[grid[0].length];
for (int i = 0; i < ans.length; i++) {
ans[i] = finalPos(grid, i);
}
return ans;
}
private int finalPos(int[][] grid, int startCol) {
int currRow = 0, currCol = startCol;
while (currRow < grid.length && currCol < grid[0].length) {
if (grid[currRow][currCol] == 1) {
if (currCol == grid[0].length - 1 || grid[currRow][currCol + 1] == -1) {
break;
} else {
currRow += 1;
currCol += 1;
}
} else {
if (currCol == 0 || grid[currRow][currCol - 1] == 1) {
break;
} else {
currRow += 1;
currCol -= 1;
}
}
}
return currRow == grid.length ? currCol : -1;
}
}
|
思路就是看球在哪个格子, 球所在的格子我们假设它是和该格子的对角线不接触的地方放下. 于是一开始从最左边的column开始, 也就是column0. 第一个球从这里放下, 我们看该格子是1还是-1, 如果是1就要看当前位置右侧是否为-1或者右侧是否出界, 如果满足其中一个, 那么球就会被卡在这里. 如果不是, 当球放下, 球受到重力会往右侧向下滚, 到达右下角格子, 此时我们按下暂停键, 球到达右下侧格子但是没有和该格子中对角线挨着的位置. 此时又是解决相同的问题: 看当前格子是1还是-1. 如果格子是-1, 那么我们就要看左侧是否是1或者左侧是否出界, 如果满足其中任意一个条件, 球就会被 卡在这里, 如果不是那么球受到重力就会往左下方滚. 到达左下方后我们按下暂停键, 此时球又是和当前格子对角线不接触的位置, 此时我们还是回到相同的 问题: 当前的格子是什么. 这样以此类推即可. 如果最后球的位置等于列数, 这说明球成功穿过, 此时答案就是球所在的col, 否则就是-1.
时间复杂度: O(m * n) 因为要把每个col的位置都放一个小球, 对于研究一个小球, 我们最多要走完m行. 因此是m * n.
空间复杂度: O(1)
