LeetCode 刷题笔记

Secriy

算法刷题

发布于：2021年7月15日

次浏览

LeetCode 刷题记录。

1~100

1. Two Sum

最容易想到的方式是使用 Map 存储遍历到的数字，并判断目标数字减去当前数字的结果是否在 Map 中，如过是直接返回。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)    // key: number, value: index
    for k, v := range nums {
        if idx, ok := m[target-v]; ok {
            return []int{k, idx}
        }
        m[v] = k
    }
    return nil
}

2. Add Two Numbers

常规

用 l1 存加法结果，l1 长度小于 l2 时将 l2 后半部分链表接到 l1 末尾。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0 // 进位
    dummy := l1 // 结果
    var pre *ListNode // 指向最后一个结点
    for l1 != nil {
        pre = l1
        if l1.Next == nil && l2 != nil {
            // l2 长度大于 l1，将 l2 链接到 l1 上
            l1.Next = l2.Next
            l2.Next = nil
        }
        if l2 != nil {
            l1.Val += (l2.Val + carry)
        } else {
            l1.Val += carry
        }

        carry = l1.Val/10
        l1.Val %= 10

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

    if carry > 0 {
        pre.Next = &ListNode{Val: carry}
    }

    return dummy
}

3. Longest Substring Without Repeating Characters

滑动窗口（双指针）

func lengthOfLongestSubstring(s string) int {
    res, left, right := 0, 0, 0
    m := make(map[byte]bool, 0)
    for right < len(s) {
        if _, ok := m[s[right]]; !ok {
            m[s[right]] = true
            if right-left+1 > res {
                res = right - left + 1
            }
            right++
        } else {
            delete(m, s[left])
            left++
        }
    }
    return res
}

func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    left, right := 0, 0
    max := 0
    for left < len(s) && right < len(s) {
        // duplicate
        if v, ok := m[s[right]]; ok && v >= left{
            left = v+1
        } else {
            if right-left+1 > max {
                max = right-left+1
            }
        }
        m[s[right]] = right
        right++
    }
    return max
}

7. Reverse Integer

先提出符号，对数字进行循环对 10 取余来得到高一位数字，对地位数字循环乘 10 来进位。

func reverse(x int) int {
    result := 0
    for x != 0 {
        result = result*10 + x%10
        x /= 10
    }
    if bit := result >> 31; bit != 0 && bit != -1 {
        // 判断是否超出范围
        return 0
    }
    return result
}

8. String to Integer (atoi)

func myAtoi(s string) (ret int) {
    i := 0    // 记录位置
    flag := 1 // 标识正负
    for i < len(s) && s[i] == ' ' {
        // 去除前导空格
        i++
    }
    if i < len(s) && s[i] == '-' {
        flag = -1
    }
    if i < len(s) && (s[i] == '+' || s[i] == '-') {
        i++
    }
    for i < len(s) {
        sub := s[i] - '0'
        if sub < 0 || sub >= 10 {
            // 检查是不是数字
            break
        }
        if ret > math.MaxInt32/10 || (ret == math.MaxInt32/10 && sub > 7) {
            // 越界
            if flag > 0 {
                return math.MaxInt32
            } else {
                return math.MinInt32
            }
        }
        ret = ret*10 + int(sub)
        i++
    }
    return ret * flag
}

9. Palindrome Number

翻转数字

按照第七题写法判断翻转过后是否相等。

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    return x == reverse(x)
}

// 翻转数字
func reverse(x int) int {
    res := 0
    for x != 0 {
        res = res*10 + x%10
        x /= 10
    }
    return res
}

简化：

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    tmp := x
    y := 0
    for x != 0 {
        y = y*10 + x%10
        x /= 10
    }
    return tmp == y
}

可以将x的低位反转存入另一个变量中，并将x除以 10，最后判断二者是否相等。

func isPalindrome(x int) bool {
    if x < 0 || (x%10 == 0 && x != 0) {
        return false // x为负数或10的倍数返回false
    }
    num := 0
    for x > num {
        num = num*10 + x%10
        x /= 10
    }
    return x == num || x == num/10
}

转换为字符串

把数字转换为字符串，用双指针各自从左右遍历字符串判断二者对应字符是否相同，直到两个指针重叠。

func isPalindrome(x int) bool {
    str := strconv.FormatInt(int64(x), 10)
    length := len(str)
    for i := 0; 2*i < length-1; i++ {
        if str[i] != str[length-1-i] {
            return false
        }
    }
    return true
}

11. Container With Most Water

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    max := 0
    for left < right {
        capacity, min := 0, 0
        if height[left] < height[right] {
            min = height[left]
            capacity = min * (right - left)
            left++
        } else {
            min = height[right]
            capacity = min * (right - left)
            right--
        }
        if capacity > max {
            max = capacity
        }
    }
    return max
}

13. Roman to Integer

Ideas

最简单粗暴的解法就是使用switch语句判断每一种情况，当遇到能作为前缀的数字时判断后面的数字是否是组合数的情况，如果是则减去多余的值。
仍然是switch判断每一种情况，但首先把其中带有前缀的字符替换为其他字符。

Solutions

Switch

func romanToInt(s string) int {
    result := 0
    for i := 0; i < len(s); i++ {
        switch s[i] {
        case 'I':
            result += 1
            if i+1 != len(s) && (s[i+1] == 'V' || s[i+1] == 'X') {
                result += -2
            }
        case 'V':
            result += 5
        case 'X':
            result += 10
            if i+1 != len(s) && (s[i+1] == 'L' || s[i+1] == 'C') {
                result += -20
            }
        case 'L':
            result += 50
        case 'C':
            result += 100
            if i+1 != len(s) && (s[i+1] == 'D' || s[i+1] == 'M') {
                result += -200
            }
        case 'D':
            result += 500
        case 'M':
            result += 1000
        }
    }
    return result
}

判断前一字符的解法为：

func romanToInt(s string) int {
    result := 0
    for i := 0; i < len(s); i++ {
        switch s[i] {
        case 'I':
            result += 1
        case 'V':
            result += 5
            if i > 0 && s[i-1] == 'I' {
                result -= 2
            }
        case 'X':
            result += 10
            if i > 0 && s[i-1] == 'I' {
                result -= 2
            }
        case 'L':
            result += 50
            if i > 0 && s[i-1] == 'X' {
                result -= 20
            }
        case 'C':
            result += 100
            if i > 0 && s[i-1] == 'X' {
                result -= 20
            }
        case 'D':
            result += 500
            if i > 0 && s[i-1] == 'C' {
                result -= 200
            }
        case 'M':
            result += 1000
            if i > 0 && s[i-1] == 'C' {
                result -= 200
            }
        }
    }
    return result
}

Replace

func romanToInt(s string) int {
    s = strings.Replace(s, "IV", "1", -1)
    s = strings.Replace(s, "IX", "2", -1)
    s = strings.Replace(s, "XL", "3", -1)
    s = strings.Replace(s, "XC", "4", -1)
    s = strings.Replace(s, "CD", "5", -1)
    s = strings.Replace(s, "CM", "6", -1)
    result := 0
    fmt.Println(s)
    for _, v := range s {
        result += getVal(v)
    }
    return result
}

func getVal(r rune) int {
    switch r {
    case '1':
        return 4
    case '2':
        return 9
    case '3':
        return 40
    case '4':
        return 90
    case '5':
        return 400
    case '6':
        return 900
    case 'I':
        return 1
    case 'V':
        return 5
    case 'X':
        return 10
    case 'L':
        return 50
    case 'C':
        return 100
    case 'D':
        return 500
    case 'M':
        return 1000
    default:
        return 0
    }
}

17. Letter Combinations of a Phone Number

var chars = [][]byte{
    {'a', 'b', 'c'},       // 2
    {'d', 'e', 'f'},       // 3
    {'g', 'h', 'i'},       // 4
    {'j', 'k', 'l'},       // 5
    {'m', 'n', 'o'},       // 6
    {'p', 'q', 'r', 's'}, // 7
    {'t', 'u', 'v'},      // 8
    {'w', 'x', 'y', 'z'}, // 9
}

var result []string

func letterCombinations(digits string) []string {
    // 边界判断
    if len(digits) == 0 {
        return []string{}
    }
    // 清空全局变量，防止下一示例直接使用了该变量
    result = []string{}
    dfs(digits, 0, "")
    return result
}

func dfs(digits string, level int, str string) {
    // 递归出口
    if level == len(digits) {
        result = append(result, str)
        return
    }
    // 将输入的单个digit转换为数字
    digit, _ := strconv.Atoi(string(digits[level]))
    // 在单个键位的字符中循环
    for i := 0; i < len(chars[digit-2]); i++ {
        // 下一层递归
        dfs(digits, level+1, str+string(chars[digit-2][i]))
    }
}

19. Remove Nth Node From End of List

Ideas

双指针，第一个指针一直往下走，并将倒数的数值n减一，直到n==0第二个指针再走，其中用pre指针记录第二个指针的原位置。第一个指针到底（为nil）时则返回。

Solutions

