LC吐血整理之Matrix篇

Posted on | In
人生苦短 我学python

所有题解方法请移步 github-Leecode_summary

63.旋转图像

其实官方题解中转置加翻转是比较简洁的方法
下图是题解方法二的图解（仅供参考： 我写的好像跟题解方法二类似 我写的好像跟题解方法二类似

Tips1: List.reverse()

1
2
3
>>> matrix[i]= [1, 2, 3]
>>> matrix[i].reverse()
[3, 2, 1]

Tips2: python中向上取整与向下取整

1
2
3
4
5
6
7
8
9
>>> import math
# n为整数 对n/2向上取整
>>> math.ceil(n/2) / (n // 2 + n % 2) / (n + 1) / 2
>>> math.floor(2.3)   # 向下取整
2
>>> round(2.3)    #四舍五入
2
>>> round(2.335443, 3)      # 更新round方法 今天偶然看到 可以指定输出位数
2. 335

54.螺旋矩阵I&II

我也不知道我写的复杂不复杂，代码有点多，详情看github代码
逻辑理顺了还是比较好做的，今天无 Tips，今天上来补Tips了，看答案 发现一个规律： 

1
2
3
4
5
6
7
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(map(list, zip(*matrix)))[::-1]
        return res

　　2020.2.11我又来了，做剑指offer，看到一个挺好的想法，标记数组法，观察顺时针打印矩阵规律, 打印顺序 向右->向下->向左->向上，当走一个方向到边界或者已经走过了就改变方向。 　　这种方式只需要改变走的方向就可以修改为逆时针打印数组，不足就是需要一个marked数组（如果定义了矩阵元素全为数字，那就可以在原数组上修改了~看情况吧）,代码在github嗷。

73.矩阵置零

O(m+n)比较容易想到，看了O(1)的作法，不得不说，妙啊！
注意: Github上O(1)解法，倒序遍历的巧妙之处在于一次循环就可以完成置零，之后不用额外对第一行第一列进行遍历。
顺手贴一下代码吧… 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
class Solution(object):
    def setZeroes(self, matrix):
        is_col = False
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            if matrix[i][0] == 0: is_col = True
            for j in range(1, C):
                if matrix[i][j]  == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        for i in range(R-1,-1,-1):
            for j in range(C-1,0,-1):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0
            if is_col: matrix[i][0] = 0

329.矩阵中的最长递增路径

今日份的Tips-1：
在做这个题的时候，我用maxlen数组保存matrix上每个位置的最长递增路径，然后求max(maxlen)，奇怪的事情发生了： 

1
2
3
4
5
6
7
8
>>> maxlen = [[0, 0, 1], [2, 1, 0], [0, 2, 3]]
>>> max(maxlen)
[2, 1, 0]
>>> maxlen = [[9,9,4],[6,10,8],[2,1,1],[9,2,4]]
>>> max(maxlen)
[9, 9, 4]
>>> max(max(maxlen))
9   # 目标是得到最大值10

max(二维list) 难道不是对每一列/每一行求最大值..?? 迷惑行为，实际是返回第一列最大值所在行，有多个最大值时比较下一列，返回下一列最大值所在行。
正确写法： 

1
2
3
4
5
>>> maxlen = [[9,9,4],[6,10,8],[2,1,1],[9,2,4]]
>>> max(max(row) for row in maxlen )
10
>>> max(map(max, maxlen))
10

Ps:我记得以前有过max(max())这种写法啊…不知道是numpy还是tensorflow…，不管怎样，二维list求最大值不能这么求…