第7周
2021-11-20
20分钟阅读时长
第7周 第13课 | 字典树和并查集
1. Trie树的基本实现和特性
参考链接
102. 二叉树的层序遍历
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* bfs
* @param TreeNode $root
* @return Integer[][]
*/
function levelOrder($root) {
if (!$root) return [];
$queue = [$root];
$res = [];
while ($queue) {
$count = count($queue);
$row = [];
while ($count--) {
$node = array_shift($queue);
$row[] = $node->val;
$node->left && $queue[] = $node->left;
$node->right && $queue[] = $node->right;
}
$res[] = $row;
}
return $res;
}
//
function levelOrder($root) {
if (!$root) return [];
$res = [];
$this->dfs($res, 0, $root);
return $res;
}
function dfs(&$res, $level, $root) {
if($level == count($res)) $res[] = [];
$res[$level][] = $root->val;
$root->left && $this->dfs($res, $level + 1, $root->left);
$root->right && $this->dfs($res, $level + 1, $root->right);
}
}
208. 实现 Trie (前缀树)
Tire 树代码模板
class Trie(object):
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 node:
return False
node = node[char]
return self.end_of_word in node
def startsWith(self, prefix):
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
2. Trie树实战题目解析：单词搜索2
208. 实现 Trie (前缀树)
class Node {
public $is_end = false;
public $child = [];
}
class Trie {
private $root = null;
/**
* Initialize your data structure here.
*/
function __construct() {
$this->root = new Node();
}
/**
* Inserts a word into the trie.
* @param String $word
* @return NULL
*/
function insert($word) {
$node = &$this->root;
for($i = 0; $i < strlen($word); $i++) {
if( ! isset($node->child[ $word{$i} ])) {
$node->child[ $word{$i} ] = new Node();
}
$node = &$node->child[ $word{$i} ];
if($i == strlen($word)-1) {
$node->is_end = true;
}
}
}
/**
* Returns if the word is in the trie.
* @param String $word
* @return Boolean
*/
function search($word) {
$node = &$this->root;
for($i = 0; $i < strlen($word); $i++) {
if(isset($node->child[ $word{$i} ])) {
$node = &$node->child[ $word{$i} ];
} else {
return false;
}
}
return $node->is_end;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param String $prefix
* @return Boolean
*/
function startsWith($prefix) {
$node = &$this->root;
for($i = 0; $i < strlen($prefix); $i++) {
if(isset($node->child[ $prefix{$i} ])) {
$node = &$node->child[ $prefix{$i} ];
} else {
return false;
}
}
return true;
}
}
//数组实现方法
class Trie {
/**
* Initialize your data structure here.
*/
function __construct() {
$this->root = [];
}
/**
* Inserts a word into the trie.
* @param String $word
* @return NULL
*/
function insert($word) {
$node = &$this->root;
$n = strlen($word);
$word = str_split($word);
foreach ($word as $index=>$char) {
if (!isset($node[$char])) $node[$char] = [0];
if ($index + 1 == $n) {//标识结束
$node[$char][0] = 1;
break;
}
$node = &$node[$char];
}
}
/**
* Returns if the word is in the trie.
* @param String $word
* @return Boolean
*/
function search($word) {
$node = $this->root;
$word = str_split($word);
foreach ($word as $char) {
if (!isset($node[$char])) {
return false;
}
$node = $node[$char];
}
return $node[0] == 1;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param String $prefix
* @return Boolean
*/
function startsWith($prefix) {
$node = $this->root;
$word = str_split($prefix);
foreach ($word as $char) {
if (!isset($node[$char])) {
return false;
}
$node = $node[$char];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* $obj = Trie();
* $obj->insert($word);
* $ret_2 = $obj->search($word);
* $ret_3 = $obj->startsWith($prefix);
*/
212. 单词搜索 II
class TrieNode {
public $children = [];
public $word;
}
class Trie {
/**
* Initialize your data structure here.
*/
function __construct() {
$this->root = new TrieNode();
}
/**
* Inserts a word into the trie.
* @param String $word
* @return NULL
*/
function insert($word) {
$node = &$this->root;
$n = strlen($word);
$nword = str_split($word);
foreach ($nword as $char) {
if (!$node->children[$char]) $node->children[$char] = new TrieNode();
$node = &$node->children[$char];
}
$node->word = $word;
}
/**
* Returns if the word is in the trie.
* @param String $word
* @return Boolean
*/
function search($word) {
$node = $this->root;
$nword = str_split($word);
foreach ($nword as $char) {
if (!$node->children[$char]) return false;
$node = $node->children[$char];
}
return $node->word == $word;
}
public function getRoot()
{
return $this->root;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param String $prefix
* @return Boolean
*/
function startsWith($prefix) {
$node = $this->root;
$word = str_split($prefix);
foreach ($word as $char) {
if (!$node->children[$char]) return false;
$node = $node->children[$char];
}
return true;
}
}
class Solution {
private $res = [];
/**
* @param String[][] $board
* @param String[] $words
* @return String[]
*/
function findWords($board, $words) {
$trie = new Trie();
foreach ($words as $word) {
$trie->insert($word);
}
$n = count($board);
$m = count($board[0]);
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++){
if ($trie->startsWith($board[$i][$j])) {
$this->backtracking($board, $i, $j,$n, $m, $trie->getRoot());
}
}
}
return $this->res;
}
function backtracking(&$board, $i, $j,$n, $m, &$root)
{
$letter = $board[$i][$j];
if ($letter == '#') return;
$board[$i][$j] = '#';
$currNode = &$root->children[$letter];
if ($currNode->word) {
$this->res[] = $currNode->word;
$currNode->word = null;
}
$dx = [0, 1, 0, -1];
$dy = [1, 0, -1, 0];
for ($k = 0; $k < 4; $k++) {
$ni = $i + $dx[$k];
$nj = $j + $dy[$k];
if ($ni < 0 || $ni >= $n || $nj < 0 || $nj >= $m || $board[$ni][$nj] == '#') continue;
if ($currNode->children[$board[$ni][$nj]]) {
$this->backtracking($board, $ni, $nj, $n, $m, $currNode);
}
}
$board[$i][$j] = $letter;
}
}
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
WORD_KEY = '$'
trie = {}
for word in words:
node = trie
for letter in word:
# retrieve the next node; If not found, create a empty node.
node = node.setdefault(letter, {})
# mark the existence of a word in trie node
node[WORD_KEY] = word
rowNum = len(board)
colNum = len(board[0])
matchedWords = []
def backtracking(row, col, parent):
letter = board[row][col]
currNode = parent[letter]
# check if we find a match of word
word_match = currNode.pop(WORD_KEY, False)
if word_match:
# also we removed the matched word to avoid duplicates,
# as well as avoiding using set() for results.
matchedWords.append(word_match)
# Before the EXPLORATION, mark the cell as visited
board[row][col] = '#'
# Explore the neighbors in 4 directions, i.e. up, right, down, left
for (rowOffset, colOffset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
newRow, newCol = row + rowOffset, col + colOffset
if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
continue
if not board[newRow][newCol] in currNode:
continue
backtracking(newRow, newCol, currNode)
# End of EXPLORATION, we restore the cell
board[row][col] = letter
# Optimization: incrementally remove the matched leaf node in Trie.
if not currNode:
parent.pop(letter)
for row in range(rowNum):
for col in range(colNum):
# starting from each of the cells
if board[row][col] in trie:
backtracking(row, col, trie)
return matchedWords
分析单词搜索 2 用 Tire 树方式实现的时间复杂度
请同学们提交在第 7 周的学习总结中。
3. 并查集的基本实现、特性和实战题目解析
参考链接
200. 岛屿数量
并查集代码模板
Java 模板
class UnionFind {
private int count = 0;
private int[] parent;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
}
Python 模板
def init(p):
# for i = 0 .. n: p[i] = i;
p = [i for i in range(n)]
def union(self, p, i, j):
p1 = self.parent(p, i)
p2 = self.parent(p, j)
p[p1] = p2
def parent(self, p, i):
root = i
while p[root] != root:
root = p[root]
while p[i] != i: # 路径压缩 ?
x = i; i = p[i]; p[x] = root
return root
实战题目
547. 朋友圈
class Solution
{
private $parent = [];
private $rank = [];
private $count = 0;
function find(int $i)
{
if ($this->parent[$i] != $i) {
$this->parent[$i] = $this->find($this->parent[$i]);
}
return $this->parent[$i];
}
function union($x, $y)
{
$rootX = $this->find($x);
$rootY = $this->find($y);
if ($rootX != $rootY) {
if ($this->rank[$rootX] > $this->rank[$rootY]) {
$this->parent[$rootY] = $rootX;
} else if ($this->rank[$rootX] < $this->rank[$rootY]) {
$this->parent[$rootX] = $rootY;
} else {
$this->parent[$rootY] = $rootX;
$this->rank[$rootX] += 1;
}
--$this->count;
}
}
/**
* @param String[][] $grid
* @return Integer
*/
function findCircleNum($grid)
{
if (empty($grid) || !$grid[0]) return 0;
$m = $this->count = count($grid);
for ($i = 0; $i < $m; ++$i) {
$this->parent[$i] = $i;
$this->rank[$i] = 0;
}
for ($i = 0; $i < $m; ++$i) {
for ($j = 0; $j < $m; ++$j) {
if ($grid[$i][$j] == 1 && $i != $j) {
$this->union($i, $j);
}
}
}
return $this->count;
}
}
200. 岛屿数量
/**
* 上面的注释是为了直接提交leetcode
* @lc app=leetcode.cn id=200 lang=php
* @author 刘兵兵 <lbbniu@gmail.com>
* 200. 岛屿数量
* 链接：https://leetcode-cn.com/problems/number-of-islands/
*/
class Solution {
/**
* dfs
* @param String[][] $grid
* @return Integer
*/
function numIslands($grid) {
$n = count($grid);
if ($n == 0) return 0;
$m = count($grid[0]);
$count = 0;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
if ($grid[$i][$j] == 1) {
$count++;
$this->bfs($grid, $i, $j, $n, $m);
}
}
}
return $count;
}
function dfs(&$grid, $i, $j, $n, $m)
{
if ($i < 0 || $i >= $n || $j < 0 || $j >= $m || $grid[$i][$j] != 1) return;
$grid[$i][$j] = 0;
$this->dfs($grid, $i + 1, $j, $n, $m);
$this->dfs($grid, $i - 1, $j, $n, $m);
$this->dfs($grid, $i, $j + 1, $n, $m);
$this->dfs($grid, $i, $j - 1, $n, $m);
}
function bfs (&$grid, $i, $j, $n, $m) {
$dx = [0, 1, 0, -1];
$dy = [1, 0, -1, 0];
$queue = [[$i, $j]];
$grid[$i][$j] = 0;
while ($queue) {
[$i, $j] = array_shift($queue);
for ($k = 0; $k < 4; $k++) {
$ni = $i + $dx[$k];
$nj = $j + $dy[$k];
if ($ni >= 0 && $ni < $n && $nj >= 0 && $nj < $m && $grid[$ni][$nj] == 1) {
$queue[] = [$ni, $nj];
$grid[$ni][$nj] = 0;
}
}
}
}
}
class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent.push_back(i * n + j);
++count;
}
else {
parent.push_back(-1);
}
rank.push_back(0);
}
}
}
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty);
}
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
--count;
}
}
int getCount() const {
return count;
}
private:
vector<int> parent;
vector<int> rank;
int count;
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
UnionFind uf(grid);
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
}
}
}
return uf.getCount();
}
};
130. 被围绕的区域
class Solution {
/**
* @param String[][] $board
* @return NULL
*/
function solve(&$board) {
$n = count($board);
$m = count($board[0]);
//替换边缘节点为#
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
$isEdge = $i == 0 || $j == 0 || $i == $n - 1 || $j == $m - 1;
if ($isEdge && $board[$i][$j] == 'O') {
$this->dfs($board, $i, $j, $n, $m);
}
}
}
//填充
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
if ($board[$i][$j] == 'O') {
$board[$i][$j] = 'X';
} else if ($board[$i][$j] == '#'){
$board[$i][$j] = 'O';
}
}
}
}
function dfs(&$board, $i, $j, $n, $m) {
if ($i < 0 || $i >= $n || $j < 0 || $j >= $m || $board[$i][$j] == 'X' ||
$board[$i][$j] == '#') return;
$board[$i][$j] = '#';
$dx = [0, 1, 0, -1];
$dy = [1, 0, -1, 0];
$queue = [[$i, $j]];
$grid[$i][$j] = 0;
for ($k = 0; $k < 4; $k++) {
$ni = $i + $dx[$k];
$nj = $j + $dy[$k];
$this->dfs($board, $ni, $nj, $n, $m);
}
}
}
class UF1
{
private $id = []; // id[i] = parent of i
private $rank = []; // rank[i] = rank of subtree rooted at i (cannot be more than 31)
private $count = 0; // number of components
public function __construct($N)
{
$count = $N;
for ($i = 0; $i < $N; $i++) {
$this->id[$i] = $i;
$this->rank[$i] = 0;
}
}
public function find($p) {
while ($p != $this->id[$p]) {
$this->id[$p] = $this->id[$this->id[$p]]; // path compression by halving
$p = $this->id[$p];
}
return $p;
}
public function getCount() {
return $this->count;
}
public function connected($p, $q) {
return $this->find($p) == $this->find($q);
}
public function connect($p, $q) {
$i = $this->find($p);
$j = $this->find($q);
if ($i == $j) return;
if ($this->rank[$i] < $this->rank[$j])
$this->id[$i] = $j;
else if ($this->rank[$i] > $this->rank[$j])
$this->id[$j] = $i;
else {
$this->id[$j] = $i;
$this->rank[$i]++;
}
$this->count--;
}
}
class UF {
private $parent = [];
public function __construct($m)
{
for ($i = 0; $i < $m; $i++) {
$this->parent[$i] = $i;
}
}
public function connect($x, $y) {
$rootx = $this->find($x);
$rooty = $this->find($y);
if ($rootx != $rooty) {
$this->parent[$rootx] = $rooty;
}
}
public function find($x) {
while ($this->parent[$x] != $x) {
$this->parent[$x] = $this->parent[$this->parent[$x]];
$x = $this->parent[$x];
}
return $this->parent[$x];
}
public function isConnected($x, $y) {
return $this->find($x) == $this->find($y);
}
}
class Solution {
public function solve(&$board) {
$n = count($board);
if($n==0) return;
$m = count($board[0]);
$uf = new UF($n * $m + 1);
for($i = 0; $i<$n; $i++){
for($j = 0; $j < $m; $j++){
if(($i == 0||$i == $n - 1|| $j == 0|| $j == $m - 1) && $board[$i][$j]=='O') // if a 'O' node is on the boundry, connect it to the dummy node
$uf->connect($i*$m+$j,$n*$m);
else if($board[$i][$j]=='O') // connect a 'O' node to its neighbour 'O' nodes
{
if($board[$i-1][$j]=='O')
$uf->connect($i*$m+$j,($i-1)*$m+$j);
if($board[$i+1][$j]=='O')
$uf->connect($i*$m+$j,($i+1)*$m+$j);
if($board[i][j-1]=='O')
$uf->connect($i*$m+$j,$i*$m+$j-1);
if($board[i][j+1]=='O')
$uf->connect($i*$m+$j,$i*$m+$j+1);
}
}
}
for($i=0;$i<$n;$i++){
for($j=0;$j<$m;$j++){
if(!$uf->isConnected($i*$m+$j,$n*$m)){ // if a 'O' node is not connected to the dummy node, it is captured
$board[$i][$j]='X';
}
}
}
}
}
第7周 第14课｜高级搜索
1. 剪枝的实现和特性
参考链接
DFS 代码模板
递归写法
visited = set()
def dfs(node, visited):
if node in visited: # terminator
# already visited
return
visited.add(node)
# process current node here.
...
for next_node in node.children():
if next_node not in visited:
dfs(next_node, visited)
非递归写法
def DFS(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process (node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work
...
BFS 代码模板
AlphaZero Explained
棋类复杂度
2.剪枝实战题目解析：数独
实战题目
70. 爬楼梯
22. 括号生成
51. N皇后
class Solution {
private $col = [];
private $pie = [];
private $na = [];
private $res = [];
/**
* @param Integer $n
* @return String[][]
*/
function solveNQueens($n) {
$this->dfs($n, 0, []);
return $this->res;
}
function dfs($n, $row, $curr_state) {
if ($n == $row) {
$res = [];
foreach ($curr_state as $col) {
$res[] = str_pad('', $col, '.') . 'Q' . str_pad('', $n - $col - 1, '.');
}
$this->res[] = $res;
return;
}
for ($i = 0; $i < $n; $i++) {
if ($this->col[$i] || $this->pie[$row + $i] || $this->na[$row - $i]) continue;
$this->col[$i] = true;
$this->pie[$row + $i] = true;
$this->na[$row - $i] = true;
$curr_state[] = $i;
$this->dfs($n, $row + 1, $curr_state);
array_pop($curr_state);
$this->col[$i] = false;
$this->pie[$row + $i] = false;
$this->na[$row - $i] = false;
}
}
}
36. 有效的数独
class Solution {
/**
* @param String[][] $board
* @return Boolean
*/
function isValidSudoku($board) {
if (count($board) != 9 || count($board[0]) != 9) return false;
$rows = $colunms = $blocks = [];
for ($i = 0; $i < 9; $i++) {
$rows[$i] = [];
$colunms[$i] = [];
$blocks[$i] = [];
}
for ($i = 0; $i < 9; $i++) {
for ($j = 0; $j < 9; $j++) {
if ($board[$i][$j] != '.') {
$num = $board[$i][$j];
$b_index = intval($i / 3) * 3 + intval($j / 3);
if (isset($rows[$i][$num])
|| isset($colunms[$j][$num])
|| isset($blocks[$b_index][$num])) return false;
$rows[$i][$num] = true;
$colunms[$j][$num] = true;
$blocks[$b_index][$num] = true;
}
}
}
return true;
}
}
37. 解数独
class Solution {
/**
* @param String[][] $board
* @return NULL
*/
function solveSudoku(&$board) {
if (count($board) != 9 || count($board[0]) != 9) return false;
//初始化
$rows = $columns = $blocks = [];
$nums = array_flip(range(1, 9));
for ($i = 0; $i < 9; $i++) {
$rows[$i] = $nums;
$columns[$i] = $nums;
$blocks[$i] = $nums;
}
//收集需要填数的位置
$empty = [];
for ($i = 0; $i < 9; $i++) {
for ($j = 0; $j < 9; $j++) {
if ($board[$i][$j] != '.') {
$num = $board[$i][$j];
$b = intval($i / 3) * 3 + intval($j / 3);
unset($rows[$i][$num], $columns[$j][$num], $blocks[$b][$num]);
} else {
$empty[] = [$i, $j];
}
}
}
$this->backtrack($board, $empty, $rows, $columns, $blocks);
}
function backtrack(&$board, $empty, $rows, $columns, $blocks, $index = 0)
{
if ($index == count($empty)) {
return true;
}
[$i, $j] = $empty[$index];
$b = intval($i / 3) * 3 + intval($j / 3);
$nums = array_intersect(array_keys($rows[$i]), array_keys($columns[$j]), array_keys($blocks[$b]));
foreach ($nums as $num) {
unset($rows[$i][$num], $columns[$j][$num], $blocks[$b][$num]);
$board[$i][$j] = (string)$num;
if ($this->backtrack($board, $empty, $rows, $columns, $blocks, $index + 1))
return true;
$rows[$i][$num] = $num;
$columns[$j][$num] = $num;
$blocks[$b][$num] = $num;
}
return false;
}
}
3. 双向BFS的实现、特性和题解
实战题目
127. 单词接龙
class Solution {
/**
* 双bfs
* @param String $beginWord
* @param String $endWord
* @param String[] $wordList
* @return Integer
*/
function ladderLength($beginWord, $endWord, $wordList) {
$wordList = array_flip($wordList);
if (!isset($wordList[$endWord])) return 0;
$queue1 = [$beginWord];
$queue2 = [$endWord];
$visited = [];
$visited[$beginWord] = true;
$n = strlen($beginWord);
$step = 0;
while($queue1) {
if (count($queue1) > count($queue2)) [$queue1, $queue2] = [$queue2, $queue1];
$step++;
$size = count($queue1);
$h2 = array_flip($queue2);
while ($size--) {
$word = array_shift($queue1);
for($i = 0; $i < $n; $i++) {
$old = $word[$i];
for ($k = ord('a'); $k <= ord('z'); $k++) {
if ($old == chr($k)) continue;
$word[$i] = chr($k);
if (isset($h2[$word])) return $step + 1;
if (!$visited[$word] && isset($wordList[$word])) {
$queue1[] = $word;
$visited[$word] = true;
}
}
$word[$i] = $old;
}
}
}
return 0;
}
/**
* 优化双bfs
* @param String $beginWord
* @param String $endWord
* @param String[] $wordList
* @return Integer
*/
function ladderLength($beginWord, $endWord, $wordList) {
$wordList = array_flip($wordList);
if (!isset($wordList[$endWord])) return 0;
$queue1 = [$beginWord];
$queue2 = [$endWord];
$n = strlen($beginWord);
$step = 0;
while($queue1) {
if (count($queue1) > count($queue2)) [$queue1, $queue2] = [$queue2, $queue1];
$step++;
$size = count($queue1);
$h2 = array_flip($queue2);
while ($size--) {
$word = array_shift($queue1);
for($i = 0; $i < $n; $i++) {
$old = $word[$i];
for ($k = ord('a'); $k <= ord('z'); $k++) {
if ($old == chr($k)) continue;
$word[$i] = chr($k);
if (isset($h2[$word])) return $step + 1;
if (isset($wordList[$word])) {
unset($wordList[$word]);
$queue1[] = $word;
}
}
$word[$i] = $old;
}
}
}
return 0;
}
}
433. 最小基因变化
class Solution {
/**
* 双bfs
* @param String $start
* @param String $end
* @param String[] $bank
* @return Integer
*/
function minMutation($start, $end, $bank) {
$bank = array_flip($bank);
if (!isset($bank[$end])) return -1;
if ($start == $end) return 0;
$q1 = [$start];
$q2 = [$end];
$len = strlen($start);
$chars = ['A', 'C', 'G', 'T'];
$step = 0;
while ($q1) {
$step++;
if (count($q1) > count($q2)) [$q1, $q2] = [$q2, $q1];
$size = count($q1);
$h2 = array_flip($q2);
while ($size--) {
$word = array_shift($q1);
for ($i = 0; $i < $len; $i++) {
$old = $word[$i];
foreach ($chars as $char) {
$word[$i] = $char;
if (isset($h2[$word])) return $step;
if (isset($bank[$word])) {
unset($bank[$word]);
$q1[] = $word;
}
}
$word[$i] = $old;
}
}
}
return -1;
}
}
课后作业
总结双向 BFS 代码模版
请同学们提交在第 6 周学习总结中。
4. 启发式搜索的实现、特性和题解
参考链接
def AstarSearch(graph, start, end):
pq = collections.priority_queue() # 优先级 —> 估价函数
pq.append([start])
visited.add(start)
while pq:
node = pq.pop() # can we add more intelligence here ?
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
unvisited = [node for node in nodes if node not in visited]
pq.push(unvisited)
实战题目
1091. 二进制矩阵中的最短路径
class Solution {
/**
* bfs
* @param Integer[][] $grid
* @return Integer
*/
function shortestPathBinaryMatrix($grid) {
$n = count($grid);
$m = count($grid[0]);
if ($grid[0][0] == 1 || $grid[$n - 1][$m - 1] == 1) return -1;
if ($n == 1) return 1;
$queue = [];
$visited = [];
$queue[] = [0, 0];
$visited[0][0] = true;
$ans = 0;
$dx = [0, 1, 0, -1, -1, 1, -1, 1];
$dy = [1, 0, -1, 0, -1, 1 , 1, -1];
while ($queue) {
$ans++;
$size = count($queue);
while ($size--) {
[$x, $y] = array_shift($queue);
//8连通
for ($i = 0; $i < 8; $i++) {
$nx = $x + $dx[$i];
$ny = $y + $dy[$i];
if ($nx >= 0 && $nx < $n && $ny >= 0 && $ny < $m
&& $grid[$nx][$ny] != 1 && !$visited[$nx][$ny]) {
if ($nx == $n - 1 && $ny == $m - 1) return $ans + 1;
$queue[] = [$nx, $ny];
$visited[$nx][$ny] = true;
}
}
}
}
return -1;
}
}
// A* Search 启发式搜索
class Solution {
/**
* @param Integer[][] $grid
* @return Integer
*/
function shortestPathBinaryMatrix($grid) {
$n = count($grid);
$m = count($grid[0]);
if ($grid[0][0] == 1 || $grid[$n - 1][$m - 1] == 1) return -1;
if ($n == 1) return 1;
$pq = new SplMinHeap();
$pq->insert([$grid[0][0] = 1, [0, 0, 1]]);
$dx = [0, 1, 0, -1, -1, 1, -1, 1];
$dy = [1, 0, -1, 0, -1, 1 , 1, -1];
while ($pq->count()) {
$current = $pq->current();
$pq->next();
[$x, $y, $step] = $current[1];
//8连通
for ($i = 0; $i < 8; $i++) {
$nx = $x + $dx[$i];
$ny = $y + $dy[$i];
if ($nx == $n - 1 && $ny == $m - 1) return $step + 1;
if ($nx < 0 || $nx >= $n || $ny < 0 || $ny >= $m) continue;
if ($grid[$nx][$ny] != 0 && $grid[$nx][$ny] <= $step + 1) continue;
$grid[$nx][$ny] = $step + 1;
$p = max(abs($n - 1 - $nx), abs($n - 1 - $ny)) + $grid[$nx][$ny];
$pq->insert([$p, [$nx, $ny, $grid[$nx][$ny]]]);
}
}
return -1;
}
}
773. 滑动谜题
class Solution {
/**
* bfs
* @param Integer[][] $board
* @return Integer
*/
function slidingPuzzle($board) {
$moves = [
[1, 3],
[0, 2, 4],
[1, 5],
[0, 4],
[1, 3, 5],
[2, 4]
];
$used = [];
$cnt = 0;
$s = implode('', array_map(function ($val) {return implode('', $val);}, $board));
$q[] = [$s, strpos($s, '0')];
while ($q) {
$new = [];
foreach ($q as $val) {
[$s, $i] = $val;
$used[$s] = true;
if ($s == '123450') return $cnt;
foreach ($moves[$i] as $move) {
$tmp = $s[$i];
$s[$i] = $s[$move];
$s[$move] = $tmp;
if (!isset($used[$s])) $new[] = [$s, $move];
$tmp = $s[$i];
$s[$i] = $s[$move];
$s[$move] = $tmp;
}
}
$q = $new;
$cnt++;
}
return -1;
}
}
第7周 第15课 | 红黑树和AVL树
AVL树和红黑树的实现和特性
参考链接
平衡树
本周作业
简单
70. 爬楼梯
方法一：暴力递归【时间复杂度：O(2^n)， 空间复杂度：O(n)】
方法二：递归+记忆化 【时间复杂度：O(n)， 空间复杂度：O(n)】
方法三：动态规划 【时间复杂度：O(n)， 空间复杂度：O(n)】
方法四：斐波那契数【时间复杂度：O(n)， 空间复杂度：O(1)】
方法五：Binets 方法（矩阵乘法）【时间复杂度：O(log(n))， 空间复杂度：O(1)】
方法六：斐波那契公式【时间复杂度：O(log(n))， 空间复杂度：O(1)】
public class Solution {
public int climbStairs(int n) {
double sqrt5=Math.sqrt(5);
double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
return (int)(fibn/sqrt5);
}
}
中等
208. 实现 Trie (前缀树)
方法一：使用数组实现
方法二：定义单独的节点实现
547. 朋友圈
方法一：深度优先搜索【时间复杂度：O(n^2)， 空间复杂度：O(n)】
方法二：广度优先搜索【时间复杂度：O(n^2)， 空间复杂度：O(n)】
方法三：并查集【时间复杂度：O(n^3)， 空间复杂度：O(n)】
200. 岛屿数量
方法一：深度优先搜索【时间复杂度：O(MN)， 空间复杂度：O(MN)】
方法二：广度优先搜索【时间复杂度：O(MN)， 空间复杂度：O(min(M,N))】
方法三：并查集【时间复杂度：O(MN∗α(MN))， 空间复杂度：O(MN)】
130. 被围绕的区域
方法一：深度优先搜索
方法二：广度优先搜索
方法三：并查集
36. 有效的数独
方法一：一次迭代【时间复杂度：O(1)， 空间复杂度：O(1)】
//块索引转换
(i / 3 ) * 3 + j / 3
22. 括号生成
方法一：暴力
方法二：回溯法
方法三：按括号序列的长度递归
方法四：深度优先搜索
方法五：广度优先搜索
方法六：动态规划
127. 单词接龙
方法一：单向bfs
方法二：双向bfs
433. 最小基因变化
方法一：单向bfs
方法二：双向bfs
127 和 433 方法相同
1091. 二进制矩阵中的最短路径
方法一：bfs
方法二：A*search（优先级队列）重点优先级计算公式
773. 滑动谜题
方法一：bfs
方法二：A*search（优先级队列）重点优先级计算公式
困难
212. 单词搜索 II
方法一：trie+dfs
方法二：trie+bfs
51. N皇后
方法一：回溯法
方法二：回溯+位运算
方法三：dfs 题解
37. 解数独
方法一：回溯法
下周预习
预习知识点：
- 位图：如何实现网页爬虫中的 URL 去重功能？
- 概率统计：如何利用朴素贝叶斯算法过滤垃圾短信？
- 排序（上）：为什么插入排序比冒泡排序更受欢迎？
- 排序（下）：如何用快排思想在 O(n) 内查找第 K 大元素？
- 线性排序：如何根据年龄给 100 万用户数据排序？
- 排序优化：如何实现一个通用的、高性能的排序函数？
- 堆和堆排序：为什么说堆排序没有快速排序快？
- 拓扑排序：如何确定代码源文件的编译依赖关系？
预习题目：