双指针

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    pre, p1, p2 := head, head, head        // pre记录前置节点
    for p2 != nil {
        if n == 0 {
            pre = p1
            p1 = p1.Next
        } else {
            n--
        }
        p2 = p2.Next
    }
    // 判断是否删除的是链表头节点，若是直接返回下一节点
    if pre == p1 {
        return pre.Next
    }
    // 删除pre节点后一节点（即p1s）
    pre.Next = p1.Next
    return head
}

双指针（改良）

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := new(ListNode) // 在 head 前防止虚拟节点，解决删除的是第一个元素的问题
    dummy.Next = head
    p := head    // p 是用于探底的指针
    head = dummy
    // p 先走
    for n > 0 {
        p = p.Next
        n--
    }
    // dummy 跟着往后走，直到 p 到底
    for p != nil {
        dummy = dummy.Next
        p = p.Next
    }
    // 删除结点
    dummy.Next = dummy.Next.Next
    return head.Next
}

20. Valid Parentheses

字符串替换

循环将字符串里的'{}()[]'替换为空字符串，最终得到空字符串即为匹配。该解法实际效率较低。

func isValid(s string) bool {
    for strings.Contains(s, "[]") || strings.Contains(s, "{}") || strings.Contains(s, "()") {
        s = strings.Replace(s, "[]", "", -1)
        s = strings.Replace(s, "{}", "", -1)
        s = strings.Replace(s, "()", "", -1)
    }
    if s == "" {
        return true
    }
    return false
}

栈匹配

对于括号匹配问题常见的解法是使用栈匹配。

func isValid(s string) bool {
    stack := make([]byte, 0)
    length := 0    // 记录栈顶
    for _, v := range []byte(s) {
        stack = append(stack, v)
        length++
        for length > 1 {
            left := stack[length-2]        // 栈末尾倒数第二个
            right := stack[length-1]    // 栈末尾倒数第一个
            if (left == '(' && right == ')') || (left == '{' && right == '}') || (left == '[' && right == ']') {
                length -= 2
                stack = stack[:length]
                continue
            }
            break
        }
    }
    return len(stack) == 0
}

21. Merge Two Sorted Lists

递归

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    } else {
        l2.Next = mergeTwoLists(l1, l2.Next)
        return l2
    }
}

去重*

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    } else if l1.Val > l2.Val {
        l2.Next = mergeTwoLists(l1, l2.Next)
        return l2
    } else {
        l1.Next = mergeTwoLists(l1.Next, l2.Next)
        return l1
    }
}

22. Generate Parentheses

使用回溯，左右括号各 n 个，用完即可。

func generateParenthesis(n int) []string {
    res := make([]string, 0)
    dfs(n, n, "", &res)
    return res
}

func dfs(left, right int, tmp string, res *[]string) {
    if left == 0 && right == 0 {
        // 当括号用完，返回
        *res = append(*res, tmp)
        return
    }

    if left == right {
        // 左右括号数量相等，只能用左括号
        dfs(left-1, right, tmp + "(", res)
    } else if left < right {
        // 左括号数量小于右括号，左右括号都可以用
        if left > 0 {
            dfs(left-1, right, tmp + "(", res)
        }
        dfs(left, right-1, tmp + ")", res)
    }
    // 左括号数量大于右括号，无法再闭合，不可能生成有效的字符串，则丢弃
}

由于函数最初已经判断过了，因此 left == right 语句中，两个变量不可能同为 0 ，简化上面的代码控制流如下：

func generateParenthesis(n int) []string {
    res := make([]string, 0)
    dfs(n, n, "", &res)
    return res
}

func dfs(left, right int, tmp string, res *[]string) {
    if left == 0 && right == 0 {
        *res = append(*res, tmp)
        return
    }
    if left > 0 {
        dfs(left-1, right, tmp + "(", res)
    }
    if left < right {
        dfs(left, right-1, tmp + ")", res)
    }
}

26. Remove Duplicates from Sorted Array

双指针

left 移动条件：left 为 0 或 left 元素和 left-1 的元素不相等
right 移动条件：right 和 left 不等（相等则用 right 覆盖 left）

func removeDuplicates(nums []int) int {
    left, right := 0, 1
    for right <= len(nums) {
        // left 左移条件
        if left == 0 || nums[left-1] != nums[left] {
            left++
        }
        // right 越界跳出（此时 left 左移条件已经执行了）
        if right == len(nums) {
            break
        }
        // right 右移条件
        if nums[left] == nums[right] {
            right++
        } else {
            nums[left] = nums[right]
        }
    }
    return left
}

27. Remove Element

双指针

双指针，左指针一步步走，右指针遇到目标数就跳过数字并跳到下一循环。简单来说就是把除了等于目标数的元素都覆盖到前面去

func removeElement(nums []int, val int) int {
    left, right := 0, 0
    for right < len(nums) {
        // 跳过
        if nums[right] == val {
            right++
            continue
        }
        nums[left] = nums[right]
        left++
        right++
    }
    return left
}

31. Next Permutation

Ideas

双指针
首先要找到左指针元素比其后一个元素小的位置作为 left，在 left 左侧的元素都不需要变动，其后的值必定是递减的，在这后面的值里找一个大于 left 的最小值，二者交换值，最终再将 left 之后的元素按递增排序

Solutions

双指针

func nextPermutation(nums []int)  {
    left, right := len(nums)-2, len(nums)-1
    // 固定left位置
    for left >=0 && nums[left] >= nums[left+1] {
        left--
    }
    if left >= 0 {
        // 查找left右侧大于left的最小值
        for right >=0 && nums[left] >= nums[right] {
            right--
        }
        // 交换
        nums[left], nums[right] = nums[right], nums[left]
    }
    // 翻转
    reverse(nums[left+1:])
}

func reverse(nums []int) {
    for i, n := 0, len(nums)-1; i <= n/2 ; i++ {
        nums[i], nums[n-i] = nums[n-i], nums[i]
    }
}

33. Search in Rotated Sorted Array

旋转排序数组，仍然按照二分法，分别对左有序和右有序的情况作判断。

Go

