推荐一波 B站上的 算法与数据结构课程
深度优先算法
深度优先算法和广度优先算法在学习数据结构 图的遍历 中都已经接触过，其中深度有限算法更符合计算机的思维习惯，应用更加广泛。
实例
比如 N皇后问题，数独问题等。以 LeetCode 中 N皇后II 为例：如何将 n 个皇后放在 n 乘 n 的棋盘上，使得皇后之间不能相互攻击。给出所有可行的方案。
这怎么与深度优先有关呢？我们在某一行中放置皇后之后，便去研究下一行该怎么放，直至成功获取一个方案，或这一步不合理需要另作选择。这便是 深度优先 的应用。
假设我们在 (i, j) 位置放置了皇后，那么第 i 行，第j 列， 斜线 y-x = j-i 、y+x = j+i 也不能放了。我们可以在 DFS() 函数中传递已经占用的列、斜线等信息，行数则不需要，因为我们是一行一行地放，皇后们自然不会在同一行。
代码如下所示，用 cur_state 表示占用的列数，row 为当前行数，xy_sub 和 xy_sum 是斜线方程：
def DFS(self, cur_state, row, n, xy_sub, sy_sum):
if row == self.n:
self.res.append(cur_state)
return
for col in range(n):
if col in cur_state or col-row in xy_sub or col+row in xy_sum:
continue
self.DFS(cur_state+[col], row+1, n, xy_sub+[col-row], xy_sum+[col+row])
字典树
字典树也叫前缀树，Trie树。实现：
def __init__(self):
self.root = {}
self.end_of_word = '#'
def insert(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
def search(self, word):
node = self.root
for char in word:
if char not in word:
return False
node = node[char]
return self.end_of_word in node
def startsWith(self, prefix):
node = self.root
for char in word:
if char not in word:
return False
node = node[char]
return self.end_of_word in node
可以看出这是一个嵌套，比如有两个单词 egg、eleven 在 Trie 中，它的结构应该是：`{ e: { g: { g: { #: { # } } }, l :{ e: { v: { e : { n: { # : { # } } } } } } } }。 `
示例 单词搜索II
这道题目我们就可以先把单词列表放到 Trie 中：
trie = {}
for word in words:
node = trie
for char in word:
node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
之后再用深度优先算法在二维网格中搜索：
def dfs(self, board, i, j, cur_word, cur_dict):
if self.end_of_word in cur_dict:
self.res.add(cur_word)
return
temp = board[i][j]
#设置标识，避免重复访问
board[i][j] = '@'
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for k in range(4):
x, y = i + dx[k], j+ dy[k]
if x in range(self.m) and y in range() and board[x][y] != '@' and board[x][y] in cur_dict:
self.dfs(board, x, y, cur_word+board[x][y], cue_dict[board[x][y])
board[x][y] = temp
值得注意的是，在搜索过程中，需要标识访问过的位置，不然将会出现重复访问。比如判断 "aaa"是否在[["a", "a"]]中，很显然不在，但是如果没有标识的话就会返回在。
总结
深度优先和Trie树之前接触较少，现在学了之后有些难题也不那么吓人了。