颜色分类

这真的是 Medium 吗，哈哈哈😂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func sortColors(nums []int) {
    var red, white, blue int
    for i := 0; i < len(nums); i++ {
        switch nums[i] {
        case 0:
            red++
        case 1:
            white++
        case 2:
            blue++
        }
    }

    for i := 0; i < red; i++ {
        nums[i] = 0
    }
    for i := red; i < red+white; i++ {
        nums[i] = 1
    }
    for i := red + white; i < red+white+blue; i++ {
        nums[i] = 2
    }
    return
}

最小覆盖子串

很好的滑动窗口的题目

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
func minWindow(s string, t string) string {
    target:=make(map[byte]int)
    window:=make(map[byte]int)

    for i:=0;i<len(t);i++{
        target[t[i]]++
    }

    left,right:=0,0
    ansLeft,ansRight:=0,math.MaxInt
    diff:=len(t)

    for right<len(s){
        c:=s[right]
        right++

        if _,ok:=target[c] ; ok{
            if window[c]<target[c]{
                diff--
            }
            window[c]++
        }

        for diff == 0{
            if right-left<ansRight-ansLeft{
                ansRight,ansLeft=right,left
            }

            d:=s[left]
            left++

            if _,ok:=target[d];ok{
                if window[d] <= target[d]{
                    diff++
                }
                window[d]--
            }

        }

    }

    if ansRight == math.MaxInt{
        return ""
    }else{
        return s[ansLeft:ansRight]
    }

}

子集

直接套模板，请见『算法拾遗』排列与组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func subsets(nums []int) [][]int {
   n := len(nums)
   var ans [][]int

   for i := 0; i < (1 << n); i++ {
      var tmp []int
      for j := 0; j < n; j++ {
         if i&(1<<j) != 0 {
            tmp = append(tmp, nums[j])
         }
      }
      ans = append(ans, tmp)
   }
   return ans
}

单词搜索

暴力 DFS

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
61
62
func exist(board [][]byte, word string) bool {
    dir := [][]int{
        {1, 0},
        {-1, 0},
        {0, -1},
        {0, 1},
    }

    m, n := len(board), len(board[0])
    vis := make([][]bool, m)
    for i := 0; i < m; i++ {
        vis[i] = make([]bool, n)
    }

    startX, startY := []int{}, []int{}

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == word[0] {
                startX = append(startX, i)
                startY = append(startY, j)
            }
        }
    }

    var dfs func(count int, x int, y int) bool
    dfs = func(count int, x int, y int) bool {
        if count == len(word) {
            return true
        }

        vis[x][y] = true

        for i := 0; i < 4; i++ {
            nx := x + dir[i][0]
            ny := y + dir[i][1]

            if nx >= 0 && ny >= 0 && nx < m && ny < n && board[nx][ny] == word[count] && !vis[nx][ny] {
                vis[nx][ny] = true
                if dfs(count+1, nx, ny) == true {
                    return true
                }
                vis[nx][ny] = false
            }

        }
        return false
    }

    for i := 0; i < len(startX); i++ {
        vis = make([][]bool, m)
        for i := 0; i < m; i++ {
            vis[i] = make([]bool, n)
        }
        if dfs(1, startX[i], startY[i]) == true {
            return true
        }
    }

    return false

}

柱状图中最大的矩形

一开始以为是 dp，但想了一下感觉又不行，想不到什么好方法，干脆看题解去了（

首先暴力很容易写，但是会 TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func largestRectangleArea(heights []int) int {
    ans := 0

    for i := 0; i < len(heights); i++ {
        left, right := i, i
        for left-1 >= 0 && heights[left-1] >= heights[i] {
            left--
        }
        for right+1 < len(heights) && heights[right+1] >= heights[i] {
            right++
        }
        area := (right - left + 1) * heights[i]
        if area > ans {
            ans = area
        }
    }
    return ans
}

