用位运算节省空间用位运算节省空间

0X00 例子

动态规划的空间优化（滚动数组）

0 ^ 1 = 0 1 ^ 1 = 0

少状态时用位运算在原地记录状态

【用位运算节省空间】289. 生命游戏

class Solution: def gameOfLife(self, board: List[List[int]]) -> None: if not len(board): return m, n = len(board), len(board[0]) for i in range(m): for j in range(n): s = board[i][j] cnt = 0 for x in range(i-1, i+2): for y in range(j-1, j+2): if x < 0 or y < 0 or x >= m or y >= n: continue if x == i and y == j: continue if board[x][y] & 1: cnt += 1 # print(cnt) if s & 1: if cnt < 2 or cnt > 3: s |= 4 else: s |= 8 else: if cnt == 3: s |= 2 else: s |= 16 board[i][j] = s# print(board) for i in range(m): for j in range(n): s = board[i][j] if s & 2 or s & 8: s = 1 else: s = 0 board[i][j] = s