【MIX】算法题解(20200704)

题目列表

LC 73. 矩阵置零LC 74. 搜索二维矩阵LC 785. 判断二分图LC 31. 下一个排列

LC 73. 矩阵置零

题目链接 为了在$\mathcal{O}(1)$的空间复杂度内求解, 考虑将矩阵数值信息压缩到第一行和第一列, 使用两个标志变量r0和c0记录矩阵第一行和第一列是否有0.

扫描矩阵，如果matrix[i][j]=0那么将matrix[i][0]=matrix[0][j]=0.扫描首行(除首列)，如果matrix[i][0]=0，则将该行所在列元素全部置0.扫描首列(除首行)，如果matrix[0][j]=0，则将该列所在行元素全部置0.检查标志位r0, c0， 如果为True，则对应将首行/首列元素全部置0.

算法空间复杂度$\mathcal{O}(1)$， 时间复杂度$\mathcal{O}(rc)$

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ r, c=len(matrix), len(matrix[0]) if not r or not c: return r0, c0= False, False for i in range(r): for j in range(c): if not matrix[i][j]: matrix[i][0], matrix[0][j]=0, 0 if not i: r0=True if not j: c0=True # sweep row for i in range(1, r): if not matrix[i][0]: for j in range(1, c): matrix[i][j]=0 # sweep col for j in range(1, c): if not matrix[0][j]: for i in range(1, r): matrix[i][j]=0 if r0: for j in range(c): matrix[0][j]=0 if c0: for i in range(r): matrix[i][0]=0

LC 74. 搜索二维矩阵

题目链接 题目中给出的升序矩阵，强烈提示使用二分法. 方法1： 设计行二分函数bsr和列二分函数bsc，其中bst搜索到第一个大于等目标值的行首i，根据矩阵性质，需要检测一下i-1行和i行是否存在目标值，最坏情况下需要进行三轮二分搜索. 时间复杂度: $\mathcal{O}(logN+2\ast logM)$

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: r=len(matrix) if not r: return False c=len(matrix[0]) if not c: return False def bsr(l, r, v): while l<r: mid=(l+r)//2 if matrix[mid][0]<v: l=mid+1 else: r=mid return l def bsc(k, l, r, v): while l<r: mid=(l+r)//2 if matrix[k][mid]<v: l=mid+1 else: r=mid return l i=bsr(0, r-1, target) if matrix[i][0]==target: return True if i: j1=bsc(i-1, 0, c-1, target) if matrix[i-1][j1]==target: return True j2=bsc(i, 0, c-1, target) if matrix[i][j2]==target: return True return False

方法2： 将二维矩阵映射到一维坐标系中，发现是递增序列，直接使用二分法求解

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: n=len(matrix) if not n: return False m=len(matrix[0]) if not m: return False l, r=0, n*m-1 while l<r: mid=(l+r)//2 if matrix[mid//m][mid%m]<target: l=mid+1 else: r=mid if matrix[l//m][l%m]==target: return True return False

LC 785. 判断二分图

题目链接 染色法判断二分图的模板题, 详细理论可见【MIX】二分图&匹配&覆盖(1)，采用DFS实现，当待染色点已经染上了待染色时，该图不是二分图.

class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: n=len(graph) colors=[-1 for _ in range(n)] def dfs(node, color): if colors[node]==-1: colors[node]=color for v in graph[node]: if colors[v]==color: return False elif colors[v]==-1 and not dfs(v, 1-color): return False return True for i in range(n): if colors[i]==-1 and not dfs(i, 0): return False return True

LC 31. 下一个排列

题目链接 字节跳动提前批笔试题 本题为实现c++ STL中next_permutation(iter1, iter2)接口，可以直接调用函数AC. 实现这个接口， 分两种情况考虑这个问题

special judge， vector已经是当前最大排列，即vector是单调不升序列，只要将vector逆序即可一般情况，从后向前找到vector中第一个上升序列(nums[i]<nums[i+1])，标记位置i，从i+1开始寻找小于nums[i]且最大的元素nums[j]， swap(nums[i], nums[j])，将i+1至最后的元素从大到小排序即可. class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n=len(nums) i=n-2 while i>=0 and nums[i]>=nums[i+1]: i-=1 if i<0: nums.reverse() return else: p, j=nums[i], n-1 nums[i], nums[i+1]=nums[i+1], nums[i] while j>i: if nums[j]>p and nums[j]<nums[i]: nums[j], nums[i]=nums[i], nums[j] j-=1 pn=sorted(nums[i+1:]) # 手动做一下列表的部分排序 nums[i+1:]=pn return