leetcode hot 100 刷题（go语言版）

入口

Cookbook

codetop

ps: 空间复杂度不需要考虑入参和返回值

通用定义

子串（substring）：原始字符串的一个连续子集；

子序列（subsequence）：原始字符串的一个子集。

空间复杂度：注意是排除入参出参的额外空间

哈希

1. 两数之和

查看代码

func twoSum(nums []int, target int) []int {
    visitedNumMap := make(map[int]int, len(nums)) // [num]numIndex
    ans := make([]int, 2)

    for curNumIndex, curNum := range nums {
    anotherPartNum := target - curNum
    if anotherPartNumIndex, ok := visitedNumMap[anotherPartNum]; ok {
        ans[0], ans[1] = curNumIndex, anotherPartNumIndex
        return ans
    }
    visitedNumMap[curNum] = curNumIndex
    }

    return ans
}

• 时间复杂度O(n)
• 空间复杂度O(n)

49. 字母异位词分组

查看代码

import (
    "sort"
)

func groupAnagrams(strs []string) [][]string {
    collectAnagrams := make(map[string][]string) // [sortedStr]collectAnagram

    for _, str := range strs {
        sortedStr := sortStr(str)
        collectAnagrams[sortedStr] = append(collectAnagrams[sortedStr], str)
    }

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

    return ans
}

func sortStr(str string) string {
    sliceStr := []byte(str)
    sort.Slice(sliceStr, func(i, j int) bool { return sliceStr[i] < sliceStr[j] })
    return string(sliceStr)
}

• 时间复杂度O(n log m)
• 空间复杂度O(nm)

func groupAnagrams(strs []string) [][]string {
    collectAnagrams := make(map[[26]int][]string) // [charCnts]collectAnagram

    for _, str := range strs {
        var charCnts [26]int
        for _, b := range str {
            charCnts[b-'a']++
        }
        collectAnagrams[charCnts] = append(collectAnagrams[charCnts], str)
    }

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

    return ans
}

• 时间复杂度O(nm)
• 空间复杂度O(nm)

ps：for _, b := range str b的类型是rune

---

双指针

283. 移动零

查看代码

func moveZeroes(nums []int) {
    leftMostZeroIndex := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != 0 {
            if nums[leftMostZeroIndex] == 0 { // 只有为0才需要交换
                nums[leftMostZeroIndex], nums[i] = nums[i], nums[leftMostZeroIndex]
            }
            leftMostZeroIndex++
        }
    }
}

• 时间复杂度O(n)

• 空间复杂度O(1)

15. 三数之和

查看代码

// 神来之笔：排序
// 我们从O(n^3)开始优化(i, j, k)
// 第一层循环确定一个值之后，后面只需要完成一次两数字之和的任务，
// 但是原本使用map的解法来做两数之和，会导致最后空间复杂度变为O(n^2)，时间复杂度为O(n^2)。
// 但是和两数之和不同的是，当前序列已经排好了，可以使用双指针两边同时逼近
// 如果num[j] + num[k] > target, 那么让k左移，也就是让num[j] + num[k]变小一些来贴近target
// 如果num[j] + num[k] < target, 那么让j右移，同上
// 最坏的情况就是j和k相遇了，那也一共也就是O(n), 加上最外层i循环，也就是O(n^2)的时间复杂度，但是空间复杂度只有O(1)
// 排序的作用1: 避免重复
// 排序的作用2: 让两数之和的时间复杂度保持O(n)，但是空间复杂度由O(n)->O(1)

import "sort"

func threeSum(nums []int) (ans [][]int) {
    sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
    for i := 0; i < len(nums)-2; i++ {
        if i != 0 && nums[i] == nums[i-1] {
            continue
        }
        target := 0 - nums[i]
        j, k := i+1, len(nums)-1
        for j < k {
            sum := nums[j] + nums[k]
            switch {
            case j != i+1 && nums[j] == nums[j-1]:
                j++
            case sum < target:
                j++
            case sum > target:
                k--
            case sum == target:
                ans = append(ans, []int{nums[i], nums[j], nums[k]})
                j++
            }
        }
    }
    return ans
}

• 时间复杂度O(n^2)

• 空间复杂度O(logn) sort内部是快排，快排里面是递归，栈区占用空间。

---

滑动窗口

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

查看代码

rightMostWindowIndex始终处于一个试探的位置，只有发现map中没有重复的字符才会+1

