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)
}

---

图论

200. 岛屿数量

查看代码

var (
    dirI = [...]int{-1, 0, 1, 0}
    dirJ = [...]int{0, 1, 0, -1}
)

func numIslands(grid [][]byte) int {
    n, m := len(grid), len(grid[0])
    cnt := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == '1' {
                cnt++
                dfs(i, j, n, m, grid)
            }
        }
    }
    return cnt
}

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

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

994. 腐烂的橘子

查看代码

package main

type Position struct {
    i, j int
}

var (
    dirI = [...]int{-1, 0, 1, 0}
    dirJ = [...]int{0, 1, 0, -1}
)

func orangesRotting(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    queue := []Position{}
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 2 {
                queue = append(queue, Position{i, j})
            }
        }
    }
    if len(queue) == 0 {
        if leftFresh(grid) { return -1 }
        return 0
    }

    cntMin := -1
    for len(queue) > 0 {
        curNumOfRot := len(queue)
        for i := 0; i < curNumOfRot; i++ {
            spread(queue[0], grid, &queue)
            queue = queue[1:]
        }
        cntMin++
    }
    if leftFresh(grid) { return -1 }
    return cntMin
}

func spread(centerOrange Position, grid [][]int, originQueue *[]Position) {
    n, m := len(grid), len(grid[0])
    for k := 0; k < 4; k++ {
        tmpI := centerOrange.i + dirI[k]
        tmpJ := centerOrange.j + dirJ[k]
        if !isOver(tmpI, tmpJ, n, m) && grid[tmpI][tmpJ] == 1 {
            grid[tmpI][tmpJ] = 2
            *originQueue = append(*originQueue, Position{tmpI, tmpJ})
        }
    }
}

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

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

---

二分查找

35. 搜索插入位置

查看代码

func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

---

栈

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
}

---

135. 只出现一次的数字

查看代码

func singleNumber(nums []int) int {
    ans := nums[0]
    for i := 1; i < len(nums); i++ {
        ans ^= nums[i]
    }
    return ans;
}

---

动态规划

70. 爬楼梯

查看代码

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

118. 杨辉三角

查看代码

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

---

others

633. 平方数之和

查看代码

import "math"

func judgeSquareSum(c int) bool {
    for a := 0; a <= int(math.Sqrt(float64(c))); a++ {
        partA2 := a * a
        partB2 := c - partA2
        b := int(math.Sqrt(float64(partB2)))
        if b * b == partB2 {
            return true
        }
    }
    return false
}

547. 省份数量

查看代码

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

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

437. 路径总和 III

查看代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var (
    preSum = []int{0}
    curSum = 0
)

func pathSum(root *TreeNode, targetSum int) int {
    ans := 0
    pathSumPart(root, targetSum, 1, &ans)
    return ans
}

func pathSumPart(root *TreeNode, targetSum, depth int, ans *int) {
    if root == nil {
        return
    }
    curSum += root.Val
    if len(preSum) <= depth {
        preSum = append(preSum, curSum)
    } else {
        preSum[depth] = curSum
    }
    for i := 0; i < depth; i++ {
        if (curSum - preSum[i]) == targetSum {
            *ans++
        }
    }
    pathSumPart(root.Left, targetSum, depth+1, ans)
    pathSumPart(root.Right, targetSum, depth+1, ans)
    curSum -= root.Val
}

优化：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var (
    preSum = make(map[int]int)
    curSum = 0
)

func pathSum(root *TreeNode, targetSum int) int {
    ans := 0
    preSum[0] = 1
    pathSumPart(root, targetSum, &ans)
    return ans
}

func pathSumPart(root *TreeNode, targetSum int, ans *int) {
    if root == nil {
        return
    }
    curSum += root.Val
    if val, ok := preSum[curSum-targetSum]; ok {
        *ans += val
    }
    preSum[curSum]++
    pathSumPart(root.Left, targetSum, ans)
    pathSumPart(root.Right, targetSum, ans)
    preSum[curSum]--
    curSum -= root.Val
}