LeetCode Hot100笔记-上

Posted on Edited on In Views:
现在面试肯定有笔试环节，大部分的笔试题在 ht100 中又可以找到相似的思路。笔者在刷的时候对里面的知识点再次细化一下，感触颇深。本篇文章是上部分，包含 50 道题。

简单

1. 两数之和

image-20240528162000681

知识点：hashmap

使用 hashmap，遍历数组的时候，查询另外一个值是否在 hashmap 中。

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    total := make(map[int]int)
    for i, v := range nums {
        if idx, ok := total[target-v]; ok {
            return []int{idx, i}
        }
        total[v] = i
    }
    return nil
}

这里还需要联想到双指针，如果是返回数字，可以使用双指针。先排序，然后一个指针在最左，一个指针在最右，判断指针的值相加跟 target 的大小对比，往中间走。

283. 移动零

image-20240528164105774

知识点：双指针

左右指针，左指针记录需要调换的非零数字的位置，右指针往右边走，如果不是 0，则跟左指针调换，左指针往右移

1
2
3
4
5
6
7
8
9
func moveZeroes(nums []int)  {
    var l,r int 
    for ;r<len(nums);r++{
        if nums[r] != 0{
            nums[l],nums[r] = nums[r],nums[l]
            l++
        }
    }
}

160. 相交链表

image-20240529115512378

知识点：链表，hashmap，双指针

最简单的方法是使用 hashmap，将节点作为 map 的 key 保存进去。

还有另外一种方法，可以理解为双指针，一个从 A 开始走，一个从 B 开始走，某一个走到结尾，则从另外一个开始走，相交的时候则代表是重复节点。如果想等了，说明要么是到了相交点，要么是都是 空。

一般来说，hashmap 的思路都可以想到，双指针的思路如果可以想到则尽量使用这个思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    tmpA,tmpB := headA,headB
    for tmpA != tmpB {
        if tmpA == nil {
            tmpA = headB
        }
        if tmpB == nil {
            tmpB = headA
        }
        if tmpA != tmpB {
            tmpA = tmpA.Next
            tmpB = tmpB.Next
        } else {
            return tmpA
        }
    }

    return tmpA 
}

206. 反转链表

image-20240529142729920

知识点：链表

翻转链表的方法有很多，最朴实的方式是全部放在一个数组，然后重新排列。

还有两外一种方法，就是递归，链表的题目大部分可以使用递归来实现，[1,2,3,4,5] 的翻转，其实是操作 1 和 [2,3,4,5] 翻转后的链表。

递归的核心是什么时候退出链表；递归内的操作是什么；递归下一个的是什么。

链表的处理方法，一半要画图来解决，思路会更加清晰，否则很容易搞混淆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func reverseList(head *ListNode) *ListNode {
    // 使用递归
    if head == nil || head.Next == nil {
        return head 
    }
    // 拿到下一个
    next := head.Next
    // 设置Next 为空，避免出现空指针
    head.Next = nil 
    // 反转后面的
    n := reverseList(next)
    // 放入自己
    next.Next = head 
    // 返回后面返回的头
    return n
}

234. 回文链表

image-20240529150554143

知识点：链表

如果都拿出来，放在数组里面，可能后导致数组长度过大，因此还是需要按照链表的方式解决。

如果是用链表来解决，可以尝试翻转链表，然后跟原链表对比，此时会新增内存；或者使用递归，递归到最后如果下一个是 nil 则开始比较。

这里用比较简单的方法，就是使用数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    total := make([]*ListNode,0,100)
    for head != nil {
        total = append(total,head)
        head = head.Next
    }
    for i:=0;i < len(total) >> 1; i++{
        if total[i].Val != total[len(total)-1-i].Val {
            return false 
        }
    }

    return true 
}

141. 环形链表

image-20240529151316179

知识点：链表，hashmap

首先可以考虑使用hashmap，记录所有已经写入进去的节点。

还有一种更快的方法，快慢指针，慢指针一次性走一步，快指针一次性走两步，如果重合了说明有环。

hashmap 比较容易想出来，这里使用快慢指针；

1
2
3
4
5
6
7
8
9
10
11
12
13
func hasCycle(head *ListNode) bool {
    // 快慢指针
    fast,slow := head,head
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        fast = fast.Next
        slow = slow.Next
        if fast == slow {
            return true 
        }
    }
    return false 
}

21. 合并两个有序链表

image-20240529152450345

知识点：双指针、链表、排序

最容易也是简单的方法是都放在一个数组里面，排序，然后组合成链表；

还可以使用双指针，比较出一个较小的吐出来，放在新的链表后面。这里使用这种方法来解答，时间复杂度更优。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    pre := &ListNode{}
    node := pre 
    
    for list1 != nil && list2 != nil {
        if list1.Val > list2.Val {
            node.Next = list2
            list2 = list2.Next
        } else {
            node.Next = list1
            list1 = list1.Next
        }

        node = node.Next
    }
    // 然后将剩下的放在后面
    if list1 != nil {
        node.Next = list1
    }
    if list2 != nil {
        node.Next = list2
    }

    return pre.Next
}

94. 二叉树的中序遍历

