两数之和

暴力枚举

暴力枚举 i 和 j ，没什么好说的

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    for i, _ := range nums {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

哈希表

对于每一个 x，检查以前有没有遍历过另一半

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int, target int) []int {
    m := map[int]int{}

    for i, x := range nums {
        j, ok := m[target-x]
        if ok {
            return []int{i, j}
        }
        m[x] = i
    }
    return nil
}

两数相加

一开始想着能不能抽离出一个函数用来维护 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
53
54
55
56
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 创建一个哨兵节点作为新链表的头部
    dummy := &ListNode{}
    curr := dummy

    i, j := l1, l2

    for i != nil && j != nil {

        addNum(&curr, i.Val+j.Val)

        if i.Next == nil && j.Next != nil {
            for j != nil {
                addNum(&curr, j.Val)
                j = j.Next
            }
            break
        }

        if j.Next == nil && i.Next != nil {
            for i != nil {
                addNum(&curr, i.Val)
                i = i.Next
            }
            break
        }

        i = i.Next
        j = j.Next
    }

    return dummy
}

func addNum(curr **ListNode, num int) {
    fmt.Println(num)

    (*curr).Val = ((*curr).Val + num) % 10
    (*curr).Next = &ListNode{
        Val:  num / 10,
        Next: nil,
    }

    fmt.Println(*curr)

    *curr = (*curr).Next
    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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 创建一个哨兵节点作为新链表的头部
    dummy := &ListNode{}
    curr := dummy

    // 暂存进位
    tmp := 0
    i, j := l1, l2

    for i != nil || j != nil {
        x, y := 0, 0
        if i != nil {
            x = i.Val
            i = i.Next
        }
        if j != nil {
            y = j.Val
            j = j.Next
        }
        sum := x + y + tmp
        sum, tmp = sum%10, sum/10

        curr.Next = &ListNode{Val: sum}
        curr = curr.Next
    }

    if tmp > 0 {
        curr.Next = &ListNode{Val: tmp}
    }

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

    // 记录某个字符有没有出现过，也可以用 [128]int{}
    set := make(map[byte]bool)
    // 左右指针
    i, j, ans := 0, 0, 0

    for j < n {
        if set[s[j]] { // 如果存在，就在左侧一直删，删到不存在
            delete(set, s[i])
            i++
        } else { // 如果不存在就记录并更新长度
            set[s[j]] = true
            ans = max(ans, j-i+1)
            j++
        }
    }
    return ans
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

寻找两个正序数组的中位数

合并后排序

没什么好说的，最暴力的方法

1
2
3
4
5
6
7
8
9
10
11
12
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    nums3 := append(nums1, nums2...)
    sort.Ints(nums3)
    // fmt.Println(nums3)

    n := len(nums3)
    if n%2 == 1 {
        return float64(nums3[n/2])
    } else {
        return float64(nums3[n/2]+nums3[n/2-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
39
40
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    // 定义三个指针和两个数组长度
    i, j, k := 0, 0, 0
    n1, n2 := len(nums1), len(nums2)
    // 定义中位数变量和之前的值
    pre, cur := 0, 0
    // 计算总元素个数
    m := n1 + n2
    // 计算中位数的位置
    mid := m / 2

    // 循环，直到找到中位数的位置
    for k <= mid {
        // 保存上一次的值
        pre = cur
        // 比较两个数组的元素，将较小的元素放入当前位置，指针向后移动
        if i < n1 && j < n2 {
            if nums1[i] < nums2[j] {
                cur = nums1[i]
                i++
            } else {
                cur = nums2[j]
                j++
            }
        } else if i < n1 { // 第一个数组还有剩余元素
            cur = nums1[i]
            i++
        } else { // 第二个数组还有剩余元素
            cur = nums2[j]
            j++
        }
        k++
    }

    // 判断总元素个数是奇数还是偶数，返回相应的结果
    if m % 2 == 0 {
        return float64(pre + cur) / 2
    }
    return float64(cur)
}

双指针二分移动（类似第 k 小数）

建议去看一眼题解👀

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
66
67
68
69
70
71
72
73
74
75
76
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    // 确保nums1是较短的数组
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1
    }

    // 获取两个数组的长度
    m, n := len(nums1), len(nums2)
    // 计算总元素个数
    total := m + n

    // 定义二分查找的边界
    left, right := 0, m

    // 二分查找
    for left <= right {
        // 二分查找分割线的位置
        partition1 := (left + right) / 2
        partition2 := (total+1)/2 - partition1

        // 计算分割线两边的最大最小值
        maxLeft1 := math.MinInt32
        if partition1 > 0 {
            maxLeft1 = nums1[partition1-1]
        }

        maxLeft2 := math.MinInt32
        if partition2 > 0 {
            maxLeft2 = nums2[partition2-1]
        }

        minRight1 := math.MaxInt32
        if partition1 < m {
            minRight1 = nums1[partition1]
        }

        minRight2 := math.MaxInt32
        if partition2 < n {
            minRight2 = nums2[partition2]
        }

        // 判断是否找到了正确的分割线
        if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
            // 根据总元素个数是奇数还是偶数返回结果
            if total % 2 == 0 {
                return float64(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
            } else {
                return float64(max(maxLeft1, maxLeft2))
            }
        } else if maxLeft1 > minRight2 {
            // 如果当前分割线左侧的元素过多，缩小右边界
            right = partition1 - 1
        } else {
            // 如果当前分割线右侧的元素过多，增大左边界
            left = partition1 + 1
        }
    }

    return 0.0 // 输入数组有误
}

// 辅助函数，返回两个整数中较大的一个
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
}
GPT 的解释

