Go 刷题清单¶

func subarraySum(nums []int, k int) int {
    count, prefixSum := 0, 0
    prefixSumMap := map[int]int{0:1} // 兼容 nums=[3], k=3
    for i := range nums {
        currentSum += nums[i] // 计算前缀和
        if _, ok := prefixSumMap[currentSum-k]; ok { // 也可以利用 Go Map 的零值机制优化为一行代码
            count += prefixSumMap[currentSum-k] // 累计频率
        }
        prefixSumMap[currentSum]++ // 对前缀和值的出现次数统计
    }

    return count
}

func twoSum(nums []int, target int) []int {
    // 哈希表记录出现的元素及索引
    // 遍历 nums，如果 target - num 在哈希表中，返回索引
    // 否则将 num 加入哈希表

    seen := map[int]int{}
    for i, num := range nums {
        if j, ok := seen[target-num]; ok {
            return []int{i, j}
        }
        seen[num] = i
    }

    return []int{}
}

func longestConsecutive(nums []int) int {
    has := map[int]bool{} // 直接初始化为 bool 可以简化哈希表判断
    for _, num := range nums {
        has[num] = true
    }

    ans := 0
    for num := range has {
        prev, next := num-1, num+1
        if has[prev] { // 上一个数存在于哈希表，说明 num 不是序列的起点
            continue
        }

        for has[next] { // 不断查找下一个序列是否在哈希表中
            next++
        }

        ans = max(ans, next-num)
    }

    return ans
}

// 排序解法
// Time: O(m*nlogn), Space: O(m*n)
func groupAnagrams(strs []string) [][]string {
    groups := map[string][]string{}
    for _, str := range strs {
        bytes := []byte(str)
        slices.Sort(bytes)
        key := string(bytes)
        groups[key] = append(groups[key], str)
    }

    ans := make([][]string, 0, len(groups))
    for _, group := range groups {
        ans = append(ans, group)
    }

    return ans
}

// 计数解法
// Time: O(m*n), Space: O(m*n)
func groupAnagrams(strs []string) [][]string {
    groups := map[[26]int][]string{}
    for _, str := range strs {
        count := [26]int{}
        for _, ch := range str {
            count[ch-'a']++
        }
        groups[count] = append(groups[count], str)
    }

    ans := make([][]string, 0, len(groups))
    for _, group := range groups {
        ans = append(ans, group)
    }

    return ans
}

func maxArea(height []int) int {
    maxArea, left, right := 0, 0, len(height)-1
    for left < right {
        area := (right - left) * min(height[left], height[right]) // 以较矮的作为高计算面积
        maxArea = max(maxArea, area)
        // 只移动较矮的一边
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
}

// Time: O(m+n), Space: O(1)
func merge(nums1 []int, m int, nums2 []int, n int) {
    p1, p2, tail := m-1, n-1, m+n-1

    // 只需检查 p2 >= 0，因为 nums2 处理完后，nums1 剩余元素已在正确位置
    for p2 >= 0 {
        if p1 >= 0 && nums1[p1] > nums2[p2] {
            nums1[tail] = nums1[p1]
            p1--
        } else {
            nums1[tail] = nums2[p2]
            p2--
        }
        tail--
    }
}

func moveZeroes(nums []int)  {
    slow := 0 // 并不能确定 nums[0] 是否为非零值
    for fast := range nums { // fast 要从0开始遍历，否则可能遗漏首位的零值交换。首位是非零值会发生自己和自己交换
        if nums[fast] != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }
}

func removeDuplicates(nums []int) int {
    slow := 0
    for fast := 1; fast < len(nums); fast++ {
        if nums[slow] != nums[fast] {
            slow++ // // 注意要交换到 slow 的下一个位置
            nums[slow] = nums[fast]
        }
    }

    return slow+1 // 注意差1问题。Go 中 i++ 是语句，不是表达式，不能返回 i++
}

func lengthOfLongestSubstring(s string) int {
    // 哈希表记录出现的元素及索引
    // 哈希表出现的元素，left 移动到哈希表中索引 +1 位置，否则右指针右移扩大窗口

    seen := map[byte]int{}
    left, right, maxWin := 0, 0, 0
    for right < len(s) {
        if prevIndex, ok := seen[s[right]]; ok {
            left = prevIndex + 1
        }

        seen[s[right]] = right
        right++

        maxWin = max(maxWin, right-left)
    }

    return maxWin
}

func threeSum(nums []int) [][]int {
    if len(nums) < 3 {
        return nil
    }

    sort.Ints(nums)

    ans := [][]int{}
    // 先固定第一个数
    for i := 0; i < len(nums)-2; i++ {
        // 提前剪枝：如果第一个数已经大于0，后面都是正数，不可能和为0
        if nums[i] > 0 {
            break
        }

        if i > 0 && nums[i] == nums[i-1] {
            continue // 跳过重复的第一个数
        }

        // 用双指针让剩余两数之和与第一个数的和为0
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]

            // 注意此时已经排序
            if sum < 0 { // 和太小，需要右移靠近较大数
                left++
            } else if sum > 0 { // 和太大，需要左移靠近较小数
                right--
            } else { // 和为 0
                ans = append(ans, []int{nums[i], nums[left], nums[right]})

                // 跳过重复的第二个数
                for left < right && nums[left] == nums[left+1] {
                    left++
                }

                // 跳过重复的第三个数
                for left < right && nums[right] == nums[right-1] {
                    right--
                }

                left++
                right--
            }
        }
    }

    return ans
}