image-20240529170613533

知识点：二叉树，遍历

使用二叉树的遍历，就容易想到递归。中序遍历是先左边，再中间，再右边。左边作为一个集体，可以单独递归处理，右边同理。

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 inorderTraversal(root *TreeNode) (res []int) {
    if root == nil {
        return nil 
    }

    // 处理左边
    res = inorderTraversal(root.Left)
    // 把自己放进去
    res = append(res,root.Val)
    // 处理右边
    res = append(res,inorderTraversal(root.Right)...)

    return res
}

104. 二叉树的最大深度

image-20240529170942663

知识点：二叉树

首先想到的是使用 bfs，一层一层的遍历下去。但是这个题目可以使用更好的方法，也就是遍历。最大深度为左右节点的最大深度的最大值+1

1
2
3
4
5
6
7
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0 
    }

    return max(maxDepth(root.Left),maxDepth(root.Right)) + 1 
}

226. 翻转二叉树

image-20240529173023889

知识点：二叉树

这个题目里面非常适合使用递归来做，其他的方法都没有递归简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil 
    }

    // 翻转左右两边，然后递归
    root.Left,root.Right = root.Right,root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

101. 对称二叉树

image-20240529175712166

知识点：二叉树

判断轴对称，也可以使用递归，值是这个递归就变成一个往左边，一个往右边走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    var dfs func(left,right *TreeNode) bool 
    dfs = func(left,right *TreeNode) bool {
        if left == nil && right == nil {
            return true 
        } else if left != nil && right != nil {
            // fmt.Println(left.Val,right.Val)
            return left.Val == right.Val && dfs(left.Left,right.Right) && dfs(left.Right,right.Left)
        }

        return false 
    }

    return dfs(root.Left,root.Right)
}

543. 二叉树的直径

image-20240530093315348

知识点：二叉树

这个题目应该不算简单难度，寻常递归无法解决，dfs 每一个节点计算每个节点作为根时的直径，并且返回该节点的最大深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) (res int) {
    var dfs func(node *TreeNode) int 
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0 
        }

        l,r := dfs(node.Left),dfs(node.Right)
        res = max(res,l+r)
        return max(l,r)+1
    }
    dfs(root)

    return res 
}

108. 将有序数组转换为二叉搜索树

image-20240530094442319

知识点：二叉树

按照题目需要组装成一个平衡二叉树，就可以想到使用分治，选择中值作为节点，然后左边的值放在左边，分治迭代，右边的值放在右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    mid := len(nums) >> 1
    node := &TreeNode{
        Val: nums[mid],
        Left: sortedArrayToBST(nums[:mid]),
        Right:sortedArrayToBST(nums[mid+1:]),
    }

    return node 
}

中等

49. 字母异位词分组

image-20240528162533308

知识点：hashmap

由于 str 只包含小写字母，因此可以使用 map 作为条件聚合，此时 key 的选取就非常关键，对于有限的内容，可以使用有限长度数组，或者使用二进制最后的值来存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func groupAnagrams(strs []string) (res [][]string) {
    total := make(map[[26]int][]string)
    for _, str:= range strs {
        tmp := [26]int{}
        for _,v := range str {
            tmp[int(v-'a')]++
        }
        total[tmp] = append(total[tmp],str)
    }

    // 这里提前分配可以节约时间
    res = make([][]string,0,len(total))
    for _,v := range total {
        res = append(res,v)
    }
    return res 
}

128. 最长连续序列

image-20240528163030751

知识点：hashmap、排序、双指针

方法 1：使用 hashmap，然后遍历 map 中的所有元素，找到左边没有的元素，开始往右遍历，确定最大长度

方法 2：先排序，然后使用双指针，左边指针是连续数组的开头，结尾指针是连续数组的结尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestConsecutive(nums []int) (res int) {
    total := make(map[int]struct{},len(nums))
    for _,v:= range nums {
        total[v]= struct{}{}
    }

    for i := range total {
        if _, ok:= total[i-1];!ok{
            // 左边不存在，开始计算
            l:=i+1
            for {
                if _,o := total[l];!o{
                    // 此时 l 不在了，退出循环
                    break 
                }
                l++
            }
            res = max(res,l-i)
        }
    }
    
    return res 
}

11. 盛最多水的容器

image-20240528164407067

知识点：双指针

左指针在最左边，右指针在最右边，两个指针往中间移动，获取当前容量。左右两个指针较小的值往中间移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxArea(height []int) (res int) {
    l,r:=0,len(height)-1
    for l<r {
        tmp := (r-l) * min(height[l],height[r])
        res = max(res,tmp)
        if height[l] > height[r] {
            r--
        } else {
            l++
        }
    }

    return res 
}

15. 三数之和

image-20240528164751480

知识点：双指针

