《算法通關之路》學習筆記，記錄一下自己的刷題過程，詳細的內(nèi)容請大家購買作者的書籍查閱。

1 看限制條件

1.1數(shù)據(jù)規(guī)模

有的題目數(shù)據(jù)規(guī)模較小，那么暴力法就可行；如果暴力法不行，那么再稍微加一個諸如緩存和剪枝的優(yōu)化一般可以通過。

根據(jù)題目所給的數(shù)據(jù)規(guī)模，就大概鎖定了能夠選擇的算法。
≤$10^6$可接受的復雜度O(nlogn)
≤$10^7$可接受的復雜度O(n)

轉(zhuǎn)化為全零矩陣的最少反轉(zhuǎn)次數(shù)

力扣第1284題
給你一個 m x n 的二進制矩陣 mat。每一步，你可以選擇一個單元格并將它反轉(zhuǎn)（反轉(zhuǎn)表示 0 變 1 ，1 變 0 ）。如果存在和它相鄰的單元格，那么這些相鄰的單元格也會被反轉(zhuǎn)。相鄰的兩個單元格共享同一條邊。

請你返回將矩陣 mat 轉(zhuǎn)化為全零矩陣的最少反轉(zhuǎn)次數(shù)，如果無法轉(zhuǎn)化為全零矩陣，請返回 -1 。

二進制矩陣 的每一個格子要么是 0 要么是 1 。

全零矩陣 是所有格子都為 0 的矩陣。

1 <= m <= 3
1 <= n <= 3

'''
方法一：廣度優(yōu)先遍歷（降維）時間復雜度：O（2^{mn}）
空間復雜度：O（2^{mn}）
'''class Solution:def minFlips(self, mat: list[list[int]]) -> int:# 放到flip函數(shù)外部可以減少計算mapper = {'0': '1', '1': '0'}def flip(state: list[str], i: int) -> None:state[i] = mapper[state[i]]if i % n != 0:state[i - 1] = mapper[state[i - 1]]if i % n < n - 1:state[i + 1] = mapper[state[i + 1]]if i >= n:state[i - n] = mapper[state[i - n]]if i < (m - 1) * n:state[i + n] = mapper[state[i + n]]m, n = len(mat), len(mat[0])target = '0' * (m * n)cur = ''.join(str(cell) for row in mat for cell in row)queue = [cur]visited = set()steps = 0while len(queue) > 0:for _ in range(len(queue)):cur = queue.pop(0)if cur == target:return stepsif cur in visited:continuevisited.add(cur)for i in range(len(cur)):s = list(cur)flip(s, i)queue.append(''.join(s))steps += 1return -1mat = [[0,0],[0,1]]
solu = Solution()
solu.minFlips(mat)

3

1.2 復雜度

題目要求時間復雜度是對數(shù)復雜度，就很容易想到二分查找。
題目要求常數(shù)的空間復雜度，就很容易想到原地算法。
題目中出現(xiàn)有序，應該聯(lián)想到雙指針、二分法等有序序列算法。
題目中出現(xiàn)連續(xù)子數(shù)組或連續(xù)子串，我們應該聯(lián)想到滑動窗口。

矩陣置零

力扣第73題
給定一個 m x n 的矩陣，如果一個元素為 0 ，則將其所在行和列的所有元素都設為 0 。請使用 原地 算法。

'''
方法一：原地算法時間復雜度：O（mn）
空間復雜度：O（1）
'''class Solution:def setZeroes(self, matrix: list[list[int]]) -> None:C = len(matrix[0])R = len(matrix)def setRowZeros(matrix: list[list[int]], i: int) -> None:matrix[i] = [0] * Cdef setColZeros(matrix: list[list[int]], j: int) -> None:for i in range(R):matrix[i][j] = 0isCol = False # 如果不使用一個變量來存第一行或者第一列，最后矩陣會都變?yōu)?for i in range(R):if matrix[i][0] == 0:isCol = Truefor j in range(1, C):if matrix[i][j] == 0:matrix[i][0] = 0matrix[0][j] = 0for j in range(1, C): # 第一列存著行的變換if matrix[0][j] == 0:setColZeros(matrix, j)for i in range(R):if matrix[i][0] == 0:setRowZeros(matrix, i)if isCol:setColZeros(matrix, 0)matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
solu = Solution()
solu.setZeroes(matrix)
print(matrix)