// Time: O(n²), Space: O(1)
func longestPalindrome(s string) string {
    start, maxLen := 0, 0

    // 从中心向两侧扩展，返回回文长度
    expand := func(l, r int) {
        for l >= 0 && r < len(s) && s[l] == s[r] {
            l--
            r++
        }
        // 此时 [l+1, r-1] 是回文
        if r-l-1 > maxLen {
            start = l + 1
            maxLen = r - l - 1
        }
    }

    for i := range s {
        // 无法预知以某个位置为中心的最长回文是奇数还是偶数长度，因此需要同时遍历两种情况，取最长的那个
        expand(i, i)   // 奇数长度回文（如 "aba"）
        expand(i, i+1) // 偶数长度回文（如 "abba"）
    }

    return s[start : start+maxLen]
}

// Time: O(n), Space: O(1)
func nextPermutation(nums []int) {
    // 从右往左找到第一个下降点 i
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }

    if i >= 0 {
        // 从右往左找到第一个大于 nums[i] 的数 j
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        // 交换 i 和 j
        nums[i], nums[j] = nums[j], nums[i]
    }

    // 反转 i 之后的部分
    left, right := i+1, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

// Time: O(n+m), Space: O(1)
func compareVersion(version1, version2 string) int {
    n, m := len(version1), len(version2)
    i, j := 0, 0
    for i < n || j < m {
        x := 0
        for i < n && version1[i] != '.' {
            x = x*10 + int(version1[i]-'0')
            i++
        }
        i++ // 跳过点号

        y := 0
        for j < m && version2[j] != '.' {
            y = y*10 + int(version2[j]-'0')
            j++
        }
        j++ // 跳过点号

        if x > y {
            return 1
        }
        if x < y {
            return -1
        }
    }

    return 0
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    // 暂存、反转、移动
    for head != nil {
        next := head.next
        head.Next = prev
        prev = head
        head = next
    }

    return prev
}

func reverseBetween(head *ListNode, left, right int) *ListNode {
    dummy := &ListNode{Next: head} // 可能从头结点开始反转

    prev := dummy
    for i := 1; i < left; i++ {
        prev = prev.Next
    }

    curr := prev.Next
    for ; left < right; left++ { // 这段代码画个步骤图就出来了
        next := curr.Next     // 暂存操作节点的移动路径
        curr.Next = next.Next // 摘下节点
        next.Next = prev.Next // 插到区间头部
        prev.Next = next      // 移动操作的节点
    }

    return dummy.Next
}

func middleNode(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }

    return slow
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}

func detectCycle(head *ListNode) *ListNode {
    seen := map[*ListNode]bool{}
    for head != nil {
        if seen[head] {
            return head
        }
        seen[head] = true
        head = head.Next
    }

    return nil
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }

        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }

    return pA // 没有相交时，遍历结束的链表最终指向 nil
}

func mergeSortedTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    // 注意该遍历需同时操作3个链表
    for l1 != nil && l2 != nil { // 注意是 &&
        if l1.Val < l2.Val {     // 将较小的值挂载在新链表上
            current.Next = l1
            l1 = l1.Next         // 移动原链表
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next   // 移动新链表
    }

    // 将链表剩余部分挂载，同时处理原链表为空
    if l1 != nil {
        current.Next = l1
    } else {
        current.Next = l2
    }

    // 注意返回的是 dummy.Next
    return dummy.Next
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy

    for {
        tail := prev
        for range k {
            tail = tail.Next
            if tail == nil {
                return dummy.Next // 不足 k 个时结束反转
            }
        }

        nextGroup := tail.Next // 下一组起始位置

        // 头插法局部反转链表
        cur := prev.Next
        for range k - 1 {
            next := cur.Next
            cur.Next = next.Next
            next.Next = prev.Next
            prev.Next = next
        }

        // 区间反转完成后，准备下一组的反转，此时 curr 移动到了区间末尾
        cur.Next = nextGroup
        prev = cur
    }
}

func mergeKListsByDivideAndConquer(lists []*utils.ListNode) *utils.ListNode {
    if len(lists) == 0 {
        return nil
    }

    return mergeRange(lists, 0, len(lists)-1)
}

func mergeRange(lists []*utils.ListNode, left, right int) *utils.ListNode {
    if left == right {
        return lists[left]
    }

    mid := left + (right-left)/2
    l1 := mergeRange(lists, left, mid)
    l2 := mergeRange(lists, mid+1, right)

    return mergeTwoLists(l1, l2)
}