这是一个双指针的另外一种用法，先固定一个点，然后另外两个点作为双指针操作。需要注意的是要去重，也就是当指针移动的数字相同时，要继续移动。

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
func threeSum(nums []int) (res [][]int) {
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        // 先固定 i
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // 双指针
        l, r := i+1, len(nums)-1
        // 退化成两值相加
        for l < r {
            tmp := nums[i] + nums[l] + nums[r]
            // fmt.Println(tmp,i,l,r)
            if tmp > 0 {
                // 过滤重复的
                r--
                for r >= 0 && r < len(nums)-1&& nums[r]== nums[r+1] {
                    r--
                }
            } else if tmp < 0 {
                l++
                for l>0 && l < len(nums) && nums[l]==nums[l-1] {
                    l++
                }
            } else {
                res = append(res, []int{nums[i], nums[l], nums[r]})
                r--
                for r >= 0 && r < len(nums)-1&& nums[r]== nums[r+1] {
                    r--
                }
                l++
                for l>0 && l < len(nums) && nums[l]==nums[l-1] {
                    l++
                }
            }
        }
    }

    return res 
}

3. 无重复字符的最长子串

image-20240528174108703

知识点：hashmap、双指针

这是一个非常典型的双指针问题，双指针的核心：

  1. 如何定义左指针和右指针（大部分右指针是 i，往右边移动；也有小部分左指针是左右两端）
  2. 如何移动左边指针（或者说移动右边指针；特别需要注意是否可以往回移动）

这个题目使用双指针，右指针记录为子串的结束，左指针记录为子串的开头。当遍历的时候，移动右边指针，当出现重复的时候，移动左指针到重复索引的右边，避免被过滤。

这个题目需要注意的点就是左指针只能往右移动，不能重复移动到左边。

使用 hashmap 记录最后一次出现的位置可以，但是字符串组成内容有限，所以使用有限数组也行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func lengthOfLongestSubstring(s string) (res int) {
    // 记录索引+1，避免 0 影响
    total := [256]int{}
    l := 0

    for i,v := range s {
        if total[int(v)] > 0 {
            // 代表以前出现过
            if l < total[int(v)] {
                // l 只能往右移动
                l = total[int(v)]
            }
        }
        // 记录最后出现的位置
        total[int(v)] = i+1
        // 判断结果
        res = max(res,i+1-l)
    }

    return 
}

438. 找到字符串中所有字母异位词

image-20240528174911328

知识点：双指针。

由于 p 是由小写字母组成，可以使用有限数组记录 p，然后遍历 s 时，遍历对应长度的子串，判断子串是否也可以组成数组。

可以理解为左边指针是遍历字符串，右边指针从左指针开始，移动到长度为 p 的地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findAnagrams(s string, p string) (res []int) {
    total := [256]int{}
    for _, v := range p {
        total[int(v)]++
    }

    for i := 0; i <= len(s)-len(p); i++ {
        tmp := [256]int{}
        for j:=0;j<len(p);j++{
            tmp[int(s[i+j])]++
        }
        if tmp == total {
            res = append(res,i)
        }
    }
    return 
}

560. 和为 K 的子数组

image-20240528175607797

知识点：双指针、前缀和、hashmap

可以使用双指针，记录 l 到 r 之间的和，如何和小于值，则移动右边，大于等于值，则移动左边；

也可以使用前缀和，记录到 hashmap 中，遍历的时候记录前缀和，然后判断另外一半是否存在于 hashmap 中。

1
2
3
4
5
6
7
8
9
10
11
12
func subarraySum(nums []int, k int) (res int) {
    // 前缀和
    total := map[int]int{0:1}
    var sum int 
    for _,v := range nums {
        sum += v 
        res += total[sum-k]
        total[sum] ++
    }

    return res 
}

53. 最大子数组和

image-20240529101445458

知识点：前缀和，动态规划

使用前缀和则是记录所有 idx 的前缀和，然后遍历之前的前缀和，寻找最大差值，这种方法很容易超时，时间复杂度相当于是 O(n^2)

使用 dp 则是记录当 idx 为结尾时的最大前缀和，状态转移方程则是判断 dp[i-1] 是否大于 0，如果大于 0，则表示可以带上前面，如果不大于 0，则表示不用带上前面的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxSubArray(nums []int) (res int) {
    dp := make([]int,len(nums))
    dp[0] = nums[0]   
    res = nums[0]

    for i:=1;i<len(nums);i++{
        if dp[i-1] > 0 {
            dp[i] = dp[i-1]+nums[i]
        } else {
            dp[i] = nums[i]
        }

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

    return res  
}

56. 合并区间

image-20240529102256425

知识点：双指针

先按照左边排序，然后使用双指针，左指针和右指针分别代表一个区间；左指针是最左边，往右遍历的时候移动右指针，如果大于右边的左边界，且可以增加右边界，则移动右边，无法移动的时候，代表这是一个区间。

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 merge(intervals [][]int) (res [][]int) {
    // 先排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    // 然后双指针
    l, r := intervals[0][0], intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        // 判断是否可移动右指针
        tmp := intervals[i]
        if r >= tmp[0] {
            // 可移动，
            r = max(r, tmp[1])
        } else {
            // 不可移动
            res = append(res, []int{l, r})
            l,r = tmp[0],tmp[1]
        }
    }
    // 将最后的区间也放进去
    res = append(res, []int{l, r})

    return 
}

189. 轮转数组

image-20240529102939870

知识点：数组转换

