二叉树的层序遍历

简单的 BFS 练习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func levelOrder(root *TreeNode) [][]int {
    ans := [][]int{}
    if root == nil {
        return ans
    }
    queue := []TreeNode{}
    queue = append(queue, *root)

    for len(queue) != 0 {
        tmpAns := []int{}
        nextLevel := []TreeNode{}

        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]

            tmpAns = append(tmpAns, curr.Val)
            if curr.Left != nil {
                nextLevel = append(nextLevel, *curr.Left)
            }
            if curr.Right != nil {
                nextLevel = append(nextLevel, *curr.Right)
            }
        }

        ans = append(ans, tmpAns)
        queue = nextLevel
    }
    return ans
}

二叉树的最大深度

直接上一题改改哈哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func maxDepth(root *TreeNode) int {
    ans := 0
    if root == nil {
        return ans
    }
    queue := []TreeNode{}
    queue = append(queue, *root)

    for len(queue) != 0 {
        ans++
        nextLevel := []TreeNode{}

        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]

            if curr.Left != nil {
                nextLevel = append(nextLevel, *curr.Left)
            }
            if curr.Right != nil {
                nextLevel = append(nextLevel, *curr.Right)
            }
        }
        queue = nextLevel
    }
    return ans
}

从前序与中序遍历序列构造二叉树

前序中左右，中序左中右，后序左右中（「中」在前、在中、在后）

二叉树基本功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
 * 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
    }
    if len(preorder) == 1 {
        return &TreeNode{
            Val:   preorder[0],
            Left:  nil,
            Right: nil,
        }
    }

    // ans:=&TreeNode{}

    midVal := preorder[0] // mid 的值
    inorderMinIdx := 0    // mid 在中序的位置
    for i := 0; i < len(inorder); i++ {
        if inorder[i] == midVal {
            inorderMinIdx = i
            break
        }
    }

    leftInorder := inorder[:inorderMinIdx]
    rightInorder := inorder[inorderMinIdx+1:]

    // 因为 len(「右」) 在前序和中序是一样的，并且都在结尾
    // 所以很容易能把前序的「左」「右」区分开来
    lenRight := len(inorder) - inorderMinIdx
    leftPreorder := preorder[1 : len(preorder)-lenRight+1]
    rightPreorder := preorder[len(preorder)-lenRight+1:]

    // fmt.Println("leftInorder",leftInorder)
    // fmt.Println("rightInorder",rightInorder)
    // fmt.Println("leftPreorder",leftPreorder)
    // fmt.Println("rightPreorder",rightPreorder)

    return &TreeNode{
        Val:   midVal,
        Left:  buildTree(leftPreorder, leftInorder),
        Right: buildTree(rightPreorder, rightInorder),
    }
}

二叉树展开为链表

要求展开成先序遍历一样的顺序

首先你遍历的同时构造新链表肯定是可以的，但是这样就没意思了，肯定得写个原地的

首先先序是中左右，所以你把左和右分别搞定之后，再拼一起就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
   _ = myFlatten(root)
   return
}

func myFlatten(root *TreeNode) (tail *TreeNode) {
   if root == nil {
      return nil
   } else if root.Left == nil && root.Right == nil {
      return root
   }

   leftTail := myFlatten(root.Left)
   rightTail := myFlatten(root.Right)

   if leftTail != nil {
      leftTail.Left = nil
      leftTail.Right = root.Right
      root.Right = root.Left
      root.Left = nil
   }

   if rightTail != nil {
      return rightTail
   }
   return leftTail
}

买卖股票的最佳时机

首先暴力肯定没问题，但是数据量大了会 TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int) int {
    n := len(prices)
    ans := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            v := prices[j] - prices[i]
            if v > ans {
                ans = v
            }
        }
    }
    return ans
}

其实实质就是找到差别最大的两个数字，并且小的在前面

求出相邻之间的 diff 数组，然后遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxProfit(prices []int) int {
    n := len(prices)
    diff := make([]int, n)
    for i := 1; i < n; i++ {
        diff[i] = prices[i] - prices[i-1]
    }

    ans := 0
    curr := 0
    // fmt.Println(diff)
    for i := 1; i < n; i++ {
        curr += diff[i]
        if curr > ans {
            ans = curr
        } else if curr < 0 {
            curr = 0
        }
    }
    return ans
}

