...
https://leetcode.com/problems/open-the-lock/
| Code Block | ||
|---|---|---|
| ||
import "fmt" func openLock(deadends []string, target string) int { var q []string visited := make(map[string]bool) for _, x := range deadends { visited[x] = true } if visited["0000"] { return -1 } q = append(q, "0000") visited["0000"] = true step := 0 for len(q) > 0 { qq := q q = nil for _, node := range qq { if node == target { return step } for _, next := range getNext(node) { if visited[next] { continue } q = append(q, next) visited[next] = true } } step++ } return -1 } func getNext(node string) []string { result := make([]string, 0, 8) nb := []byte(node) add := func(i, x int) { v := (int(nb[i] - '0') + x + 10) % 10 nb[i] = '0' + byte(v) } for i := 0; i < 4; i++ { add(i, 1) result = append(result, string(nb)) add(i, -2) result = append(result, string(nb)) add(i, 1) } return result } |
优化：双向 BFS
头尾同时遍历（实际代码上是遍历一端完再遍历另一端），出现交集时返回
| Code Block | ||
|---|---|---|
| ||
func openLock(deadends []string, target string) int {
visited := make(map[string]bool)
for _, x := range deadends {
visited[x] = true
}
if visited["0000"] {
return -1
}
q1 := make(map[string]bool)
q2 := make(map[string]bool)
q1["0000"] = true
q2[target] = true
step := 0
for len(q1) > 0 && len(q2) > 0 {
temp := make(map[string]bool)
for node := range q1 {
if q2[node] {
return step
}
visited[node] = true
for _, next := range getNext(node) {
if visited[next] {
continue
}
temp[next] = true
}
}
step++
q1, q2 = q2, temp
}
return -1
}
func getNext(node string) []string {
result := make([]string, 0, 8)
nb := []byte(node)
add := func(i, x int) {
v := (int(nb[i] - '0') + x + 10) % 10
nb[i] = '0' + byte(v)
}
for i := 0; i < 4; i++ {
add(i, 1)
result = append(result, string(nb))
add(i, -2)
result = append(result, string(nb))
add(i, 1)
}
return result
} |
二叉树
...
LC 144. Binary Tree Preorder Traversal 二叉树的前序遍历
https://leetcode.com/problems/binary-tree-preorder-traversal/description/
| Code Block | ||
|---|---|---|
| ||
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) (result []int) {
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
result = append(result, node.Val)
traverse(node.Left)
traverse(node.Right)
}
traverse(root)
return
} |
LC 543. Diameter of Binary Tree 二叉树的直径
https://leetcode.com/problems/diameter-of-binary-tree/description/
二叉树的直径定义：二叉树中任意两个节点的最大距离（边数）
| Code Block | ||
|---|---|---|
| ||
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func diameterOfBinaryTree(root *TreeNode) (diameter int) {
traverse(root, &diameter)
return
}
func traverse(root *TreeNode, diameter *int) int {
if root == nil {
return 0
}
leftCount := traverse(root.Left, diameter)
rightCount := traverse(root.Right, diameter)
*diameter = max(*diameter, leftCount + rightCount + 1)
return max(leftCount, rightCount) + 1
} |
LC 104. Maximum Depth of Binary Tree 二叉树的最大深度
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
深度：从根节点到叶子结点的最长节点数
| Code Block | ||
|---|---|---|
| ||
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
} |