网站设计像素,wordpress 页面 评论链接 新窗口打开,设计制作内容,c2c模式的诞生与发展文章目录1. 题目2. 解题1. 题目
这个问题是实现一个简单的消除算法。
给定一个二维整数数组 board 代表糖果所在的方格#xff0c;不同的正整数 board[i][j] 代表不同种类的糖果#xff0c;如果 board[i][j] 0 代表 (i, j) 这个位置是空的。 给定的方格是玩家移动后的游戏…
文章目录1. 题目2. 解题1. 题目
这个问题是实现一个简单的消除算法。
给定一个二维整数数组 board 代表糖果所在的方格不同的正整数 board[i][j] 代表不同种类的糖果如果 board[i][j] 0 代表 (i, j) 这个位置是空的。 给定的方格是玩家移动后的游戏状态现在需要你根据以下规则粉碎糖果使得整个方格处于稳定状态并最终输出。
如果有三个及以上水平或者垂直相连的同种糖果同一时间将它们粉碎即将这些位置变成空的。 在同时粉碎掉这些糖果之后如果有一个空的位置上方还有糖果那么上方的糖果就会下落直到碰到下方的糖果或者底部这些糖果都是同时下落也不会有新的糖果从顶部出现并落下来。 通过前两步的操作可能又会出现可以粉碎的糖果请继续重复前面的操作。 当不存在可以粉碎的糖果也就是状态稳定之后请输出最终的状态。 你需要模拟上述规则并使整个方格达到稳定状态并输出。
样例 :
输入:
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]]解释:
注释 :
board 数组的行数区间是 [3, 50]。
board[i] 数组的长度区间即 board 数组的列数区间是 [3, 50]。
每个 board[i][j] 初始整数范围是 [1, 2000]。来源力扣LeetCode 链接https://leetcode-cn.com/problems/candy-crush 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
把连续三个不为0的标记为负数待删除横向和纵向都要扫描把标记为负数的置为0按纵向扫描填补下方的空白双指针法递归处理如果没有需要操作的达到稳态返回不再递归
class Solution {
public:vectorvectorint candyCrush(vectorvectorint b) {bool todo false;int m b.size(), n b[0].size(), i, j, up, down;for(i 0; i m; i)//横向检查for(j 0; j n-2; j){if(b[i][j] 0)continue;if(abs(b[i][j])abs(b[i][j1]) abs(b[i][j1])abs(b[i][j2])){b[i][j] b[i][j1] b[i][j2] -abs(b[i][j]);//标记为负的todo true;}}for(j 0; j n; j)//纵向检查for(i 0; i m-2; i){if(b[i][j] 0)continue;if(abs(b[i][j])abs(b[i1][j]) abs(b[i1][j])abs(b[i2][j])){b[i][j] b[i1][j] b[i2][j] -abs(b[i][j]);//标记为负的todo true;}}for(i 0; i m; i)//负的 标记为0要删除for(j 0; j n; j)if(b[i][j] 0)b[i][j] 0;for(j 0; j n; j)//纵向掉落{down up m-1;//从最底下开始往上找while(down 0){ //双指针搬移数据if(b[down][j] 0)//底下待填{up min(down, up);//up记住上次的位置while(up 0 b[up][j] 0)up--;if(up 0)//上面找到糖果swap(b[down][j], b[up][j]);//交换elsebreak;//找完了}down--;}}if(todo)candyCrush(b);return b;}
};24 ms 10.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
