知识储备--基础算法篇-矩阵

2.矩阵

2.1第54题螺旋矩阵

第一题上来就跪了，看了官方答案感觉不是很好理解，找了一个比较容易理解的。

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        m = len(matrix)
        n = len(matrix[0])
        result = []
        left = 0
        right = n-1
        top = 0
        bottom = m-1
        nums = m*n
        while nums >= 1:
            i = left
            while i <= right and nums >= 1:
                result.append(matrix[top][i])
                nums = nums - 1
                i = i + 1
            top = top + 1
            i = top
            while i <= bottom and nums >= 1:
                result.append(matrix[i][right])
                nums = nums - 1
                i = i + 1
            right = right - 1
 
            i = right
            while i >= left and nums >= 1:
                result.append(matrix[bottom][i])
                nums = nums - 1
                i = i - 1
            bottom = bottom - 1
 
            i = bottom
            while i >= top and nums >= 1:
                result.append(matrix[i][left])
                nums = nums - 1
                i = i - 1
            left = left + 1
 
 
        return result

还有一个暴力方法，其中有几个知识点，

• list的[]中有三个参数，用冒号分割
• list[param1:param2:param3]
• param1，相当于start_index，可以为空，默认是0
• param2，相当于end_index，可以为空，默认是list.size
• param3，步长，默认为1。步长为-1时，返回倒序原序列

技巧：使用zip(*matrix)

代码：这里*解包，zip压缩，zip后变成zip类型，zip会把原有矩阵从第一列开始，把每一列打包成一个元祖,把元祖强转为list达到矩阵转置的效果。

但是实现顺时针旋转效果还需要配合[::-1]使用，先把行调换，第一行与最后一行换，然后再矩阵转置，达到矩阵旋转的效果。

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        res = []
        while matrix:
            # 删除第一行并返回
            res += matrix.pop(0)
            # 矩阵转置
            matrix = list(zip(*matrix))
            # 行调换，如第一行与最后一行换
            matrix = matrix[::-1]
 
        return res

2.2第73题-矩阵置零

第二道题还是比较简单的，获得0元素的行列索引，将其存到字典中，如果有重复的就不管，最后遍历字典的key，将指定的行列都置0就行了。

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
        hang = {}
        lie = {}
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==0:
                    if i not in hang:
                        hang[i] = 1
                    if j not in lie:
                        lie[j] = 1
        
        for i in hang:
            for j in range(n):
                matrix[i][j] = 0
        
        for i in lie:
            for j in range(m):
                matrix[j][i] = 0

2.3第48题-旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

直接用刚学会的矩阵转置来做，飞快，就是内存用的多。

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        # 直接用转置
        # 先颠倒，再转置
        matrix[:] = matrix[::-1]
        matrix[:] = list(zip(*matrix))

用常规方法，第i行的第x个元素(列)移动到第m-i-1列的第x个位置(行)

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        matrix2 = copy.deepcopy(matrix)
        m = len(matrix)
        for i in range(m):
            for j in range(m):
                matrix[j][m-1-i] = matrix2[i][j]

2.4第240题搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # 对角线上的元素是左上角块的最大值，只需要确定target的范围，
        # 找到比target小的对应行列就可以了
        # 比如target=14，先确定范围，>1,>5,>9,<17
        # 这时候就可以在元素17对应的左边和上边遍历寻找了
        # 如果m!=n，则先寻找对角线，再寻找剩下几列
        max_ = []
        m = len(matrix)
        n = len(matrix[0])
        a = min(m,n)
        flag = False
        for i in range(a):
            max_.append(matrix[i][i])
        b = 0
        c = 0
        d = 0
        for i in range(a):
            if target < max_[i]:
                b = i-1
                break
            elif target==max_[i]:
                return True
 
        for i in range(b+1,n):
            if target < matrix[b][i]:
                c = i
                break
            elif target == matrix[b][i]:
                return True
        for i in range(b+1,m):
            if target < matrix[i][b]:
                d = i
                break
            elif target == matrix[i][b]:
                return True
        for j in range(c,n):
            for i in range(b):
                if matrix[i][j] == target:
                    return True
        
        for j in range(d,m):
            for i in range(b):
                if matrix[j][i] == target:
                    return True
 
 
        
        

看了答案，发现从右上角慢慢缩小范围就可以了，妈的，这没想到。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m = len(matrix)
        n = len(matrix[0])
        x = 0
        y = n-1
        while xand y>=0:
            if matrix[x][y]==target:
                return True
            elif matrix[x][y] < target:
                x = x + 1
            else:
                y = y - 1