最佳方法是使用单调栈，主要思路我感觉 GPT 说的比题解更清楚：

  1. 创建一个栈来存储柱子的索引。栈中的元素满足递增顺序，表示当前柱子高度在数组中的位置。
  2. 从左到右遍历数组中的每个柱子：
    • 如果栈为空，或者当前柱子的高度大于等于栈顶柱子的高度，将当前柱子的索引入栈。
    • 如果当前柱子的高度小于栈顶柱子的高度，说明栈顶柱子不再能够向右扩展，因此弹出栈顶元素，并计算以该栈顶柱子为高度的矩形的面积。栈顶柱子出栈后，其左边第一个比它矮的柱子即为当前栈顶元素，右边第一个比它矮的柱子为当前遍历到的柱子。
  3. 在每次弹出栈顶元素时，计算以该柱子为高度的矩形的面积，其宽度为当前遍历到的柱子索引与栈顶柱子的索引之差。
  4. 重复步骤 2 和 3，直到遍历完整个数组。
  5. 在遍历完数组后，可能还有一些柱子留在栈中。对于这些柱子，它们的右边界就是数组的末尾，左边界就是栈中紧邻的柱子。弹出这些柱子并计算矩形面积。
  6. 在整个过程中，不断更新并记录最大的矩形面积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func largestRectangleArea(heights []int) int {
    heights = append(heights, 0)
    n := len(heights)
    stack := []int{}
    ans := 0

    for i := 0; i < n; i++ {
        for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
            curr := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := (i - left - 1) * heights[curr]
            if area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }

    return ans
}

这里有一个技巧就是直接在末尾添加一个 0 ，这样就能强制清空栈，不用再写个循环来最后清空栈

但是这个两重 for 我不是很能理解，就这样吧（

最大矩形

一眼 dp，但是我看了半天想不出转移方程😭

只能去看题解了

发现可以直接转换成上一题，但是那个 dp 我看不懂，算了

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 maximalRectangle(matrix [][]byte) int {
    m,n:=len(matrix),len(matrix[0])
    if m==0{
        return 0
    }

    heights:=make([]int,n)
    ans:=0

    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if matrix[i][j]=='1'{
                heights[j]+=1
            }else{
                heights[j]=0
            }
        }
        ans=max(ans,largestRectangleArea(heights))
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

二叉树的中序遍历

前序中左右，中序左中右，后序左右中（「中」在前、在中、在后，左右的顺序就是左右）

我的写法有点浪费空间，每次都要拷贝，但是随便了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */


func inorderTraversal(root *TreeNode) []int {
    ans:=[]int{}
    if root==nil{
        return ans
    }
    if root.Left!=nil{
        ans=inorderTraversal(root.Left)
    }
    ans=append(ans,root.Val)
    if root.Right!=nil{
        ans=append(ans,inorderTraversal(root.Right)...)
    }
    return ans
}

不同的二叉搜索树

什么同分异构体

第一眼，范围那么小，直接打表出省一

第二眼，肯定有数学规律，套公式就行

头疼，直接看题解去了，发现是卡特兰数，没事了

1
2
3
4
5
6
7
func numTrees(n int) int {
    C := 1
    for i := 0; i < n; i++ {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C
}

验证二叉搜索树

经典递归，看了眼题解还可以用「二叉搜索树中序遍历一定是递增的」这个性质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isValidBST(root *TreeNode) bool {
    return myIsValidBST(root, math.MinInt, math.MaxInt)
}

func myIsValidBST(root *TreeNode, minVal, maxVal int) bool {
    if root == nil {
        return true
    }

    if root.Val <= minVal || root.Val >= maxVal {
        return false
    }

    leftIsValid := myIsValidBST(root.Left, minVal, root.Val)
    rightIsValid := myIsValidBST(root.Right, root.Val, maxVal)

    return leftIsValid && rightIsValid
}

对称二叉树

第一反应：嗯？

第二反应：左侧用「左中右」遍历，右侧用「右中左」遍历，然后比较行不行？

第三反应：将一侧的左右儿子递归地反转，然后和另一侧比较是不是完全一样

但是这样感觉太麻烦了，我递归的时候直接镜像比较行不行（左边的左儿子比较右边的右儿子）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSymmetric(root *TreeNode) bool {
    return myIsSymmetric(root.Left, root.Right)
}

func myIsSymmetric(left *TreeNode, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    } else if (left == nil && right != nil) || (left != nil && right == nil) || left.Val != right.Val {
        return false
    }

    return myIsSymmetric(left.Left, right.Right) && myIsSymmetric(left.Right, right.Left)
}