粉碎糖果

723. 粉碎糖果

这个问题是实现一个简单的消除算法。

给定一个 m x n 的二维整数数组 board 代表糖果所在的方格，不同的正整数 board[i][j] 代表不同种类的糖果，如果 board[i][j] == 0 代表 (i, j) 这个位置是空的。

给定的方格是玩家移动后的游戏状态，现在需要你根据以下规则粉碎糖果，使得整个方格处于稳定状态并最终输出：

如果有三个及以上水平或者垂直相连的同种糖果，同一时间将它们粉碎，即将这些位置变成空的。
在同时粉碎掉这些糖果之后，如果有一个空的位置上方还有糖果，那么上方的糖果就会下落直到碰到下方的糖果或者底部，这些糖果都是同时下落，也不会有新的糖果从顶部出现并落下来。
通过前两步的操作，可能又会出现可以粉碎的糖果，请继续重复前面的操作。
当不存在可以粉碎的糖果，也就是状态稳定之后，请输出最终的状态。

你需要模拟上述规则并使整个方格达到稳定状态，并输出。

示例 1 :

输入: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
输出: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

示例 2:

输入: board = [[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]]
输出: [[1,3,0,0,0],[3,4,0,5,2],[3,2,0,3,1],[2,4,0,5,2],[1,4,3,1,1]]

提示:

m == board.length
n == board[i].length
3 <= m, n <= 50
1 <= board[i][j] <= 2000

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> candyCrush(vector<vector<int>>& board) { } };

golang 解法, 执行用时: 8 ms, 内存消耗: 3.5 MB, 提交时间: 2023-10-21 19:04:18

func candyCrush(board [][]int) [][]int {
	abs := func(x int) int {
		if x < 0 {
			return -x
		}
		return x
	}
	m, n := len(board), len(board[0])
	erase := true
	for erase {
		erase = false
		// 横向消除
		for _, line := range board {
			for j, num := range line {
				num = abs(num)
				if num > 0 && j > 1 {
					if abs(line[j]) == abs(line[j-1]) && abs(line[j-1]) == abs(line[j-2]) {
						line[j], line[j-1], line[j-2] = -num, -num, -num
						erase = true
					}
				}
			}
		}
		// 纵向消除
		for j := 0; j < n; j++ {
			for i := 0; i < m; i++ {
				num := abs(board[i][j])
				if num > 0 && i > 1 {
					if abs(board[i][j]) == abs(board[i-1][j]) && abs(board[i-1][j]) == abs(board[i-2][j]) {
						board[i][j], board[i-1][j], board[i-2][j] = -num, -num, -num
						erase = true
					}
				}

			}
		}

		// 下落
		for r := 0; r < n; r++ {
			up, dp := m-1, m-1
			for ; up >= 0; up-- {
				board[dp][r], board[up][r] = board[up][r], board[dp][r]
				if board[dp][r] > 0 {
					dp--
				}
			}
			for ; dp >= 0; dp-- {
				board[dp][r] = 0
			}
		}

	}
	return board
}

cpp 解法, 执行用时: 24 ms, 内存消耗: 8.6 MB, 提交时间: 2023-10-21 19:03:44

class Solution 
{
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) 
    {
        int Row = board.size(), Col = board[0].size();
        bool need_todo = true;
        //////// 思路：根据例子，L形也是可以的。先把原先的数组置为 -abs(x, x, x),省掉mark数组
        while (need_todo == true)   //上一次有消消乐，这次可能还需要消消乐
        {
            need_todo = false;  //标记，看这轮需不需要消消乐
            ////先搞定行
            for (int r = 0; r < Row; r ++)
            {   //// 用for有点暴力，其实while可以优化一下，减少比较次数。但是：干不动了……想休息…… -_-!
                for (int c = 0; c < Col - 2; c ++)
                {
                    if ( board[r][c]!=0 && abs(board[r][c]) == abs(board[r][c+1]) && abs(board[r][c+1]) == abs(board[r][c+2]) )
                    {
                        need_todo = true;
                        int tmp = - abs(board[r][c]);
                        board[r][c]   = tmp;
                        board[r][c+1] = tmp;
                        board[r][c+2] = tmp;
                    }
                }
            }
            //// 再搞定列
            for (int c = 0; c < Col; c ++)
            {
                for (int r = 0; r < Row - 2; r ++)
                {
                    if ( board[r][c] != 0 && abs(board[r][c]) == abs(board[r+1][c]) && abs(board[r+1][c]) == abs(board[r+2][c]) )
                    {
                        need_todo = true;
                        int tmp = -abs(board[r][c]);
                        board[r][c]   = tmp;
                        board[r+1][c] = tmp;
                        board[r+2][c] = tmp;
                    }
                }
            }
            if (need_todo == true)      //如果需要消消乐
            {
                //// 因为是从上往下掉落，需要一列一列的搞定。
                for (int c = 0; c < Col; c ++)
                {
                    int rr = Row - 1;
                    for (int r = Row - 1; r > -1; r --)
                    {
                        if (board[r][c] > 0)
                        {
                            board[rr][c] = board[r][c];
                            rr --;
                        }
                    }
                    while (rr > -1) //上面有空缺的，补0
                    {
                        board[rr][c] = 0;
                        rr --;
                    }
                }
            }
        }
        return board;
    }
};