当我们处理两个已排序的数组，要找到它们的中位数时，使用二分查找是一种高效的方法。这个方法的核心思想是在较短的数组上进行二分查找，通过分割线将两个数组划分成左右两部分，并满足一定的条件。让我们详细解释一下这个二分法。

  1. 确定较短的数组：为了减少时间复杂度，我们选择在较短的数组上进行二分查找。首先，我们比较两个数组的长度，如果nums1的长度大于nums2的长度，则交换它们，确保nums1是较短的数组。

  2. 设定二分查找的边界：我们在较短数组nums1上进行二分查找，所以我们设定左边界left为0，右边界right为nums1的长度。

  3. 二分查找：我们在nums1数组上进行二分查找，每次迭代都计算一个分割线的位置partition1，以及另一个数组nums2中对应的分割线位置partition2。

  4. 计算分割线两边的最大最小值：我们分别计算两个数组中分割线两边的最大和最小值。设maxLeft1为nums1中左边部分的最大值，maxLeft2为nums2中左边部分的最大值，minRight1为nums1中右边部分的最小值，minRight2为nums2中右边部分的最小值。

  5. 判断是否找到正确的分割线：如果maxLeft1小于等于minRight2且maxLeft2小于等于minRight1，说明当前的分割线位置是正确的。这是因为我们需要确保左边的元素都小于等于右边的元素，且左边的部分的长度与右边的部分长度相等或相差1（这样才能得到中位数）。如果条件满足，则我们已经找到了正确的分割线。

  6. 调整分割线位置：如果当前分割线位置不正确，我们需要根据maxLeft1和minRight2之间的关系来调整分割线位置。如果maxLeft1大于minRight2，说明nums1的分割线位置过大，需要将右边界right向左移动；如果maxLeft2大于minRight1，说明nums1的分割线位置过小，需要将左边界left向右移动。然后继续进行二分查找，直到找到正确的分割线位置。

  7. 返回结果：根据总元素个数是奇数还是偶数，返回相应的结果。如果总元素个数是偶数，则中位数为两个中间值的平均数；如果总元素个数是奇数，则中位数为较长的数组中的中间值。

通过这种方法，我们可以在O(log(min(m, n)))的时间复杂度内找到两个已排序数组的中位数，是一种高效且优雅的解决方案。

最长回文子串

暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
go
func longestPalindrome(s string) string {
    ans := ""

    for i := 0; i < len(s); i++ {
        for j := i + 1; j < len(s)+1; j++ {
            if isPaling(s[i:j]) && len(s[i:j]) > len(ans) {
                ans = s[i:j]
            }
        }
    }
    return ans
}

func isPaling(s string) bool {

    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-i-1] {
            return false
        }
    }
    return true
}

枚举中心并扩展

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 longestPalindrome(s string) string {

    var start, end int

    for i := 0; i < len(s); i++ {
        left1, right1 := expandAroundCenter(s, i, i)
        left2, right2 := expandAroundCenter(s, i, i+1)
        if right1-left1 > end-start {
            start, end = left1, right1
        }
        if right2-left2 > end-start {
            start, end = left2, right2
        }

    }
    return s[start : end+1]
}

func expandAroundCenter(s string, left, right int) (int, int) {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left = left - 1
        right = right + 1
    }
    return left + 1, right - 1
}

动态规划

  • $ dp[i][j]$ 表示 s[i][j] 是回文
  • 转移方程： $ dp[i][j]$ = $ dp[i+1][j-1]$ and $ s[i]==s[j]$
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 longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool, n)
    ans := s[0:1]

    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    for l := 2; l <= n; l++ {
        for start := 0; start < n-l+1; start++ {
            end := start + l - 1
            // 首位是否相同
            if s[start] == s[end] {
                if l == 2 {
                    dp[start][end] = true
                } else {
                    dp[start][end] = dp[start+1][end-1]
                }
                // 更新答案
                if dp[start][end] == true && (end-start+1) > len(ans) {
                    ans = s[start : end+1]
                }
            }
        }
    }
    return ans
}