[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

2 預處理

提前將計算結(jié)果存起來，在實際的計算過程中直接使用，從而節(jié)省計算資源。雖然打表是空間換時間，但是其空間并不隨著數(shù)據(jù)規(guī)模增大而增大，很多情況下都是值得的。

順次數(shù)

力扣第1291題
我們定義「順次數(shù)」為：每一位上的數(shù)字都比前一位上的數(shù)字大 1 的整數(shù)。

請你返回由 [low, high] 范圍內(nèi)所有順次數(shù)組成的 有序 列表（從小到大排序）。

10 <= low <= high <= 10^9

'''
方法一：打表時間復雜度：O（1）
空間復雜度：O（1）
'''class Solution:def sequentialDigits(self, low: int, high: int) -> list[int]:numbers = '123456789'ins = []n = len(numbers)for i in range(1, n): # i控制長度for j in range(n - i): # j控制位置ins.append(int(numbers[j : i + j + 1]))return [x for x in ins if x >= low and x <= high]low, high = 1000, 13000
solu = Solution()
solu.sequentialDigits(low, high)

[1234, 2345, 3456, 4567, 5678, 6789, 12345]

'''
方法二：打表 + 二分查找時間復雜度：O（1）
空間復雜度：O（1）
'''import bisectclass Solution:def sequentialDigits(self, low: int, high: int) -> list[int]:numbers = '123456789'ins = []n = len(numbers)for i in range(1, n): # i控制長度for j in range(n - i): # j控制位置ins.append(int(numbers[j : i + j + 1]))return ins[bisect.bisect_left(ins, low) : bisect.bisect(ins, high)]low, high = 1000, 13000
solu = Solution()
solu.sequentialDigits(low, high)

[1234, 2345, 3456, 4567, 5678, 6789, 12345]

'''
方法三：最樸實的打表時間復雜度：O（1）
空間復雜度：O（1）
'''import bisectclass Solution:def sequentialDigits(self, low: int, high: int) -> list[int]:ins = [12, 23, 34, 45, 56, 67, 78, 89, 123, 234, 345, 456, 567, 678, 789, 1234, 2345, 3456, 4567, 5678, 6789, 12345, 23456, 34567, 45678, 56789, 123456, 234567, 345678, 456789, 1234567, 2345678, 3456789, 12345678, 23456789, 123456789]return ins[bisect.bisect_left(ins, low) : bisect.bisect(ins, high)]low, high = 1000, 13000
solu = Solution()
solu.sequentialDigits(low, high)

[1234, 2345, 3456, 4567, 5678, 6789, 12345]

單詞接龍

力扣第127題
字典 wordList 中從單詞 beginWord 和 endWord 的 轉(zhuǎn)換序列 是一個按下述規(guī)格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一對相鄰的單詞只差一個字母。
對于 1 <= i <= k 時，每個 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
給你兩個單詞 beginWord 和 endWord 和一個字典 wordList ，返回 從 beginWord 到 endWord 的 最短轉(zhuǎn)換序列 中的 單詞數(shù)目 。如果不存在這樣的轉(zhuǎn)換序列，返回 0 。

'''
方法一：暴力BFS（超時）時間復雜度：O（m^2*n）
空間復雜度：O（n）
'''class Solution:def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:queue = [beginWord]visited = set()steps = 1L = len(beginWord)while len(queue) > 0:for _ in range(len(queue)):cur = queue.pop(0)if cur in visited:continuevisited.add(cur)if cur == endWord:return stepsfor i in range(L):for j in range(26):s = list(cur)s[i] = chr(ord('a') + j) # ord()轉(zhuǎn)換ASCII碼，chr轉(zhuǎn)換為字符for word in wordList:if word == ''.join(s):queue.append(word)steps += 1return 0beginWord, endWord, wordList = "hit", "cog", ["hot","dot","dog","lot","log","cog"]
solu = Solution()
solu.ladderLength(beginWord, endWord, wordList)

5

'''
方法二：預處理 + BFS （空間換時間）時間復雜度：O（m*n）
空間復雜度：O（m*n）
'''from collections import defaultdictclass Solution:def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:queue = [beginWord]visited = set()steps = 1L = len(beginWord)n = len(wordList)wizards = defaultdict(list)for i in range(n):word = wordList[i]for j in range(L):wizards[word[:j] + '*' + word[j + 1 : ]].append(word)print(wizards)while len(queue) > 0:for _ in range(len(queue)):cur = queue.pop(0)if cur in visited:continuevisited.add(cur)if cur == endWord:return stepsfor i in range(L):for word in wizards.get(cur[:i] + '*' + cur[i + 1 :], []):queue.append(word)steps += 1return 0beginWord, endWord, wordList = "hit", "cog", ["hot","dot","dog","lot","log","cog"]
solu = Solution()
solu.ladderLength(beginWord, endWord, wordList)

5

3 不要忽視暴力法

統(tǒng)計全為 1 的正方形子矩陣

力扣第1277題
給你一個 m * n 的矩陣，矩陣中的元素不是 0 就是 1，請你統(tǒng)計并返回其中完全由 1 組成的 正方形 子矩陣的個數(shù)。

'''
方法一：暴力法（超時）時間復雜度：O（m*n*min(m,n)）
空間復雜度：O（1）
'''class Solution:def countSquares(self, matrix: list[list[int]]) -> int:num_rows, num_cols = len(matrix), len(matrix[0])min_side_length = min(num_rows, num_cols)def is_all_ones(matrix):for row in matrix:for element in row:if element != 1:return Falsereturn Truecnt = 0for side_length in range(1, min_side_length + 1):for i in range(num_rows - side_length + 1):for j in range(num_cols - side_length + 1):if is_all_ones([row[j : j + side_length] for row in matrix[i : i + side_length]]): # 遍歷二維list中所有邊長為side_length的正方形cnt += 1return cntmatrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]
]
solu = Solution()
solu.countSquares(matrix)