func lengthOfLongestSubstring(s string) int {
    charWindowMap := make(map[byte]struct{}, 128)
    var leftMostWindowIndex, rightMostWindowIndex, maxWindowLen int

    for rightMostWindowIndex < len(s) {
        curChar := s[rightMostWindowIndex]
        if _, ok := charWindowMap[curChar]; ok {
            delete(charWindowMap, s[leftMostWindowIndex])
            leftMostWindowIndex++
            continue
        }
        charWindowMap[curChar] = struct{}{}
        maxWindowLen = max(maxWindowLen, len(charWindowMap))
        rightMostWindowIndex++
    }

    return maxWindowLen
}

• 时间复杂度O(n)

• 空间复杂度O(n)

---

子串

215. 数组中的第K个最大

查看代码

// 维护一个小根堆（capcity为k）
// 堆没有满时：直接入堆
// 堆满时：如果堆顶元素小于当前元素，堆顶元素被淘汰，当前元素入堆
// 遍历结束后，堆顶即第K大的元素
// 可以类比江湖十大强者，每次和最弱的比，如果你比他强，你就杀进了前十，并且再看一下最后排在什么位置
import "container/heap"

type minHeap struct {
    heap    []int
    capcity int
}

func newMinHeap(capcity int) *minHeap {
    return &minHeap{
        heap:    make([]int, 0, capcity),
        capcity: capcity,
    }
}

func (h *minHeap) Len() int { return len(h.heap) }

func (h *minHeap) Less(i, j int) bool { return h.heap[i] < h.heap[j] }

func (h *minHeap) Swap(i, j int) { h.heap[i], h.heap[j] = h.heap[j], h.heap[i] }

func (h *minHeap) Push(n interface{}) {
    nInt := n.(int)
    if len(h.heap) >= h.capcity {
        if h.heap[0] < nInt {
            heap.Pop(h)
            h.heap = append(h.heap, nInt)
        }
    } else {
        h.heap = append(h.heap, nInt)
    }
}

func (h *minHeap) Pop() interface{} {
    n := h.heap[len(h.heap)-1]
    h.heap = h.heap[:len(h.heap)-1]
    return n
}

func findKthLargest(nums []int, k int) int {
    h := newMinHeap(k)
    heap.Init(h)
    for _, num := range nums {
        heap.Push(h, num)
    }
    return heap.Pop(h).(int)
}

• 时间复杂度O(nlogk)

• 空间复杂度O(k)

---

普通数组

53. 最大子数组和

查看代码

func maxSubArray(nums []int) int {
    preMinSum, curSum, maxSum := 0, 0, nums[0]
    for _, n := range nums {
        curSum += n
        maxSum = max(maxSum, curSum-preMinSum)
        preMinSum = min(preMinSum, curSum)
    }
    return maxSum
}

• 时间复杂度O(n)

• 空间复杂度O(1)

56. 合并区间

查看代码

// 1. 按照左端点排序
// 2. 遍历，取一个左边的区间作待merge的区间，
// 遍历只要当前merged的区间的右端点比需要merge区间的左端点大/等，那么merge，
// 否则得到一个最终的merged区间，并取当前区间作为一个新的待merge的区间
import "sort"

func merge(intervals [][]int) (ans [][]int) {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    var ansInterval []int
    for _, interval := range intervals {
        if len(ansInterval) == 0 {
            ansInterval = interval
            continue
        }
        if ansInterval[1] >= interval[0] {
            mergeInterval(ansInterval, interval)
        } else {
            ans = append(ans, ansInterval)
            ansInterval = interval
        }
    }
    ans = append(ans, ansInterval)
    return ans
}

func mergeInterval(src, target []int) {
    if src[0] > target[0] {
        src[0] = target[0]
    }
    if src[1] < target[1] {
        src[1] = target[1]
    }
}

• 时间复杂度O(nlogn)

• 空间复杂度O(logn) 排序占用的

---

链表

106. 相交链表

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA, lenB := getListNodeLen(headA), getListNodeLen(headB)
    if lenA < lenB {
        lenA, lenB = lenB, lenA
        headA, headB = headB, headA
    }
    for i := 0; i < lenA - lenB; i++ {
        headA = headA.Next
    }
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }
    return headA
}

func getListNodeLen(node *ListNode) int {
    if node == nil {
        return 0
    }
    return getListNodeLen(node.Next) + 1
}

• 时间复杂度O(n+m)

• 空间复杂度O(1)

206. 反转链表

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    sentinelNode := &ListNode{}
    
    for head != nil {
        curNeedInsertNode := head
        head = head.Next
        curNeedInsertNode.Next = sentinelNode.Next
        sentinelNode.Next = curNeedInsertNode
    }

    return sentinelNode.Next
}