func search(nums []int, target int) int {
    low, high := 0, len(nums) - 1

    for low <= high {
        mid := (low + high) >> 1

        if nums[mid] == target {
            return mid
        }

        if nums[mid] >= nums[low] {
            // left ordered
            if target < nums[mid] && target >= nums[low] {
                // 说明 target 只能在左侧
                high = mid - 1
            } else {
                // target 可能在右侧（比左侧最小的还要小或是比左侧最大的还要大）
                low = mid + 1
            }
        } else {
            // right ordered
            if target > nums[mid] && target <= nums[high] {
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
    }

    return -1
}

Java

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid = 0;

        while (low <= high) {
            mid = (low + high) >> 1;
            if(nums[mid] == target) {
                return mid;
            }

            if (nums[mid] >= nums[low]) {
                // left ordered
                if (target < nums[mid] && target >= nums[low]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                // right ordered
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
}

34. Find First and Last Position of Element in Sorted Array

简单两次二分查找即可。

时间复杂度：$O(log{n})$
空间复杂度：$O(1)$

Go

func searchRange(nums []int, target int) []int {
    res := []int{-1, -1}    // 返回值

    left, right := 0, len(nums) - 1

    if right < left {
        // nums 为空
        return res
    }

    // 找左边界
    for left < right {
        mid := (left + right) >> 1
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if nums[left] != target {
        // 数组中不存在
        return res
    }
    res[0] = left
    right = len(nums)    // 复位 right

    for left < right {
        mid := (left + right) >> 1
        if nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    res[1] = right - 1

    return res
}

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid = 0;
        int res[] = {-1, -1};
        if (nums.length == 0) {
            return res;
        }

        while(low < high) {
            mid = (low + high) / 2;
            if (nums[mid] >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        if (nums[low] != target) {
            return res;
        }
        res[0] = low;
        high = nums.length;

        while(low < high) {
            mid = (low + high) / 2;
            if (nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        res[1] = high - 1;
        return res;
    }
}

39. Combination Sum

Ideas

回溯法

Solutions

回溯

func combinationSum(candidates []int, target int) [][]int {
    res := make([][]int, 0)
    tmp := make([]int, 0)
    backtracking(candidates, target, 0, &res, &tmp)
    return res
}

func backtracking(candidates []int, target, index int, res *[][]int, tmp *[]int) {
    if target <= 0 {
        if target == 0 {
            dst := make([]int, len(*tmp))
            copy(dst, *tmp)
            *res = append(*res, dst)
        }
        return
    }

    for i := index; i < len(candidates); i++ {
        target -= candidates[i]
        *tmp = append(*tmp, candidates[i])
        backtracking(candidates, target, i, res, tmp)
        *tmp = (*tmp)[:len(*tmp)-1]
        target += candidates[i]
    }
}

45. Jump Game II

Ideas

贪心策略，从后找最靠左的能找到自己的位置，从该位置重复上述操作，直到数组开头。

Solutions

贪心

func jump(nums []int) int {
    length := len(nums)
    if length == 1 {
        return 0
    }
    count := 0
    for i := length-1; i > 0; i-- {
        for j := 0; j < i; j++ {
            if nums[j] >= i-j {
                i = j+1
                break
            }
        }
        count++
    }
    return count
}

func jump(nums []int) int {
    curJump, farthestJump, jumps := 0, 0, 0
    for i := 0; i < len(nums)-1; i++ {
        // push index of furthest jump during current iteration
        if i+nums[i] > farthestJump {
            farthestJump = i + nums[i]
        }

        // if current iteration is ended - setup the next one
        if i == curJump {
            jumps, curJump = jumps+1, farthestJump

            if curJump >= len(nums)-1 {
                return jumps
            }
        }
    }

    // it's guaranteed to never hit it
    return 0
}

46. Permutations

Ideas

典型回溯

Solutions

回溯

func permute(nums []int) [][]int {
    res := make([][]int, 0)
    tmp := make([]int, 0)
    visited := make([]bool, len(nums))
    backtracking(nums, &res, &tmp, &visited)
    return res
}

func backtracking(nums []int, res *[][]int, tmp *[]int, visited *[]bool) {
    if len(nums) == 0 {
        return
    }
    if len(*tmp) == len(nums) {
        dst := make([]int, len(*tmp))
        copy(dst, *tmp)
        *res = append(*res, dst)
        return
    }
    for i := 0; i < len(nums); i++ {
        if (*visited)[i] {
            continue
        }
        *tmp = append(*tmp, nums[i])
        (*visited)[i] = true
        backtracking(nums, res, tmp, visited)
        (*visited)[i] = false
        *tmp = (*tmp)[:len(*tmp)-1]
    }
}

47. Permutations II

Ideas

回溯，相较于 46 题，需要跳过重复元素，因此首先要判断元素是否已经存在。

Solutions

回溯

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    res := make([][]int, 0)
    tmp := make([]int, 0)
    visited := make([]bool, len(nums))
    backtracking(nums, &res, &tmp, &visited)
    return res
}

func backtracking(nums []int, res *[][]int, tmp *[]int, visited *[]bool) {
    if len(nums) == 0 {
        return
    }
    if len(*tmp) == len(nums) {
        dst := make([]int, len(*tmp))
        copy(dst, *tmp)
        *res = append(*res, dst)
        return
    }
    for k, v := range nums {
        // 当左相邻元素和当前元素相等且未访问过时跳出
        if (*visited)[k] || k > 0 && !(*visited)[k-1] && v == nums[k-1] {
            continue
        }
        *tmp = append(*tmp, nums[k])
        (*visited)[k] = true
        backtracking(nums, res, tmp, visited)
        (*visited)[k] = false
        *tmp = (*tmp)[:len(*tmp)-1]
    }
}

48. Rotate Image

先斜对角翻转，再横向翻转。

如：[[1,2,3],[4,5,6],[7,8,9]] => [[1,4,7],[2,5,8],[3,6,9]] => [[7,4,1],[8,5,2],[9,6,3]]

func rotate(matrix [][]int)  {
    for i := 1; i < len(matrix); i++ {
        for j := 0; j < i; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }

    for k := 0; k < len(matrix); k++ {
        for i, j := 0, len(matrix[0])-1; i < j; i, j = i+1, j-1 {
            matrix[k][i], matrix[k][j] = matrix[k][j], matrix[k][i]
        }
    }
}

49. Group Anagrams

Hash Table

将字符串排序后的字符串作为键放入哈希表中，值为一个字符串数组。最后遍历哈希表输出即可。

func groupAnagrams(strs []string) [][]string {
    m := make(map[string][]string)
    for _, v := range strs {
        bt := []byte(v)    // 字符串转换为 byte 数组
        // 排序
        sort.Slice(bt, func(a, b int) bool {
            return bt[a] < bt[b]
        })
        str := string(bt)
        m[str] = append(m[str], v)
    }
    res := make([][]string, 0)
    for _, v := range m {
        res = append(res, v)
    }
    return res
}

54. Spiral Matrix

模拟

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return nil
    }
    rowMin, colMin := 0, 0
    rowMax, colMax := len(matrix), len(matrix[0])
    res := make([]int, rowMax * colMax)
    index := 0

    for {
        // left -> right
        for i := colMin; i < colMax; i++ {
            res[index] = matrix[rowMin][i]
            index++
        }
        rowMin++
        if rowMin >= rowMax {
            break
        }
        // top -> down
        for i := rowMin; i < rowMax; i++ {
            res[index] = matrix[i][colMax-1]
            index++
        }
        colMax--
        if colMin >= colMax {
            break
        }
        // right -> left
        for i := colMax-1; i >= colMin; i-- {
            res[index] = matrix[rowMax-1][i]
            index++
        }
        rowMax--
        if rowMin >= rowMax {
            break
        }
        // down -> top
        for i := rowMax-1; i >= rowMin; i-- {
            res[index] = matrix[i][colMin]
            index++
        }
        colMin++
        if colMin >= colMax {
            break
        }
    }
    return res
}

53. Maximum Subarray

动态规划

原地修改。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func maxSubArray(nums []int) int {
    maxNum := nums[0]
    sum := 0
    for i := 1; i < len(nums); i++ {
        if sum = nums[i]+nums[i-1]; sum > nums[i] {
            nums[i] = sum
        }
        if nums[i] > maxNum {
            maxNum = nums[i]
        }
    }
    return maxNum
}

分治

55. Jump Game

Ideas

Solutions

func canJump(nums []int) bool {
    if len(nums) == 1 {
        return true
    }
    cur, further, jumps := 0, 0, 0
    for i := 0; i < len(nums)-1; i++ {
        if i+nums[i] > further {
            further = i+nums[i]
        }
        if i == cur {
            jumps++
            cur = further
            if cur >= len(nums)-1 {
                return true
            }
        }
    }
    return false
}

56. Merge Intervals

排序

将数组按第一个值排序，遍历数组列表，当后一个数组第一个值不大于前一个数组第二个值，且后一个数组第二个值大于前一个数组第二个值时，更新前一个数组在结果列表里的数据。

func merge(intervals [][]int) [][]int {
    // 排序列表
    sort.Slice(intervals, func(a, b int) bool {
        return intervals[a][0] < intervals[b][0]
    })

    res := [][]int{intervals[0]}    // 结果列表，已经插入了第一对数字

    for i := 1; i < len(intervals); i++ {
        if num := res[len(res)-1][1]; num >= intervals[i][0] {
            if num <= intervals[i][1] {
                res[len(res)-1][1] = intervals[i][1]
            }
        } else {
            res = append(res, intervals[i])
        }
    }

    return res
}

58. Length of Last Word

双指针

从后向前遍历，分别记录第一个非空格字符和第二个空格字符串的位置。

func lengthOfLastWord(s string) int {
    left, right := len(s)-1, len(s)-1
    for i := len(s)-1; i >= 0; i-- {
        if left == right && s[i] == ' ' {
            right--
        } else if s[i] == ' ' {
            break
        }
        left--
    }
    return right - left
}

61. Rotate List

Ideas

双指针解法，本题要求得到循环n次的链表，循环次数可能比链表本身的长度还要长，因此可以将链表串成循环链表，再将其从中间拆分
时间复杂度：$O(n+k)$
空间复杂度：$O(1)$

Solutions

双指针

func rotateRight(head *ListNode, k int) *ListNode {
      if head == nil {
        return head
    }
    p := head
    // 计算链表长度
    count := 0
    for {
        count++
        if p.Next == nil {
            break
        }
        p = p.Next
    }
    // 连接链表头尾
    p.Next = head
    // 定位中断位置
    k = count - (k%count)
    for k > 1 {
        head = head.Next
        k--
    }
    // 截断循环链表
    tmp := head.Next
    head.Next = nil
    return tmp
}

62. Unique Paths

动态规划

简单动态规划。

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    dp[0][0] = 1

    for i := range dp {
        for j := range dp[i] {
            if i > 0 {
                dp[i][j] += dp[i-1][j]
            }
            if j > 0 {
                dp[i][j] += dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

64. Minimum Path Sum

DP

简单的动态规划，从判断上、左元素大小，取小值加到当前位置，可以使用原数组存结果：

1    3    1    ->    1    4    5
1   5   1    ->    2    7    6
4    2    1   ->    6    8    7

func minPathSum(grid [][]int) int {
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if i == 0 && j > 0 {
                // 第一行
                grid[i][j] = grid[i][j-1] + grid[i][j]
            } else if  i > 0 && j == 0 {
                // 第一列
                grid[i][j] = grid[i-1][j] + grid[i][j]
            } else if i > 0 {
                grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
            }
        }
    }
    return grid[len(grid)-1][len(grid[0])-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

66. Plus One

数组

从数组末端开始遍历，当当前数字 +1 后大于 9 即进位，将当前数字置 0。如果当前位置为数组首端，在数组前面插入一个 1 即可。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        digits[i]++
        if digits[i] > 9 {
            digits[i] = 0
            if i == 0 {
                digits = append([]int{1}, digits...)
                break
            }
            continue
        }
        break
    }
    return digits
}

69. Sqrt(x)

二分查找

采用二分查找的方式，不断缩小范围。

func mySqrt(x int) int {
    low, high := 0, x
    for low <= high {
        mid := (low+high)>>1
        if m := mid*mid; m == x {
            return mid
        } else if m > x {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return low-1
}

74. Search a 2D Matrix

二分查找

将二维数组看作一维数组，转换下标即可。

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0, mid = 0, high = m * n - 1;

        while (low <= high) {
            mid = (low + high) >> 1;
            int row = mid / n;
            int col = mid % n;
  
            if (matrix[row][col] == target) {
                return true;
            }
            if (matrix[row][col] < target) {
                low = mid + 1;
            } else {
                high = mid -1;
            }
        }
        return false;
    }
}

75. Sort Colors

荷兰国旗问题，使用双指针，参见漫画：常考的荷兰国旗问题你还不会吗？（初级）

func sortColors(nums []int)  {
    pa, pb := 0, len(nums)-1
    for i := 0; i <= pb; i++ {
        if nums[i] == 0 {
            nums[i], nums[pa] = nums[pa], nums[i]
            pa++
        }
        if nums[i] == 2 {
            nums[i], nums[pb] = nums[pb], nums[i]
            pb--
            i--
        }
    }
}

78. Subsets

回溯

var res [][]int

func subsets(nums []int) [][]int {
    res = make([][]int, 0)
    dfs(nums, []int{}, 0)
    return res
}

func dfs(nums, tmp []int, index int) {
    dst := make([]int, len(tmp))
    copy(dst, tmp)
    res = append(res, dst)

    for i := index; i < len(nums); i++ {
        tmp = append(tmp, nums[i])
        dfs(nums, tmp, i+1)
        tmp = tmp[:len(tmp)-1]
    }
}

79. Word Search

DFS

简单回溯。

var find bool

func exist(board [][]byte, word string) bool {
    find = false

    visited := make([][]bool, len(board))
    for i := range visited {
        visited[i] = make([]bool, len(board[0]))
    }

    for i := range board {
        for j := range board[0] {
            dfs(board, word, visited, i, j, 0)
            if find {
                return true
            }
        }
    }
    return false
}

func dfs(board [][]byte, word string, visited [][]bool, i, j, idx int) {
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || find {
        // 判断是否越界、已经访问、已经找到
        return
    }

    if board[i][j] != word[idx] {
        return
    }

    if len(word) == idx+1 {
        find = true
        return
    }

    visited[i][j] = true
    dfs(board, word, visited, i+1, j, idx+1)
    dfs(board, word, visited, i-1, j, idx+1)
    dfs(board, word, visited, i, j+1, idx+1)
    dfs(board, word, visited, i, j-1, idx+1)
    visited[i][j] = false
}

80. Remove Duplicates from Sorted Array II

双指针，一个指针不断前进，另一个指针停留在重复的第三个数上，用前者替换后者内容。

func removeDuplicates(nums []int) int {
    p := 0
    for i := range nums {
        if p < 2 || nums[i] != nums[p-2] {
            nums[p] = nums[i]
            p++
        }
    }
    return p
}

82. Remove Duplicates from Sorted List II

虚结点dummy指向链表头，使用slow、fast双指针来标记非重复结点和每一个结点。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}

    slow, fast := dummy, head

    for slow.Next != nil {
        for fast = slow.Next; fast.Next != nil && fast.Next.Val == slow.Next.Val; {
            fast = fast.Next
        }
        if slow.Next != fast {
            slow.Next = fast.Next
        } else {
            slow = slow.Next
        }
    }
    return dummy.Next
}

83. Remove Duplicates from Sorted List

func deleteDuplicates(head *ListNode) *ListNode {
    dummy := new(ListNode)
    dummy.Next = head

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

    return dummy.Next
}

86. Partition List

用两个结点分别生成两个链表，一个记录小于x的结点，另一个记录大于等于x的结点，最后拼接返回。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    dummyMin := new(ListNode)
    dummyMax := new(ListNode)

    tmp1 := dummyMin
    tmp2 := dummyMax

    for head != nil {
        if head.Val < x {
            tmp1.Next = head
            head = head.Next
            tmp1 = tmp1.Next
            tmp1.Next = nil
        } else {
            tmp2.Next = head
            head = head.Next
            tmp2 = tmp2.Next
            tmp2.Next = nil
        }
    }
    tmp1.Next = dummyMax.Next
    return dummyMin.Next
}

88. Merge Sorted Array

Ideas

设置三个指针，分别位于nums1（不含 0）末尾、nums1（含 0）末尾、nums2末尾，从后向前对比两个数组的末尾元素，取大者放入 0 元素位置。
- 时间复杂度：$O(m+n)$
- 空间复杂度：$O(1)$

Solutions

Three Pointers

func merge(nums1 []int, m int, nums2 []int, n int)  {
    for idx := m+n-1; idx >= 0; idx-- {
        if n-1 < 0 || (m-1 >= 0 && nums1[m-1] >= nums2[n-1]) {
            nums1[idx] = nums1[m-1]
            m--
        } else {
            nums1[idx] = nums2[n-1]
            n--
        }
    }
}

89. Gray Code

数学

按照规律解法，当 $n=3$ 时，$Gray(i)=i^{i \over 2}$ 。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func grayCode(n int) []int {
    res := make([]int, 0)
    max := 1 << n
    for i := 0; i < max; i++ {
        res = append(res, i ^ i >> 1)
    }
    return res    
}

92

Ideas

Solutions

反转

func reverseBetween(head *ListNode, left, right int) *ListNode {
    dummy := new(ListNode)
    dummy.Next = head
    pre := dummy
    for i := 1; i < left; i++ {
        pre = pre.Next
    }
    head = pre.Next
    for i := left; i < right; i++ {
        next := head.Next
        head.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return dummy.Next
}

94. Binary Tree Inorder Traversal

Ideas

递归
迭代

Solutions

递归

func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    helper(root, &result)
    return result
}

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

迭代

func inorderTraversal(root *TreeNode) []int {
    stack := make([]*TreeNode, 0)
    result := make([]int, 0)
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        if len(stack) > 0 {
            root = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result = append(result, root.Val)
            root = root.Right
        }
    }
    return result
}

98. Validate Binary Search Tree

中序遍历（递归）

BST 中序遍历结果是有序的。最简单的方式是用全局变量。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var first = true
var last int
var ret = true

func isValidBST(root *TreeNode) bool {
    // 重置全局变量
    first = true
    last = root.Val
    ret = true
    inorder(root)
    return ret
}

func inorder(root *TreeNode) {
    if root == nil {
        return
    }
    inorder(root.Left)
    if root.Val <= last && !first {
        ret = false
        return
    }
    last = root.Val
    first = false
    inorder(root.Right)
}

中序遍历（迭代）

func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    last := math.MinInt64
    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Val <= last {
            return false
        }
        last = root.Val
        root = root.Right
    }
    return true
}