15

'''
方法二：動態(tài)規(guī)劃時間復雜度：O（m*n）
空間復雜度：O（m*n）
'''class Solution:def countSquares(self, matrix: list[list[int]]) -> int:num_rows, num_cols = len(matrix), len(matrix[0])cnt = 0# dp[i][j]表示以頂點i，j為右下角所能構(gòu)成的最大正方形邊長dp = [[0] * (num_cols + 1) for _ in range(num_rows + 1)]for i in range(1, num_rows + 1):for j in range(1, num_cols + 1):if matrix[i - 1][j - 1] == 1:dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1cnt += dp[i][j]return cntmatrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]
]
solu = Solution()
solu.countSquares(matrix)

15

子串的最大出現(xiàn)次數(shù)

力扣第1297題
給你一個字符串 s ，請你返回滿足以下條件且出現(xiàn)次數(shù)最大的 任意 子串的出現(xiàn)次數(shù)：

子串中不同字母的數(shù)目必須小于等于 maxLetters 。
子串的長度必須大于等于 minSize 且小于等于 maxSize 。

'''
方法一：暴力法時間復雜度：O（(26^2)*n）
空間復雜度：O（(26^2)*n）
'''class Solution:def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:counter = {}for i in range(0, len(s) - minSize + 1): # 記住這種寫法for length in range(minSize, maxSize + 1):if i + length > len(s):breaksub = s[i : i + length]if len(set(sub)) <= maxLetters: # 用set統(tǒng)計不同字符數(shù)目counter[sub] = counter.get(sub, 0) + 1return max(counter.values()) if counter else 0s, maxLetters, minSize, maxSize = "aababcaab", 2, 3, 4
solu = Solution()
solu.maxFreq(s, maxLetters, minSize, maxSize)

2

'''
方法二：暴力法剪枝（只統(tǒng)計長度為minSize的子串即可）時間復雜度：O（26*n）
空間復雜度：O（26*n）
'''class Solution:def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:counter = {}for i in range(0, len(s) - minSize + 1):sub = s[i : i + minSize]if len(set(sub)) <= maxLetters:counter[sub] = counter.get(sub, 0) + 1return max(counter.values()) if counter else 0s, maxLetters, minSize, maxSize = "aababcaab", 2, 3, 4
solu = Solution()
solu.maxFreq(s, maxLetters, minSize, maxSize)

