73. Set Matrix Zeroes - Medium
前往題目
想法
- 遇到
0
就直接整行和整列換成0
,這樣時間是O(m * n (m + n))
- 感覺比較適合用
DFS
思路
結果不是BFS
也不是DFS
,因為不是感染的方式,而是只看初始狀態
- 第一行和第一列拿來當作儲存空間,遇到
cell
為0
的就直接把最上面和最左邊的cell
賦值為0
,這還算是紀錄而已(因為只紀錄在第一行和第一列) - 實際把該為
0
的cell
替換為0
(但是不替換第一行和第一列,要保持原始狀態) - 最後再把第一行或第一列該為
0
的話就換成0
Code
Neetcode大大講得非常清楚,從brute force
一步步慢慢優化
73. Set Matrix Zeroes - Medium
https://f88083.github.io/2024/01/16/73-Set-Matrix-Zeroes-Medium/