这个题目的解决方法很多，但是如果在面试的时候碰到，应该选择最为稳妥和容易想到的方法先解决，解决之后如果面试官再追问则可以深入讨论。

这里推荐使用复制一份数组出来，然后将新的数组回填到老的数组中。

1
2
3
4
5
6
7
func rotate(nums []int, k int)  {
    tmp := make([]int,len(nums))
    copy(tmp,nums)
    for i,v := range tmp {
        nums[(i+k)%len(nums)] = v
    }
}

238. 除自身以外数组的乘积

image-20240529103426009

知识点：前缀和（前缀积）

先遍历数组，获取所有数字的乘积，过程中记录 0 的个数，如果两个 0，则都是 0，如果一个 0，则除了这个点，其他的都是 0，如果没有 0，则再次遍历数组，计算每个点的答案；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func productExceptSelf(nums []int) []int {
    // 记录0的个数和位置
    var size,idx int
    total := 1
    for i,v := range nums{
        if v == 0 {
            size++
            idx = i
        } else {
            total *= v
        }
    }
    res := make([]int,len(nums))
    if size == 0 {
        for i,v := range nums{
            res[i] = total / v
        }
    } else if size == 1 {
        res[idx] = total
    }
    
    return res
}

73. 矩阵置零

image-20240529113011253

知识点：数组

首先遍历一次，获取所有的 0 的横和列，然后遍历横和列，将对应的位置置为 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func setZeroes(matrix [][]int)  {
    x,y:=make([]int,0),make([]int,0)
    for i,row := range matrix {
        for j,v := range row {
            if v == 0 {
                x = append(x,i)
                y = append(y,j)
            }
        }
    }

    for _,i := range x {
        for j := 0;j < len(matrix[0]);j++{
            matrix[i][j] = 0 
        }
    }
    for _,i := range y {
        for j := 0;j < len(matrix);j++{
            matrix[j][i] = 0 
        }
    }
}

54. 螺旋矩阵

image-20240529113351412

知识点：数组

这个问题的核心解决点是遍历数组的过程，方向的选择。避免撞到重复，可以在遍历了这个点之后，修改这个值，作为后续方向判断的条件

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 spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    // 方向
    directions := [4][2]int{[2]int{0, 1}, [2]int{1, 0}, [2]int{0, -1}, [2]int{-1, 0}}
    // 初始方向
    var d int

    res := make([]int, 0, m*n)
    var x, y int
    for len(res) < m*n {
        // 先记录下来
        res = append(res, matrix[x][y])
        // 改成一个不可能的值
        matrix[x][y] = 101
        // 判断方向
        dir := directions[d]
        tmpx := x + dir[0]
        tmpy := y + dir[1]
        for len(res) < m*n && (tmpx < 0 || tmpx == m || tmpy < 0 || tmpy == n || matrix[tmpx][tmpy] == 101 ) {
            d = (d + 1) % 4
            dir = directions[d]
            tmpx = x + dir[0]
            tmpy = y + dir[1]
        }
        x, y = tmpx, tmpy
        // fmt.Println(x, y)
    }

    return res
}

48. 旋转图像

image-20240529114545950

知识点：数组

直接在原数组上处理比较麻烦，推荐的方案依然是拷贝一份出来，然后处理。核心点是找到关系，x,y => y,n-x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func rotate(matrix [][]int) {
    // x,y => y,n-x
    n := len(matrix)
    tmp := make([][]int, n)
    for i := 0; i < n; i++ {
        tmp[i] = make([]int, n)
        copy(tmp[i], matrix[i])
    }

    // 开始转换
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            matrix[j][n-1-i] = tmp[i][j]
        }
    }
}

240. 搜索二维矩阵 II

image-20240529115050600

知识点：二分法、数组检索

像这种二维的二分法按照二分法来解决可能比较麻烦，但是可以退一步，因为每一行都已经排序了，因此可以针对每一行都检索一次，只要开头小于目标值，结尾大于目标值，就可以使用二分法查询。

这里介绍一种更加简单的做法，从右上角开始移动，如果大于目标值，说明应该向左移动，如果小于目标值，说明应该向下移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func searchMatrix(matrix [][]int, target int) bool {
    m,n := len(matrix),len(matrix[0])
    x,y := 0,n-1
    for x < m && y >= 0 {
        tmp := matrix[x][y]
        if tmp > target {
            y--
        } else if tmp < target {
            x++
        } else {
            return true 
        }
    }

    return false 
}

142. 环形链表 II

image-20240529151644049

知识点：链表，快慢指针，hashmap

跟判断是否有环的题目一样的处理逻辑，要么使用快慢指针获取节点，要么使用 hashmap 获取节点。

使用不同的是如果相交之后，快指针多走了一段路，因此快指针要从头开始，寻找第二次相遇，而且此时快指针慢下来，跟慢指针一起走完前面一样的路，再次相交则是环的开始。

hashmap 比较容易想出来，这里使用快慢指针。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast,slow := head,head
    // 第一次相遇
    for fast!=nil&& fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break 
        }
    }
    // 没有环
    if fast == nil || fast.Next == nil {
        return nil 
    }
    // 寻找第二次相遇 
    fast = head 
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }

    return fast
}

