有效的括号

栈的经典题目了属于是

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
func isValid(s string) bool {
    stack := ""

    for k := 0; k < len(s); k++ {
        i := s[k]
        switch i {
        case '(':
            stack = stack + string(i)
        case ')':
            if stack != "" && stack[len(stack)-1] == '(' {
                stack = stack[:len(stack)-1]
            } else {
                return false
            }
        case '{':
            stack = stack + string(i)
        case '}':
            if stack != "" && stack[len(stack)-1] == '{' {
                stack = stack[:len(stack)-1]
            } else {
                return false
            }
        case '[':
            stack = stack + string(i)
        case ']':
            if stack != "" && stack[len(stack)-1] == '[' {
                stack = stack[:len(stack)-1]
            } else {
                return false
            }

        }
    }
    if stack == "" {
        return true
    } else {
        return false
    }

}

合并两个有序链表

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

括号生成

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 generateParenthesis(n int) []string {
    ans = []string{}
    dfs(0, n)
    return ans
}

var (
    curr string
    ans  []string
)

func dfs(count int, n int) {
    if len(curr) >= n*2 {
        if count == 0 {
            ans = append(ans, curr)
        }
        return
    }
    pre := curr
    if count < n {
        curr = pre + "("
        dfs(count+1, n)
        curr = pre
    }
    if count > 0 {
        curr = pre + ")"
        dfs(count-1, n)
        curr = pre
    }
    return
}

合并 K 个升序链表

方法很多

  1. 暴力解：把所有链表的结点都拆出来，值存在一个切片里，然后排序再构建一个新链表返回
  2. 逐个对比头结点：每次逐一比较每个链表的头节点值，生成新链表
  3. 优先队列头节点：使用优先队列，存储所有链表的头节点值，之后动态取出最大值
  4. 逐一合并： 使用 合并两个有序链表 的方法，将所有链表逐个合到第一个链表中
  5. 两两合并：和上一种类型，但是是将链表两两合并，就跟淘汰赛一样，最后剩一个

暴力解

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
func mergeKLists(lists []*ListNode) *ListNode {
    var vals []int

    for _, list := range lists {
        curr := list
        for curr != nil {
            vals = append(vals, curr.Val)
            curr = curr.Next
        }
    }

    sort.Ints(vals)

    dummy := &ListNode{}
    curr := dummy

    for _, val := range vals {
        curr.Next = &ListNode{
            Val: val,
        }
        curr = curr.Next
    }

    return dummy.Next
}

逐个对比头结点

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
func mergeKLists(lists []*ListNode) *ListNode {
    dummy:=&ListNode{}
    curr:=dummy

    for {
        minIndex:=-1
        minVal:=math.MaxInt32

        for index,listHead := range lists{
            if listHead!=nil && listHead.Val<minVal{
                minIndex=index
                minVal=listHead.Val
            }
        }

        if minIndex==-1{
            break
        }

        curr.Next=lists[minIndex]
        lists[minIndex]=lists[minIndex].Next
        curr=curr.Next
    }

    return dummy.Next
}

优先队列头节点

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
type Node struct {
    Index int
    Val   int
}

func cmp(a, b any) int {
    return utils.IntComparator(
        a.(Node).Val,
        b.(Node).Val,
    )
}

func mergeKLists(lists []*ListNode) *ListNode {
    dummy := &ListNode{}
    curr := dummy

    q := priorityqueue.NewWith(cmp)

    for index, listHead := range lists {
        if listHead != nil {
            q.Enqueue(Node{
                Index: index,
                Val:   listHead.Val,
            })
        }

    }

    for !q.Empty() {

        tmp, _ := q.Dequeue()
        minNode := tmp.(Node)
        curr.Next = lists[minNode.Index]
        lists[minNode.Index] = lists[minNode.Index].Next
        curr = curr.Next

        if lists[minNode.Index] != nil {
            q.Enqueue(Node{
                Index: minNode.Index,
                Val:   lists[minNode.Index].Val,
            })
        }

    }

    return dummy.Next
}

逐一合并

1
2
3
4
5
6
7
8
9
10
11
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    for i := 1; i < len(lists); i++ {
        lists[0] = mergeTwoLists(lists[0], lists[i])
    }

    return lists[0]
}

两两合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    } else if len(lists) == 1 {
        return lists[0]
    }

    empty := make([]bool, len(lists))

    for !empty[1] {
        for i := len(lists) - 1; i > 0; i-- {
            lists[i/2] = mergeTwoLists(lists[i/2], lists[i])
            empty[i] = true
            empty[i/2] = false
        }
    }

    return lists[0]
}

下一个排列

  1. 从右向左找到第一个升序的位置 i
  2. 如果 i >= 0，从右向左找到第一个大于 nums[i] 的位置 j
  3. 交换位置 i 和 j 的元素
  4. 反转 i 之后的元素，得到下一个全排列
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
func nextPermutation(nums []int) {
    // Step 1: 从右向左找到第一个升序的位置 i
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }

    // Step 2: 如果 i >= 0，从右向左找到第一个大于 nums[i] 的位置 j
    if i >= 0 {
        j := len(nums) - 1
        for j >= 0 && nums[j] <= nums[i] {
            j--
        }
        // Step 3: 交换位置 i 和 j 的元素
        nums[i], nums[j] = nums[j], nums[i]
    }

    // Step 4: 反转 i 之后的元素，得到下一个全排列
    reverse(nums[i+1:])
}

