第3周 树、递归、分治、回溯
2021-12-02
21分钟阅读时长
题目数量：29+
第6课 | 树、二叉树、二叉搜索树
1. 树、二叉树、二叉搜索树的实现和特性
参考链接
思考题
树的面试题解法一般都是递归，为什么？ 说明：同学们可以将自己的思考写在课程下方的留言区一起讨论，也可以写在第 2 周的学习总结中。
2. 实战题目解析：二叉树的中序遍历
参考链接
实战题目 / 课后作业
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 递归
func inorderTraversal1(root *TreeNode) []int {
var inorder func (root *TreeNode)
var res []int
inorder = func (root *TreeNode) {
if root == nil {
return
}
inorder(root.Left)
res = append(res, root.Val)
inorder(root.Right)
}
inorder(root)
return res
}
// 直接迭代
func inorderTraversal2(root *TreeNode) (res []int) {
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack) - 1]
res = append(res, root.Val)
root = root.Right
}
return res
}
type Node struct {
N *TreeNode
Color int
}
// 着色迭代遍历
func inorderTraversal(root *TreeNode) (res []int) {
if root == nil {
return
}
stack := []*Node{&Node{N:root, Color:0}}
for len(stack) > 0 {
node := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if node.Color == 1 {
res = append(res, node.N.Val)
} else {
if node.N.Right != nil {
stack = append(stack, &Node{N:node.N.Right, Color: 0})
}
node.Color = 1
stack = append(stack, node)
if node.N.Left != nil {
stack = append(stack, &Node{N:node.N.Left, Color: 0})
}
}
}
return res
}
// Morris 中序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 递归
func preorderTraversal1(root *TreeNode) (res []int) {
var preorder func (root *TreeNode)
preorder = func (root *TreeNode) {
if root == nil {
return
}
res = append(res, root.Val)
preorder(root.Left)
preorder(root.Right)
}
preorder(root)
return
}
// 迭代
func preorderTraversal2(root *TreeNode) (res []int) {
if root == nil {
return
}
stack := []*TreeNode{root}
for len(stack) > 0 {
root = stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
res = append(res, root.Val)
if root.Right != nil {
stack = append(stack, root.Right)
}
if root.Left != nil {
stack = append(stack, root.Left)
}
}
return
}
type Node struct {
N *TreeNode
Color int
}
// 着色迭代遍历
func preorderTraversal(root *TreeNode) (res []int) {
if root == nil {
return
}
stack := []*Node{&Node{N:root, Color:0}}
for len(stack) > 0 {
node := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if node.Color == 1 {
res = append(res, node.N.Val)
} else {
if node.N.Right != nil {
stack = append(stack, &Node{N:node.N.Right, Color: 0})
}
if node.N.Left != nil {
stack = append(stack, &Node{N:node.N.Left, Color: 0})
}
node.Color = 1
stack = append(stack, node)
}
}
return res
}
// Morris 遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal1(root *TreeNode) (res []int) {
var postorder func(root *TreeNode)
postorder = func(root *TreeNode) {
if root == nil {
return
}
postorder(root.Left)
postorder(root.Right)
res = append(res, root.Val)
}
postorder(root)
return
}
type Node struct {
N *TreeNode
Color int
}
// 着色迭代遍历
func postorderTraversal2(root *TreeNode) (res []int) {
if root == nil {
return
}
stack := []*Node{&Node{N:root, Color:0}}
for len(stack) > 0 {
node := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if node.Color == 1 {
res = append(res, node.N.Val)
} else {
node.Color = 1
stack = append(stack, node)
if node.N.Right != nil {
stack = append(stack, &Node{N:node.N.Right, Color: 0})
}
if node.N.Left != nil {
stack = append(stack, &Node{N:node.N.Left, Color: 0})
}
}
}
return res
}
// 迭代 需要仔细体会
func postorderTraversal(root *TreeNode) (res []int) {
stack := []*TreeNode{}
var prev *TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if root.Right == nil || root.Right == prev {
res = append(res, root.Val)
prev = root
root = nil
} else {
stack = append(stack, root)
root = root.Right
}
}
return res
}
// Morris 遍历
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func postorder1(root *Node) (res []int) {
var order func(root *Node)
order = func(root *Node) {
if root == nil {
return
}
for _, children := range root.Children {
order(children)
}
res = append(res, root.Val)
}
order(root)
return
}
// 性能更好
func postorder2(root *Node) (res []int) {
var order func(root *Node)
order = func(root *Node) {
if root == nil {
return
}
n := len(root.Children)
for i := 0; i < n; i++ {
order(root.Children[i])
}
res = append(res, root.Val)
}
order(root)
return
}
// 迭代
func postorder(root *Node) (res []int) {
if root == nil {
return
}
stack := []*Node{root}
for len(stack) > 0 {
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
for n, i := len(root.Children), 0; i < n; i++ {
stack = append(stack, root.Children[i])
}
}
return reverse(res)
}
func reverse(s []int) []int {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
return s
}
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func preorder1(root *Node) (res []int) {
var pre func(root *Node)
pre = func(root *Node) {
if root == nil {
return
}
res = append(res, root.Val)
for _, children := range root.Children {
pre(children)
}
}
pre(root)
return
}
// 性能更好
func preorder2(root *Node) (res []int) {
var pre func(root *Node)
pre = func(root *Node) {
if root == nil {
return
}
res = append(res, root.Val)
n := len(root.Children)
for i := 0; i < n; i++ {
pre(root.Children[i])
}
}
pre(root)
return
}
// 迭代
func preorder(root *Node) (res []int) {
if root == nil {
return
}
stack := []*Node{root}
for len(stack) > 0 {
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
for idx := len(root.Children) - 1; idx >= 0; idx-- {
stack = append(stack, root.Children[idx])
}
}
return
}
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
// bfs
func levelOrder(root *Node) (res [][]int) {
if root == nil {
return
}
queue := []*Node{root}
for len(queue) > 0 {
n := len(queue)
tmp := []*Node{}
level := []int{}
for i := 0; i < n; i++ {
level = append(level, queue[i].Val)
for _, c := range queue[i].Children {
tmp = append(tmp, c)
}
}
res = append(res, level)
queue = tmp
}
return res
}
第6课 | 堆和二叉堆、图
1. 堆和二叉堆的实现和特性
参考链接
2. 实战题目解析：最小的k个数、滑动窗口最大值等问题
实战例题
// 快排思想
// 参考：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/
func getLeastNumbers(arr []int, k int) []int {
if k == 0 || len(arr) == 0 {
return nil
}
return quickSort(arr, 0, len(arr) - 1, k - 1)
//return arr[:k]
}
func quickSort(arr []int, l, r, k int) []int {
idx := partition(arr, l, r)
if idx == k {
return arr[:k+1]
}
if idx < k {
return quickSort(arr, idx + 1, r, k)
} else { // idx > k
return quickSort(arr, l, idx - 1, k)
}
}
func partition(arr []int, l, r int) int {
mid := arr[l]
i, j := l + 1, r
for {
for i <= j && arr[i] <= mid {
i++
}
for i <= j && arr[j] >= mid {
j--
}
if i >= j {
break
}
arr[i], arr[j] = arr[j], arr[i]
}
arr[l], arr[j] = arr[j], mid
return j
}
// 双端队列
func maxSlidingWindow(nums []int, k int) (res []int) {
dq := []int{}
for i := 0; i < len(nums); i++ {
// 移除越界
if len(dq) > 0 && dq[0] <= i - k {
dq = dq[1:]
}
// 移除比当前数小的
for len(dq) > 0 && nums[dq[len(dq)-1]] < nums[i] {
dq = dq[:len(dq)-1]
}
dq = append(dq, i)
if i >= k - 1 {
res = append(res, nums[dq[0]])
}
}
return res
}
// 大顶堆
type IHeap [][2]int
func (h IHeap) Len() int { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}
func (h *IHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func topKFrequent(nums []int, k int) []int {
}
课后作业
- HeapSort ：自学 https://www.geeksforgeeks.org/heap-sort/
- 面试题49. 丑数 和 264. 丑数 II
// 方法一：动态规划 最优
func nthUglyNumber(n int) int {
dp := make([]int, n + 1)
dp[1] = 1
p2, p3, p5 := 1, 1, 1
for i := 2; i <= n; i++ {
x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
dp[i] = min(min(x2, x3), x5)
if dp[i] == x2 {
p2++
}
if dp[i] == x3 {
p3++
}
if dp[i] == x5 {
p5++
}
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// 方法二：小顶堆
var factors = []int{2, 3, 5}
func nthUglyNumber(n int) int {
h := &hp{sort.IntSlice{1}}
seem := map[int]struct{}{1:{}}
for i := 2; i <= n; i++ {
v := heap.Pop(h).(int)
if i == n {
return v
}
for _, p := range factors {
pv := p * v
if _, ok := seem[pv]; !ok {
heap.Push(h, pv)
seem[pv] = struct{}{}
}
}
}
}
type hp struct{sort.IntSlice }
func (h *hp) Push(v interface{}) {
h.IntSlice = append(h.IntSlice, v.(int))
}
func (h *hp) Pop() interface{} {
a := h.IntSlice
v := a[len(a) - 1]
h.IntSlice = a[:len(a) - 1]
return v
}
type IHeap [][2]int
func (h IHeap) Len() int { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IHeap) Push(v interface{}) {
*h = append(*h, v.([2]int))
}
func (h *IHeap) Pop() interface{} {
old := *h
v := old[len(old) - 1]
*h = old[:len(old) - 1]
return v
}
func topKFrequent(nums []int, k int) []int {
mp := map[int]int{}
for _, num := range nums {
mp[num]++
}
h := &IHeap{}
heap.Init(h)
for key, value := range mp {
heap.Push(h, [2]int{key, value})
if h.Len() > k {
heap.Pop(h)
}
}
res := make([]int, k)
for i := 0; i < k; i++ {
res[k - i - 1] = heap.Pop(h).([2]int)[0]
}
return res
}
3. 图的实现和特性
思考题
- 自己画一下有向有权图
参考链接
- 连通图个数：200. 岛屿数量 重点
var fx = [][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}}
// dfs
func numIslands(grid [][]byte) (res int) {
n, m := len(grid), len(grid[0])
var dfs func (x, y int)
dfs = func (x, y int) {
grid[x][y] = 'x'
for _, d := range fx {
nx, ny := x + d[0], y + d[1]
if 0 <= nx && nx < n && 0 <= ny && ny < m && grid[nx][ny] == '1' {
dfs(nx, ny)
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == '1' {
res++
dfs(i, j)
}
}
}
return res
}
// bfs
// 并查集 待练习
- 拓扑排序（Topological Sorting）： https://zhuanlan.zhihu.com/p/34871092
- 最短路径（Shortest Path）：Dijkstra https://www.bilibili.com/video/av25829980?from=search&seid=13391343514095937158
- 最小生成树（Minimum Spanning Tree）： https://www.bilibili.com/video/av84820276?from=search&seid=17476598104352152051
第7课 | 泛型递归、树的递归
1. 递归的实现、特性以及思维要点
参考链接
2. 实战题目解析：爬楼梯、括号生成等问题
实战题目
// 递归
var mp = map[int]int{}
func climbStairs(n int) int {
if n <= 2 {
return n
}
if _, ok := mp[n]; !ok {
mp[n] = climbStairs(n - 1) + climbStairs(n - 2)
}
return mp[n]
}
// 动态规划
func climbStairs(n int) int {
i, j, k := 0, 1, 0
for m := 1; m <= n; m++ {
k = i + j
i, j = j, k
}
return k
}
func climbStairs(n int) int {
if n <= 2 {
return n
}
dp := make([]int, n + 1)
dp[1], dp[2] = 1, 2
for i := 3; i <= n; i++ {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
// 矩阵
// 通项公式
// 递归
func generateParenthesis(n int) (res []string) {
var helper func(l, r int, p string)
helper = func(l, r int, p string) {
if l == n && r == n {
res = append(res, p)
return
}
if l < n {
helper(l + 1, r, p + "(")
}
if r < l {
helper(l, r + 1, p + ")")
}
}
helper(0, 0, "")
return res
}
// 非递归：
type node struct {
res string
left int
right int
}
func generateParenthesis(n int) []string {
ans := []string{}
queue := []node{}
queue = append(queue, newNode("", n, n))
for len(queue) > 0 {
n := queue[0]
queue = queue[1:]
if n.left == 0 && n.right == 0 {
ans = append(ans, n.res)
}
if n.left > 0 {
queue = append(queue, newNode(n.res + "(", n.left - 1, n.right))
}
if n.left < n.right && n.right > 0 {
queue = append(queue, newNode(n.res + ")", n.left, n.right - 1))
}
}
return ans
}
func newNode(res string, left, right int) node {
return node{
res: res,
left: left,
right: right,
}
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 递归
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
// 非递归：使用队列，迭代
func invertTree(root *TreeNode) *TreeNode {
}
// 递归
func isValidBST(root *TreeNode) bool {
var isValid func(root *TreeNode, min, max int) bool
isValid = func(root *TreeNode, min, max int) bool {
if root == nil {
return true
}
if root.Val <= min || root.Val >= max {
return false
}
return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
}
return isValid(root, math.MinInt64, math.MaxInt64)
}
// 递归中序遍历
// 迭代中序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 递归， dfs
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// bfs
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 递归（深度优先遍历）
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 1
}
ld, rd := minDepth(root.Left), minDepth(root.Right)
if ld == 0 || rd == 0 {
return ld + rd + 1
}
return min(ld, rd) + 1
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// bfs, 广度优先遍历
func minDepth(root *TreeNode) (res int) {
if root == nil {
return 0
}
queue := []*TreeNode{}
depth := []int{}
queue = append(queue, root)
depth = append(depth, 1)
for len(queue) > 0 {
n := len(queue)
for i := 0; i < n; i++ {
root := queue[0]
level := depth[0]
queue = queue[1:]
depth = depth[1:]
if root.Left == nil && root.Right == nil {
return level
}
if root.Left != nil {
queue = append(queue, root.Left)
depth = append(depth, level + 1)
}
if root.Right != nil {
queue = append(queue, root.Right)
depth = append(depth, level + 1)
}
}
}
return res
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 前序遍历
type Codec struct {
}
func Constructor() *Codec {
return &Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
sb := &strings.Builder{}
var preorder func(root *TreeNode)
preorder = func (root *TreeNode) {
if root == nil {
sb.WriteString("null,")
return
}
sb.WriteString(strconv.Itoa(root.Val))
sb.WriteByte(',')
preorder(root.Left)
preorder(root.Right)
}
preorder(root)
return sb.String()
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
sp := strings.Split(data, ",")
var decode func() *TreeNode
decode = func() *TreeNode {
val := sp[0]
sp = sp[1:]
if val == "null" {
return nil
}
v, _ := strconv.Atoi(val)
return &TreeNode{v, decode(), decode()}
}
return decode()
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/
每日一课
课后作业
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || p == root || q == root {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left == nil {
return right
} else if right == nil {
return left
}
return root
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// 递归
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{Val: preorder[0]}
i := 0
for ; i < len(inorder); i++ {
if preorder[0] == inorder[i] {
break
}
}
root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[0:i])
root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
return root
}
// 迭代
// 参考php中的写法
func combine(n int, k int) (res [][]int) {
path := []int{}
var bracktrack func (int)
bracktrack = func(first int) {
if len(path) == k {
res = append(res, append([]int(nil), path...))
return
}
for i := first; n - i + 1 >= k - len(path); i++ {
path = append(path, i)
bracktrack(i + 1)
path = path[:len(path) - 1]
}
}
bracktrack(1)
return res
}
// 官方： 递归实现组合型枚举
// 官方：非递归（字典序法）实现组合型枚举
第8课 | 分治、回溯
1. 分治、回溯的实现和特性
参考链接
2. 实战题目解析：Pow(x,n)、子集
预习题目
func myPow(x float64, n int) float64 {
if n == 0 {
return 1
}
if n < 0 {
n = -n
x = 1 / x
}
p := myPow(x, n >> 1)
if n & 1 == 0 {
return p * p
} else {
return x * p * p
}
}
// 多种写法勤加练习
// 迭代
// 递归
参考链接
3. 实战题目解析：电话号码的字母组合、N皇后
实战题目
- 169. 多数元素 （简单、但是高频）
// 分治
// hash表
// 排序
// 随机
// 官方方法五：Boyer-Moore 投票算法 重点
func majorityElement(nums []int) (ans int) {
count := 0
for _, num := range nums {
if count == 0 {
ans = num
}
if ans == num {
count++
} else {
count--
}
}
return ans
}
// dfs
// 写法一：
var mp = map[string]string{
"2": "abc",
"3": "edf",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
func letterCombinations(digits string) (res []string) {
if digits == "" {
return res
}
n := len(digits)
var dfs func(string, int)
dfs = func(path string, idx int){
if idx == n {
res = append(res, path)
return
}
letters := mp[string(digits[idx])]
for _, c := range letters {
dfs(path + string(c), idx + 1)
}
}
dfs("", 0)
return res
}
// 写法二：dfs
var digitMap = map[byte][]byte{
'2': {'a', 'b', 'c'},
'3': {'d', 'e', 'f'},
'4': {'g', 'h', 'i'},
'5': {'j', 'k', 'l'},
'6': {'m', 'n', 'o'},
'7': {'p', 'q', 'r', 's'},
'8': {'t', 'u', 'v'},
'9': {'w', 'x', 'y', 'z'},
}
var buf []byte
var ans []string
func letterCombinations(digits string) []string {
buf = buf[:0]
ans = ans[:0]
if len(digits) == 0 {
return ans
}
dfs(digits, 0)
return ans
}
func dfs(digits string, n int) {
if n == len(digits) {
ans = append(ans, string(buf))
return
}
for _, v := range digitMap[digits[n]] {
buf = append(buf, v)
dfs(digits, n+1)
buf = buf[:len(buf)-1]
}
return
}
// bfs, 队列迭代
func letterCombinations(digits string) (res []string) {
if len(digits) == 0 {
return res
}
res = append(res, "")
for _, digit := range digits {
n := len(res)
for ; n > 0; n-- {
m := res[0]
res = res[1:]
for _, d := range mp[string(digit)] {
res = append(res, m + string(d))
}
}
}
return res
}
// 普通dfs
func solveNQueens(n int) (res [][]string) {
pie, na, col := map[int]bool{}, map[int]bool{}, map[int]bool{}
var dfs func(int, []int)
dfs = func (row int, queen []int) {
// 递归终止
if row == n {
ans := []string{}
for _, c := range queen {
r := make([]byte, 0, n)
for i := 0; i < n; i++ {
if i == c {
r = append(r, 'Q')
} else {
r = append(r, '.')
}
}
ans = append(ans, string(r))
}
res = append(res, ans)
return
}
for i := 0; i < n; i++ {
if pie[i + row] || na[i - row] || col[i] {
continue
}
pie[i + row] = true
na[i - row] = true
col[i] = true
queen = append(queen, i)
dfs(row + 1, queen)
queen = queen[:len(queen) - 1]
col[i] = false
na[i - row] = false
pie[i + row] = false
}
}
dfs(0, []int{})
return
}
// 官方：位运算 dfs
var solutions [][]string
func solveNQueens(n int) [][]string {
solutions = [][]string{}
queens := make([]int, n)
for i := 0; i < n; i++ {
queens[i] = -1
}
solve(queens, n, 0, 0, 0, 0)
return solutions
}
func solve(queens []int, n, row, columns, diagonals1, diagonals2 int) {
if row == n {
board := generateBoard(queens, n)
solutions = append(solutions, board)
return
}
availablePositions := ((1 << n) - 1) & (^(columns | diagonals1 | diagonals2))
for availablePositions != 0 {
position := availablePositions & (-availablePositions)
availablePositions = availablePositions & (availablePositions - 1)
column := bits.OnesCount(uint(position - 1))
queens[row] = column
solve(queens, n, row + 1, columns | position, (diagonals1 | position) >> 1, (diagonals2 | position) << 1)
queens[row] = -1
}
}
func generateBoard(queens []int, n int) []string {
board := []string{}
for i := 0; i < n; i++ {
row := make([]byte, n)
for j := 0; j < n; j++ {
row[j] = '.'
}
row[queens[i]] = 'Q'
board = append(board, string(row))
}
return board
}
// 自己写法一
func solveNQueens(n int) (res [][]string) {
var dfs func(int, int, int, int, []int)
dfs = func (row, pie, na, col int, picks []int) {
// 递归终止
if row == n {
ans := []string{}
for _, c := range picks {
r := make([]byte, 0, n)
for i := 0; i < n; i++ {
if c & (1 << i) > 0 {
r = append(r, 'Q')
} else {
r = append(r, '.')
}
}
ans = append(ans, string(r))
}
res = append(res, ans)
return
}
// 取所有可以放的位置
bits := (^(pie | na | col)) & (1 << n - 1)
for bits > 0 {
// 取可以放的位置
p := bits & - bits
bits = bits & (bits - 1) // 移除最后一个1位
picks[row] = p
dfs(row + 1, (pie | p) << 1, (na | p) >> 1, col | p, picks)
}
}
dfs(0, 0, 0 , 0, make([]int, n))
return
}
// 自己写法二
var ress [][]string
func solveNQueens(n int) [][]string {
ress = [][]string{}
dfs(n, 0, 0, 0, 0, make([]int, n))
return ress
}
func dfs(n, row, cols, pie, na int, picks []int) {
//处理结果
if n <= row {
res := make([]string, n)
for index, col := range picks {
str := ""
for i := 0; i < n; i++ {
if col & (1 << i) > 0 {
str += "Q"
} else {
str += "."
}
}
res[index] = str
}
ress = append(ress, res)
return
}
bits := (^(cols | pie | na)) & ((1 << n) - 1) //获取所有二进制1位
for bits > 0 {
p := bits & -bits
picks[row] = p;
dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1, picks);
bits = bits & (bits - 1);
}
}
本周作业及下周预习
本周作业
简单
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func postorder(root *Node) []int {
}
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func preorder(root *Node) []int {
}
中等
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
}
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) [][]int {
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
}
func combine(n int, k int) [][]int {
}
func permute(nums []int) [][]int {
}
func permuteUnique(nums []int) [][]int {
}
下周预习
预习知识点
- 深度和广度优先搜索：如何找出社交网络中的三度好友关系？
- 贪心算法：如何用贪心算法实现 Huffman 压缩编码？
- 二分查找（上）：如何用最省内存的方式实现快速查找功能？
- 二分查找（下）：如何快速定位 IP 对应的省份地址？