• 时间复杂度O(n)

• 空间复杂度O(1)

234. 回文链表

查看输出

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    var checkReversedListNodeFunc func (reversedNode *ListNode) bool
    checkReversedListNodeFunc = func (reversedNode *ListNode) bool {
        if reversedNode == nil {
            return true
        }
        if checkReversedListNodeFunc(reversedNode.Next) == false {
            return false
        }
        if head.Val != reversedNode.Val {
            return false
        }
        head = head.Next
        return true
    }
    return checkReversedListNodeFunc(head)
}

• 时间复杂度O(n)

• 空间复杂度O(n) 递归调用栈占用

141. 环形链表

查看代码

这种方法，栈空间O(n)，后面想想别的办法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    fastPtr, slowPtr := head.Next, head
    for fastPtr != slowPtr {
        if fastPtr == nil || fastPtr.Next == nil {
            return false
        }
        fastPtr = fastPtr.Next.Next
        slowPtr = slowPtr.Next
    }
    return true
}

• 时间复杂度O(n)

• 空间复杂度O(1)

142. 环形链表 II

查看代码

哈希表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    mark := make(map[*ListNode]struct{})
    for ; head != nil ; head = head.Next {
        if _, ok := mark[head]; ok {
            return head
        } else {
            mark[head] = struct{}{}
        }
    }
    return nil
}

• 时间复杂度O(n)
• 空间复杂度O(1)

快慢指针

懒得记了，具体看leetcode题解

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    fast, slow := head.Next, head
    for fast != slow {
    if fast == nil || fast.Next == nil {
        return nil
    }
    fast = fast.Next.Next
    slow = slow.Next
    }
    slow = slow.Next
    ptr := head
    for ptr != slow {
    ptr = ptr.Next
    slow = slow.Next
    }
    return ptr
}

• 时间复杂度O(n)
• 空间复杂度O(1)

21. 合并两个有序链表

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    sentinelNode := &ListNode{}
    curMergedNode := sentinelNode

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            curMergedNode.Next = list1
            list1 = list1.Next
        } else {
            curMergedNode.Next = list2
            list2 = list2.Next
        }
        curMergedNode = curMergedNode.Next
    }

    switch {
    case list1 != nil:
        curMergedNode.Next = list1
    case list2 != nil:
        curMergedNode.Next = list2
    }

    return sentinelNode.Next
}

• 时间复杂度O(n + m)

• 空间复杂度O(1)

146. LRU 缓存

查看代码

type node struct {
    key    int
    val    int
    pre    *node
    next *node
}

// LRU链表，头尾两个哨兵（方便减少边界判断）
// 最新的是tear.pre，最旧的是head.next
// map用来快速查找
// 采用链表是因为插入操作多，方便维护LRU淘汰队列
// 注意：查找key和更新key 均算一次访问，需要更新淘汰队列
type LRUCache struct {
    maxCapacity int
    mapToNode     map[int]*node
    head        *node 
    tear        *node
}

func Constructor(capacity int) LRUCache {
    head := &node{}
    tear := &node{}
    head.next = tear
    tear.pre = head
    return LRUCache{
        maxCapacity: capacity,
        mapToNode:     make(map[int]*node, capacity),
        head:        head,
        tear:        tear,
    }
}

func (this *LRUCache) Get(key int) int {
    node, ok := this.mapToNode[key]
    if !ok {
        return -1
    }
    this.moveNodeToTear(node) // 维护淘汰队列
    return node.val
}

func (this *LRUCache) Put(key int, value int) {
    // 命中：更新目标的值 且 维护淘汰队列
    if node, ok := this.mapToNode[key]; ok {
        node.val = value
        this.moveNodeToTear(node)
        return
    }
    // 插入新的节点
    newNode := &node{ key: key, val: value }
    this.mapToNode[key] = newNode
    this.insertNodeToTear(newNode)
    // 按需淘汰最旧的节点
    this.deleteOldestNode()
}

func (this *LRUCache) moveNodeToTear(node *node) {
    // 取出节点 并 插入末尾
    preNode, nextNode := node.pre, node.next
    preNode.next = nextNode
    nextNode.pre = preNode
    this.insertNodeToTear(node)
}

func (this *LRUCache) insertNodeToTear(node *node) {
    node.next = this.tear
    node.pre = this.tear.pre
    this.tear.pre.next = node
    this.tear.pre = node
}