100. Same Tree

Ideas

递归 DFS

Solutions

递归

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil || p.Val != q.Val  {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

101-200

101. Symmetric Tree

Ideas

常规递归解法。

Solutions

Recursion

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return helper(root.Left, root.Right)
}

func helper(left, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil || left.Val != right.Val {
        return false
    }
    return helper(left.Left, right.Right) && helper(left.Right, right.Left)
}

102. Binary Tree Level Order Traversal

层序遍历

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

103. Binary Tree Zigzag Level Order Traversal

队列

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    res := make([][]int, 0)
    queue := []*TreeNode{root}

    level := 0

    for len(queue) > 0 {
        tmp := make([]int, 0)
        // 偶数层处理
        for i := len(queue); level % 2 == 0 && i > 0; i-- {
            node := queue[0]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            tmp = append(tmp, node.Val)
            queue = queue[1:]
        }
        for i := len(queue); level % 2 != 0 && i > 0; i-- {
            node := queue[len(queue)-1]
            if node.Right != nil {
                queue = append([]*TreeNode{node.Right}, queue...)
            }
            if node.Left != nil {
                queue = append([]*TreeNode{node.Left}, queue...)
            }
            tmp = append(tmp, node.Val)
            queue = queue[:len(queue)-1]
        }
        res = append(res, tmp)
        level++
    }
    return res
}

队列，按层反转

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    res := make([][]int, 0)
    queue := []*TreeNode{root}
    level := 0
    for len(queue) > 0 {
        tmp := make([]int, 0)
        for i := len(queue); i > 0; i-- {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            tmp = append(tmp, node.Val)
        }
        // 奇数层就翻转一下结果
        if level % 2 == 1 {
            for i, n := 0, len(tmp); i < n/2; i++ {
                tmp[i], tmp[n-1-i] = tmp[n-1-i], tmp[i]
            }
        }
        res = append(res, tmp)
        level++
    }
    return res
}

104. Maximum Depth of Binary Tree

递归

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

迭代（层序遍历）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) (level int) {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        length := len(queue)
        level++
        for i := 0; i < length; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return
}

105. Construct Binary Tree from Preorder and Inorder Traversal

