【游戏】消消乐游戏

labuladong原创约 478 字

在消消乐游戏中，玩家可以交换方块，当三个或三个以上相同的方块连在同一行或同一列时，它们就会被消除，然后上方方块会下坠填补空缺。

在本站配套的消消乐游戏中，请你实现 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

// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑

class Solution {
public:
    void applyGravity(vector<vector<int>>& board) {
        int rows = board.size();
        int cols = board[0].size();
        
        // 遍历每一列
        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;
            }
        }
    }
};

python

# 游戏面板仅支持提交 JavaScript 代码
# 其他语言代码的作用是帮助大家理解算法逻辑

class Solution:
    def applyGravity(self, board: List[List[int]]) -> None:
        if not board or not board[0]:
            return
        
        rows = len(board)
        cols = len(board[0])
        
        # 遍历每一列
        for col in range(cols):
            # 初始化快慢指针
            slow = rows - 1
            fast = rows - 1
            
            while fast >= 0:
                if board[fast][col] != 0:
                    # 将非 0 元素移动到慢指针位置
                    board[slow][col] = board[fast][col]
                    slow -= 1
                fast -= 1
            
            # 将剩余的顶部位置填充为 0
            for i in range(slow + 1):
                board[i][col] = 0

// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑

func applyGravity(board [][]int) {
    rows := len(board)
    cols := len(board[0])
    
    // 遍历每一列
    for col := 0; col < cols; col++ {
        // 初始化快慢指针
        slow := rows - 1
        fast := rows - 1
        
        for fast >= 0 {
            if board[fast][col] != 0 {
                // 将非 0 元素移动到慢指针位置
                board[slow][col] = board[fast][col]
                slow--
            }
            fast--
        }
        
        // 将剩余的顶部位置填充为 0
        for i := 0; i <= slow; i++ {
            board[i][col] = 0
        }
    }
}

javascript

function applyGravity(board) {
    const rows = board.length;
    const cols = board[0].length;

    // 遍历每一列
    for (let col = 0; col < cols; col++) {
        // 初始化快慢指针
        let slow = rows - 1;
        let fast = rows - 1;

        while (fast >= 0) {
            if (board[fast][col] !== 0) {
                // 将非 0 元素移动到慢指针位置
                board[slow][col] = board[fast][col];
                slow--;
            }
            fast--;
        }

        // 将剩余的顶部位置填充为 0
        for (let i = 0; i <= slow; i++) {
            board[i][col] = 0;
        }
    }
}