dp 我也想了，但是想了半天都是 n 方的（

结果看见了这条评论，感觉还是人外有人👀（

二叉树中的最大路径和

第一眼：嗯？图的最长路算法？

但是这个数据量应该来不及转换成图然后处理

第二眼：嗯？树形 dp？

但是有个问题就是不好确定起点哇，如果是必须经过 root 的话还可以左右两边分别 dp，然后合一起

仔细思考，我感觉可以从所有的叶子结点向 root 开始 dp，转移方程就是，每一个分支结点都可以选择继承左儿子，或者继承右儿子，或者都不继承

但是这个遍历顺序有点难搞，算了，还是写成记忆化搜索吧（dp 其实就是记忆化搜索 Pro Max）

哎等等？好像可以直接写成搜索？

再等等？好像少了一种情况，或者在当前打住，把两边拉一起，但是上面不能再引用这个数据（啊我好像知道 ans 怎么求了

啊好像还得加个只选自身结点

啊还有只选左边和只选右边

我去我居然手搓过了一个 hard，成绩还这么好😭

image-20230813下午113211729

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func maxPathSum(root *TreeNode) int {
    ans := math.MinInt

    var dfs func(curr *TreeNode) int
    dfs = func(curr *TreeNode) int {
        var left, right int
        if curr.Left != nil {
            left = dfs(curr.Left)
        }
        if curr.Right != nil {
            right = dfs(curr.Right)
        }

        ans = max(ans,
            left+right+curr.Val,
            left+curr.Val,
            right+curr.Val,
            curr.Val,
        )

        return max(left+curr.Val, right+curr.Val, curr.Val)
    }
    _ = dfs(root)
    return ans
}

func max(a ...int) int {
    max := a[0]
    for _, v := range a {
        if v > max {
            max = v
        }
    }

    return max
}

最长连续序列

啊，一眼貌似 dp，但是我想不出怎么写

能不能用桶排的思路呢？数据范围太大了

但是要求 O(n) ，我感觉也只有 dp 了哇

实在写不出来，一看标签，卧槽，有并查集，但是也不行哇（

看了题解之后：

原来哈希表不是 O(logn) 哇， 我一直以为 map 是 O(logn)，那没事了~~（高中学的 C++ 的 std::map 说是基于红黑树的，红黑树是 O(logn)，所以一直记得 map 就是 O(logn)~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func longestConsecutive(nums []int) int {
    n := len(nums)
    fa := make(map[int]int)
    exist := make(map[int]bool)
    count := make(map[int]int)
    ans := 0

    for i := 0; i < n; i++ {
        fa[nums[i]] = nums[i]
        exist[nums[i]] = true
    }

    find := func(x int) int {
        for x != fa[x] {
            fa[x] = fa[fa[x]]
            x = fa[x]
        }
        return x
    }

    combine := func(a, b int) {
        // fmt.Println(a,b)
        fa[find(a)] = find(b)
    }

    for i := 0; i < n; i++ {
        if exist[nums[i]-1] {
            combine(nums[i], nums[i]-1)
        }
        if exist[nums[i]+1] {
            combine(nums[i], nums[i]+1)
        }
    }

    for i := range exist {
        count[find(i)]++
    }

    // fmt.Println(n)
    // fmt.Println(fa)
    // fmt.Println(exist)
    // fmt.Println(count)

    for _, i := range count {
        if i > ans {
            ans = i
        }
    }
    return ans
}

只出现一次的数字

完全想不出「该算法只使用常量额外空间」的方法

我能想到的是一个变量连续计算，然后两个相同的能自动抵消，O(n) 只能是这样，但是想不出来

一看标签卧槽位运算

1
2
3
4
5
6
7
func singleNumber(nums []int) int {
    ans := 0
    for _, i := range nums {
        ans ^= i
    }
    return ans
}

单词拆分

先来个暴力好吧，但是 TLE 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func wordBreak(s string, wordDict []string) bool {
    if s == "" {
        return true
    }

    for _, word := range wordDict {
        if isTrim(s, word) && wordBreak(s[len(word):], wordDict) {
            return true
        }
    }

    return false
}