递归

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }

    // 找中序序列左右子树分界点
    i := 0
    for ; i < len(inorder); i++ {
        if preorder[0] == inorder[i] {
            break
        }
    }

    root := &TreeNode{preorder[0], nil, nil}
    // len(inorder[:i]) 为左子树结点数量
    root.Left = buildTree(preorder[1:1+len(inorder[:i])], inorder[:i])
    root.Right = buildTree(preorder[1+len(inorder[:i]):], inorder[i+1:])

    return root
}

后序遍历

110. Balanced Binary Tree

递归

先递归求左右子树的深度，判断深度差是否满足条件，递归所有子树

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    // 求左右子树深度差
    sub := helper(root.Left) - helper(root.Right)
    if sub > 1 || sub < -1 {
        return false
    } else {
        // 递归判断子树
        return isBalanced(root.Left) && isBalanced(root.Right)
    }
}

// 求二叉树深度，来自 LeetCode 104
func helper(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(helper(root.Left), helper(root.Right)) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

113. Path Sum II

Ideas

回溯

Solutions

回溯

func pathSum(root *TreeNode, targetSum int) [][]int {
    results := make([][]int, 0)
    tmp := make([]int, 0)
    backtracking(root, targetSum, tmp, &results)
    return results
}

func backtracking(root *TreeNode, targetSum int, tmp []int, results *[][]int) {
    if root == nil {
        return
    }
    tmp = append(tmp, root.Val)
    // 递归出口
    if targetSum == root.Val && root.Left == nil && root.Right == nil {
        dst := make([]int, len(tmp))
        copy(dst, tmp)
        *results = append(*results, dst)
        return
    }
    backtracking(root.Left, targetSum-root.Val, tmp, results)
    backtracking(root.Right, targetSum-root.Val, tmp, results)
    tmp = tmp[:len(tmp)-1]
}

114. Flatten Binary Tree to Linked List

递归

采用全局变量存储最后一个递归到的结点。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var last *TreeNode

func flatten(root *TreeNode)  {
    last = nil    // 清空全局变量，防止干扰下一个用例
    helper(root)
}

func helper(root *TreeNode) {
    if root == nil {
        return
    }
    helper(root.Right)
    helper(root.Left)
    root.Right = last
    root.Left = nil
    last = root
}

121. Best Time to Buy and Sell Stock

记录最小值以及当前值与最小值的差值，记录最大的那个差值。

func maxProfit(prices []int) int {
    minNum := prices[0]
    maxNum := 0
    for i := 1; i < len(prices); i++ {
        if res := prices[i] - minNum; res > maxNum {
            // 记录最大的差值
            maxNum = res
        }
        if prices[i] < minNum {
            // 记录最小值
            minNum = prices[i]
        }
    }
    return maxNum
}

122. Best Time to Buy and Sell Stock II

Ideas

DP
贪心

Solutions

func maxProfit(prices []int) int {
    length := len(prices)
    // 滚动数组节省空间
    var dp [2][2]int
    dp[0][0] = 0             // cash
    dp[0][1] = -prices[0]      // stock
    for i := 1; i < length; i++ {
        dp[1][0] = max(dp[0][0], dp[0][1]+prices[i])
        dp[1][1] = max(dp[0][1], dp[0][0]-prices[i])
        dp[0] = dp[1]
    }
    return dp[1][0]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

124. Binary Tree Maximum Path Sum

递归

遍历即可。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var maxNum int

func maxPathSum(root *TreeNode) int {
    maxNum = -1001
    pathSum(root)
    return maxNum
}

func pathSum(root *TreeNode) int {
    if root == nil {
        return 0
    }

    l := pathSum(root.Left)
    r := pathSum(root.Right)

    maxNum = max(maxNum, l + r + root.Val)

    return max(max(max(l, r), 0) + root.Val, 0)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

DFS

输出路径如何解？

129. Sum Root to Leaf Numbers

递归

尝试其他方法？

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

func helper(root *TreeNode, num int) int {
    if root == nil {
        return 0
    }
    num *= 10
    if root.Left == nil && root.Right == nil {
        return num + root.Val
    }
    return helper(root.Left, num+root.Val) + helper(root.Right, num+root.Val)
}

135. Candy

贪心策略：先从左往右扫一遍，将右边大于左边的加一；再从右往左扫一遍，将左边大于右边的加一。注意第二次扫可能已经分配的足够多了，可以和原始值对比再考虑是否加一。

func candy(ratings []int) int {
    nums := make([]int, len(ratings))

    nums[0] = 1    // 填充初始的 1

    // 左 -> 右
    for i := 1; i < len(ratings); i++ {
        nums[i] = 1    // 填充初始的 1
        if ratings[i] > ratings[i-1] {
            nums[i] = nums[i-1] + 1
        }
    }

    // 右 -> 左
    for i := len(ratings)-1; i > 0; i-- {
        if ratings[i] < ratings[i-1] {
            nums[i-1] = max(nums[i-1], nums[i] + 1)
        }
    }

    // 数组求和
    for i := 1; i < len(nums); i++ {
        nums[0] += nums[i]
    }
    return nums[0]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

136. Single Number

简单异或运算，相同的值都会变为 0。

func singleNumber(nums []int) int {
    res := 0
    for i := range nums {
        res ^= nums[i]
    }
    return res
}

138. Copy List with Random Pointer

Hash Table

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    m := make(map[*Node]*Node)

    for cur := head; cur != nil; cur = cur.Next {
        m[cur] = &Node{cur.Val, nil, nil}
    }

    for cur := head; cur != nil; cur = cur.Next {
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
    }

    return m[head]
}

141. Linked List Cycle

哈希表

使用哈希表保存结点，当遇到重复即返回。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

func hasCycle(head *ListNode) bool {
    m := make(map[*ListNode]bool)
    for head != nil {
        if _, ok := m[head]; ok {
            return true
        }
        m[head] = true
        head = head.Next
    }
    return false
}

快慢指针

如果存在循环则二者必然交叉，当遇到交叉即返回。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

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

142. Linked List Cycle II

快慢指针

快慢指针解法，当二者第一次相遇时将其中一个指针返回到链开头，二者以同样的速度往下遍历，直到二者相等即返回。

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

143. Reorder List

双指针

先找到链表中点，将其切割成两个链表，再翻转后一链表，最后拼接即可。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    mid := searchMiddle(head)
    rr := reverse(mid.Next)
    mid.Next = nil
    ll := head
    var ltmp, rtmp *ListNode
    left, right := ll, rr
    for left != nil && right != nil {
        ltmp = left.Next
        rtmp = right.Next

        left.Next = right
        left = ltmp

        right.Next = left
        right = rtmp
    }
}

// 查找链表中点
func searchMiddle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

// 翻转链表
func reverse(head *ListNode) *ListNode {
    var pre, next *ListNode
    for head != nil {
        next = head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

144. Binary Tree Preorder Traversal

辅助栈

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

    stack := make([]*TreeNode, 0)

    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            res = append(res, root.Val)
            root = root.Left
        }
        if len(stack) > 0 {
            root = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            root = root.Right
        }
    }

    return res
}

146. LRU Cache

LRU 算法模板。

type entry struct {
    key int
    val int
}


type LRUCache struct {
    cap int
    ll  *list.List
    cache map[int]*list.Element
}


func Constructor(capacity int) LRUCache {
    return LRUCache {capacity, list.New(), make(map[int]*list.Element)}
}


func (this *LRUCache) Get(key int) int {
    ele := this.cache[key]
    if ele == nil {
        return -1
    }
    this.ll.MoveToFront(ele)
    return ele.Value.(entry).val
}


func (this *LRUCache) Put(key int, value int)  {
    if ele := this.cache[key]; ele != nil {
        // 已存在，更新并移动至链首
        ele.Value = entry{key, value}
        this.ll.MoveToFront(ele)
        return
    }
    if len(this.cache) == this.cap {
        // 容量已满，删除链尾
        delete(this.cache, this.ll.Remove(this.ll.Back()).(entry).key)
    }
    this.cache[key] = this.ll.PushFront(entry{key, value})
}


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

151. Reverse Words in a String

反转

去除多余空格（快慢指针）
反转整个字符串
反转单词

时间复杂度：$O(n)$
空间复杂度：$O(n)$
空间复杂度（优化）：$O(1)$

可以不把步骤单独封装为函数以减小内存消耗，如忽略 Go 字符串不可变的问题，空间复杂度可以达到 $O(1)$。

func reverseWords(s string) string {
    str := []byte(s)

    str = trim(str)
    reverse(str)
    
    for i, j := 0, 0; j <= len(str); {
        if j < len(str) && str[j] != ' ' {
            j++
            continue
        } else {
            reverse(str[i:j])
            j++
            i = j
        }
    }

    return string(str)
}

// trim 函数删除多余空格
func trim(s []byte) []byte {
    slow, fast := 0, 0
    for fast < len(s) && s[fast] == ' ' {
        fast++
    }
    for ; fast < len(s); fast++ {
        if fast > 1 && s[fast] == ' ' && s[fast-1] == s[fast] {
            continue
        }
        s[slow] = s[fast]
        slow++
    }
    if s[slow-1] == ' ' {
        return s[:slow-1]
    }
    return s[:slow]
}

// reverse 函数反转整个 s
func reverse(s []byte) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

153. Find Minimum in Rotated Sorted Array

二分查找

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

Java

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length-1, mid = 0;

        while (low < high) {
            mid = (low + high) >> 1;
            if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
}

154. Find Minimum in Rotated Sorted Array II

二分查找

func findMin(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        mid := (low + high) >> 1
        if nums[mid] < nums[high] {
            // right ordered
            high = mid
        } else if nums[mid] > nums[high] {
            // left ordered
            low = mid + 1
        } else {
            high--
        }
    }
    return nums[low]
}