2. 两数相加

image-20240529153025376

知识点：链表，数学

从题目中可以看到，算法是按照十进制来运算的，链表也一样的运算即可

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    pre := &ListNode{}
    node := pre 

    // 满 10 之后要进一位
    var gate int 
    for l1 != nil && l2 != nil {
        val := l1.Val + l2.Val + gate
        gate = val / 10 
        val = val % 10 
        node.Next = &ListNode{Val:val}
        node = node.Next
        l1 = l1.Next
        l2 = l2.Next
    }
    // 再处理剩下的
    for l1 != nil {
        val := l1.Val + gate
        gate = val / 10 
        val = val % 10 
        node.Next = &ListNode{Val:val}
        node = node.Next
        l1 = l1.Next
    }
    for l2 != nil {
        val := l2.Val + gate
        gate = val / 10 
        val = val % 10 
        node.Next = &ListNode{Val:val}
        node = node.Next
        l2 = l2.Next
    }
    // 最后处理多进的一位
    if gate > 0 {
        node.Next = &ListNode{Val:gate}
    }

    return pre.Next
}

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

image-20240529154046000

知识点：链表

核心点是找到倒数第 n 个节点是哪个，因此，可以尝试做补全，假设有一个节点在前n 个的地方，逐步移动这两个节点，当节点移动为空，前面的节点就是倒数第 n 个节点。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    pre := &ListNode{Next:head}
    node,target := head,pre

    for node != nil {
        node = node.Next
        if n > 0 {
            n -- 
        } else {
            target = target.Next 
        }
    }

    // 此时 pre 的下一个节点就是需要删除的节点
    target.Next = target.Next.Next

    return pre.Next
}

24. 两两交换链表中的节点

image-20240529154500550

知识点：链表

这种题目很容易让人想到使用递归，交换了两个节点之后，递归处理后面的节点

需要注意的是处理顺序，避免出现死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head 
    }

    pre := &ListNode{Next:head}
    node,next := head,head.Next
    // 交换
    pre.Next = next
    // 处理后面的
    node.Next = swapPairs(next.Next)
    next.Next = node 

    return pre.Next
}

138. 随机链表的复制

image-20240529160242903

知识点：链表

先将链表按照 next 拷贝出来，核心在于找到 random，既可以使用 hashmap ，值是老的链表，value 是新的链表，也可以使用两个链表一起遍历，前者快一些，后者慢一些，毕竟便利的时候需要从头开始。

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
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    pre := &Node{}
    node1,node2 := head,pre
    total := make(map[*Node]*Node)
    for node1 != nil {
        tmp := &Node{Val:node1.Val}
        node2.Next = tmp 
        total[node1] = tmp
        node1 = node1.Next
        node2 = node2.Next 
    }

    node1,node2 = head,pre.Next
    for node1 != nil {
        node2.Random = total[node1.Random]
        node1 = node1.Next
        node2 = node2.Next
    }

    return pre.Next
}

148. 排序链表

image-20240529161109394

知识点：链表，排序

解决方法也比较多，但是面试时碰到原题，依然推荐最简单的方法，也就是放在数组里面排序，然后组装成链表。需要注意的是最后一个节点的 next 要指向 nil，避免出环。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    // 都拿出来
    total := make([]*ListNode, 0, 100)
    for head != nil {
        total = append(total, head)
        head = head.Next
    }
    // 排序
    sort.Slice(total, func(i, j int) bool {
        return total[i].Val < total[j].Val
    })

    // 组合
    for i := 0; i < len(total)-1; i++ {
        total[i].Next = total[i+1]
    }
    total[len(total)-1].Next = nil

    return total[0]
}

146. LRU 缓存

image-20240529162357272

知识点：链表，LRU

LRU 的核心能力是移动链表中的节点，以及删除最后一个节点的能力。但是又需要提供 O(1) 的查询能力，因此需要双向链表和 hashmap。节点中除了存储双向，还需要存储 key 和 value，用于删除最末尾一个节点时，查找 hashmap 中的值。

真实编码的时候，在面试 de 环境下，很容易思维混乱，因此先不要取巧，当已经解决出来之后，再想办法优化代码。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
type node struct {
    pre  *node
    next *node
    key int // 需要通过 key 获取到map 的 key，用于删除
    val  int
}

type LRUCache struct {
    capacity int
    all      map[int]*node
    start    *node
    end      *node
}

func Constructor(capacity int) LRUCache {
    start, end := &node{}, &node{}
    start.next = end
    end.pre = start
    return LRUCache{
        capacity: capacity,
        all:      make(map[int]*node, capacity),
        start:    start,
        end:      end,
    }
}

func (this *LRUCache) Get(key int) int {
    n, ok := this.all[key]
    if !ok {
        // 没有找到
        return -1
    }
    // 找到了，这里不要直接调用 put 去偷懒，避免逻辑混乱了
    // 从原先的位置去掉
    pre, next := n.pre, n.next
    pre.next = next
    next.pre = pre

    // 插入开头
    start := this.start.next
    this.start.next = n
    n.pre = this.start

    n.next = start
    start.pre = n

    return n.val
}

