73. Set Matrix Zeroes - Medium

前往題目

想法

  • 遇到0就直接整行和整列換成0,這樣時間是O(m * n (m + n))
  • 感覺比較適合用DFS

思路

結果不是BFS也不是DFS,因為不是感染的方式,而是只看初始狀態

  1. 第一行和第一列拿來當作儲存空間,遇到cell0的就直接把最上面和最左邊的cell賦值為0,這還算是紀錄而已(因為只紀錄在第一行和第一列)
  2. 實際把該為0cell替換為0(但是不替換第一行和第一列,要保持原始狀態)
  3. 最後再把第一行或第一列該為0的話就換成0

Code

Neetcode大大講得非常清楚,從brute force一步步慢慢優化

class Solution {
    public void setZeroes(int[][] matrix) {
        final int ROWS = matrix.length, COLS = matrix[0].length;
        boolean rowZero = false; // Overlapping cell, for first row

        // Check and record which rows and cols should be zero
        for (int row = 0; row < ROWS; ++row) {
            for (int col = 0; col < COLS; ++col) {
                if (matrix[row][col] == 0) {
                    matrix[0][col] = 0;
                    // Handle overlapping cell
                    if (row > 0) {
                        matrix[row][0] = 0;
                    } else {
                        rowZero = true;
                    }
                }
            }
        }

        // Assign zeros
        for (int row = 1; row < ROWS; ++row) {
            for (int col = 1; col < COLS; ++col) {
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;
                }
            }
        }
        
        // Assign zeros to the first row and col
        if (matrix[0][0] == 0) {
            for (int row = 0; row < ROWS; ++row) {
                matrix[row][0] = 0;
            }
        }

        if (rowZero) {
            for (int col = 0; col < COLS; ++col) {
                matrix[0][col] = 0;
            }
        }
    }
}

73. Set Matrix Zeroes - Medium
https://f88083.github.io/2024/01/16/73-Set-Matrix-Zeroes-Medium/
作者
Simon Lai
發布於
2024年1月16日
許可協議