import sys
def fibonacci(n): # 生成器函数 - 斐波那契
a, b, counter = 0, 1, 0
while True:
if (counter > n):
return
yield a
a, b = b, a + b
counter += 1
f = fibonacci(10) # f 是一个迭代器，由生成器返回生成
while True:
try:
print (next(f), end=" ")
except StopIteration:
sys.exit()
并查集用在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。
# Python Version
fa = [0] * MAXN # 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
# 递归
def find(x):
# 寻找x的祖先
if fa[x] == x:
return x # 如果x是祖先则返回
else:
return find(fa[x]) # 如果不是则 x 的爸爸问 x 的爷爷
# 非递归
def find(x):
while x != fa[x]: # 如果 x 不是祖先，就一直往上一辈找
x = fa[x]
return x # 如果 x 是祖先则返回
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
self.isEnd = '#'
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
if char not in node:
node[char] = {} #如果没有这一字母则新建一个字典
node = node[char]
node[self.isEnd] = '#' #加上结束符
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.isEnd in node #如果没有# 说明只是前缀
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
2.采用defaultdict创建trie
from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
def __init__(self):
self.trie = TrieNode()
def insert(self, word):
reduce(dict.__getitem__, word, self.trie)['end'] = True
def search(self, word):
return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
def startsWith(self, word):
return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())
"""Bisection algorithms."""
def insort_right(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]: hi = mid
else: lo = mid+1
a.insert(lo, x)
insort = insort_right # backward compatibility
def bisect_right(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]: hi = mid
else: lo = mid+1
return lo
bisect = bisect_right # backward compatibility
def insort_left(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
a.insert(lo, x)
def bisect_left(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
except ImportError:
pass
方法介绍
bisect模块采用经典的二分算法查找元素。模块提供下面几个方法：
bisect.bisect_left(a, x, lo=0, hi=len(a))：返回待插入值应该放置的位置下标，如果 a 中有和x相同的元素，就在返回该元素左边的下标，即在左边插入
堆是一种数据结构，它是一颗完全二叉树。最小堆则是在堆的基础增加了新的规则，它的根结点的值是最小的，而且它的任意结点的父结点的值都小于或者等于其左右结点的值。因为二进制堆可以使用有组织的列表或数组来表示，所以元素N的子元素位于位置2 * N + 1和2 * N + 2。这种布局使重新安排堆成为可能，因此在添加或删除项时不需要重新分配那么多内存 区分堆(heap)与栈(stack)：堆与二叉树有关，像一堆金字塔型泥沙；而栈像一个直立垃圾桶，一列下来。