func (this *LRUCache) Put(key int, value int) {
    // put 的时候首先判断这个节点是否存在，如果存在需要从链表中删除
    n, ok := this.all[key]
    if ok {
        // 找到了，先删除
        pre, next := n.pre, n.next
        pre.next = next
        next.pre = pre

        // 然后更新值，放在最前面
        n.val = value
        // 插入开头
        start := this.start.next
        this.start.next = n
        n.pre = this.start

        n.next = start
        start.pre = n

        return
    }

    // 没有找到
    n = &node{key:key,val: value}
    // 判断是否满了 
    if len(this.all) == this.capacity {
        // 满了需要去掉最后一位
        del := this.end.pre
        delete(this.all,del.key)
        end := del.pre

        end.next = this.end
        this.end.pre = end 
    }

    // 然后放在最前面
    start := this.start.next

    // 放在最前面
    this.start.next = n
    n.pre = this.start

    // 插队
    start.pre = n
    n.next = start

    this.all[key] = n
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

102. 二叉树的层序遍历

image-20240530093815446

知识点：多叉树

使用非常典型的 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) (res [][]int) {
    if root == nil {
        return nil 
    }
    total := []*TreeNode{root}
    for len(total) > 0 {
        tmp := make([]*TreeNode,0,len(total)*2)
        tmpRes := make([]int,0,len(total))
        for _,v := range total {
            tmpRes = append(tmpRes,v.Val)
            if v.Left != nil {
                tmp = append(tmp,v.Left)
            }
            if v.Right != nil {
                tmp = append(tmp,v.Right)
            }
        }
        total = tmp 
        res = append(res,tmpRes)
    }

    return res 
}

98. 验证二叉搜索树

image-20240530101158822

知识点：二叉树

按照题目要求，必须是一个有效的二叉搜索树，那么需要判断每个节点的值是否满足条件。

使用 dfs 判断每一个节点，节点需要满足的最大值和最小值作为 dfs 的条件传递下去。

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 isValidBST(root *TreeNode) bool {
    var dfs func(node *TreeNode, ma int, mi int) bool
    dfs = func(node *TreeNode, ma int, mi int) bool {
        if node == nil {
            return true
        }
        // fmt.Println(node.Val,ma,mi)
        return node.Val < ma && node.Val > mi &&
            dfs(node.Left, min(ma, node.Val), mi) &&
            dfs(node.Right, ma, max(mi, node.Val))
    }

    return dfs(root.Left, root.Val, math.MinInt) && dfs(root.Right, math.MaxInt, root.Val)
}

230. 二叉搜索树中第K小的元素

image-20240530102059597

知识点：二叉搜索树

第 k 个最小元素，其实是中序遍历的第 k 个值，便利的时候遍历到第 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) (res int) {
    tmp := make([]int, 0, k)
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        if len(tmp) == k {
            return
        }
        // 前
        dfs(node.Left)
        // 中
        tmp = append(tmp, node.Val)
        // 后
        dfs(node.Right)
    }
    dfs(root)

    return tmp[k-1]
}

199. 二叉树的右视图

image-20240530110122014

知识点：二叉树

按照题目要求，使用 bfs 即可，每次 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) (res []int) {
    if root == nil {
        return nil 
    }

    total := []*TreeNode{root}
    for len(total) > 0 {
        tmpTotal := make([]*TreeNode,0,len(total)*2)
        res = append(res,total[len(total)-1].Val)
        for _,v := range total {
            if v.Left != nil {
                tmpTotal = append(tmpTotal,v.Left)
            }
            if v.Right != nil {
                tmpTotal = append(tmpTotal,v.Right)
            }
        }
        total = tmpTotal
    }

    return res 
}

114. 二叉树展开为链表

image-20240530110519525

知识点：链表

按照题目所述是先序遍历，因此按照先序遍历处理即可。这种返回一个节点的要求，一半可以使用 pre 虚拟节点来实现。

如果在面试的时候，捋不清使用 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
    pre := &TreeNode{Right: root}
    tmp := pre

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }

        // 先序遍历
        tmp.Left = nil
        tmp.Right = node
        tmp = tmp.Right
        // 这里要临时保留左右节点，避免递归后节点信息发生变化，导致出环或者其他异常。
        l, r := node.Left, node.Right
        dfs(l)
        dfs(r)
    }
    dfs(root)
}

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

image-20240530111349482

知识点：二叉树的遍历

这个题目如果不知道解决方法在面试中比较难想出来的。核心点是先序遍历和中序遍历的相同点和不同点。

