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

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 = 0right = n-1top = 0bottom = m-1nums = m*nwhile nums >= 1:i = leftwhile i <= right and nums >= 1:result.append(matrix[top][i])nums = nums - 1i = i + 1top = top + 1i = topwhile i <= bottom and nums >= 1:result.append(matrix[i][right])nums = nums - 1i = i + 1right = right - 1i = rightwhile i >= left and nums >= 1:result.append(matrix[bottom][i])nums = nums - 1i = i - 1bottom = bottom - 1i = bottomwhile i >= top and nums >= 1:result.append(matrix[i][left])nums = nums - 1i = i - 1left = left + 1return 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] = 1if j not in lie:lie[j] = 1for i in hang:for j in range(n):matrix[i][j] = 0for 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 = Falsefor i in range(a):max_.append(matrix[i][i])b = 0c = 0d = 0for i in range(a):if target < max_[i]:b = i-1breakelif target==max_[i]:return Truefor i in range(b+1,n):if target < matrix[b][i]:c = ibreakelif target == matrix[b][i]:return Truefor i in range(b+1,m):if target < matrix[i][b]:d = ibreakelif target == matrix[i][b]:return Truefor j in range(c,n):for i in range(b):if matrix[i][j] == target:return Truefor 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 = 0y = n-1while x<m and y>=0:if matrix[x][y]==target:return Trueelif matrix[x][y] < target:x = x + 1else:y = y - 1