func (this *LRUCache) deleteOldestNode() {
    if this.len() == 0 || this.len() <= this.maxCapacity {
        return
    }
    oldestNode := this.head.next
    this.head.next.next.pre = this.head
    this.head.next = this.head.next.next
    delete(this.mapToNode, oldestNode.key)
}

func (this *LRUCache) len() int {
    return len(this.mapToNode)
}

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

• 时间复杂度O(1)
  • 查找O(1): 查找O(1) + 维护淘汰队列O(1)
  • 插入O(1): 直接命中O(1) + 维护淘汰队列O(1)，未命中时插入O(1)且淘汰O(1).
• 空间复杂度O(n)

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

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    head0 := &ListNode{Next: head}
    traverseAnsDelete(head0, n)
    return head0.Next
}

func traverseAnsDelete(node *ListNode, target int) int {
    if node == nil {
        return 0
    }
    cntReverse := traverseAnsDelete(node.Next, target)
    if cntReverse+1 == target+1 { // 是需要删除节点的前一个（cntReverse是从0开始算的，所以要+1）
        node.Next = node.Next.Next
    }
    return cntReverse + 1
}

• 时间复杂度O(n)

• 空间复杂度O(n)

2. 两数相加

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 整体上不难，主要是处理进位边界情况比较多
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    l1Head := &ListNode{Next: l1}
    preL1 := l1Head
    overflow := false
    for l1 != nil && l2 != nil {
        l1.Val += l2.Val
        if overflow {
            l1.Val += 1
        }
        if l1.Val >= 10 {
            l1.Val %= 10
            overflow = true
        } else {
            overflow = false
        }
        preL1 = l1
        l1 = l1.Next
        l2 = l2.Next
    }
    // l1指针回到末尾的前一位，并继续处理后续部分
    if l1 == nil {
        preL1.Next = l2
    }
    l1 = preL1
    if overflow {
        for l1.Next != nil {
            l1.Next.Val += 1
            if l1.Next.Val >= 10 {
                l1.Next.Val %= 10
            } else {
                overflow = false
                break
            }
            l1 = l1.Next
        }
        if overflow && l1.Next == nil {
            l1.Next = &ListNode{Val: 1}
        }
    }
    return l1Head.Next
}

• 时间复杂度O(n)

• 空间复杂度O(1)

---

二叉树

94. 二叉树的中序遍历

查看代码

递归：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
    var inorderInternalFunc func(node *TreeNode)
    inorderInternalFunc = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorderInternalFunc(node.Left)
        ans = append(ans, node.Val)
        inorderInternalFunc(node.Right)
    }
    inorderInternalFunc(root)
    return ans
}

• 时间复杂度O(n)

• 空间复杂度O(n)

迭代：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
    nodeStack := make([]*TreeNode, 0)
    for root != nil || len(nodeStack) > 0 {
        for root != nil {
            nodeStack = append(nodeStack, root)
            root = root.Left
        }
        root = nodeStack[len(nodeStack)-1]
        nodeStack = nodeStack[:len(nodeStack)-1]
        ans = append(ans, root.Val)
        root = root.Right
    }
    return ans
}

• 时间复杂度O(n)

• 空间复杂度O(n)

104. 二叉树最大深度

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

• 时间复杂度O(n)

• 空间复杂度O(n)

226. 翻转二叉树

查看代码

