31 剪枝
是在搜索中必用的优化手段
先回顾一下搜索：(BFS、DFS)
AlphaGo
没有模板，要具体问题具体分析
32 N皇后问题
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
#代码的规范
if n<1:
return []
self.result=[]
self.cols=set();
self.pie=set()
self.na=set()
self.DFS(n,0,[])
return self._genetrate_result(n)
def DFS(self,n,row,cur_state):
if row==n:
self.result.append(cur_state)
return
for col in range(n):
if col in self.cols or row+col in self.pie or row-col in self.na:
continue
self.cols.add(col)
self.pie.add(row+col)
self.na.add(row-col)
self.DFS(n,row+1,cur_state+[col])
self.cols.remove(col)
self.pie.remove(row+col)
self.na.remove(row-col)
def _genetrate_result(self,n):
board=[]
for res in self.result:
for i in res:
board.append("."*i+"Q"+"."*(n-i-1))
return [board[i:i+n] for i in range(0,len(board),n)]
33、数独问题
搜索+剪枝
34、二分查找
该方法使用的条件
为了避免出现溢出问题，二分查找代码的第三行建议写为：
mid=left+(right-left)/2
35、实现一个求解平方根的函数
https://blog.csdn.net/zuyuhuo6777/article/details/90546725
36、字典树
37、实现一个字典树
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root={}
self.end_of_word= "#"
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node=self.root
for char in word:
node=node.setdefault(char,{})
node[self.end_of_word]=self.end_of_word
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.end_of_word 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
38 二维网格中的单词搜索问题
1、深度优先搜索（DFS）
2、Trie类
39 位运算
(Bitwise operations)
40、统计位的个数
代码：https://mp.csdn.net/postedit/90546725
