生活随笔
收集整理的這篇文章主要介紹了
LeetCode 723. 粉碎糖果（模拟）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
1. 題目
這個問題是實現(xiàn)一個簡單的消除算法。
給定一個二維整數(shù)數(shù)組 board 代表糖果所在的方格，不同的正整數(shù) board[i][j] 代表不同種類的糖果，如果 board[i][j] = 0 代表 (i, j) 這個位置是空的。
給定的方格是玩家移動后的游戲狀態(tài)，現(xiàn)在需要你根據(jù)以下規(guī)則粉碎糖果，使得整個方格處于穩(wěn)定狀態(tài)并最終輸出。
如果有三個及以上水平或者垂直相連的同種糖果，同一時間將它們粉碎，即將這些位置變成空的。
在同時粉碎掉這些糖果之后，如果有一個空的位置上方還有糖果，那么上方的糖果就會下落直到碰到下方的糖果或者底部，這些糖果都是同時下落，也不會有新的糖果從頂部出現(xiàn)并落下來。
通過前兩步的操作，可能又會出現(xiàn)可以粉碎的糖果，請繼續(xù)重復前面的操作。
當不存在可以粉碎的糖果，也就是狀態(tài)穩(wěn)定之后，請輸出最終的狀態(tài)。
你需要模擬上述規(guī)則并使整個方格達到穩(wěn)定狀態(tài)，并輸出。
樣例
:
輸入
:
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 數(shù)組的行數(shù)區(qū)間是
[3, 50]。
board
[i
] 數(shù)組的長度區(qū)間（即 board 數(shù)組的列數(shù)區(qū)間）是
[3, 50]。
每個 board
[i
][j
] 初始整數(shù)范圍是
[1, 2000]。
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/candy-crush
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
2. 解題
- 把連續(xù)三個不為0的標記為負數(shù)，待刪除，橫向和縱向都要掃描
- 把標記為負數(shù)的置為0
- 按縱向掃描，填補下方的空白，雙指針法
- 遞歸處理，如果沒有需要操作的，達到穩(wěn)態(tài)，返回不再遞歸
class Solution {
public:vector
<vector
<int>> candyCrush(vector
<vector
<int>>& 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
][j
+1]) && abs(b
[i
][j
+1])==abs(b
[i
][j
+2])){b
[i
][j
] = b
[i
][j
+1] = b
[i
][j
+2] = -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
[i
+1][j
]) && abs(b
[i
+1][j
])==abs(b
[i
+2][j
])){b
[i
][j
] = b
[i
+1][j
] = b
[i
+2][j
] = -abs(b
[i
][j
]);todo
= true;}}for(i
= 0; i
< m
; ++i
)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
);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/
長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學習進步！
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎
總結(jié)
以上是生活随笔為你收集整理的LeetCode 723. 粉碎糖果（模拟）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