python3 解法, 执行用时: 116 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-21 19:03:27

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        Row, Col = len(board), len(board[0])
        need_todo = True
        ################ 注意L形也是可以的
        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐
            need_todo = False
            #### 先搞定行
            for r in range(Row):
                for c in range(Col - 2):
                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):
                        need_todo = True
                        tmp = - abs(board[r][c])
                        board[r][c]   = tmp
                        board[r][c+1] = tmp
                        board[r][c+2] = tmp
            #### 再搞定列
            for c in range(Col):
                for r in range(Row - 2):
                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):
                        need_todo = True
                        tmp = -abs(board[r][c])
                        board[r][c]   = tmp
                        board[r+1][c] = tmp
                        board[r+2][c] = tmp
            #### 根据标记，整理。因为要从上往下掉落。要按列来
            if need_todo == True:
                for c in range(Col):
                    rr = Row - 1
                    for r in range(Row - 1, -1, -1):
                        if board[r][c] > 0:
                            board[rr][c] = board[r][c]
                            rr -= 1
                    while rr > -1:
                        board[rr][c] = 0
                        rr -= 1

        return board

java 解法, 执行用时: 4 ms, 内存消耗: 42.9 MB, 提交时间: 2023-10-21 19:02:41

class Solution {
    public int[][] candyCrush(int[][] board) {
        int rows = board.length, cols = board[0].length;
        boolean todo = false;   // 是否存在要粉碎的糖果
        // 一行一行扫描
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c + 2 < cols; ++c) {
                // 取出这个点的绝对值（可能被取反了，所以要绝对值）
                int v = Math.abs(board[r][c]);
                // 如果连续三个格子是相同的糖果
                if (v != 0 && v == Math.abs(board[r][c + 1]) && v == Math.abs(board[r][c + 2])) {
                    // 把这三个连续格子的糖果数值取反，表明待粉碎状态
                    board[r][c] = board[r][c + 1] = board[r][c + 2] = -v;
                    todo = true;
                }
            }
        }
        // 一列一列扫描
        for (int r = 0; r + 2 < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                // 取出这个点的绝对值（可能被取反了，所以要绝对值）
                int v = Math.abs(board[r][c]);
                // 如果连续三个格子是相同的糖果
                if (v != 0 && v == Math.abs(board[r + 1][c]) && v == Math.abs(board[r + 2][c])) {
                    // 把这三个连续格子的糖果数值取反，表明待粉碎状态
                    board[r][c] = board[r + 1][c] = board[r + 2][c] = -v;
                    todo = true;
                }
            }
        }
        // 经过上面两个 for 循环后，需要粉碎糖果的格子已经变为负数

        // 遍历所有格子进行粉碎糖果
        if (todo) {
            for (int c = 0; c < cols; ++c) {   // 从左到右每一列
                int wr = rows - 1;  // 接收掉落糖果所在行
                for (int r = rows - 1; r >= 0; r--) {  // 从下往上遍历每一行
                    if (board[r][c] > 0) {
                        // 把 (r,c) 的糖果掉落到 (wr,c) 上
                        // r 和 wr 要么在同一行，要么 r 在上面，因此不用特地找到 wr 的初始行。
                        board[wr][c] = board[r][c]; 
                        wr--;   // 往上走一行
                    }
                }
                // 如果 wr 没有走到最顶行，说明上面应该全是要粉碎的
                while (wr >= 0) {
                    board[wr--][c] = 0;
                }
            }
        }
        // 如果还有需要粉碎的糖果，则再调用一次 candyCrush(board)
        // 注意，本次 candyCrush 后是不确定存不存在新的要粉碎的糖果，只能再调用一次 candyCrush
        // 如果多调用的 candyCrush 中两个 for 循环都没有把 tod0 标记为 true，则表示结束了
        // 因此，本方法都会多调用一次 candyCrush 但不进行粉碎的操作。
        return todo ? candyCrush(board) : board;
    }

}

java 解法, 执行用时: 4 ms, 内存消耗: 42.8 MB, 提交时间: 2023-10-21 19:02:24

class Solution {
    public int[][] candyCrush(int[][] board) {
        int R = board.length, C = board[0].length;
        boolean todo = false;
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c + 2 < C; ++c) {
                int v = Math.abs(board[r][c]);
                if (v != 0 && v == Math.abs(board[r][c+1]) && v == Math.abs(board[r][c+2])) {
                    board[r][c] = board[r][c+1] = board[r][c+2] = -v;
                    todo = true;
                }
            }
        }
        for (int r = 0; r + 2 < R; ++r) {
            for (int c = 0; c < C; ++c) {
                int v = Math.abs(board[r][c]);
                if (v != 0 && v == Math.abs(board[r+1][c]) && v == Math.abs(board[r+2][c])) {
                    board[r][c] = board[r+1][c] = board[r+2][c] = -v;
                    todo = true;
                }
            }
        }

        for (int c = 0; c < C; ++c) {
            int wr = R - 1;
            for (int r = R-1; r >= 0; --r)
                if (board[r][c] > 0)
                    board[wr--][c] = board[r][c];
            while (wr >= 0)
                board[wr--][c] = 0;
        }

        return todo ? candyCrush(board) : board;
    }
}

python3 解法, 执行用时: 132 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-21 19:02:02

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        R, C = len(board), len(board[0])
        todo = False

        for r in range(R):
            for c in range(C-2):
                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:
                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])
                    todo = True

        for r in range(R-2):
            for c in range(C):
                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:
                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])
                    todo = True

        for c in range(C):
            wr = R-1
            for r in range(R-1, -1, -1):
                if board[r][c] > 0:
                    board[wr][c] = board[r][c]
                    wr -= 1
            for wr in range(wr, -1, -1):
                board[wr][c] = 0

        return self.candyCrush(board) if todo else board

上一题

下一题

详情