比如上面的节点 3，前序遍历时，3 的后面是他的所有子节点，但是在中序遍历时，3的前面是左边子节点，3 的后面是右子节点。因此可以使用分治递归的方法，将左边子节点找出来，将右边子节点找出来，作为子数组进行递归，通过数组的长度固定，可以确定左子节点的前序遍历中序遍历的子数组，右子节点同理。

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
/**
 * 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
    }

    node := &TreeNode{Val: preorder[0]}
    var idx int
    for inorder[idx] != node.Val {
        idx++
    }
    li := inorder[:idx]
    ri := inorder[idx+1:]
    lp := preorder[1 : 1+len(li)]
    rp := preorder[1+len(li):]
    node.Left = buildTree(lp, li)
    node.Right = buildTree(rp, ri)

    return node
}

437. 路径总和 III

image-20240530112202476

知识点：二叉树、前缀和

每一个节点获取到前面节点的前缀和，此时即可判断自己这个点到前面某一个点之间的距离，满足条件即可。

使用 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) (res int) {
    var dfs func(node *TreeNode, dis int, total []int)
    dfs = func(node *TreeNode, dis int, total []int) {
        if node == nil {
            return
        }

        // 先计算自己的前缀和
        dis += node.Val
        tmp := dis-targetSum
        // fmt.Println(node.Val, tmp, total)
        for _, v := range total {
            if tmp == v {
                // fmt.Println(node.Val)
                res++
            }
        }
        total = append(total, dis)
        dfs(node.Left, dis, total)
        dfs(node.Right, dis, total)
    }
    dfs(root, 0, []int{0})

    return res
}

236. 二叉树的最近公共祖先

image-20240530114013712

知识点：二叉树

寻找公共祖先，可以用一个简单方法，那就是返回自己的祖先，当两个节点返回的祖先相同，则代表是公共祖先。

使用 dfs，先便利左边和右边，判断返回，如果这个节点是 p 或者 q 则返回这个节点，如果不是，则判断子节点是否有返回，如果子节点都有返回，说明左边和右边都找到了，则返回自己；如果某个子节点有返回则返回子节点的内容，否则就是都为空，返回 nil。最终返回出来的结果就是公共祖先节点。

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
/**
 * 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 {
        return nil 
    }

    if root == p || root == q {
        return root 
    }
    l,r := lowestCommonAncestor(root.Left,p,q),lowestCommonAncestor(root.Right,p,q)
    if l != nil && r != nil {
        return root 
    } else if l == nil {
        return r 
    } 

    return l
}

困难

42. 接雨水

image-20240528172622206

知识点：单调栈

如果不看答案，很少能想得到使用单调栈来解决。除了接雨水，还有获取最大面积也都是一样的逻辑。

单调栈，使用单调递减栈，入栈的是索引，入栈的时候，说明左边有着落，当出栈的时候，说明右边有着落了，此时就需要计算当前这个点可以接下的雨水。计算可以接下的雨水，是左边到右边的间隔，乘以中间的差值。例如上面的 2,1,0,1,2 ，先入栈 2,1,0，然后在入栈 1 的时候，0 出栈，此时计算的是 1,0,1 的雨水，当 1 出栈的时候，计算的是左边的 2 到右边的 2 之间，在 1 之上的雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func trap(height []int) (res int) {
    // 使用严格递增栈，记录 idx
    stack := make([]int, 0)
    for i := 0; i < len(height); i++ {
        // 先出栈
        for len(stack) > 0 && height[stack[len(stack)-1]] <= height[i] {
            tmp := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 出栈的时候，计算当前的雨水，左边是栈顶，右边是i
            if len(stack) > 0 {
                l := stack[len(stack)-1]
                // 高度，是左边和右边的较小值，减去自己
                hei := min(height[l], height[i]) - height[tmp]
                res += (i - l - 1) * hei
            }
        }
        // 入栈
        stack = append(stack, i)
    }
    return res
}

239. 滑动窗口最大值

image-20240529093253614

知识点：堆

通过题目比较容易想到使用最大堆，将 k 个数字都存入堆，进一个值的时候，获取堆顶的元素，而且要确保堆顶要大于 i-k，也就是在窗口内，因此获取堆顶时可以使用 for 循环。

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
// 0 存放 idx，1 存放数字
type stack [][2]int

func (n *stack) Len() int {
    return len(*n)
}

func (n *stack) Less(i, j int) bool {
    // 最大堆
    return (*n)[i][1] > (*n)[j][1]
}

func (n *stack) Swap(i, j int) {
    (*n)[i], (*n)[j] = (*n)[j], (*n)[i]
}

func (n *stack) Push(x interface{}) {
    *n = append(*n, x.([2]int))
}

func (n *stack) Pop() interface{} {
    x := (*n)[len(*n)-1]
    *n = (*n)[:len(*n)-1]
    return x
}

func maxSlidingWindow(nums []int, k int) []int {
    var s stack
    for i := 0; i < k; i++ {
        heap.Push(&s, [2]int{i, nums[i]})
    }
    res := make([]int, 0, len(nums)-k+1)
    res = append(res, s[0][1])
    for i := k; i < len(nums); i++ {
        // 先入栈
        heap.Push(&s, [2]int{i, nums[i]})
        // 判断是否在窗口中
        for s[0][0] <= i-k {
            heap.Pop(&s)
        }
        res = append(res, s[0][1])
    }

    return res
}

76. 最小覆盖子串

image-20240529094753016

知识点：滑动窗口、双指针

使用双指针记录滑动窗口中的内容，先移动右边，找到包含 t 的所有子串，记录此时的答案；滑动左边，直到不包含子串，然后查询下一个包含 t 的子串。

这个方法的难点是如何记录 t，以及子串，因为子串需要记录出现的次数，用于记录当左指针移动的时候，确保刚好不含有子串。因此，除了使用数组记录 t和临时子串，还需要有一个数组记录多出来的次数，移动的时候如果临时子串满了，则放在次数数组中记录。

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
func minWindow(s string, t string) (res string) {
    total := [256]int{}
    for _, v := range t {
        total[int(v)]++
    }

    // 记录临时的字母
    tmpL := [256]int{}
    // 记录临时的个数
    tmpN := [256]int{}
    // 左指针
    var l int
    // 记录答案
    res = s 
    // 判断是否有答案
    var flag bool 

    for i, v := range s {
        // 移动右指针
        // 是目标子串
        if total[int(v)] > 0 {
            // 判断是否满了
            if tmpL[int(v)] == total[int(v)] {
                tmpN[int(v)]++
            } else {
                tmpL[int(v)]++
            }

            // 判断是否移动左边指针
            // 开始移动左指针
            for tmpL == total {
                flag = true 
                if total[int(s[l])] > 0 {
                    // 先减去满的
                    if tmpN[int(s[l])] > 0 {
                        tmpN[int(s[l])]--
                    } else {
                        // fmt.Println(l,i)
                        // 不满，此时是最短子串
                        if i+1-l < len(res) {
                            res = s[l : i+1]
                        }
                        tmpL[int(s[l])]--
                    }
                }

                l++
            }
        }
    }
    if flag {
        return res 
    }
    return ""
}

41. 缺失的第一个正数

image-20240529111500283

知识点：hashmap

这套题的解决方法也有很多，面试时轻快好解的思路，选择使用 hashmap，记录所有出现的正数，然后从 1 开始判断不存在的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func firstMissingPositive(nums []int) int {
    total := make(map[int]struct{})
    for _, v := range nums {
        if v > 0 {
            total[v] = struct{}{}
        }
    }

    i := 1
    for ; i <= len(total); i++ {
        if _, ok := total[i]; !ok {
            return i
        }
    }

    return i
}

25. K 个一组翻转链表

image-20240529155159670

知识点：链表

字节一面碰到过。

这种问题使用递归最好，核心是处理递归和递归内部链表翻转。递归比较好处理，如果满足个数即可处理，内部翻转在面试时很容易晕头转向，处理不好节点之间的跳跃关系，可以尝试换成使用数组。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil {
        return head 
    }

    // 判断是否满足 k 个
    tmp := make([]*ListNode, 0, k)
    for i := 0; i < k && head != nil; i++ {
        tmp = append(tmp,head)
        head = head.Next
    }
    // 不满
    if len(tmp) != k {
        return tmp[0]
    }
    // fmt.Println(tmp,head)

    // 满足的时候，先处理后面的，让后面的翻转了之后，再处理自己
    tmp[0].Next = reverseKGroup(head,k)
    // 翻转
    for i:=1;i<k;i++{
        tmp[i].Next = tmp[i-1]
    }

    return tmp[len(tmp)-1]
}

23. 合并 K 个升序链表

image-20240529161623207

知识点：链表、堆

从前面两个链表升级到多个链表，因此可以使用堆排序来实现。从堆里面取出来，取最小的，放到答案里面，然后移动链表，非空的话再丢进去。

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
 * }
 */