155. Min Stack

设置辅助栈，当有比辅助栈栈顶更小或与其相等的值输入则入栈。弹出时当栈顶相等时弹出辅助栈栈顶。

type MinStack struct {
    Stack []int
    Helper []int
}


func Constructor() MinStack {
    return MinStack{[]int{}, []int{}}
}


func (this *MinStack) Push(val int)  {
    if len(this.Helper) == 0 || val <= this.Helper[len(this.Helper)-1] {
        this.Helper = append(this.Helper, val)
    }
    this.Stack = append(this.Stack, val)
}


func (this *MinStack) Pop()  {
    if this.Stack[len(this.Stack)-1] == this.Helper[len(this.Helper)-1] {
        this.Helper = this.Helper[:len(this.Helper)-1]
    }
    this.Stack = this.Stack[:len(this.Stack)-1]
}


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


func (this *MinStack) GetMin() int {
    return this.Helper[len(this.Helper)-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();
 */

157. Read N Characters Given Read4

题目意思是用函数 read4() 来实现函数 read()，前者每次只能读取 4 个字符。使用循环解答即可，当 read4() 返回的值小于 4，表示已经不再需要 read4() 了，可以停止循环。

/**
 * The read4 API is already defined for you.
 *
 *     read4 := func(buf4 []byte) int
 *
 * // Below is an example of how the read4 API can be called.
 * file := File("abcdefghijk") // File is "abcdefghijk", initially file pointer (fp) points to 'a'
 * buf4 := make([]byte, 4) // Create buffer with enough space to store characters
 * read4(buf4) // read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
 * read4(buf4) // read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
 * read4(buf4) // read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
 */

var solution = func(read4 func([]byte) int) func([]byte, int) int {
    // implement read below.
    return func(buf []byte, n int) int {
        cnt := 0    // 统计数量
        num := 4    // read4() 读取的数量
        for num == 4 {
            num = read4(buf[cnt:])    // 偏移 cnt
            cnt += num
        }
        // 返回 n 和 cnt 二者较小值
        if n < cnt {
            return n
        }
        return cnt
    }
}

160. Intersection of Two Linked Lists

Hash Table

使用 Map 保存一个链表的所有节点，遍历第二个链表，如果在 Map 中已存在则返回。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    m := make(map[*ListNode]bool)
    for headA != nil {
        m[headA] = true
        headA = headA.Next
    }
    for headB != nil {
        if _, ok := m[headB]; ok {
            return headB
        }
        headB = headB.Next
    }
    return nil
}

交叉

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // 边界判断
    if headA == nil || headB == nil {
        return nil
    }
    pA, pB := headA, headB
    for pA != pB {
        if pA != nil {    
            pA = pA.Next
        } else {
            pA = headB
        }
        if pB != nil {
            pB = pB.Next
        } else {
            pB = headA
        }
    }
    return pA
}

162. Find Peak Element

二分查找

爬坡法。

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

Java

class Solution {
    public int findPeakElement(int[] nums) {
        int low = 0, high = nums.length-1, mid = 0;

        while (low < high) {
            mid = (low + high) >> 1;
            if (nums[mid] < nums[mid+1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

163. Missing Ranges

简单遍历。

func findMissingRanges(nums []int, lower int, upper int) []string {
    res := make([]string, 0)
    if len(nums) == 0 {
        res = append(res, genStr(lower, upper))
        return res
    }
    if nums[0] != lower {
        // lower 不在数组内
        res = append(res, genStr(lower, nums[0]-1))
    }
    for i := 0; i < len(nums)-1; i++ {
        // 对比相邻数字
        if nums[i+1] - nums[i] > 1 {
            res = append(res, genStr(nums[i]+1, nums[i+1]-1))
        }
    }
    if upper != nums[len(nums)-1] {
        // upper 不在数组内
        res = append(res, genStr(nums[len(nums)-1]+1, upper))
    }
    return res
}

// 生成字符串
func genStr(x, y int) string {
    if x == y {
        return fmt.Sprintf("%d", x)
    }
    return fmt.Sprintf("%d->%d", x, y)
}

169. Majority Element

摩尔投票法

假设一个数为众数，当有数字与其相同时众数统计数量加一，不同时统计数量减一，统计数量为 0 则重新设置众数，这样到最后除目标数字以外都会被抵消掉。

func majorityElement(nums []int) int {
    // num 为众数，sum 为和
    num, sum := 0, 0
    for i := range nums {
        if sum == 0 {
            num = nums[i]
        }
        if nums[i] != num {
            sum--
        } else {
            sum++
        }
    }
    return num
}

191. Number of 1 Bits

func hammingWeight(num uint32) int {
    count := 0
    for num != 0 {
        if num&1 == 1 {
            count++
        }
        num = num >> 1
    }
    return count
}

199. Binary Tree Right Side View

队列

与 102 题相同，简单修改即可，求每一层的最后一个元素。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    ret := make([]int, 0)
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        tmp := root.Val
        for i := len(queue); i > 0; i-- {
            node := queue[0]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            tmp = node.Val
            queue = queue[1:]
        }
        ret = append(ret, tmp)
    }
    return ret
}

200. Number of Islands

DFS

创建 visited 数组标记是否遍历到，再逐个进行 DFS 即可。

func numIslands(grid [][]byte) int {
    visited := make([][]bool, len(grid))
    for i := range visited {
        visited[i] = make([]bool, len(grid[0]))
    }

    count := 0

    for i := range grid {
        for j := range grid[0] {
            if grid[i][j] == '1' && !visited[i][j] {
                dfs(grid, visited, i, j)
                count++
            }
        }
    }

    return count

}

func dfs(grid [][]byte, visited [][]bool, row, col int) {
    if row < 0 || col < 0 || row >= len(grid) || col >= len(grid[0]) || visited[row][col] || grid[row][col] == '0' {
        return
    }
    visited[row][col] = true

    dfs(grid, visited, row + 1, col)
    dfs(grid, visited, row - 1, col)
    dfs(grid, visited, row, col + 1)
    dfs(grid, visited, row, col - 1)
}

优化上述代码，在原矩阵上标记即可。

func numIslands(grid [][]byte) int {
    count := 0

    for i := range grid {
        for j := range grid[0] {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                count++
            }
        }
    }

    return count
}

func dfs(grid [][]byte, row, col int) {
    if row < 0 || col < 0 || row >= len(grid) || col >= len(grid[0]) || grid[row][col] != '1' {
        return
    }

    grid[row][col] = '0'    // 标记为非 1 字符都可

    dfs(grid, row + 1, col)
    dfs(grid, row - 1, col)
    dfs(grid, row, col + 1)
    dfs(grid, row, col - 1)
}

201-300

206. Reverse Linked List

Ideas

遍历链表并重新创建一个链表，比较简单粗暴。
记录前一个结点，并将当前节点指向前一结点。
递归

Solutions

反转

func reverseList(head *ListNode) *ListNode {
    var prev, next *ListNode
    for {
        next = head.Next     // 存储下一结点
        head.Next = prev       // 改变指针
        prev = head            // 存储当前结点
        head = next            // 跳转到下一个结点
    }
    return prev
}

递归

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    dummy := reverseList(head.Next)
    head.Next.Next = head    // 让下一结点指向自己
    head.Next = nil            // 删除指向下一结点的指针
    return dummy
}

215. Kth Largest Element in an Array

排序

堆排序：

func HeapSort(arr []int) {
    for i := len(arr) - 1; i >= 0; i-- {
        heapify(arr, i)
        arr[0], arr[i] = arr[i], arr[0]
    }
    return
}

func heapify(arr []int, end int) {
    for i := (len(arr) - 2) / 2; i >= 0; i-- {
        sift_down(arr, i, end)
    }
}

func sift_down(arr []int, start, end int) {
    root := start
    for {
        child := root*2 + 1
        if child > end {
            break
        }
        if child+1 <= end && arr[child] < arr[child+1] {
            child++
        }
        if arr[root] >= arr[child] {
            return
        }
        arr[root], arr[child] = arr[child], arr[root]
        root = child
    }
}

226. Invert Binary Tree

递归

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

230. Kth Smallest Element in a BST

中序遍历（递归）

利用中序遍历 BST 的结果有序的特性递归求解。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var count int
var node *TreeNode

func kthSmallest(root *TreeNode, k int) int {
    count = 0
    node = new(TreeNode)
    inorder(root, k)
    return node.Val
}

func inorder(root *TreeNode, k int) {
    if root == nil {
        return
    }
    inorder(root.Left, k)
    count++
    if count == k {
        node = root
        return
    }
    inorder(root.Right, k)
}

234. Palindrome Linked List

辅助栈

时间复杂度：$O(n)$
空间复杂度：$O(n)$

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    stack := make([]int, 0)
    for p := head; p != nil; p = p.Next {
        stack = append(stack, p.Val)
    }

