二分法
我总结的一般写法
class Solution:
def search(self, nums, target):
# step1:定义初始搜索范围
left,right=0,len(nums)-1
if left==right:return None # step1.1 增加鲁棒性，也就是一开始即达到结束条件。需不需要视 step4是否容易写而定
# step2：定义结束时的搜索范围，一般为left==right，但某些问题未必
while left<right:
mid=(left+right)//2
if nums[mid]<target: # step2.5：必须把所有的if考虑到，否则有可能死循环
left=mid+1
elif nums[mid]>target:
right=mid-1
elif nums[mid]==target: # step3：搜索时遇到解，便直接返回。如果是复杂形式，注意index out of range
return mid
# step4:搜索结束后的小区域的情况判断。这里小区域范围为1，且必为解，因此无需多做处理。
# 一般情况下，应当处理这个小区域
mid=left # 为了可读性（代码表示的统一性）。注意决不能直接使用之前的mid，因为那个赋值是否运行是不一定的
# if nums[left]==target: # 一般情况下，与while循环中的return出口条件一致
# return mid
# else:return -1
return -1
注：
- 某些题目中，可能搜索不到，让输出四舍五入解。最后一步的left可能越过“有理数解”，所以需要检查left-1
- 理论上right也可能越过，（不过如果要求输出舍弃小数，其实不用检查的）
LeetCode上的写法
第一种
def binarySearch(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# End Condition: left > right
return -1
- Initial Condition:
left = 0, right = length-1 - Termination:
left > right - Searching Left:
right = mid-1 - Searching Right:
left = mid+1
第二种
- Initial Condition:
left = 0, right = length - Termination:
left == right - Searching Left:
right = mid - Searching Right:
left = mid+1
第三种
- Initial Condition:
left = 0, right = length-1 - Termination:
left + 1 == right - Searching Left:
right = mid - Searching Right:
left = mid
并查集
class UnionFind:
def __init__(self, n: int):
self.n = n # 元素的个数
self.cnt = n # 类的个数
self.parent = list(range(n))
self.depth = [1] * n # 树的深度，根结点那里有效，其余都是1
def find(self, x: int) -> int:
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
# x,y 原本就是1类
return False
if self.depth[root_x] > self.depth[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_x] = root_y
self.depth[root_y] += self.depth[root_x]
self.cnt -= 1
return True
def is_connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
- 并查集的解释 https://zhuanlan.zhihu.com/p/93647900/
- 对查询做了优化，做find的时候，自动把节点连接到根结点，
- 元素是 list(range(n)) 的int类型
简化版并查集
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
def find(self, idx: int) -> int:
if idx != self.parent[idx]:
self.parent[idx] = self.find(self.parent[idx])
return self.parent[idx]
def union(self, idx1: int, idx2: int):
self.parent[self.find(idx1)] = self.find(idx2)
def is_connected(self, idx1: int, idx2: int) -> bool:
return self.find(idx1) == self.find(idx2)
parent 是什么？
- parent[idx] 是 idx 的上一级，
- 如果被 find 过， parent[idx] 是根节点。否则的话是父节点，因此不能直接
len(set(parent))来判断有几个类 i == parent[i]用来判断 i 是否是根结点。（进而计算有几个类）