func reverse(nums []int) {
    left, right := 0, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

最长有效括号

栈

题解里面的先压入 -1 我是真的理解不来，这个是我一开始手搓的，没发现还要连着看之前的记录，后来发现了，就加了个 maxLen ，居然就过了

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
func longestValidParentheses(s string) int {
    // 某个下标的有效长度，这东西有点dp那味了哈哈哈
    maxLen := make([]int, len(s))
    ans := 0

    stack := []int{}

    for idx, i := range s {
        if i == '(' {
            stack = append(stack, idx)
        } else {
            if len(stack) == 0 {
                continue
            }
            pre := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            // 当前这对括号的有效长度
            maxLen[idx] = idx - pre + 1
            if pre-1 > 0 { // 看看能不能和前面的拼一起👀
                maxLen[idx] += maxLen[pre-1]
            }

            if maxLen[idx] > ans {
                ans = maxLen[idx]
            }
        }
    }
    return ans
}

动态规划

dp[i] 表示以第 i 个字符为结尾的最长有效括号子串的长度

  1. 对于每个 s[i] 为 ( ，dp[i] 必定为 0 ，因为以 ( 结尾的字符串永远不会是有效的括号子串。
  2. 对于每个 s[i] 为 )，如果 s[i-1] 为 ( ，则 dp[i] = dp[i-2] + 2
  3. 对于每个 s[i] 为 )，如果 s[i-1] 为 )并且 s[i-dp[i-1]-1] 为 (，则 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]

我只能说我的🧠不可能自己转的过来🥲

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
func longestValidParentheses(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }

    dp := make([]int, n)
    maxLength := 0

    for i := 1; i < n; i++ {
        if s[i] == ')' {
            if s[i-1] == '(' {
                if i-2 >= 0 {
                    dp[i] = dp[i-2] + 2
                } else {
                    dp[i] = 2
                }
            } else if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
                if i-dp[i-1]-2 >= 0 {
                    dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
                } else {
                    dp[i] = dp[i-1] + 2
                }
            }

            maxLength = max(maxLength, dp[i])
        }
    }

    return maxLength
}

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func search(nums []int, target int) int {
    // 初始化左右指针
    left, right := 0, len(nums) - 1

    // 使用二分查找算法，在搜索范围内查找目标值
    for left <= right {
        // 计算中间位置
        mid := left + (right - left) / 2

        // 如果中间值等于目标值，则找到目标，返回下标
        if nums[mid] == target {
            return mid
        }

        // 判断哪一半是有序的
        if nums[left] <= nums[mid] {
            // 如果左半段有序
            if nums[left] <= target && target < nums[mid] {
                // 如果目标值在左半段范围内，则在左半段继续查找
                right = mid - 1
            } else {
                // 否则在右半段继续查找
                left = mid + 1
            }
        } else {
            // 如果右半段有序
            if nums[mid] < target && target <= nums[right] {
                // 如果目标值在右半段范围内，则在右半段继续查找
                left = mid + 1
            } else {
                // 否则在左半段继续查找
                right = mid - 1
            }
        }
    }

    // 如果未找到目标值，则返回 -1
    return -1
}

在排序数组中查找元素的第一个和最后一个位置

也是二分，我的思路是先传统二分找到一个元素，再两侧二分

其实也可以两次二分，一次找最小值，一次找最大值

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
63
64
65

func searchRange(nums []int, target int) []int {
    if len(nums) == 1 {
        if nums[0] == target {
            return []int{0, 0}
        } else {
            return []int{-1, -1}
        }
    }

    idx := findIdx(nums, target)
    fmt.Println(idx)
    if idx == -1 {
        return []int{-1, -1}
    }

    left := leftExt(nums, idx)
    right := rightExt(nums, idx)
    return []int{left, right}
}

func findIdx(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

func leftExt(nums []int, idx int) int {
    target := nums[idx]
    left, right := 0, idx
    for left < right {
        mid := (left + right) / 2
        if nums[mid] == target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func rightExt(nums []int, idx int) int {
    target := nums[idx]
    left, right := idx, len(nums)-1
    for left < right {
        mid := (left + right + 1) / 2
        if nums[mid] == target {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return right
}

组合总和

想起来高中的经典硬币买商品的题目，但是那个好像是统计有多少种方法，从 0 开始往后 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
func combinationSum(candidates []int, target int) [][]int {
    var curr []int // 当前选择的元素
    var ans [][]int

    var dfs func(target int, pre int) // 目标 target，之前是第 pre 个元素
    dfs = func(target int, pre int) {
        if target == 0 {
            // 因为切片是引用类型，所以得深拷贝一下
            tmp := make([]int, len(curr))
            copy(tmp, curr)
            ans = append(ans, tmp)
            return
        }

        for i := pre; i < len(candidates); i++ {
            if target-candidates[i] >= 0 {
                curr = append(curr, candidates[i])
                dfs(target-candidates[i], i)
                curr = curr[:len(curr)-1]
            }

        }
    }
    dfs(target, 0)
    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
func trap(height []int) (ans int) {
    n := len(height)
    if n == 0 {
        return
    }

    leftMax := make([]int, n)  // 当前及左边的最大高度
    rightMax := make([]int, n) // 当前及右边的最大高度
    leftMax[0] = height[0]
    rightMax[n-1] = height[n-1]

    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    for idx, h := range height {
        ans += min(leftMax[idx], rightMax[idx]) - h
    }

    return
}

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}