在消消乐游戏中,玩家可以交换方块,当三个或三个以上相同的方块连在同一行或同一列时,它们就会被消除,然后上方方块会下坠填补空缺。
在本站配套的消消乐游戏中,请你实现 applyGravity 函数,完成这个方块下坠的逻辑。要求原地修改 board 数组,并避免直接在数组中间插入/删除元素。
讲解
这道题本质上是考察 数组双指针技巧汇总 中的 moveZeroes 解法,使用快慢指针技巧将每一列方块的元素 0 移动到顶部。
参考解法如下:
java
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
class Solution {
public void applyGravity(int[][] board) {
if (board == null || board.length == 0) {
return;
}
int rows = board.length;
int cols = board[0].length;
// 遍历每一列
for (int col = 0; col < cols; col++) {
// 初始化快慢指针
int slow = rows - 1;
int fast = rows - 1;
while (fast >= 0) {
if (board[fast][col] != 0) {
// 将非 0 元素移动到慢指针位置
board[slow][col] = board[fast][col];
slow--;
}
fast--;
}
// 将剩余的顶部位置填充为 0
for (int i = 0; i <= slow; i++) {
board[i][col] = 0;
}
}
}
}cpp
python
go
javascript