leetcode hot 100 刷题（go语言版）

入口

Cookbook

哈希

1. 两数之和

查看代码

顺序扫描数组，对每一个元素，在 map 中找能组合给定值的另一半数字，如果找到了，直接返回 2 个数字的下标即可。如果找不到，就把这个数字存入 map 中，等待扫到“另一半”数字的时候，再取出来返回结果。

func twoSum(nums []int, target int) []int {
    visited := make(map[int]int)    // map[val]index
    ans := make([]int, 2)

    for i := 0; i < len(nums); i++ {
        anotherPart := target - nums[i]
        anotherPartIndex, ok := visited[anotherPart]
        if ok {
            ans[0] = anotherPartIndex
            ans[1] = i
            break
        }
        visited[nums[i]] = i    // 将访问过的放入map中
    }

    return ans
}

49. 字母异位词分组

查看代码

import (
    "sort"
)

func groupAnagrams(strs []string) [][]string {
    collectAnagrams := make(map[string][]string)
    ans := [][]string{}

    for _, str := range strs {
        sortedStr := sortRune([]rune(str))
        sort.Sort(sortedStr)
        anagrams := collectAnagrams[string(sortedStr)]
        anagrams = append(anagrams, str)
        collectAnagrams[string(sortedStr)] = anagrams
    }

    for _, val := range collectAnagrams {
        ans = append(ans, val)
    }

    return ans
}

type sortRune []rune 

func (s sortRune) Less (i, j int) bool {
    return s[i] < s[j]
}

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

func (s sortRune) Len() int {
    return len(s)
}

---

双指针

283. 移动零

查看代码

1. 初始化 lastNonZeroIndex 为 0，用来记录最后一个非零元素应该放置的位置。

2. 遍历数组 nums，如果发现一个非零元素，就将它移动到 lastNonZeroIndex 的位置，同时 lastNonZeroIndex 增加 1。

3. 遍历结束后，从 lastNonZeroIndex 开始，将数组剩余的位置全部填充为零。

思想就是，前面为全非0数组，lastNonZeroIndex用来统计全非0数组的长度，后面为全0数组

func moveZeroes(nums []int)  {
    lastNonZeroIndex := 0		// 理解为长度
  
    for i := 0; i < len(nums); i++ {
      if nums[i] != 0 {
        nums[lastNonZeroIndex] = nums[i]
        lastNonZeroIndex++
      }
    }
  
    for i := lastNonZeroIndex; i < len(nums); i++ {
        nums[i] = 0;
    }
}

---

滑动窗口

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

查看代码

func lengthOfLongestSubstring(s string) int {
    chars := []rune(s)
    left, right, curLen, maxLen := 0, 0, 0, 0
    marked := make(map[rune]bool)

    for right < len(chars) {
        if _, ok := marked[chars[right]]; !ok {
            marked[chars[right]] = true
            curLen++
            maxLen = max(maxLen, curLen)
            right++
        } else {
            delete(marked, chars[left])
            left++
            curLen--
        }
    }

    return maxLen
}

---

链表

106. 相交链表

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    len1, len2 := getListNodeLen(headA), getListNodeLen(headB)
    if len1 < len2 {                // 保证headA不比headB短
        len1, len2 = len2, len1
        headA, headB = headB, headA
    }
    for i := 0; i < len1 - len2; i++ {
        headA = headA.Next
    }
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }

    return headA
}

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

206. 反转链表

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    // 头插法：建立哨兵节点，把每一个节点都插入哨兵节点后面
    head0 := new(ListNode)
    head0.Next = nil
    
    for head != nil {
        curNode := head
        head = head.Next
        curNode.Next = head0.Next
        head0.Next = curNode
    }

    return head0.Next
}

234. 回文链表

查看输出

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 已知可以通过回溯来逆序打印链表，
// 那我们在逆序的时候和正序判断不就好了吗
func isPalindrome(head *ListNode) bool {
    p := head
    return isPalindromePart(head, &p)
}

func isPalindromePart(reverse *ListNode, normal **ListNode) bool {
    if reverse == nil {
        return true
    }
    if isPalindromePart(reverse.Next, normal) == false {
        return false
    }
    if reverse.Val != (*normal).Val {
        return false
    }
    *normal = (*normal).Next  // 如果相同表示继续判断
    return true
}

141. 环形链表

查看代码

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 快慢指针
func hasCycle(head *ListNode) bool {
    if head == nil { return false }
    slow, fast := head, head.Next
    for fast != nil {
        if slow == fast { return true }
        if slow = slow.Next; slow == nil { return false }
        if fast = fast.Next; fast == nil { return false }
        if fast = fast.Next; fast == nil { return false }
    }
    return false
}

21. 合并两个有序链表

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    head0 := new(ListNode)
    p := head0
    
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            p.Next = list1
            list1 = list1.Next
        } else {
            p.Next = list2
            list2 = list2.Next
        }
        p = p.Next
    }
    p.Next = nil    // 保证后面一定指空

    if list1 != nil {
        p.Next = list1
    }
    if list2 != nil {
        p.Next = list2
    }

    return head0.Next
}

---

二叉树

94. 二叉树的中序遍历

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    ans := make([]int, 0)
    inorder(root, &ans)
    return ans
}

func inorder(root *TreeNode, ans *[]int) {
    if root == nil {
        return
    }
    inorder(root.Left, ans)
    *ans = append(*ans, root.Val)
    inorder(root.Right, ans)
}

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
    }
    // max min函数是在1.21版本后才有的内置函数
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

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

543. 二叉树的直径

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 每个节点的左右子树的最大长度之和，最大的就是直径
func diameterOfBinaryTree(root *TreeNode) int {
    diameter := 0
    diameterOfBinaryTreePart(root, 0, &diameter)
    return diameter
}

func diameterOfBinaryTreePart(root *TreeNode, depth int, diameter *int) int {
    if root == nil { return depth - 1}
    leftChildLen := diameterOfBinaryTreePart(root.Left, depth + 1, diameter) - depth
    rightChildLen := diameterOfBinaryTreePart(root.Right, depth + 1, diameter) - depth
    *diameter = max(*diameter, leftChildLen + rightChildLen)
    return depth + max(leftChildLen, rightChildLen)
}

---

栈

20. 有效的括号

查看代码

func isValid(s string) bool {
    stack := make([]rune, 0)

    for _, char := range s {
        if char == '(' || char == '[' || char == '{' {
            stack = append(stack, char)
        } else {
            if len(stack) == 0 {
                return false
            }
            top := stack[len(stack) - 1]    // 取出栈顶
            if char == ')' && top != '(' || 
               char == ']' && top != '[' ||
               char == '}' && top != '{' {
                return false
            }
            stack = stack[:len(stack) - 1]
        }
    }

    if len(stack) != 0 {
        return false
    }

    return true
}

---

贪心算法

121. 买卖股票的最佳时机

查看代码

// 记录目前最低的价格，以及目前最高的利润
func maxProfit(prices []int) int {
    curMinPrice, curMaxProfit := prices[0], 0

    for _, curPrice := range prices {
        if curProfit := curPrice - curMinPrice; curProfit > curMaxProfit {
            curMaxProfit = curProfit
        }
        if curPrice < curMinPrice {
            curMinPrice = curPrice
        }
    }

    return curMaxProfit
}