動機

讓題我想起多allocate一塊記憶體去當dummy的手法 但是這裡不用多allocate，而是利用matrix的第一列與第一排

而如果第一列與第一排原本就該被處理的話，就用變數存狀態!!

這裡的教訓是狀態與被處理的資料勢必要分開，就像loop會看cond會不會收斂，有關的index會不會收斂，遞迴的變數會不會往base case靠近，是設計時的規則!!

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

 

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

 

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

 

Follow up:

  • A straightforward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

Sol

如果不追求記憶體用量的話，其實記下所有有0的點就好

如果不想用其他記憶體，就要有地方放mark，區分這是原本的0還是後面加的，所以在python之類的語言可以用None之類的去區分

但像c之類的就沒辦法，這時需要別的方法 可以把第一列與第一排當成checklist，這樣就沒問題了

但要記得處理原本第一列與第一排就有0的case

class Solution:
    def setZeroes(self, ms: List[List[int]]) -> None:
        Col1,Row1 = False, False
        for i in range(len(ms)):
            if ms[i][0] == 0:
                Col1 = True
        for j in range(len(ms[0])):
            if ms[0][j] == 0:
                Row1 = True

        for i in range(1,len(ms)):
            for j in range(1,len(ms[0])):
                if ms[i][j] == 0:
                    ms[i][0] = ms[0][j] = 0
        
        for i in range(1,len(ms)):
            if ms[i][0] == 0:
                for j in range(1,len(ms[0])):
                    ms[i][j] = 0
        
        for j in range(1,len(ms[0])):
            if ms[0][j] == 0:
                for i in range(1,len(ms)):
                    ms[i][j] = 0

        if Col1:
            for i in range(len(ms)):
                ms[i][0] = 0
        if Row1:
            for j in range(len(ms[0])):
                ms[0][j] = 0