当前位置： 首页 > news >正文

旅游网站建设方案书范文,水果门户网站建设,聊城高端网站建设报价,青岛黄岛区做网站设计的《算法通关之路》学习笔记#xff0c;记录一下自己的刷题过程#xff0c;详细的内容请大家购买作者的书籍查阅。 1 二分法 1.1 普通二分法

查找nums数组中元素值为target的下标。如果不存在#xff0c;则返回-1def bs(nums: list[int], target: int) - int :l, h …《算法通关之路》学习笔记记录一下自己的刷题过程详细的内容请大家购买作者的书籍查阅。

1 二分法 1.1 普通二分法

查找nums数组中元素值为target的下标。如果不存在则返回-1def bs(nums: list[int], target: int) - int :l, h 0, len(nums) - 1while l h:mid l (h - l) // 2if nums[mid] target:return midelif nums[mid] target:l mid 1else:h mid - 1return -1nums [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

nums[bs(nums, 8)]81.2 二分法变种 有些二分法类型的题目在二分时无法直接判断中间元素是否为目标元素这类问题被称作二分法变种问题。 例如在有序数组里面查找第1个大于或等于5的元素每次判断中间元素时无法直接断定这个元素是否是第1个大于或等于5的元素它可能是第2个或第3个大于或等于5的元素。 二分法变种问题大致分为两种情况 查找第一个满足条件的元素查找最后一个满足条件的元素 此外需要注意边界问题这是二分法变种问题最容易出错的地方

查找第1个大于等于x的元素

左边界更新为l mid 1不会产生死循环当剩下1个元素时跳出即可def bs(nums: list[int], target: int) - int :l, h 0, len(nums) - 1while l h:mid l (h - l) // 2if l h: # 边界条件breakelif nums[mid] target:l mid 1else:h midreturn lnums [1, 2, 3, 4, 5, 6, 7, 9, 10]

nums[bs(nums, 8)]9# 查找最后1个小于等于x的元素

左边界更新为l mid会产生死循环当剩下2个元素时跳出即可def bs(nums: list[int], target: int) - int :l, h 0, len(nums) - 1while l h:mid l (h - l) // 2if l h or l 1 h: # 边界条件breakelif nums[mid] target:l midelse:h mid - 1return nums[h] if nums[h] target else nums[l]nums [1, 2, 3, 4, 5, 6, 7, 8, 10, 11]

nums[bs(nums, 8)]102 回溯法 回溯法的本质是回溯思想通常使用递归实现。 递归的实现需要考虑3个方面搜索的设计、递归的状态及递归的结束条件。 搜索的设计 对求解空间进行划分让每一层递归都去尝试搜索一部分解空间直至搜索完所有可能的解空间。 递归的状态 状态是用来区分不同递归的一般来说我们至少携带一种状态-当前位置idx它用于找到当前可以继续前进的搜索空间以此进入下一层递归。 递归的结束状态 通常包括两个方面找到可行解提前结束搜索搜索完毕已经没有搜索的解空间。

——

ans [] target 0 n 0 nums [] error 0 visited set()

——# idx表示当前位置cur表示当前路径的某个信息path表示路径