type stack []*ListNode

func (s *stack) Len() int {
    return len(*s)
}

func (s *stack) Swap(i, j int) {
    (*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}

// 最小堆
func(s *stack) Less(i,j int) bool {
    return (*s)[i].Val < (*s)[j].Val
}

func(s *stack) Push(x interface{}) {
    (*s) = append((*s),x.(*ListNode))
}

func(s *stack) Pop() interface{} {
    x := (*s)[len(*s)-1]
    (*s) = (*s)[:len(*s)-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    var s stack
    // 入栈
    for _,v := range lists {
        if v != nil {
            heap.Push(&s,v)
        }
    }
    pre := &ListNode{}
    node := pre 

    for len(s) != 0 {
        tmp := heap.Pop(&s).(*ListNode)
        node.Next = tmp 
        tmp = tmp.Next
        if tmp != nil {
            heap.Push(&s,tmp)
        }
        node = node.Next
    }

    return pre.Next
}

124. 二叉树中的最大路径和

image-20240530114813934

知识点：二叉树

跟直径的题目原理差不多，使用 dfs 判断所有节点的路径和，返回该节点的最大路径，用本节点左边的最大路径和右边节点的最大路径相加，就是本节点的最大路径和。

由于测试用例中会出现 0，因此需要注意最小数和返回给上层的结果。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) (res int) {
    res = math.MinInt
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        l, r := dfs(node.Left), dfs(node.Right)
        if l >= 0 && r >= 0 {
            res = max(res, l+r+node.Val)
        } else if l < 0 && r >= 0 {
            res = max(res, r+node.Val)
        } else if l >= 0 && r < 0 {
            res = max(res, l+node.Val)
        } else {
            res = max(res, node.Val)
        }
        return max(0, max(l, r)) + node.Val
    }

    dfs(root)

    return res
}