func mergeTwoLists(l1, l2 *utils.ListNode) *utils.ListNode {
    dummy := &utils.ListNode{}
    cur := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }

    return dummy.Next
}

// 注意 Go 中需要实现 heap 接口
func mergeKListsByMinHeap(lists []*utils.ListNode) *utils.ListNode {
    h := &listNodeHeap{}
    heap.Init(h)

    for _, node := range lists {
        if node != nil {
            heap.Push(h, node)
        }
    }

    dummy := &utils.ListNode{}
    cur := dummy

    for h.Len() > 0 {
        node := heap.Pop(h).(*utils.ListNode)
        cur.Next = node
        cur = cur.Next

        if node.Next != nil {
            heap.Push(h, node.Next)
        }
    }

    return dummy.Next
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    mid := split(head)
    left := sortList(head)
    right := sortList(mid)

    return mergeTwoLists(left, right)
}

func split(head *ListNode) *ListNode {
    prev, slow, fast := head, head, head
    for fast != nil && fast.Next != nil {
        prev, slow, fast = slow, slow.Next, fast.Next.Next
    }

    prev.Next = nil // 注意需要切断链表

    return slow
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            curr.Next = l1
            l1 = l1.Next
        } else {
            curr.Next = l2
            l2 = l2.Next
        }
        curr = curr.Next
    }

    if l1 != nil {
        curr.Next = l1
    }
    if l2 != nil {
        curr.Next = l2
    }

    return dummy.Next
}

func reorderList(head *ListNode)  {
    mid := middleNode(head)
    reversedHead := reverseList(mid)
    p1, p2 := head, reversedHead
    for p2.Next != nil {                    // 注意结束条件
        p1Next, p2Next := p1.Next, p2.Next  // 保存指针避免断链
        p1.Next, p2.Next = p2, p1Next       // 交叉连接
        p1, p2 = p1Next, p2Next             // 移动节点
    }
}

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }

    return slow
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }

    return prev
}

type Node struct { // 内部实现，不允许外部访问
    key, value int
    prev, next *Node
}

type LRUCache struct {
    capacity int
    cache    map[int]*Node // 哈希表：key -> 链表节点
    head     *Node         // 虚拟头节点（最近使用）
    tail     *Node         // 虚拟尾节点（最久未使用）
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        capacity: capacity,
        cache:    make(map[int]*Node),
        head:     &Node{},
        tail:     &Node{},
    }

    lru.head.next = lru.tail
    lru.tail.prev = lru.head

    return lru
}

func (lc *LRUCache) Get(key int) int {
    if node, exists := lc.cache[key]; exists {
        // 将节点移到头部（标记为最近使用）
        lc.moveToHead(node)
        return node.value
    }
    return -1
}

func (lc *LRUCache) Put(key, value int) {
    if node, exists := lc.cache[key]; exists {
        // 更新已存在的节点
        node.value = value
        lc.moveToHead(node)
    } else {
        // 创建新节点
        newNode := &Node{key: key, value: value}
        lc.cache[key] = newNode
        lc.addToHead(newNode)

        // 检查容量，必要时删除最久未使用的节点
        if len(lc.cache) > lc.capacity {
            removed := lc.removeTail()
            delete(lc.cache, removed.key)
        }
    }
}

// 辅助方法：将节点添加到头部
// 画一个三角插入图形理解分析：先把新节点与左右节点相连，再把右侧节点指向新节点，最后把head指向新节点。插入头部的节点操作要基于 head。
//               ┌──────┐          node.prev        ┌──────┐
//               │ head │◀╌╌╌╌╌╌╌╌╌╳╌╌╌╌╌╌╌╳╌╌╌╌╌╌╌╌│ node │
//               └─▲─┬──┘╌╌╌╌╌╌╌╌╌╌╳╌╌╌╌╌╌╌╳╌╌╌╌╌╌╌▶└──┬─▲─┘
//                 │ │             head.next           │ │
//                 │ │                                 │ │
// 1. newNode.prev │ │               3. head.next.prev │ │ 2. newNode.next
//                 │ │ 4. head.next                    │ │
//                 │ │                                 │ │
//                 │ ╰──────────▶ ┌─────────┐ ◀────────╯ │
//                 ╰───────────── │ newNode │ ───────────╯
//                                └─────────┘
func (lc *LRUCache) addToHead(node *Node) {
    node.prev = lc.head
    node.next = lc.head.next
    lc.head.next.prev = node
    lc.head.next = node
}

// 辅助方法：移除节点
func (lc *LRUCache) removeNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// 辅助方法：将节点移到头部
func (lc *LRUCache) moveToHead(node *Node) {
    lc.removeNode(node)
    lc.addToHead(node)
}

// 辅助方法：移除尾部节点
func (lc *LRUCache) removeTail() *Node {
    node := lc.tail.prev
    lc.removeNode(node)
    return node
}