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相同的元素，就在返回该元素左边的下标，即在左边插入
def outer_fun():
a = 1
def fun():
nonlocal a # a为外层变量
print(a) # 输出1
a = 2
fun()
print(a) #输出2
outer_fun()
注意：可以发现，之前的将 global 换为 nonlocal 的报错，和这次的将 nonlocal 改为 global 的报错，错误类型是不同的。前者是 nonlocal a 这一行报错，后者是 print(a) 这一行报错。也就是说，在使用 nonlocal a 之前，必须保证外层的确已经定义过 a 了，但是在 global a 的时候，可以允许全局变量中还没有定义过a，可以留在后面定义。比如将 print(a) 之前加上对a的定义，便不会出错：
def outer_fun():
a = 1
def fun():
global a # a为全局变量，与上面等于1的 a 没有关系
a = 3 # 定义全局变量
print(a) # 输出3
a = 2
fun()
print(a) #输出1，局部变量
outer_fun()
print(a) # 输出2，全局变量