正则表达式匹配

hard 题，先放弃了

动态规划，dp[i][j] 表示 s 的前 i 个字符和 p 的前j 个字符是否能匹配

转移方程 GPT

对于状态转移方程的解释，我们来具体说明一下在动态规划中如何构建状态转移。

我们使用 dp[i][j] 来表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。

  1. 当 p[j-1] 是普通字符（小写字母），且与 s[i-1] 匹配时，dp[i][j] 的值由 dp[i-1][j-1] 决定。即：

    plaintext
    if p[j-1] == s[i-1] {
        dp[i][j] = dp[i-1][j-1]
    }

  2. 当 p[j-1] 是 “.”（匹配任意单个字符）时，dp[i][j] 的值同样由 dp[i-1][j-1] 决定。即：

    plaintext
    if p[j-1] == '.' {
        dp[i][j] = dp[i-1][j-1]
    }

  3. 当 p[j-1] 是 “*”（匹配零个或多个前面的字符）时，情况稍微复杂一些。

    • 如果 p[j-2] 与 s[i-1] 不匹配，那么 * 只能让 p 的前面两个字符消失，即匹配 0 次，dp[i][j] 的值由 dp[i][j-2] 决定。即：

      plaintext
      if p[j-1] == '*' && p[j-2] != s[i-1] {
          dp[i][j] = dp[i][j-2]
      }

    • 如果 p[j-2] 与 s[i-1] 匹配，或者 p[j-2] 是 “.”（匹配任意单个字符），那么我们有多种选择：

      • * 匹配 0 次：dp[i][j] 的值由 dp[i][j-2] 决定。
      • * 匹配 1 次：dp[i][j] 的值由 dp[i-1][j-2] 决定。
      • * 匹配多次：dp[i][j] 的值由 dp[i-1][j] 决定。

      综合上述情况，dp[i][j] 的值为这些选择的逻辑或（||）结果。即：

      plaintext
      if p[j-1] == '*' && (p[j-2] == s[i-1] || p[j-2] == '.') {
          dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j]
      }

这就是状态转移方程的具体表达式，通过合理的状态转移，我们可以在动态规划的过程中求解出 dp[m][n] 的值，其中 m 是字符串 s 的长度，n 是字符规律 p 的长度。最终，dp[m][n] 的值即为整个字符串 s 和字符规律 p 是否匹配的结果。

盛最多水的容器

经典的二维接雨水，双指针法

已知：

  • 相同情况下，两边越远越好
  • 面积受限于短边

策略：

  • 从左右两边开始往中间扫
  • 尽量保持长边不动，移动短边
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 maxArea(height []int) int {
    n := len(height)

    left, right := 0, n-1
    ans := 0

    for left < right {
        ans = max(ans, (right-left)*min(height[right], height[left]))

        if height[left] > height[right] {
            right--
        } else {
            left++
        }
    }
    return ans
}

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

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
func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    ans := make([][]int, 0)

    for k := 0; k < n-2; k++ { // 第一个数
        if nums[k] > 0 { // 因为 k,i,j 递增，如果 k>0 就直接不可能了
            break
        }
        if k > 0 && nums[k] == nums[k-1] {  // 跳过重复
            continue
        }
        i, j := k+1, n-1 // i,j 从 [k+1,n-1] 向中间走
        for i < j {
            sum := nums[k] + nums[i] + nums[j]
            if sum == 0 {
                ans = append(ans, []int{nums[k], nums[i], nums[j]})
                for i < j && nums[i] == nums[i+1] {
                    i++
                }
                for i < j && nums[j] == nums[j-1] {
                    j--
                }
                i++
                j--
            } else if sum > 0 { // 依据递增性质，调整 i,j
                j--
            } else {
                i++
            }
        }
    }

    return ans
}

电话号码的字母组合

经典回溯，但是我感觉 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
32
33
34
35
36
37
38
39
var m = map[byte][]string{
    '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"},
}

func letterCombinations(digits string) []string {
    if digits == "" {
        return []string{}
    }

    var queue []string
    queue = append(queue, m[digits[0]]...) // 把首位数字对应的字母放入队列
    digits = digits[1:]                    // 去掉首位数字

    for digits != "" {
        var tmp []string
        for _, v := range queue {
            tmp = append(tmp, combination(v, digits[0])...)
        }
        queue = tmp
        digits = digits[1:]
    }
    return queue
}

// 将 s 的结尾分别加上 target 的映射
func combination(s string, target byte) []string {
    var ans []string
    for _, v := range m[target] {
        ans = append(ans, s+v)
    }
    return ans
}

删除链表的倒数第 N 个结点

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