def dfs(idx, cur, path):# ————-结束条件# 1 找到解if cur target:ans.append(path.copy())return# 2 搜索完毕if idx n:return# ——————–# 考虑可能的解进入下一层递归for num in nums:if num error or num in visited:continue# 更新状态visited.add(num)dfs(idx 1, cur num, path [num])# 恢复状态visited.remove(num)3 并查集 使用parent数组记录每个节点的父节点在初始情况下每个节点的父结点为本身并使用rank记录每个节点为根的树的权值树的节点数。 find§当parent[p]不为p时表示存在非本身的父节点此时让p等于parent[p]即向上寻找祖先节点不断寻找祖先节点不断重复这个过程直到parnet[p]等于p。union(p, q)通过find(p,q)找到p和q的共同祖先节点然后将权值小的祖先节点树合并到较高的树中。理论证明这种算法能够保证合并后的树高度为O(logn)。 可以使用find§ find(q)来判断两个节点是否属于同一个祖先。 class UnionFind:加权快速合并def init(self, n: int) - None:self.parent [i for i in range(n)] # 每个节点的父节点self.rank [0 for _ in range(n)] # 以该节点为根的树权值树的节点数self.cnt n # 连通区域数量def find(self, p: int) - int: while p ! self.parent[p]:p self.parent[p]return pdef union(self, p: int, q: int) - None: # 按秩合并root_p, root_q self.find(p), self.find(q)if root_p root_q:returnif self.rank[root_p] self.rank[root_q]:self.parent[root_q] root_pelif self.rank[root_p] self.rank[root_q]:self.parent[root_p] root_qelse:self.parent[root_q] root_pself.rank[root_p] 1self.cnt - 1class UnionFind:路径压缩加权快速合并def init(self, n: int) - None:self.parent [i for i in range(n)] # 每个节点的父节点self.rank [0 for _ in range(n)] # 以该节点为根的树权值树的节点数self.cnt n # 连通区域数量def find(self, p: int) - int: # 路径压缩if p ! self.parent[p]:self.parent[p] self.find(self.parent[p])return self.parent[p]def union(self, p: int, q: int) - None: # # 按秩合并root_p, root_q self.find(p), self.find(q)if root_p root_q:returnif self.rank[root_p] self.rank[root_q]:self.parent[root_q] root_pelif self.rank[root_p] self.rank[root_q]:self.parent[root_p] root_qelse:self.parent[root_q] root_pself.rank[root_p] 1self.cnt - 14 BFS 基于队列的广度优先遍历将起始节点放入队列中循环遍历队列中的节点。扩展节点相邻的有效节点并将其放入队列中。 from collections import dequegrid [0 * 5 for _ in range(5)] # n * m的矩阵def bfs(grid):m, n len(grid), len(grid[0])directions [(0, 1), (0, -1), (-1, 0), (1, 0)] # 扩展方向visited [[False] * n for _ in range(m)] # 记录节点是否被访问queue deque()level 0 # 深度queue.append((0, 0))visited[0][0] Truewhile len(queue) 0:sz len(queue)for _ in range(sz):top queue.popleft()x, y top# 扩展节点for d in directions:next_x, next_y x d[0], y d[1]# 判断相邻节点是否有效if next_x 0 or next_x m or next_y 0 or next_y n:continuequeue.append((next_x, next_y))visited[next_x][next_y] Truelevel 1return level5 滑动窗口 借助双指针表示窗口的左边界和右边界并非根据题目要求不断移动指针。 根据窗口大小是否固定以及最优解为最大或最小窗口可以将滑动窗口分为3种类型。 5.1 窗口大小固定最优解与窗口大小无关 nums [] # 题目给定数组 cnt {x : 0 for x in nums} #字典记录出现次数 ans 0 # 答案 init_len 0 # 窗口大小def check(cnt): # 题目所述条件passdef get(left, right): # 题目要求的答案pass# 初始化大小为init_len的窗口 for i in range(init_len):num nums[i]cnt[num] 1left, right 0, init_len# 检查是否满足题目要求 if check(cnt):ans get(left, right)while right len(nums):num, num2 nums[left], nums[right]cnt[num] - 1cnt[num2] 1# 检查是否满足题目要求if check(cnt):# 优化答案ans max(ans, get(left, right))left 1right 15.2 窗口大小不固定最优解为最小窗口 初始化大小为0的滑动窗口然后循环移动窗口直到抵达边界每次右指针right向右移动一步并检查窗口是否满足条件如果是则循环向右移动左指针left每移动一步不断尝试缩小窗口直到窗口不满足条件更新最优解。 left, right 0, 0 nums [] # 题目给定数组 cnt {x : 0 for x in nums} #字典记录出现次数 ans len(nums) # 初始值while right len(nums):cnt[nums[right]] 1# 满足题目要求尽可能缩小窗口while left right and check(cnt):# 优化答案ans min(ans, right - left 1)# 尝试缩小窗口cnt[nums[left]] - 1left 1right 15.3 窗口大小不固定最优解为最大窗口 初始化大小为0的滑动窗口然后循环移动窗口直到抵达边界每次右指针right向右移动一步并检查窗口是否不满足条件如果是则循环向右移动左指针left每移动一步直到满足条件更新最优解。 left, right 0, 0 nums [] # 题目给定数组 cnt {x : 0 for x in nums} #字典记录出现次数 ans 0 # 初始值while right len(nums):cnt[nums[right]] 1# 不满足题目要求需要缩小窗口while not check(cnt):cnt[nums[left]] - 1left 1ans max(ans, right - left 1)right 16 数学 6.1 判断素数 def isPrime(n: int) - bool:if n 1:return Falsei 2while i * i n:if n % i 0:return Falsei 1return TrueisPrime(121)False6.2 最大公约数 欧几里得算法 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 def gcd(a: int, b: int) - int:return a if b 0 else gcd(b, a % b)6.3 最小公倍数 两个数的乘积等于这两个数最大公约数和最小公倍数的乘积最小公倍数 两数乘积 / 两数最大公约数 def lcm(a, int, b: int) - int:return a * b // gcd(a, b)