2

4 降維與狀態(tài)壓縮

# 判斷一個字符串中的字符是否全部唯一（狀態(tài)壓縮）def isUnique(s: str) -> bool:seen = 0 # 相當于set()for c in s:if seen & 1 << ord(c) - ord('a') != 0: # 相當于判斷c是否在set中return Falseseen |= 1 << ord(c) - ord('a') # 相當于將c加入setreturn TrueisUnique('absxssxsxsxsxsx')

False

生命游戲

力扣第289題
根據(jù) 百度百科 ， 生命游戲 ，簡稱為 生命 ，是英國數(shù)學家約翰·何頓·康威在 1970 年發(fā)明的細胞自動機。
給定一個包含 m × n 個格子的面板，每一個格子都可以看成是一個細胞。每個細胞都具有一個初始狀態(tài)： 1 即為 活細胞 （live），或 0 即為 死細胞 （dead）。每個細胞與其八個相鄰位置（水平，垂直，對角線）的細胞都遵循以下四條生存定律：
如果活細胞周圍八個位置的活細胞數(shù)少于兩個，則該位置活細胞死亡；
如果活細胞周圍八個位置有兩個或三個活細胞，則該位置活細胞仍然存活；
如果活細胞周圍八個位置有超過三個活細胞，則該位置活細胞死亡；
如果死細胞周圍正好有三個活細胞，則該位置死細胞復活；
下一個狀態(tài)是通過將上述規(guī)則同時應用于當前狀態(tài)下的每個細胞所形成的，其中細胞的出生和死亡是同時發(fā)生的。給你 m x n 網(wǎng)格面板 board 的當前狀態(tài)，返回下一個狀態(tài)。

'''
方法一：常規(guī)方法時間復雜度：O（mn）
空間復雜度：O（mn）
'''import copyclass Solution:def gameOfLife(self, board: list[list[int]]) -> None:"""Do not return anything, modify board in-place instead."""m, n = len(board), len(board[0])old = copy.deepcopy(board)def cntLiveCell(i: int, j: int) -> int:cnt = 0directions = [(0, 1),(0, -1),(-1, 0),(1, 0),(1, 1),(1, -1),(-1, 1),(-1, -1)]for (dx, dy) in directions:if i + dx >= 0 and i + dx < m and j + dy >= 0 and j + dy < n:cnt += old[i + dx][j + dy]return cntfor i in range(m):for j in range(n):cnt = cntLiveCell(i, j)if old[i][j] == 0 and cnt == 3:board[i][j] = 1if old[i][j] == 1 and (cnt < 2 or cnt > 3):board[i][j] = 0board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
solu = Solution()
solu.gameOfLife(board)
print(board)

[[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]

'''
方法二：狀態(tài)壓縮（將這個細胞中有多少活細胞這個信息存儲到高位）時間復雜度：O（mn）
空間復雜度：O（1）
'''class Solution:def gameOfLife(self, board: list[list[int]]) -> None:"""Do not return anything, modify board in-place instead."""m, n = len(board), len(board[0])def cntLiveCell(i: int, j: int) -> int:cnt = 0directions = [(0, 1),(0, -1),(-1, 0),(1, 0),(1, 1),(1, -1),(-1, 1),(-1, -1)]for (dx, dy) in directions:if i + dx >= 0 and i + dx < m and j + dy >= 0 and j + dy < n:cnt += board[i + dx][j + dy] & 1return cntfor i in range(m):for j in range(n):cnt = cntLiveCell(i, j)board[i][j] |= cnt << 1for i in range(m):for j in range(n):cell = board[i][j] & 1cnt = board[i][j] >> 1if cell == 0 and cnt == 3:board[i][j] = 1elif cell == 1 and (cnt > 3 or cnt < 2):board[i][j] = 0else:board[i][j] = cellboard = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
solu = Solution()
solu.gameOfLife(board)
print(board)

[[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]