    for i := len(stack)-1; i >= 0; i-- {
        if stack[i] != head.Val {
            return false
        }
        head = head.Next
    }
    return true
}

翻转链表

先找到链表中点，再翻转链表后半部分。

注意，这种方法会改变原链表结构，如有必要，需要将链表恢复原状。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    // 快慢指针找到链表中点
    slow, fast := head, head
    count := 0
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        count++
    }
    right := reverse(slow)
    // 分别遍历
    for count > 0 {
        if head.Val != right.Val {
            return false
        }
        head = head.Next
        right = right.Next
        count--
    }
    return true
}

// 翻转链表
func reverse(head *ListNode) *ListNode {
    pre, next := head, head
    for head != nil {
        next = head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

235. Lowest Common Ancestor of a Binary Search Tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for root != nil {
        if root.Val < p.Val && root.Val < q.Val {
            root = root.Right
        } else if  root.Val > p.Val && root.Val > q.Val {
            root = root.Left
        } else {
            break
        }
    }
    return root
}

236. Lowest Common Ancestor of a Binary Tree

递归

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || p == root || q == root {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left == nil {
        return right
    }
    return left
}

237. Delete Node in a Linked List

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
    *node = *(node.Next)
}

242. Valid Anagram

Ideas

使用 HashTable 存储s中所有字符的出现次数，和 t 进行对比，相同则返回true。
和 HashTable 同样的思路，但由于存储的是小写字母，因此可以直接用一个长度为 26 的数组存储每一个字符的 ASCII 码值。

Solutions

HashTable

func isAnagram(s string, t string) bool {
    m := make(map[rune]int)
    for _, v := range s {
        m[v]++
    }
    for _, v := range t {
        m[v]--
    }
    for _, v := range m {
        if v != 0 {
            return false
        }
    }
    return true
}

数组

func isAnagram(s string, t string) bool {
    arr := [26]int{0}
    for _, v := range s {
        arr[v%97]++
    }
    for _, v := range t {
        arr[v%97]--
    }
    for _, v := range arr {
        if v != 0 {
            return false
        }
    }
    return true
}

264. Ugly Number II

动态规划

func nthUglyNumber(n int) int {
    dp := make([]int, n)
    dp[0] = 1

    p1, p2, p3 := 0, 0, 0

    for i := 1; i < n; i++ {
        dp[i] = min(dp[p1] * 2, dp[p2] * 3, dp[p3] * 5)
        if dp[i] == dp[p1] * 2 {
            p1++
        }
        if dp[i] == dp[p2] * 3 {
            p2++
        }
        if dp[i] == dp[p3] * 5 {
            p3++
        }
    }
    return dp[len(dp)-1]
}

func min(a, b, c int) int {
    switch {
    case a <= b && a <= c:
        return a
    case a <= b:
        return c
    case b <= c:
        return b
    default:
        return c
    }
}

283. Move Zeroes

双指针

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func moveZeroes(nums []int)  {
    left, right, length := 0, 0, len(nums)
    for right < length {
        if nums[right] != 0 {
            if nums[left] == 0 {
                nums[left], nums[right] = nums[right], nums[left]
            }
            left++
        }
        right++
    }
}

287. Find the Duplicate Number

双指针

本题与链表找环入口同理，用下标当作链表的下一节点，会形成一个存在环的链表。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func findDuplicate(nums []int) int {
    slow, fast := 0, 0
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            fast = 0
            break
        }
    }
    for nums[slow] != nums[fast] {
        fast = nums[fast]
        slow = nums[slow]
    }
    return nums[slow]
}

299. Bulls and Cows

哈希表

本题本质上就是求出两对数字中的相同位置数个数以及公有的数字个数。用哈希表存储就可以，但因为数字只在 0 ~ 9 范围内，可以使用数组存储。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func getHint(secret string, guess string) string {
    nums := make([]int, 10)    // replace hash table
    a, b := 0, 0    // count A and B
    for i := 0; i < len(secret); i++ {
        if secret[i] == guess[i] {
            a++
        } else {
            if nums[secret[i]-'0'] < 0 {
                b++
            }
            nums[secret[i]-'0']++
            if nums[guess[i]-'0'] > 0 {
                b++
            }
            nums[guess[i]-'0']--
        }
    }
    return fmt.Sprintf("%dA%dB", a, b)
}

301-400

338.Counting Bits

动态规划，存在如下规律：

对于奇数$i$，其含二进制 1 个数与$i\over2$含二进制 1 个数相等
对于偶数$i$，其含二进制 1 个数等于$i-1$含二进制 1 个数加一

func countBits(n int) []int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        if i%2 == 0 {
            dp[i] = dp[i/2]
        } else {
            dp[i] = dp[i-1] + 1
        }
    }
    return dp
}

