题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

一个直接的解决方案是使用 O(m**n) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

最优解法——首行、首列存储（AC）

可以借用原矩阵的首行和首列来存储这个信息。这个方法的缺点在于，如果我们直接将0存入首行或首列来表示相应行和列要置0的话，我们很难判断首行或者首列自己是不是该置0。这里我们用两个boolean变量记录下首行和首列原本有没有0，然后在其他位置置完0后，再单独根据boolean变量来处理首行和首列，就避免了干扰的问题。
时间复杂度O(n^2)，空间复杂度O(1)
Beat 65%

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        now = '1'
        
        for k in range(2,n + 1):
            last = now
            now = ''
            i = 0
            
            while(i < len(last)):
                j = len(last) - 1
                for jj in range(i + 1,len(last)):
                    if(last[jj] != last[i]):
                        j = jj - 1
                        break
                now += str(j - i + 1)
                now += str(last[i])
                
                i = j + 1
        return now