[抄题]:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it .
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1]]Output: [ [1,0,1], [0,0,0], [1,0,1]]
[暴力解法]:
时间分析:
空间分析:
[优化后]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
[思维问题]:
以为可以直接改,那就全都变成0了啊
[英文数据结构或算法,为什么不用别的数据结构或算法]:
for循环特别多的时候,每次int都需要重新说明
[一句话思路]:
做标记 标记大法好,最后一起改
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
== true 不用写啊亲 专业一点
[二刷]:
if matrix[i][j] == 0 的条件提出来,后面一起写,分开写反而有bug
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
做标记 标记大法好,最后一起改
[复杂度]:Time complexity: O(mn) Space complexity: O(1)
[算法思想:迭代/递归/分治/贪心]:
[关键模板化代码]:
row是0时,处理的是j, 想象一下就行了
//set the edge for x if (rowSign) { for (int j = 0; j < col; j++) matrix[0][j] = 0; }
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
[是否头一次写此类driver funcion的代码] :
[潜台词] :
class Solution { public void setZeroes(int[][] matrix) { //ini: rowSign, colSign boolean rowSign = false; boolean colSign = false; int row = matrix.length; int col = matrix[0].length; //cc if(matrix == null || row == 0 || col == 0) return ; //for loop and make sign for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if(matrix[i][j] == 0) { if(i == 0) rowSign = true; if(j == 0) colSign = true; matrix[0][j] = 0; matrix[i][0] = 0; } } } //set the inside for x for (int i = 1; i < row; i++) { if (matrix[i][0] == 0) { for (int j = 1; j < col; j++) { matrix[i][j] = 0; } } } //set the inside for y for (int j = 1; j < col; j++) { if (matrix[0][j] == 0) { for (int i = 1; i < row; i++) { matrix[i][j] = 0; } } } //set the edge for x if (rowSign) { for (int i = 0; i < row; i++) matrix[i][0] = 0; } //set the edge for y if (colSign) { for (int j = 0; j < col; j++) matrix[0][j] = 0; } }}