/**
 * 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
    }
    invertTree(root.Left)
    invertTree(root.Right)
    root.Left, root.Right = root.Right, root.Left
    return root
}

• 时间复杂度O(n)

• 空间复杂度O(n)

543. 二叉树的直径

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 每个节点的左右子树的最大长度之和，最大的就是直径
func diameterOfBinaryTree(root *TreeNode) (ans int) {
    var maxDepth func(root *TreeNode) int
    maxDepth = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        leftTreeDepth := maxDepth(root.Left)
        rightTreeDepth := maxDepth(root.Right)
        ans = max(ans, leftTreeDepth + rightTreeDepth)
        return max(leftTreeDepth, rightTreeDepth) + 1
    }
    maxDepth(root)
    return ans
}

• 时间复杂度O(n)

• 空间复杂度O(n)

102. 二叉树的层序遍历

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) (ans [][]int) {
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) != 0 {
        curLevelLen := len(queue)
        curLevelAns := make([]int, 0, curLevelLen)
        for i := 0; i < curLevelLen; i++ {
            node := queue[0]
            queue = queue[1:]
            if node != nil {
                curLevelAns = append(curLevelAns, node.Val)
                queue = append(queue, node.Left)
                queue = append(queue, node.Right)
            }
        }
        if len(curLevelAns) != 0 {
            ans = append(ans, curLevelAns)
        }
    }
    return ans
}

• 时间复杂度O(n)

• 空间复杂度O(1)

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

查看代码

/**
 * 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 || root == p || root == q {
        return root
    }
    // 使用是否为nil，来间接表示是否找到目标节点, 并且间接返回了最近公共祖先
    leftTarget := lowestCommonAncestor(root.Left, p, q)
    rightTarget := lowestCommonAncestor(root.Right, p, q)
    switch {
    case leftTarget != nil && rightTarget != nil: // 表示是最近公共祖先
        return root
    case leftTarget != nil && rightTarget == nil: // 至少有一个目标节点（最近公共祖先也属于这种情况）
        return leftTarget
    case leftTarget == nil && rightTarget != nil: // 至少有一个目标节点（最近公共祖先也属于这种情况）
        return rightTarget
    default: // 一个都没有命中
        return nil
    }
}

• 时间复杂度O(n)

• 空间复杂度O(n)

101. 对称二叉树

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    return traverse(root, root)
}

func traverse(node1, node2 *TreeNode) bool {
    if node1 == nil && node2 == nil {
        return true
    }
    if node1 == nil || node2 == nil {
        return false
    }
    if node1.Val != node2.Val ||
        !traverse(node1.Left, node2.Right) ||
        !traverse(node1.Right, node2.Left) {
        return false
    }
    return true
}

• 时间复杂度O(n)

• 空间复杂度O(n)

---

图论

200. 岛屿数量

同类题目 547. 省份数量 解法一摸一样

查看代码

var dirs = [...]struct{ i, j int }{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}

// 复用grid数组来打标记，'2'：表示已经访问过
func numIslands(grid [][]byte) (ans int) {
    m, n := len(grid), len(grid[0])
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                ans++
                dfs(grid, i, j, m, n)
            }
        }
    }
    return ans
}

func dfs(grid [][]byte, i, j, m, n int) {
    grid[i][j] = '2'
    for k := 0 ; k < 4; k++ {
        tmpI := i + dirs[k].i
        tmpJ := j + dirs[k].j
        if !isOverflow(tmpI, tmpJ, m, n) && grid[tmpI][tmpJ] == '1' {
            dfs(grid, tmpI, tmpJ, m, n)
        }
    }
}

func isOverflow(i, j, m, n int) bool {
    return i < 0 || j < 0 || i >= m || j >= n
}

• 时间复杂度O(mn)

• 空间复杂度O(1)

994. 腐烂的橘子

查看代码

var dirs = [...]struct{ i, j int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}

type originPosition struct {
    i, j int
}

func orangesRotting(grid [][]int) (ans int) {
    m, n := len(grid), len(grid[0])
    queue := make([]originPosition, 0)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 2 {
                queue = append(queue, originPosition{ i, j })
            }
        }
    }
    for len(queue) != 0 {
        curLen := len(queue)
        for k := 0; k < curLen; k++ {
            curRottenOrigin := queue[0]
            queue = queue[1:]
            for l := 0; l < 4; l++ {
                tmpI := curRottenOrigin.i + dirs[l].i
                tmpJ := curRottenOrigin.j + dirs[l].j
                if !isOverflow(tmpI, tmpJ, m, n) && grid[tmpI][tmpJ] == 1 {
                    grid[tmpI][tmpJ] = 2
                    queue = append(queue, originPosition{ tmpI, tmpJ })
                }
            }
        }
        ans++
    }

    if haveRemainOrigins(grid, m, n) {
        return -1
    }
    return max(0, ans - 1) // 1. 扣掉第一轮 2. 不小于0
}

func isOverflow(i, j, m, n int) bool {
    return i < 0 || j < 0 || i >= m || j >= n
}

func haveRemainOrigins(grid [][]int, m, n int) bool {
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                return true
            }
        }
    }
    return false
}

• 时间复杂度O(mn)

• 空间复杂度O(mn)

---

回溯

知识回顾：golang内置函数 - copy

copy 是 Go 语言内置的用于切片间数据拷贝的函数，它只能作用于切片（slice），不能直接用于数组。其函数签名如下：

func copy(dst []Type, src []Type) int

• 参数：
  • dst：目标切片（接收拷贝数据的切片）；
  • src：源切片（提供拷贝数据的切片）。
• 返回值：返回实际拷贝的元素个数，等于 len(dst) 和 len(src) 中的较小值。

46. 全排列

查看代码

使用回溯来进行枚举

func permute(nums []int) (ans [][]int) {
    mark := make(map[int]struct{}, len(nums))
    curAns := make([]int, 0, len(nums))
    traverse(nums, 0, curAns, &ans, mark)
    return ans
}

func traverse(nums []int, level int, curAns []int, ans *[][]int, mark map[int]struct{}) {
    if len(nums) == level {
        temp := make([]int, len(curAns))
        copy(temp, curAns)
        *ans = append(*ans, temp)
        return
    }
    for _, n := range nums {
        if _, ok := mark[n]; !ok {
            mark[n] = struct{}{}
            traverse(nums, level+1, append(curAns, n), ans, mark)
            delete(mark, n)
        }
    }
}

• 时间复杂度O(n!)

• 空间复杂度O(n)

22. 括号生成

查看代码

解法类似 46. 全排列 ，都是用回溯来进行枚举

func generateParenthesis(n int) (ans []string) {
    curAns := make([]byte, 0, 2*n)
    generate(n, 0, 0, 0, curAns, &ans)
    return ans
}

func generate(n, level, leftCnt, rightCnt int, curAns []byte, ans *[]string) {
    if level == 2*n {
    *ans = append(*ans, string(curAns))
    return
    }
    if leftCnt < n {
    generate(n, level+1, leftCnt+1, rightCnt, append(curAns, '('), ans)
    }
    if rightCnt < n && rightCnt < leftCnt { // 右括号小于左括号才允许当前放入右括号
    generate(n, level+1, leftCnt, rightCnt+1, append(curAns, ')'), ans)
    }
}

78. 子集

查看代码

同样是使用回溯来进行枚举

func subsets(nums []int) (ans [][]int) {
    curAns := make([]int, 0, len(nums))
    findSubSets(nums, 0, curAns, &ans)
    return ans
}

func findSubSets(nums []int, level int, curAns []int, ans *[][]int) {
    if level == len(nums) {
        copyCurAns := make([]int, len(curAns))
        copy(copyCurAns, curAns)
        *ans = append(*ans, copyCurAns)
        return
    }
    findSubSets(nums, level+1, append(curAns, nums[level]), ans)
    findSubSets(nums, level+1, curAns, ans)
}

• 时间复杂度O(2^n)

• 空间复杂度O(n)

---

二分查找

35. 搜索插入位置

查看代码

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2 // 防止int溢出
        switch {
        case nums[mid] == target:
            return mid
        case nums[mid] > target:
            right = mid - 1
        case nums[mid] < target:
            left = mid + 1
        }
    }
    return left
}

• 时间复杂度O(logn)

• 空间复杂度O(1)

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

查看代码

// 问题实际上是二分查找的特殊情况，找到目标元素的初始位置和末尾位置
func searchRange(nums []int, target int) (ans []int) {
    if len(nums) == 0 {
        return append(ans, -1, -1)
    }
    return append(ans, findFirstPosition(nums, target), findLastPosition(nums, target))
}

func findFirstPosition(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        switch {
        case nums[mid] < target:
            left = mid + 1
        case nums[mid] == target:
            right = mid // 关键
        case nums[mid] > target:
            right = mid - 1
        }
    }
    if nums[left] == target {
        return left
    }
    return -1
}

func findLastPosition(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left+1)/2 // 注意这里+1来取顶，不然会死循环，具体原因可以打印出来跑一下看看
        switch {
        case nums[mid] < target:
            left = mid + 1
        case nums[mid] == target:
            left = mid // 关键
        case nums[mid] > target:
            right = mid - 1
        }
    }
    if nums[right] == target {
        return right
    }
    return -1
}

• 时间复杂度O(logn)

• 空间复杂度O(1)

---

栈

20. 有效的括号

查看代码

func isValid(s string) bool {
    stack := make([]byte, 0)
    strBytes := []byte(s)
    matchMap := map[byte]byte{
        ')': '(',
        '}': '{',
        ']': '[',
    }
    for _, b := range strBytes {
        switch b {
        case '(', '{', '[':
            stack = append(stack, b)
        case ')', '}', ']':
            if len(stack) == 0 || stack[len(stack)-1] != matchMap[b] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    if len(stack) == 0 {
        return true
    }
    return false
}

• 时间复杂度O(n)

• 空间复杂度O(n)

155. 最小栈

查看代码

最小栈的辅助栈解法核心思路可简单总结为：

双栈配合，主栈存全量元素做常规操作，辅助栈仅存「各阶段最小值」，与主栈同步出栈最小值，实现 O (1) 取最小。

具体三步核心逻辑：

1. 入栈：主栈必压入新元素；若辅助栈空，或新元素≤辅助栈顶（含重复最小值），辅助栈同步压入。
2. 出栈：主栈必弹出栈顶；若弹出值等于辅助栈顶（即弹出的是当前最小值），辅助栈同步弹出。
3. 查最小 / 取栈顶：栈顶直接取主栈顶，最小值直接取辅助栈顶，均为 O (1) 操作。

辅助栈仅与主栈的「最小值节点」绑定，无多余元素，因此不会出现出栈元素在辅助栈中非栈顶的情况，全程保证辅助栈顶是当前主栈的最小值。

import "math"

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    s := MinStack{}
    s.minStack = append(s.minStack, math.MaxInt)
    return s
}

func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    if val <= this.minStack[len(this.minStack)-1] {
        this.minStack = append(this.minStack, val)
    }
}

func (this *MinStack) Pop() {
    topVal := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if topVal == this.minStack[len(this.minStack)-1] {
        this.minStack = this.minStack[:len(this.minStack)-1]
    }
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

• 时间复杂度
  • Push: O(1)
  • Pop: O(1)
  • Top: O(1)
  • GetMin: O(1)
• 空间复杂度O(n)

394. 字符串解码

查看输出

观察后发现，这个逻辑和栈操作非常类似，所以采用栈来解决

吐槽：这个题目出的太恶习，很多边界条件

func decodeString(str string) (ans string) {
    strStack := make([]string, 0)
    repeatCntStack := make([]int, 0)
    for i := 0; i < len(str); {
        if isNumber(str[i]) {
            numberLeft, numberRight := i, i
            for ; i < len(str) && isNumber(str[i]); i++ {
                numberRight++
            }
            n := convertToNumber(str[numberLeft:numberRight])
            repeatCntStack = append(repeatCntStack, n)
            continue
        }
        switch str[i] {
        case '[':
            i += 1
            strLeft, strRight := i, i
            for ; i < len(str) && !isNumber(str[i]) && str[i] != '[' && str[i] != ']'; i++ {
                strRight++
            }
            strStack = append(strStack, str[strLeft:strRight])
        case ']':
            i += 1
            pendingRepeatStr := strStack[len(strStack)-1]
            strStack = strStack[:len(strStack)-1]
            pendingRepeat := repeatCntStack[len(repeatCntStack)-1]
            repeatCntStack = repeatCntStack[:len(repeatCntStack)-1]
            repeatedStr := ""
            for j := 0; j < pendingRepeat; j++ {
                repeatedStr += pendingRepeatStr
            }
            if len(strStack) == 0 {
                ans += repeatedStr
            } else {
                strStack[len(strStack)-1] += repeatedStr
            }
        default:
            strLeft, strRight := i, i
            for ; i < len(str) && !isNumber(str[i]) && str[i] != '[' && str[i] != ']'; i++ {
                strRight++
            }
            if len(strStack) == 0 {
                ans += str[strLeft:strRight]
            } else {
                strStack[len(strStack)-1] += str[strLeft:strRight]
            }
        }
    }
    return ans
}

func isNumber(c byte) bool {
    return c >= '0' && c <= '9'
}

func convertToNumber(str string) int {
    var n int
    for _, s := range str {
        n = n*10 + int(s-'0')
    }
    return n
}

• 时间复杂度O(n)

• 空间复杂度O(n)

---

贪心算法

121. 买卖股票的最佳时机

查看代码

// 记录目前最低的价格，以及目前最高的利润
func maxProfit(prices []int) int {
    curMinPrice, curMaxProfit := prices[0], 0
    for _, price := range prices {
        curMaxProfit = max(curMaxProfit, price - curMinPrice)
        curMinPrice = min(curMinPrice, price)
    }
    return curMaxProfit
}

• 时间复杂度O(n)

• 空间复杂度O(1)

---

技巧

135. 只出现一次的数字

查看代码

func singleNumber(nums []int) (ans int) {
    for _, num := range nums {
        ans ^= num
    }
    return ans
}

• 时间复杂度O(n)

• 空间复杂度O(1)

---

动态规划

70. 爬楼梯

查看代码

func climbStairs(n int) int {
    a, b := 1, 2
    for i := 1; i < n; i++ {
        tmp := a
        a = b
        b = tmp + a
    }
    return a
}

• 时间复杂度O(n)

• 空间复杂度O(1)

118. 杨辉三角

查看代码

func generate(numRows int) [][]int {
    ans := make([][]int, 0, numRows)
    ans = append(ans, []int{1})
    ans = append(ans, []int{1, 1})
    if numRows <= 2 {
        return ans[:numRows]
    }
    for curLevel := 3; curLevel <= numRows; curLevel++ {
        curLevelList := make([]int, curLevel)
        lastLevelList := ans[curLevel-2]
        curLevelList[0], curLevelList[curLevel-1] = 1, 1
        for i := 1; i < curLevel - 1; i++ {
            curLevelList[i] = lastLevelList[i-1] + lastLevelList[i]
        }
        ans = append(ans, curLevelList)
    }
    return ans
}

---

5. 最长回文子串

查看代码

只实现了一个中心扩散解法，有空再做一下动态规划解法

func longestPalindrome(s string) string {
    left, right := 0, 0
    for i := 0; i < len(s); i++ {
        subLeft1, subRight1 := expandAroundCenter(s, i, i)
        subLeft2, subRight2 := expandAroundCenter(s, i, i+1)
        if subRight1-subLeft1 > right-left {
            left, right = subLeft1, subRight1
        }
        if subRight2-subLeft2 > right-left {
            left, right = subLeft2, subRight2
        }
    }
    return s[left : right+1]
}

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

---

others

633. 平方数之和

查看代码

import "math"

func judgeSquareSum(c int) bool {
    sqrtC := int(math.Sqrt(float64(c)))
    for i := 0; i <= sqrtC; i++ {
        otherExceptedPart := int(math.Sqrt(float64(c - i * i)))
        if (i * i + otherExceptedPart * otherExceptedPart) == c {
            return true
        }
    }
    return false
}

• 时间复杂度O (√n)

• 空间复杂度O(1)

547. 省份数量

同类题目 200. 岛屿数量 解法一摸一样

查看代码

func findCircleNum(isConnected [][]int) (ans int) {
    markedMap := make(map[int]struct{}, len(isConnected))
    for i := 0; i < len(isConnected); i++ {
        if _, ok := markedMap[i]; !ok {
            ans++
            dfs(i, markedMap, isConnected)
        }
    }
    return ans
}

func dfs(curCity int, markedMap map[int]struct{}, isConnected [][]int) {
    markedMap[curCity] = struct{}{}
    for i := 0; i < len(isConnected); i++ {
        if _, ok := markedMap[i]; !ok && isConnected[curCity][i] == 1 {
            dfs(i, markedMap, isConnected)
        }
    }
}

• 时间复杂度O(n^2)

• 空间复杂度O(1)

437. 路径总和 III

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 记录前缀和
func pathSum(root *TreeNode, targetSum int) int {
    curSum, ans := 0, 0
    preSumMap := map[int]int{0:1} // 应对路径和从root开始等于targetSum的情况
    traverse(root, targetSum, preSumMap, &curSum, &ans)
    return ans
}

func traverse(node *TreeNode, targetSum int, preSumMap map[int]int, curSum, ans *int) {
    if node == nil {
        return
    }
    *curSum += node.Val
    if val := preSumMap[*curSum-targetSum]; val > 0 {
        *ans += val
    }
    preSumMap[*curSum]++
    traverse(node.Left, targetSum, preSumMap, curSum, ans)
    traverse(node.Right, targetSum, preSumMap, curSum, ans)
    preSumMap[*curSum]--
    *curSum -= node.Val
}

• 时间复杂度O(n)
• 空间复杂度O(n)

ps: 例2数组[5,4,8,11,null,13,4,7,2,null,null,5,1]表示的二叉树为：这是用层序遍历的方式来表示

        5
    /     \
     4     8
    /     / \
 11    13    4
/    \    /    \
 7    2 5     1

912. 排序数组 手撕快排

查看代码

func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums)-1)
    return nums
}

func quickSort(nums []int, left, right int) {
    if left < right {
        pivot := partition(nums, left, right)
        quickSort(nums, left, pivot-1)
        quickSort(nums, pivot+1, right)
    }
}

func partition(nums []int, left, right int) int {
    pivotVal := nums[left]
    for left < right {
        for left < right && pivotVal <= nums[right] {
            right--
        }
        nums[left] = nums[right]
        for left < right && pivotVal >= nums[left] {
            left++
        }
        nums[right] = nums[left]
    }
    nums[left] = pivotVal
    return left
}

• 时间复杂度O(nlogn) - 平均
• 空间复杂度O(logn) - 平均

---

方法总结

前缀和

场景：求子串的和

原因：你知道当前的和，但是又需要扣掉前面部分的和

53. 最大子数组和

437. 路径总和 III