func isTrim(s, t string) bool {
    if len(t) > len(s) {
        return false
    } else if len(t) == len(s) {
        return s == t
    } else {
        for i := 0; i < len(t); i++ {
            if s[i] != t[i] {
                return false
            }
        }
        return true
    }
}

想改进一下这个暴力，如果 wordDict 中有单词可以由其他单词组合成，那就可以忽略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func wordBreak(s string, wordDict []string) bool {
    wordDict= prework(wordDict)
    return myWordBreak(s,wordDict)
}

func prework(wordDict []string) []string{
    ans := []string{}
    for i:=0;i<len(wordDict);i++{
        ext:=make([]string,len(wordDict)-1)
        copy(ext,wordDict[:i])
        copy(ext[i:],wordDict[i+1:])
        if !myWordBreak(wordDict[i],ext){
            ans=append(ans,wordDict[i])
        }
    }
    return ans
}


func myWordBreak(s string, wordDict []string) bool {
    if s == "" {
        return true
    }
    for _,word:=range wordDict{
        if isTrim(s,word)&&myWordBreak(s[len(word):],wordDict) {
            return  true
        }
    }

    return false
}

func isTrim(s,t string) bool {
    if len(t)>len(s){
        return false
    }else if len(t)==len(s){
        return s == t
    }else{
        for i:=0;i<len(t);i++{
            if s[i]!=t[i]{
                return false
            }
        }
        return true
    }
}

但是还是 TLE 了😭

再优化一手试试，来点记忆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
var vis = make(map[string]bool)
var flag bool

func wordBreak(s string, wordDict []string) bool {
    flag = false
    vis = make(map[string]bool)
    wordDict = prework(wordDict)
    vis = make(map[string]bool)
    flag = true
    return myWordBreak(s, wordDict)
}

func prework(wordDict []string) []string {
    ans := []string{}
    for i := 0; i < len(wordDict); i++ {
        ext := make([]string, len(wordDict)-1)
        copy(ext, wordDict[:i])
        copy(ext[i:], wordDict[i+1:])
        if !myWordBreak(wordDict[i], ext) {
            ans = append(ans, wordDict[i])
        }
    }
    return ans
}

func myWordBreak(s string, wordDict []string) bool {
    if s == "" {
        return true
    }

    if flag {
        if val, ok := vis[s]; ok {
            return val
        }
    }

    for _, word := range wordDict {
        if isTrim(s, word) && myWordBreak(s[len(word):], wordDict) {
            vis[s] = true
            return true
        }
    }
    vis[s] = false
    return false
}

func isTrim(s, t string) bool {
    if len(t) > len(s) {
        return false
    } else if len(t) == len(s) {
        return s == t
    } else {
        for i := 0; i < len(t); i++ {
            if s[i] != t[i] {
                return false
            }
        }
        return true
    }
}

居然过了🤣

言归正传，这个问题最好的方法肯定是 dp，GPT 给了很好的过程描述

  1. 问题定义： 我们希望判断字符串 s 是否可以被拆分成词典中的单词。为了解决这个问题，我们引入一个布尔数组 dp，其中 dp[i] 表示字符串的前 i 个字符是否可以被拆分成词典中的单词。
  2. 初始化： 我们将 dp[0] 初始化为 true，这是因为空字符串总是可以被拆分，即不拆分成任何单词。
  3. 状态转移： 对于每个位置 i（从 1 到字符串长度），我们需要判断字符串的前 i 个字符是否可以被拆分成词典中的单词。我们遍历从 0 到 i-1 的每个位置 j，如果 dp[j] 为 true，并且子串 s[j:i] 在词典中，那么我们可以将字符串的前 i 个字符拆分成单词，即 dp[i] = true。这是因为如果从位置 j 到位置 i-1 的子串是一个有效的单词，且前 j 个字符可以被拆分成单词，那么前 i 个字符也可以被拆分。
  4. 返回结果： 最终，我们返回 dp[len(s)]，即字符串的全部字符是否可以被拆分成词典中的单词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    dp := make([]bool, n+1)
    exist := make(map[string]bool)
    for i := 0; i < len(wordDict); i++ {
        exist[wordDict[i]] = true
    }
    dp[0] = true

    for i := 0; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j] && exist[s[j:i]] == true {
                dp[i] = true
                break
            }
        }
    }

    return dp[n]
}

环形链表

做过了，请见『算法拾遗』链表（Linked List）