Algorithm
本周选择的算法题是：Set Matrix Zeroes。
规则
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Follow up:
- A straight forward solution using O(m**n) space is probably a bad idea.
- A simple improvement uses O(m + n) space, but still not the best solution.
- Could you devise a constant space solution?
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
Solution
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
is_col = False
for i in range(len(matrix)):
if matrix[i][0] == 0: is_col = True
for j in range(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if matrix[0][0] == 0:
for j in range(1, len(matrix[0])):
matrix[0][j] = 0
if is_col:
for i in range(len(matrix)):
matrix[i][0] = 0
Review
How Does a Modern Microprocessor Work?
作者引入了一个虚拟的处理器用来描述现代处理器的工作原理，其中包括：
- 寄存器的作用
- 解码器的作用
- 总线的作用
- CPU 的工作内容
- ALU 的工作方式
科普性的文章，有点长，需要点耐心。
Tip
IO 多路复用的几个 API 对比。
select 的缺点：
bitmap长度有限制bitmap不可重用bitmap用户态到内核态的复制开销- 内核态添加标志位后，在用户态还需要用 \(O(n)\) 的时间复杂度检查标记
poll 相比 select：
- 结构体数组，没有长度限制
- 可重用
原理和 select 一样，也有复制开销和 \(O(n)\) 的时间复杂度。
epoll 相比 poll，又多了些变化：
epfd在用户态和内核态之间共享，省去了复制开销- 没有了
revents这样的标志位，取而代之的是“重排”并返回数量，达到了 \(O(1)\) 的时间复杂度
epoll 的使用场景很广，知名的产品如 Redis、NGINX、Java NIO(Linux) 都用了 epoll。