深圳培训手机网站建设,wordpress允许ping,公开课网站建设,网站建设实用教程《算法通关之路》学习笔记#xff0c;记录一下自己的刷题过程#xff0c;详细的内容请大家购买作者的书籍查阅。
1 看限制条件
1.1数据规模
有的题目数据规模较小#xff0c;那么暴力法就可行#xff1b;如果暴力法不行#xff0c;那么再稍微加一个诸如缓存和剪枝的优化…《算法通关之路》学习笔记记录一下自己的刷题过程详细的内容请大家购买作者的书籍查阅。
1 看限制条件
1.1数据规模
有的题目数据规模较小那么暴力法就可行如果暴力法不行那么再稍微加一个诸如缓存和剪枝的优化一般可以通过。
根据题目所给的数据规模就大概锁定了能够选择的算法。 ≤ 1 0 6 10^{6} 106可接受的复杂度O(nlogn) ≤ 1 0 7 10^{7} 107可接受的复杂度O(n)
转化为全零矩阵的最少反转次数
力扣第1284题 给你一个 m x n 的二进制矩阵 mat。每一步你可以选择一个单元格并将它反转反转表示 0 变 1 1 变 0 。如果存在和它相邻的单元格那么这些相邻的单元格也会被反转。相邻的两个单元格共享同一条边。
请你返回将矩阵 mat 转化为全零矩阵的最少反转次数如果无法转化为全零矩阵请返回 -1 。
二进制矩阵 的每一个格子要么是 0 要么是 1 。
全零矩阵 是所有格子都为 0 的矩阵。
1 m 3 1 n 3 方法一广度优先遍历降维时间复杂度O2^{mn}
空间复杂度O2^{mn}
class Solution:def minFlips(self, mat: list[list[int]]) - int:# 放到flip函数外部可以减少计算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)31.2 复杂度
题目要求时间复杂度是对数复杂度就很容易想到二分查找。 题目要求常数的空间复杂度就很容易想到原地算法。 题目中出现有序应该联想到双指针、二分法等有序序列算法。 题目中出现连续子数组或连续子串我们应该联想到滑动窗口。
矩阵置零
力扣第73题 给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 方法一原地算法时间复杂度Omn
空间复杂度O1
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 # 如果不使用一个变量来存第一行或者第一列最后矩阵会都变为0for 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 预处理
提前将计算结果存起来在实际的计算过程中直接使用从而节省计算资源。虽然打表是空间换时间但是其空间并不随着数据规模增大而增大很多情况下都是值得的。
顺次数
力扣第1291题 我们定义「顺次数」为每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表从小到大排序。
10 low high 10^9 方法一打表时间复杂度O1
空间复杂度O1
class Solution:def sequentialDigits(self, low: int, high: int) - list[int]:numbers 123456789ins []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]方法二打表 二分查找时间复杂度O1
空间复杂度O1
import bisectclass Solution:def sequentialDigits(self, low: int, high: int) - list[int]:numbers 123456789ins []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]方法三最朴实的打表时间复杂度O1
空间复杂度O1
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 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - … - sk
每一对相邻的单词只差一个字母。 对于 1 i k 时每个 si 都在 wordList 中。注意 beginWord 不需要在 wordList 中。 sk endWord 给你两个单词 beginWord 和 endWord 和一个字典 wordList 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0 。 方法一暴力BFS超时时间复杂度Om^2*n
空间复杂度On
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()转换ASCII码chr转换为字符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 空间换时间时间复杂度Om*n
空间复杂度Om*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)53 不要忽视暴力法
统计全为 1 的正方形子矩阵
力扣第1277题 给你一个 m * n 的矩阵矩阵中的元素不是 0 就是 1请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。 方法一暴力法超时时间复杂度Om*n*min(m,n)
空间复杂度O1
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方法二动态规划时间复杂度Om*n
空间复杂度Om*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]表示以顶点ij为右下角所能构成的最大正方形边长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子串的最大出现次数
力扣第1297题 给你一个字符串 s 请你返回满足以下条件且出现次数最大的 任意 子串的出现次数
子串中不同字母的数目必须小于等于 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统计不同字符数目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方法二暴力法剪枝只统计长度为minSize的子串即可时间复杂度O26*n
空间复杂度O26*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)24 降维与状态压缩
# 判断一个字符串中的字符是否全部唯一状态压缩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题 根据 百度百科 生命游戏 简称为 生命 是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态 1 即为 活细胞 live或 0 即为 死细胞 dead。每个细胞与其八个相邻位置水平垂直对角线的细胞都遵循以下四条生存定律 如果活细胞周围八个位置的活细胞数少于两个则该位置活细胞死亡 如果活细胞周围八个位置有两个或三个活细胞则该位置活细胞仍然存活 如果活细胞周围八个位置有超过三个活细胞则该位置活细胞死亡 如果死细胞周围正好有三个活细胞则该位置死细胞复活 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态返回下一个状态。 方法一常规方法时间复杂度Omn
空间复杂度Omn
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]]方法二状态压缩将这个细胞中有多少活细胞这个信息存储到高位时间复杂度Omn
空间复杂度O1
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]]