344. Reverse String

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func reverseString(s []byte)  {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

345. Reverse Vowels of a String

Ideas

双指针，题目要求仅翻转元音字母，字符串翻转通过左右双指针交换即可，让两个指针遇到非元音字母时跳过
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$（Go 中为$O(n)$）

Solutions

双指针

func reverseVowels(s string) string {
    tmp := []byte(s)
    pa, pb := 0, len(s)-1
    for pa < pb {
        for pa < len(s) && !strings.Contains("aeiouAEIOU", string(tmp[pa])) {
            pa++
        }
        for pb > 0 && !strings.Contains("aeiouAEIOU", string(tmp[pb])) {
            pb--
        }
        if pa < pb {
            tmp[pa], tmp[pb] = tmp[pb], tmp[pa]
            pa++
            pb--
        }
    }
    return string(tmp)
}

401-500

415. Add Strings

字符串

效率不够高，如何优化？

func addStrings(num1 string, num2 string) string {
    carry := 0
    ret := ""
    for i, j := len(num1) - 1, len(num2) - 1; i >= 0 || j >= 0 || carry != 0; i, j = i - 1, j - 1 {
        var a, b int
        if i >= 0 {
            a = int(num1[i] - '0')
        }
        if j >= 0 {
            b = int(num2[j] - '0')
        }
        result := a + b + carry
        ret = strconv.Itoa(result%10) + ret
        carry = result / 10
    }
    return ret
}

434. Number of Segments in a String

题目要求统计单词数量，因此统计中间的空格数量即可。设置一个 flag，遇到非空格时变为 true，当为真时统计数量。

func countSegments(s string) int {
    count := 0
    var flag bool
    for _, v := range s {
        if v != ' ' {
            flag = true
        } else if flag {
            count++
            flag = false
        }
    }
    if len(s) == 0 || s[len(s)-1] == ' ' {
        // 空字符串或存在空格
        return count
    }
    return count + 1
}

437. Path Sum III

回溯

时间复杂度：$O(n^{2})$
空间复杂度：$O(n)$

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var count int

func pathSum(root *TreeNode, targetSum int) int {
    count = 0
    preOrder(root, targetSum)
    return count
}

func preOrder(root *TreeNode, targetSum int) {
    if root == nil {
        return
    }
    dfs(root, targetSum)
    preOrder(root.Left, targetSum)
    preOrder(root.Right, targetSum)
}

func dfs(root *TreeNode, targetSum int) {
    if root == nil {
        return
    }
    targetSum -= root.Val
    if targetSum == 0 {
        count++
    }
    dfs(root.Left, targetSum)
    dfs(root.Right, targetSum)
}

448. Find All Numbers Disappeared in an Array

使用额外数组按下标存储原数组元素，再将为 0 的数据返回。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

func findDisappearedNumbers(nums []int) []int {
    arr := make([]int, len(nums))
    for i := range nums {
        arr[nums[i]-1] = 1
    }

    res := make([]int, 0)    // 存放结果

    for i := range arr {
        if arr[i] == 0 {
            res = append(res, i + 1)
        }
    }
    return res
}

优化，将每个数字按下标加上一个大于等于长度的值，这样除了缺失的位置，其他数字都会变大。

func findDisappearedNumbers(nums []int) []int {
    length := len(nums)
    for _, v := range nums {
        v = (v - 1) % length
        nums[v] += length
    }

    res := make([]int, 0)

    for i := range nums {
        if nums[i] <= length {
            res = append(res, i + 1)
        }
    }

    return res
}

453. Minimum Moves to Equal Array Elements

数学

设 $n$ 为数组长度，则有：

$result = sum(nums) - n * min(nums)$

时间复杂度：$O(n)$

求 sum 和 min 的时间开销。在 Go 中，求 n 的时间复杂度为 $O(1)$。
空间复杂度：$O(1)$

func minMoves(nums []int) int {
    minNum := nums[0]
    total := 0
    for i := range nums {
        if nums[i] < minNum {
            minNum = nums[i]
        }
        total += nums[i]
    }

    length := len(nums)

    return total - length * minNum
}

461. Hamming Distance

位运算

异或运算，统计 1 的个数。

func hammingDistance(x int, y int) int {
    count := 0
    z := x ^ y
    for z != 0 {
        count += z & 1
        z = z >> 1
    }
    return count
}

优化如下：

func hammingDistance(x int, y int) int {
    count := 0
    z := x ^ y
    for z != 0 {
        z = z & (z - 1)
        count++
    }
    return count
}

470. Implement Rand10() Using Rand7()

拒绝采样

rand7() + rand7() 生成 49 个数，去掉后九个数，前 40 个数每个数的出现概率都是 $1 \over 49$。

func rand10() int {
    for {
        row, col := rand7(), rand7()
        index := (row - 1) * 7 + col
        if index <= 40 {
            return index % 10 + 1
        }
    }
}

476. Number Complement

位运算

func findComplement(num int) int {
    bit := 1
    for bit <= num {
        num = num ^ bit
        bit = bit << 1
    }
    return num
}

494. Target Sum

回溯

简单回溯题解。

时间复杂度：$O(2^{n})$
空间复杂度：$O(n)$

var count int

func findTargetSumWays(nums []int, target int) int {
    count = 0
    dfs(nums, target, 0, 0)
    return count
}

func dfs(nums []int, target, tmp, idx int) {
    if idx == len(nums) {
        if tmp == target {
            count++
        }
        return
    }
    dfs(nums, target, tmp-nums[idx], idx+1)
    dfs(nums, target, tmp+nums[idx], idx+1)
}

动态规划

495. Teemo Attacking

遍历

放一个最大值，遍历时按情况减小即可。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

func findPoisonedDuration(timeSeries []int, duration int) int {
    ret := len(timeSeries) * duration
    for i := 0; i < len(timeSeries)-1; i++ {
        if sub := timeSeries[i+1] - timeSeries[i]; sub < duration {
            ret -= duration - sub
        }
    }
    return ret
}

减少运算次数（好像也没减少）：

func findPoisonedDuration(timeSeries []int, duration int) int {
    ret := len(timeSeries) * duration
    for i := 0; i < len(timeSeries)-1; i++ {
        if sub := duration - (timeSeries[i+1] - timeSeries[i]); sub > 0 {
            ret -= sub
        }    
    }
    return ret
}

501-600

541. Reverse String II

使用 do...while... 的循环解决数组长度小于 k 的问题。

时间复杂度：$O(n)$
空间复杂度（Go 实现）：$O(n)$
空间复杂度（原地修改）：$O(1)$

func reverseStr(s string, k int) string {
    str := []byte(s)
    for n := 0; ; n += 2*k {
        for i, j := n, min(n+k-1, len(str)-1); i < j; i, j = i+1, j-1 {
            str[i], str[j] = str[j], str[i]
        }
        if n+k > len(str) {
            break
        }
    }
    return string(str)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

543. Diameter of Binary Tree

递归

遍历整个树，把左右子树的深度和加起来，最大的深度和即答案。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var maxDepth int

func diameterOfBinaryTree(root *TreeNode) int {
    maxDepth = 0
    depth(root)
    return maxDepth
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    l := depth(root.Left)
    r := depth(root.Right)
    maxDepth = max(l + r, maxDepth)
    return max(l, r) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

575. Distribute Candies

哈希表

func distributeCandies(candyType []int) int {
    m := make(map[int]struct{})

    for i := range candyType {
        m[candyType[i]] = struct{}{}
    }

    if half := len(candyType) / 2; len(m) > half {
        return half
    }
    return len(m)
}

601-700

617. Merge Two Binary Trees

递归

递归方法合并二叉树最为简单。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil && root2 == nil {
        // 递归出口
        return nil
    }
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    root1.Val += root2.Val

    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)

    return root1
}

701-800

704. Binary Search

二分查找

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

func search(nums []int, target int) int {
    low, high := 0, len(nums)-1
    for low <= high {
        mid := (low+high)>>1
        if nums[mid] == target {
            return mid
        }
        if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

739. Daily Temperatures

单调栈

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))

    stack := []int{}

    for k, v := range temperatures {
        for len(stack) != 0 && v > temperatures[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[top] = k - top
        }
        stack = append(stack, k)
    }
    return res
}

781. Rabbits in Forest

数组

相同数字每num + 1个代表num + 1个兔子，可以使用 Map 来记录每一种数字出现的次数，当次数为 0，兔子的统计数量加上num + 1，非 0 时，则将其减一，不统计。

由题设，answers[i] < 1000，因此可以使用一个长度为 1000 的数组来代替 Map。

func numRabbits(answers []int) int {
    arr := make([]int, 1000)
    count := 0
    for _, v := range answers {
        if arr[v] == 0 {
            arr[v] = v
            count += v + 1
        } else {
            arr[v]--
        }
    }
    return count
}

贪心

先统计所有数字出现的次数，通过公式计算出结果。

如 1 出现了 3 次，则表示有 $\lceil{ {x+y}\over{y+1} }\rceil\cdot(y+1)$，$y = 1$，$x = 3$，即 3 个兔子。

func numRabbits(answers []int) (ans int) {
    count := map[int]int{}
    for _, y := range answers {
        count[y]++
    }
    for y, x := range count {
        ans += (x + y) / (y + 1) * (y + 1)
    }
    return
}

901-1000

912. Sort an Array

排序

快速排序，快排模板。

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

func quickSort(nums []int, low, high int) {
    if low >= high {
        return
    }
    pivot := nums[(low+high)/2]
    left, right := low, high
    for left <= right {
        for left <= right && nums[left] < pivot {
            left++
        }
        for left <= right && nums[right] > pivot {
            right--
        }
        if left <= right {
            nums[left], nums[right] = nums[right], nums[left]
            left++
            right--
        }
    }
    quickSort(nums, low, right)
    quickSort(nums, left, high)
}

946. Validate Stack Sequences

模拟

func validateStackSequences(pushed []int, popped []int) bool {
    stack := make([]int, 0)
    idx := 0
    for _, v := range pushed {
        stack = append(stack, v)
        for len(stack) > 0 && idx < len(popped) && popped[idx] == stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
            idx++
        }
    }
    return len(stack) == 0
}

990. Satisfiability of Equality Equations

采用并查集的思想，合并操作后判断几个元素是否在同一个集合内。

func equationsPossible(equations []string) bool {
    parent := make([]int, 26)
    for i := range parent {
        parent[i] = i
    }
    for _, str := range equations {
        if str[1] == '=' {
            x := int(str[0] - 'a')
            y := int(str[3] - 'a')
            union(parent, x, y)
        }
    }
    for _, str := range equations {
        if str[1] == '!' {
            x := int(str[0] - 'a')
            y := int(str[3] - 'a')
            if find(parent, x) == find(parent, y) {
                // 不相等的两个元素在同一集合内，与条件冲突
                return false
            }
        }
    }
    return true
}

// 合并
func union(parent []int, x, y int) {
    x = find(parent, x)
    y = find(parent, y)
    parent[x] = y
}

// 查询
func find(parent []int, x int) int {
    if parent[x] != x {
        parent[x] = find(parent, parent[x])
    }
    return parent[x]
}

1001-1100

1009. Complement of Base 10 Integer

位运算

func bitwiseComplement(n int) int {
    bit := 1
    if n == 0 {
        return n ^ bit
    }
    for bit <= n {
        n = n ^ bit
        bit = bit << 1
    }
    return n
}

更新于：2024年3月26日

Algorithms

Assembly Language

汇编语言的学习笔记，主要是对《汇编语言》（王爽）的总结、概括、补充以及实践。基础知识机器语言机器语言是机器指令的集合，以二进制表示，每一种 CPU 都有自己的机器指令集，机器指令指定 C...

剑指 Offer 刷题笔记

剑指 Offer 刷题记录。 3. 数组中重复的数字Ideas 遍历数组，将每个数字放入 Map 中，当遍历过程中发现键已在 Map 中时直接返回该键。题目中提到数组内的数字都在 0 到...

LeetCode 刷题笔记

Tags

1~100

2. Add Two Numbers

常规

滑动窗口（双指针）

翻转数字

转换为字符串

13. Roman to Integer

Ideas

Solutions

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

Ideas

Solutions

字符串替换

栈匹配

递归

去重*

双指针

双指针

31. Next Permutation

Ideas

Solutions

Go

Java

Go

Java

39. Combination Sum

Ideas

Solutions

Ideas

Solutions

46. Permutations

Ideas

Solutions

47. Permutations II

Ideas

Solutions

Hash Table

模拟

动态规划

分治

55. Jump Game

Ideas

Solutions

排序

双指针

61. Rotate List

Ideas

Solutions

动态规划

64. Minimum Path Sum

DP

数组

二分查找

二分查找

Java

回溯

DFS

83. Remove Duplicates from Sorted List

88. Merge Sorted Array

Ideas

Solutions

数学

92

Ideas

Solutions

94. Binary Tree Inorder Traversal

Ideas

Solutions

中序遍历（递归）

中序遍历（迭代）

100. Same Tree

Ideas

Solutions

101-200

101. Symmetric Tree

Ideas

Solutions