0501-0600-Easy

501.二叉搜索树中的众数(2)

  • 题目
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
    结点左子树中所含结点的值小于等于当前结点的值
    结点右子树中所含结点的值大于等于当前结点的值
    左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],
   1
    \
     2
    /
   2
返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归+哈希辅助 O(n) O(n)
02 递归+中序遍历 O(n) O(log(n))
func findMode(root *TreeNode) []int {
    m := map[int]int{}
    dfs(root, m)
    max := -1
    res := make([]int, 0)
    for i, v := range m {
        if max <= v {
            if max < v {
                max = v
                res = res[0:0]
            }
            res = append(res, i)
        }
    }
    return res
}

func dfs(root *TreeNode, rec map[int]int) {
    if root == nil {
        return
    }
    rec[root.Val]++
    dfs(root.Left, rec)
    dfs(root.Right, rec)
}

#
var max int
var res []int
var cur int
var count int

func findMode(root *TreeNode) []int {
    res = make([]int, 0)
    max, cur, count = 0, 0, 0
    dfs(root)
    return res
}

// 中序遍历保证利用二叉搜索树的性质,得到的结果是升序的
func dfs(root *TreeNode) {
    if root == nil {
        return
    }
    dfs(root.Left)
    if root.Val != cur {
        count = 0
    }
    count++
    if max < count {
        max = count
        res = []int{root.Val}
    } else if max == count {
        res = append(res, root.Val)
    }
    cur = root.Val
    dfs(root.Right)
}

504.七进制数(3)

  • 题目
给定一个整数,将其转化为7进制,并以字符串形式输出。
示例 1:输入: 100 输出: "202"
示例 2: 输入: -7 输出: "-10"
注意: 输入范围是 [-1e7, 1e7] 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(log(n)) O(1)
02 内置函数 O(log(n)) O(1)
03 递归 O(log(n)) O(log(n))
func convertToBase7(num int) string {
    if num == 0 {
        return "0"
    }

    minus := ""
    if num < 0 {
        minus = "-"
        num = -1 * num
    }

    s := ""
    for num > 0 {
        s = fmt.Sprintf("%d", num%7) + s
        num = num / 7
    }
    return minus + s
}

#
func convertToBase7(num int) string {
    return strconv.FormatInt(int64(num), 7)
}

#
func convertToBase7(num int) string {
    if num < 0 {
        return "-" + convertToBase7(-1*num)
    }
    if num < 7 {
        return strconv.Itoa(num)
    }
    return convertToBase7(num/7) + strconv.Itoa(num%7)
}

506.相对名次(1)

  • 题目
给出 N 名运动员的成绩,找出他们的相对名次并授予前三名对应的奖牌。
前三名运动员将会被分别授予 “金牌”,“银牌” 和“ 铜牌”
("Gold Medal", "Silver Medal", "Bronze Medal")。
(注:分数越高的选手,排名越靠前。)

示例 1:
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的,
因此将会分别被授予 “金牌”,“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员,我们只需要通过他们的成绩计算将其相对名次即可。
提示:
    N 是一个正整数并且不会超过 10000。
    所有运动员的成绩都不相同。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序+遍历 O(nlog(n)) O(n)
func findRelativeRanks(nums []int) []string {
    temp := make([]int, len(nums))
    copy(temp, nums)
    sort.Ints(temp)
    m := make(map[int]string)
    for i := 0; i < len(temp); i++ {
        if i == len(temp)-1 {
            m[temp[i]] = "Gold Medal"
        } else if i == len(temp)-2 {
            m[temp[i]] = "Silver Medal"
        } else if i == len(temp)-3 {
            m[temp[i]] = "Bronze Medal"
        } else {
            m[temp[i]] = strconv.Itoa(len(temp) - i)
        }
    }
    res := make([]string,0)
    for i := 0; i < len(nums); i++ {
        res = append(res, m[nums[i]])
    }
    return res
}

507.完美数(1)

  • 题目
对于一个 正整数,如果它和除了它自身以外的所有正因子之和相等,我们称它为“完美数”。
给定一个 整数 n, 如果他是完美数,返回 True,否则返回 False
示例:输入: 28 输出: True 解释: 28 = 1 + 2 + 4 + 7 + 14
提示:输入的数字 n 不会超过 100,000,000. (1e8)
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^1/2) O(1)
func checkPerfectNumber(num int) bool {
    if num == 1 {
        return false
    }
    sum := 1
    for i := 2; i <= num/i; i++ {
        if num%i == 0 {
            sum = sum + i + (num / i)
        }
    }
    return sum == num
}

509.斐波那契数(6)

  • 题目
斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。
该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。
示例 1:输入:2输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2:输入:3输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3:输入:4输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.
提示:
    0 ≤ N ≤ 30
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历+数组 O(n) O(n)
03 递归 O(2^n) O(n)
04 公式法 O(1) O(1)
05 矩阵快速幂 O(log(n)) O(1)
06 矩阵快速幂 O(n) O(1)
func fib(N int) int {
    if N == 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    n1, n2 := 0, 1
    for i := 2; i <= N; i++ {
        n1, n2 = n2, n1+n2
    }
    return n2
}

#
func fib(N int) int {
    if N == 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    res := make([]int, N+1)
    res[0] = 0
    res[1] = 1
    for i := 2; i <= N; i++ {
        res[i] = res[i-1] + res[i-2]
    }
    return res[N]
}

#
func fib(N int) int {
    if N == 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    return fib(N-1) + fib(N-2)
}

#
func fib(N int) int {
    temp1 := (1 + math.Sqrt(5)) / 2
    temp2 := (1 - math.Sqrt(5)) / 2
    fn := math.Round((math.Pow(temp1, float64(N))- math.Pow(temp2, float64(N)))/ math.Sqrt(5))
    return int(fn)
}

# 5
func fib(N int) int {
    if N == 0 {
        return 0
    }
    /*
        ans = [Fn+1 Fn
               Fn Fn-1]
            = [ 1 0
                 0 1]
    */
    ans := matrix{
        a: 1,
        b: 0,
        c: 0,
        d: 1,
    }
    m := matrix{
        a: 1,
        b: 1,
        c: 1,
        d: 0,
    }
    for N > 0 {
        if N%2 == 1 {
            ans = multi(ans, m)
        }
        m = multi(m, m)
        N = N >> 1
    }
    return ans.b
}

/*
a b
c d
*/
type matrix struct {
    a, b, c, d int
}

// 矩阵乘法
func multi(x, y matrix) matrix {
    newA := x.a*y.a + x.b*y.c
    newB := x.a*y.b + x.b*y.d
    newC := x.c*y.a + x.d*y.c
    newD := x.c*y.b + x.d*y.d
    return matrix{
        a: newA,
        b: newB,
        c: newC,
        d: newD,
    }
}

# 6
func fib(N int) int {
    if N == 0 {
        return 0
    }
    /*
        ans = [Fn+1 Fn
               Fn Fn-1]
            = [ 1 0
                 0 1]
    */
    ans := matrix{
        a: 1,
        b: 0,
        c: 0,
        d: 1,
    }
    m := matrix{
        a: 1,
        b: 1,
        c: 1,
        d: 0,
    }
    for N > 0 {
        ans = multi(ans, m)
        N--
    }
    return ans.b
}

/*
a b
c d
*/
type matrix struct {
    a, b, c, d int
}

// 矩阵乘法
func multi(x, y matrix) matrix {
    newA := x.a*y.a + x.b*y.c
    newB := x.a*y.b + x.b*y.d
    newC := x.c*y.a + x.d*y.c
    newD := x.c*y.b + x.d*y.d
    return matrix{
        a: newA,
        b: newB,
        c: newC,
        d: newD,
    }
}

520.检测大写字母(2)

  • 题目
给定一个单词,你需要判断单词的大写使用是否正确。
我们定义,在以下情况时,单词的大写用法是正确的:
    全部字母都是大写,比如"USA"。
    单词中所有字母都不是大写,比如"leetcode"。
    如果单词不只含有一个字母,只有首字母大写, 比如 "Google"。
否则,我们定义这个单词没有正确使用大写字母。
示例 1:输入: "USA"输出: True
示例 2:输入: "FlaG"输出: False
注意: 输入是由大写和小写拉丁字母组成的非空单词。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 正则 O(n) O(1)
func detectCapitalUse(word string) bool {
    if word == "" {
        return false
    }
    count := 0
    for i := 0; i < len(word); i++ {
        if word[i] >= 'A' && word[i] <= 'Z' {
            count++
        }
    }

    if count == 0 || count == len(word) ||
        (count == 1 && word[0] >= 'A' && word[0] <= 'Z') {
        return true
    }
    return false
}

#
func detectCapitalUse(word string) bool {
    pattern := "(^[a-z]+)$|(^[A-Z]+)$|(^[A-Z]{1}[a-z]*)$"
    isMatch, _ := regexp.MatchString(pattern, word)
    return isMatch
}

521.最长特殊序列Ⅰ(1)

  • 题目
给你两个字符串,请你从这两个字符串中找出最长的特殊序列。
「最长特殊序列」定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。

子序列 可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为其自身的子序列。

输入为两个字符串,输出最长特殊序列的长度。如果不存在,则返回 -1。

示例 1:输入: "aba", "cdc" 输出: 3 
解释: 最长特殊序列可为 "aba" (或 "cdc"),两者均为自身的子序列且不是对方的子序列。
示例 2:输入:a = "aaa", b = "bbb"输出:3
示例 3:输入:a = "aaa", b = "aaa"输出:-1
提示:
    两个字符串长度均处于区间 [1 - 100] 。
    字符串中的字符仅含有 'a'~'z' 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 比较 O(1) O(1)
func findLUSlength(a string, b string) int {
    if a == b {
        return -1
    }
    return max(len(a), len(b))
}

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

530.二叉搜索树的最小绝对差(3)

  • 题目
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
示例:
输入:

   1
    \
     3
    /
   2

输出:1
解释:
最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。
提示:
    树中至少有 2 个节点。
    本题与 783 https://leetcode.cn/problems/minimum-distance-between-bst-nodes/ 相同
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归+中序遍历 O(n) O(log(n))
02 递归+遍历 O(n) O(n)
03 迭代 O(n) O(n)
var minDiff, previous int
func getMinimumDifference(root *TreeNode) int {
    minDiff, previous  = math.MaxInt32, math.MaxInt32
    dfs(root)
    return minDiff
}

func dfs(root *TreeNode) {
    if root == nil {
        return
    }
    dfs(root.Left)

    newDiff := diff(previous, root.Val)
    if minDiff > newDiff {
        minDiff = newDiff
    }
    previous = root.Val
    dfs(root.Right)
}

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

#
func getMinimumDifference(root *TreeNode) int {
    arr := make([]int, 0)
    dfs(root, &arr)
    minDiff := arr[1] - arr[0]
    for i := 2; i < len(arr); i++ {
        if minDiff > arr[i]-arr[i-1] {
            minDiff = arr[i] - arr[i-1]
        }
    }
    return minDiff
}

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

532.数组中的K-diff数对(3)

  • 题目
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。
这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字,且两数之差的绝对值是 k.

示例 1: 输入: [3, 1, 4, 1, 5], k = 2 输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1,但我们只应返回不同的数对的数量。
示例 2:输入:[1, 2, 3, 4, 5], k = 1 输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:输入: [1, 3, 1, 5, 4], k = 0 输出: 1
解释: 数组中只有一个 0-diff 数对,(1, 1)。
注意:
    数对 (i, j) 和数对 (j, i) 被算作同一数对。
    数组的长度不超过10,000。
    所有输入的整数的范围在 [-1e7, 1e7]。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单哈希辅助 O(n) O(n)
02 双哈希辅助 O(n) O(n)
03 排序遍历 O(nlog(n)) O(1)
func findPairs(nums []int, k int) int {
    if k < 0 {
        return 0
    }
    record := make(map[int]int)
    for _, num := range nums {
        record[num]++
    }
    res := 0
    if k == 0 {
        for _, count := range record {
            if count > 1 {
                res++
            }
        }
        return res
    } else {
        for n := range record {
            if record[n-k] > 0 {
                res++
            }
        }
        return res
    }
}

#
func findPairs(nums []int, k int) int {
    if k < 0 {
        return 0
    }
    m := make(map[int]bool)
    res := make(map[int]bool)
    for _, value := range nums {
        if m[value-k] {
            res[value-k] = true
        }
        if m[value+k] {
            res[value] = true
        }
        m[value] = true
    }
    return len(res)
}

538.把二叉搜索树转换为累加树(2)

  • 题目
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),
使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如:
输入: 原始二叉搜索树:
              5
            /   \
           2     13
输出: 转换为累加树:
             18
            /   \
          20     13
注意:
本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/ 相同
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 栈辅助 O(n) O(n)
func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    dfs(root, &sum)
    return root
}

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

#
func convertBST(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    stack := make([]*TreeNode, 0)
    temp := root
    sum := 0
    for {
        if temp != nil {
            stack = append(stack, temp)
            temp = temp.Right
        } else if len(stack) != 0 {
            temp = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            temp.Val = temp.Val + sum
            sum = temp.Val
            temp = temp.Left
        } else {
            break
        }
    }
    return root
}

541.反转字符串II(2)

  • 题目
给定一个字符串和一个整数 k,你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。
如果剩余少于 k 个字符,则将剩余的所有全部反转。
如果有小于 2k 但大于或等于 k 个字符,则反转前 k 个字符,并将剩余的字符保持原样。

示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
要求:
    该字符串只包含小写的英文字母。
    给定字符串的长度和 k 在[1, 10000]范围内。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
func reverseStr(s string, k int) string {
    arr := []byte(s)
    for i := 0; i < len(s); i = i + 2*k {
        j := min(i+k, len(s))
        reverse(arr[i:j])
    }
    return string(arr)
}

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

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

#
func reverseStr(s string, k int) string {
    arr := []byte(s)
    for i := 0; i < len(s); i = i + k {
        if i%(2*k) == 0 {
            j := i + k
            if len(arr) < j {
                j = len(arr)
            }
            reverse(arr[i:j])
        }
    }
    return string(arr)
}

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

543.二叉树的直径(2)

  • 题目
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 栈辅助 O(n) O(n)
var res int
func diameterOfBinaryTree(root *TreeNode) int {
    res = 0
    dfs(root)
    return res
}

func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    path := max(left, right)
    res = max(left+right, res) // 当前节点最大直径与当前保存最大值比较
    return path + 1 // 以该节点为根的最大深度
}

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

#
func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    max := 0
    stack := make([]*TreeNode, 0)
    m := make(map[*TreeNode]int)

    cur := root
    var prev *TreeNode
    for cur != nil || len(stack) != 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        if cur.Right == nil || cur.Right == prev {
            cur = stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            leftLen := 0
            rightLen := 0
            if v, ok := m[cur.Left]; ok {
                leftLen = v
            }
            if v, ok := m[cur.Right]; ok {
                rightLen = v
            }
            if leftLen > rightLen {
                m[cur] = leftLen + 1
            } else {
                m[cur] = rightLen + 1
            }
            if max < leftLen+rightLen {
                max = leftLen + rightLen
            }
            prev = cur
            cur = nil
        } else {
            cur = cur.Right
        }
    }
    return max
}

551.学生出勤记录 I(2)

  • 题目
给定一个字符串来代表一个学生的出勤记录,这个记录仅包含以下三个字符:
    'A' : Absent,缺勤
    'L' : Late,迟到
    'P' : Present,到场
如果一个学生的出勤记录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。
你需要根据这个学生的出勤记录判断他是否会被奖赏。

示例 1:输入: "PPALLP"输出: True
示例 2:输入: "PPALLL"输出: False
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(1)
02 遍历 O(n) O(1)
func checkRecord(s string) bool {
    if strings.Count(s, "A") <= 1 && strings.Count(s, "LLL") == 0 {
        return true
    }
    return false
}

#
func checkRecord(s string) bool {
    aNum := 0
    lNum := 0
    for i := 0; i < len(s); i++ {
        if s[i] == 'A' {
            aNum++
        }
        if s[i] == 'L' {
            lNum++
        } else {
            lNum = 0
        }
        if aNum == 2 {
            return false
        }
        if lNum == 3 {
            return false
        }
    }
    return true
}

557.反转字符串中的单词 III(2)

  • 题目
给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 

注意:在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。
  • 解题思路分析
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
02 遍历 O(n) O(n)

func reverseWords(s string) string {
    strS := strings.Split(s, " ")
    for i, s := range strS {
        strS[i] = reverse(s)
    }
    return strings.Join(strS, " ")
}

func reverse(s string) string {
    arr := []byte(s)
    i, j := 0, len(arr)-1
    for i < j {
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
    return string(arr)
}

#
func reverseWords(s string) string {
    arr := []byte(s)
    j := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] == ' ' {
            reverse(arr, j, i-1)
            j = i + 1
        }
    }
    reverse(arr, j, len(arr)-1)
    return string(arr)
}

func reverse(arr []byte, i, j int) []byte {
    for i < j {
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
    return arr
}

559.N叉树的最大深度(2)

  • 题目
给定一个 N 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如,给定一个 3叉树 :
我们应返回其最大深度,3。
说明:
    树的深度不会超过 1000。
    树的节点总不会超过 5000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 迭代 O(n) O(n)
func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    depth := 0
    for _, node := range root.Children {
        depth = max(depth, maxDepth(node))
    }
    return depth + 1
}

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

#
func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    queue := make([]*Node, 0)
    depth := 0
    queue = append(queue, root)
    for len(queue) > 0 {
        length := len(queue)
        for i := 0; i < length; i++ {
            temp := queue[0]
            for _, node := range temp.Children {
                queue = append(queue, node)
            }
            queue = queue[1:]
        }
        depth++
    }
    return depth
}

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

561.数组拆分 I(2)

  • 题目
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,
使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:输入: [1,4,3,2]输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:
    n 是正整数,范围在 [1, 10000].
    数组中的元素范围在 [-10000, 10000].
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) P
02 数组辅助 O(n) O(1)
func arrayPairSum(nums []int) int {
    sort.Ints(nums)
    sum := 0
    for k, v := range nums {
        if k%2 == 0 {
            sum = sum + v
        }
    }
    return sum
}

#
func arrayPairSum(nums []int) int {
    var arr [20010]int
    for _, num := range nums {
        arr[num+10000]++
    }
    sum := 0
    needAdd := true
    for num, count := range arr {
        for count > 0 {
            if needAdd {
                sum = sum + num - 10000
            }
            needAdd = !needAdd
            count--
        }
    }
    return sum
}

563.二叉树的坡度(2)

  • 题目
给定一个二叉树,计算整个树的坡度。
一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。

示例:

输入: 
         1
       /   \
      2     3
输出: 1
解释: 
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
注意:
    任何子树的结点的和不会超过32位整数的范围。
    坡度的值不会超过32位整数的范围。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 迭代 O(n) O(n)
var total int

func findTilt(root *TreeNode) int {
    total = 0
    dfs(root)
    return total
}

func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    total = total + abs(left, right)
    return left + right + root.Val // 返回节点之和
}

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

#
func findTilt(root *TreeNode) int {
    if root == nil {
        return 0
    }
    stack := make([]*TreeNode, 0)
    stack = append(stack, root)
    list := make([]*TreeNode, 0)
    total := 0
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[0 : len(stack)-1]
        list = append([]*TreeNode{node}, list...)
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    for i := range list {
        node := list[i]
        left := 0
        right := 0
        if node.Left != nil {
            left = node.Left.Val
        }
        if node.Right != nil {
            right = node.Right.Val
        }
        total = total + abs(left, right)
        node.Val = left + right + node.Val
    }
    return total
}

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

566.重塑矩阵(2)

  • 题目
在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。
给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例 1:输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
输出: 
[[1,2,3,4]]
解释:行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

示例 2:输入: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
输出: 
[[1,2],
 [3,4]]
解释:没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意:
    给定矩阵的宽和高范围在 [1, 100]。
    给定的 r 和 c 都是正数。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(n^2)
02 遍历 O(n^2) O(n^2)
func matrixReshape(nums [][]int, r int, c int) [][]int {
    row, col := len(nums), len(nums[0])
    if (row*col != r*c) || (row == r && col == c) {
        return nums
    }
    res := make([][]int, r)
    for i := 0; i < len(res); i++ {
        res[i] = make([]int, c)
    }
    for i := 0; i < r*c; i++ {
        res[i/c][i%c] = nums[i/col][i%col]
    }
    return res
}

#
func matrixReshape(nums [][]int, r int, c int) [][]int {
    row, col := len(nums), len(nums[0])
    if (row*col != r*c) || (row == r && col == c) {
        return nums
    }
    res := make([][]int, 0)
    arr := make([]int, 0)
    count := 0
    for _, num := range nums {
        for _, value := range num {
            arr = append(arr, value)
            count++
            if count == c {
                res = append(res, arr)
                arr = []int{}
                count = 0
            }
        }
    }
    return res
}

572.另一个树的子树(3)

  • 题目
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。
s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
     3
    / \
   4   5
  / \
 1   2

给定的树 t:
   4 
  / \
 1   2
返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t:
   4
  / \
 1   2
返回 false。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n^2) O(log(n))
02 递归+字符串辅助 O(n) O(log(n))
03 栈辅助 O(n) O(n)
func isSubtree(s *TreeNode, t *TreeNode) bool {
    if s == nil {
        return false
    }
    return isSame(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func isSame(s *TreeNode, t *TreeNode) bool {
    if s == nil || t == nil{
        return t == s
    }
    return isSame(s.Left, t.Left) && isSame(s.Right, t.Right) && s.Val == t.Val
}

#
func isSubtree(s *TreeNode, t *TreeNode) bool {
    sStr := dfs(s, "")
    tStr := dfs(t, "")
    return strings.Contains(sStr, tStr)
}

func dfs(s *TreeNode, pre string) string {
    if s == nil {
        return pre
    }
    return fmt.Sprintf("#%d%s%s", s.Val, dfs(s.Left, "l"), dfs(s.Right, "r"))
}

#
func isSubtree(s *TreeNode, t *TreeNode) bool {
    sStr := preOrder(s)
    tStr := preOrder(t)
    return strings.Contains(sStr, tStr)
}

func preOrder(root *TreeNode) string {
    if root == nil {
        return ""
    }
    res := "!"
    stack := make([]*TreeNode,0)
    temp := root
    for {
        for temp != nil{
            res += strconv.Itoa(temp.Val)
            res += "!"
            stack = append(stack, temp)
            temp = temp.Left
        }
        res += "#!"
        if len(stack) > 0{
            node := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            temp = node.Right
        }else {
            break
        }
    }
    return res
}

575.分糖果(2)

  • 题目
给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。
你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:输入: candies = [1,1,2,2,3,3] 输出: 3
解析: 一共有三种种类的糖果,每一种都有两个。
     最优分配方案:妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 : 输入: candies = [1,1,2,3] 输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1],妹妹有两种不同的糖果,弟弟只有一种。
这样使得妹妹可以获得的糖果种类数最多。

注意:
    数组的长度为[2, 10,000],并且确定为偶数。
    数组中数字的大小在范围[-100,000, 100,000]内。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 排序遍历 O(nlog(n)) O(1)
func distributeCandies(candies []int) int {
    n := len(candies)
    r := make(map[int]bool, n)
    for _, c := range candies {
        r[c] = true
    }
    return min(len(r), n/2)
}

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

#
func distributeCandies(candies []int) int {
    length := len(candies)
    half := length / 2
    count := 1
    sort.Ints(candies)
    for i := 1; i < length; i++ {
        if candies[i] != candies[i-1] {
            count++
        }
    }
    if count >= half {
        return half
    }
    return count
}

581.最短无序连续子数组(3)

  • 题目
给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
你找到的子数组应是最短的,请输出它的长度。
示例 1:输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
说明 :
    输入的数组长度范围在 [1, 10,000]。
    输入的数组可能包含重复元素 ,所以升序的意思是<=。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 2次遍历 O(n) O(1)
03 排序遍历 O(nlog(n)) O(n)
func findUnsortedSubarray(nums []int) int {
    length := len(nums)
    left, right := 0, -1
    min, max := nums[length-1], nums[0]
    for i := 1; i < length; i++ {
        if max <= nums[i] {
            max = nums[i]
        } else {
            right = i
        }
        j := length - i - 1
        if min >= nums[j] {
            min = nums[j]
        } else {
            left = j
        }
    }
    return right - left + 1
}

#
func findUnsortedSubarray(nums []int) int {
    length := len(nums)
    right := -1
    max := nums[0]
    for i := 1; i < length; i++ {
        if max <= nums[i] {
            max = nums[i]
        } else {
            right = i
        }
    }
    if right == 0 {
        // 针对升序,特殊处理
        // 如去掉判断
        // 需要保证left,right初始值满足right-left+1=0
        return 0
    }
    left := 0
    min := nums[length-1]
    for i := length - 2; i >= 0; i-- {
        if min >= nums[i] {
            min = nums[i]
        } else {
            left = i
        }
    }
    return right - left + 1
}

#
func findUnsortedSubarray(nums []int) int {
    temp := make([]int,len(nums))
    copy(temp,nums)
    sort.Ints(temp)
    i, j := 0, len(nums)-1
    for i < len(nums) && nums[i] == temp[i]{
        i++
    }
    for i+1 < j && nums[j] == temp[j]{
        j--
    }
    return j-i+1
}

589.N叉树的前序遍历(2)

  • 题目
给定一个 N 叉树,返回其节点值的前序遍历。
例如,给定一个 3叉树 :
返回其前序遍历: [1,3,5,6,2,4]。
说明: 递归法很简单,你可以使用迭代法完成此题吗?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 迭代 O(n) O(n)
var res []int

func preorder(root *Node) []int {
    res = make([]int, 0)
    dfs(root)
    return res
}

func dfs(root *Node) {
    if root == nil {
        return
    }
    res = append(res, root.Val)
    for _, value := range root.Children {
        dfs(value)
    }
}

#
func preorder(root *Node) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }
    stack := make([]*Node, 0)
    stack = append(stack, root)
    for len(stack) > 0 {
        temp := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, temp.Val)
        for i := len(temp.Children) - 1; i >= 0; i-- {
            stack = append(stack, temp.Children[i])
        }
    }
    return res
}

590.N叉树的后序遍历(2)

  • 题目
给定一个 N 叉树,返回其节点值的后序遍历。

例如,给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单,你可以使用迭代法完成此题吗?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 迭代 O(n) O(n)
var res []int
func postorder(root *Node) []int {
    res = make([]int, 0)
    dfs(root)
    return res
}

func dfs(root *Node) {
    if root == nil {
        return
    }
    for _, value := range root.Children {
        dfs(value)
    }
    res = append(res, root.Val)
}

#
// 后序:(左右)根
// 前序:根(左右)=>根(右左)=>左右根
func postorder(root *Node) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }
    stack := make([]*Node, 0)
    stack = append(stack, root)
    for len(stack) > 0 {
        temp := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, temp.Val)
        for i := 0; i < len(temp.Children); i++ {
            stack = append(stack, temp.Children[i])
        }
    }
    for i := 0; i < len(res)/2; i++ {
        res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
    }
    return res
}

594.最长和谐子序列(2)

  • 题目
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在,给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度。
示例 1:输入: [1,3,2,2,5,2,3,7]输出: 5
原因: 最长的和谐数组是:[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 排序遍历 O(nlog(n)) O(1)
func findLHS(nums []int) int {
    m := make(map[int]int, len(nums))
    for _, n := range nums {
        m[n]++
    }
    res := 0
    for key, value := range m {
        value2, ok := m[key+1]
        if ok {
            t := value + value2
            if res < t {
                res = t
            }
        }
    }
    return res
}

#
func findLHS(nums []int) int {
    sort.Ints(nums)
    res := 0
    left := 0
    for i := 0; i < len(nums); i++ {
        for nums[i]-nums[left] > 1 {
            left++
        }
        if nums[i]-nums[left] == 1 {
            if res < i-left+1 {
                res = i - left + 1
            }
        }
    }
    return res
}

598.范围求和 II(1)

  • 题目
给定一个初始元素全部为 0,大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
操作用二维数组表示,其中的每个操作用一个含有两个正整数 a 和 b 的数组表示,
含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
在执行给定的一系列操作后,你需要返回矩阵中含有最大整数的元素个数。

示例 1:输入: m = 3, n = 3operations = [[2,2],[3,3]] 输出: 4
解释: 初始状态, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
执行完操作 [2,2] 后, M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]
执行完操作 [3,3] 后, M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
注意:
    m 和 n 的范围是 [1,40000]。
    a 的范围是 [1,m],b 的范围是 [1,n]。
    操作数目不超过 10000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(n) O(1)
func maxCount(m int, n int, ops [][]int) int {
    for _, o := range ops {
        m = min(m, o[0])
        n = min(n, o[1])
    }
    return m * n
}

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

599.两个列表的最小索引总和(2)

  • 题目
假设Andy和Doris想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。
你可以假设总是存在一个答案。

示例 1:输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”,它有最小的索引和1(0+1)。

提示:
    两个列表的长度范围都在 [1, 1000]内。
    两个列表中的字符串的长度将在[1,30]的范围内。
    下标从0开始,到列表的长度减1。
    两个列表都没有重复的元素。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 暴力法 O(n^2) I
func findRestaurant(list1 []string, list2 []string) []string {
    if len(list1) > len(list2) {
        list1, list2 = list2, list1
    }
    m2 := make(map[string]int, len(list2))
    for i := range list2 {
        m2[list2[i]] = i
    }
    min := 2000
    res := make([]string, 0, 1000)
    for key, value := range list1 {
        if key2, ok := m2[value]; ok {
            if min == key+key2 {
                res = append(res, value)
            }
            if min > key+key2 {
                min = key + key2
                res = []string{value}
            }
        }
    }
    return res
}

#
func findRestaurant(list1 []string, list2 []string) []string {
    min := 2000
    res := make([]string, 0, 1000)
    for key1, value1 := range list1 {
        for key2, value2 := range list2{
            if value1 == value2{
                if min == key1+key2 {
                    res = append(res, value1)
                }
                if min > key1+key2 {
                    min = key1 + key2
                    res = []string{value1}
                }
            }
        }
    }
    return res
}

0501-0600-Medium

503.下一个更大元素II(2)

  • 题目
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,
这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
示例 1:输入: [1,2,1] 输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
注意: 输入数组的长度不会超过 10000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单调栈 O(n) O(n)
02 单调栈 O(n) O(n)
func nextGreaterElements(nums []int) []int {
    res := make([]int, len(nums))
    if len(nums) == 0 {
        return res
    }
    for i := 0; i < len(nums); i++ {
        res[i] = -1
    }
    stack := make([]int, 0)
    for i := 0; i < len(nums)*2; i++ {
        index := i % len(nums)
        for len(stack) > 0 && nums[index] > nums[stack[len(stack)-1]] {
            if res[stack[len(stack)-1]] == -1 {
                res[stack[len(stack)-1]] = nums[index]
            }
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, index)
    }
    return res
}

# 2
func nextGreaterElements(nums []int) []int {
    res := make([]int, len(nums))
    if len(nums) == 0 {
        return res
    }
    stack := make([]int, 0)
    for i := 2*len(nums) - 1; i >= 0; i-- {
        index := i % len(nums)
        for len(stack) > 0 && nums[index] >= stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            res[index] = -1
        } else {
            res[index] = stack[len(stack)-1]
        }
        stack = append(stack, nums[index])
    }
    return res
}

508.出现次数最多的子树元素和(1)

  • 题目
给你一个二叉树的根结点,请你找出出现次数最多的子树元素和。
一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。
你需要返回出现次数最多的子树元素和。
如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。
示例 1:输入:
  5
 /  \
2   -3
返回[2, -3, 4],所有的值均只出现一次,以任意顺序返回所有值。
示例2:输入:
  5
 /  \
2   -5
返回[2],只有 2 出现两次,-5 只出现 1 次。
提示:假设任意子树元素和均可以用 32 位有符号整数表示。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(n)
var m map[int]int

func findFrequentTreeSum(root *TreeNode) []int {
    m = make(map[int]int)
    res := make([]int, 0)
    dfs(root)
    maxValue := 0
    for k, v := range m {
        if v > maxValue {
            maxValue = v
            res = []int{k}
        } else if maxValue == v {
            res = append(res, k)
        }
    }
    return res
}

func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }
    sum := root.Val + dfs(root.Left) + dfs(root.Right)
    m[sum]++
    return sum
}

513.找树左下角的值(2)

  • 题目
给定一个二叉树,在树的最后一行找到最左边的值。
示例 1:输入:
    2
   / \
  1   3
输出:1
示例 2:输入:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
输出:7
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 层序遍历 O(n) O(n)
02 递归 O(n) O(log(n))
func findBottomLeftValue(root *TreeNode) int {
    res := 0
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        length := len(queue)
        res = queue[0].Val
        for i := 0; i < length; i++ {
            if queue[i].Left != nil {
                queue = append(queue, queue[i].Left)
            }
            if queue[i].Right != nil {
                queue = append(queue, queue[i].Right)
            }
        }
        queue = queue[length:]
    }
    return res
}

# 2
var res int
var maxLevel int

func findBottomLeftValue(root *TreeNode) int {
    res = 0
    maxLevel = -1
    if root == nil {
        return res
    }
    dfs(root, 0)
    return res
}

func dfs(root *TreeNode, level int) {
    if root == nil {
        return
    }
    dfs(root.Left, level+1)
    if level > maxLevel {
        maxLevel = level
        res = root.Val
    }
    dfs(root.Right, level+1)
}

515.在每个树行中找最大值(2)

  • 题目
您需要在二叉树的每一行中找到最大的值。
示例:输入: 
          1
         / \
        3   2
       / \   \  
      5   3   9 
输出: [1, 3, 9]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 层序遍历 O(n) O(n)
02 递归 O(n) O(n)
func largestValues(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        length := len(queue)
        maxValue := math.MinInt32
        for i := 0; i < length; i++ {
            if queue[i].Left != nil {
                queue = append(queue, queue[i].Left)
            }
            if queue[i].Right != nil {
                queue = append(queue, queue[i].Right)
            }
            if maxValue < queue[i].Val {
                maxValue = queue[i].Val
            }
        }
        res = append(res, maxValue)
        queue = queue[length:]
    }
    return res
}

# 2
var res []int

func largestValues(root *TreeNode) []int {
    res = make([]int, 0)
    if root == nil {
        return res
    }
    dfs(root, 0)
    return res
}

func dfs(root *TreeNode, level int) {
    if root == nil {
        return
    }
    if level >= len(res) {
        res = append(res, math.MinInt32)
    }
    res[level] = max(res[level], root.Val)
    dfs(root.Left, level+1)
    dfs(root.Right, level+1)
}

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

516.最长回文子序列(3)

  • 题目
给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:输入:"bbbab"输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:输入:"cbbd"输出:2
一个可能的最长回文子序列为 "bb"。
提示:
    1 <= s.length <= 1000
    s 只包含小写英文字母
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
02 动态规划 O(n^2) O(n)
03 递归 O(n^2) O(n^2)
func longestPalindromeSubseq(s string) int {
    if len(s) <= 1 {
        return len(s)
    }
    n := len(s)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2 // 内层+2
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }
    return dp[0][n-1]
}

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

# 2
func longestPalindromeSubseq(s string) int {
    if len(s) <= 1 {
        return len(s)
    }
    n := len(s)
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = 1
    }
    for i := n - 1; i >= 0; i-- {
        prev := 0
        for j := i + 1; j < n; j++ {
            temp := dp[j]
            if s[i] == s[j] {
                dp[j] = prev + 2 // 内层+2
            } else {
                dp[j] = max(dp[j], dp[j-1])
            }
            prev = temp
        }
    }
    return dp[n-1]
}

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

# 3
var dp [][]int

func longestPalindromeSubseq(s string) int {
    if len(s) <= 1 {
        return len(s)
    }
    n := len(s)
    dp = make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    return dfs(s, 0, n-1)
}

func dfs(s string, i, j int) int {
    if i == j {
        return 1
    }
    if i > j {
        return 0
    }
    if dp[i][j] > 0 {
        return dp[i][j]
    }
    if s[i] == s[j] {
        dp[i][j] = dfs(s, i+1, j-1) + 2
    } else {
        dp[i][j] = max(dfs(s, i+1, j), dfs(s, i, j-1))
    }
    return dp[i][j]
}

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

518.零钱兑换II(2)

  • 题目
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 
示例 1:输入: amount = 5, coins = [1, 2, 5] 输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:输入: amount = 3, coins = [2] 输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:输入: amount = 10, coins = [10]  输出: 1
注意:你可以假设:
    0 <= amount (总金额) <= 5000
    1 <= coin (硬币面额) <= 5000
    硬币种类不超过 500 种
    结果符合 32 位符号整数
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划-二维 O(n^2) O(n^2)
02 动态规划-一维 O(n^2) O(n)
func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, amount+1)
        dp[i][0] = 1 // 金额为0的情况,只有都不选,组合情况为1
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= amount; j++ {
            if j-coins[i-1] >= 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[n][amount]
}

# 2
func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([]int, amount+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= amount; j++ {
            if j-coins[i-1] >= 0 {
                dp[j] = dp[j] + dp[j-coins[i-1]]
            }
        }
    }
    return dp[amount]
}

519.随机翻转矩阵(1)

  • 题目
题中给出一个 n_rows 行 n_cols 列的二维矩阵,且所有值被初始化为 0。
要求编写一个 flip 函数,均匀随机的将矩阵中的 0 变为 1,并返回该值的位置下标 [row_id,col_id];
同样编写一个 reset 函数,将所有的值都重新置为 0。
尽量最少调用随机函数 Math.random(),并且优化时间和空间复杂度。
注意:1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows 并且 0 <= col.id < n_cols
当矩阵中没有值为 0 时,不可以调用 flip 函数
调用 flip 和 reset 函数的次数加起来不会超过 1000 次
示例 1:输入:  ["Solution","flip","flip","flip","flip"]  [[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]
示例 2:输入:  ["Solution","flip","flip","reset","flip"] [[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]
输入语法解释:
输入包含两个列表:被调用的子程序和他们的参数。Solution 的构造函数有两个参数,分别为 n_rows 和 n_cols。
flip和 reset 没有参数,参数总会以列表形式给出,哪怕该列表为空
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
type Solution struct {
    m     map[int]bool
    rows  int
    cols  int
    total int
}

func Constructor(n_rows int, n_cols int) Solution {
    return Solution{
        m:     make(map[int]bool),
        rows:  n_rows,
        cols:  n_cols,
        total: 0,
    }
}

func (this *Solution) Flip() []int {
    if this.total >= this.rows*this.cols {
        return nil
    }
    for {
        index := rand.Intn(this.rows * this.cols)
        if this.m[index] == true {
            continue
        }
        a, b := index/this.cols, index%this.cols
        this.m[index] = true
        this.total++
        return []int{a, b}
    }
}

func (this *Solution) Reset() {
    this.m = make(map[int]bool)
    this.total = 0
}

522.最长特殊序列II(3)

  • 题目
给定字符串列表,你需要从它们中找出最长的特殊序列。
最长特殊序列定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。
子序列可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。
空序列为所有字符串的子序列,任何字符串为其自身的子序列。
输入将是一个字符串列表,输出是最长特殊序列的长度。如果最长特殊序列不存在,返回 -1 。
示例:输入: "aba", "cdc", "eae" 输出: 3
提示:所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(2^n) O(2^n)
02 暴力法 O(n^2) O(1)
03 暴力法 O(n^2) O(1)
func findLUSlength(strs []string) int {
    m := make(map[string]int)
    for i := 0; i < len(strs); i++ {
        total := 1 << (len(strs[i]))
        for j := 0; j < total; j++ {
            s := ""
            for k := 0; k < len(strs[i]); k++ {
                if (j>>k)&1 != 0 {
                    s = s + string(strs[i][k])
                }
            }
            m[s]++
        }
    }
    res := -1
    for k, v := range m {
        if v == 1 && len(k) > res {
            res = len(k)
        }
    }
    return res
}

# 2
func findLUSlength(strs []string) int {
    res := -1
    var j int
    for i := 0; i < len(strs); i++ {
        for j = 0; j < len(strs); j++ {
            if i == j {
                continue
            }
            if judge(strs[i], strs[j]) == true {
                break
            }
        }
        if j == len(strs) && len(strs[i]) > res {
            res = len(strs[i])
        }
    }

    return res
}

func judge(a, b string) bool {
    j := 0
    for i := 0; i < len(b) && j < len(a); i++ {
        if a[j] == b[i] {
            j++
        }
    }
    return j == len(a)
}

# 3
func findLUSlength(strs []string) int {
    sort.Slice(strs, func(i, j int) bool {
        return len(strs[i]) > len(strs[j])
    })
    res := -1
    var j int
    for i := 0; i < len(strs); i++ {
        for j = 0; j < len(strs); j++ {
            if i == j {
                continue
            }
            if judge(strs[i], strs[j]) == true {
                break
            }
        }
        if j == len(strs) {
            return len(strs[i])
        }
    }
    return res
}

func judge(a, b string) bool {
    j := 0
    for i := 0; i < len(b) && j < len(a); i++ {
        if a[j] == b[i] {
            j++
        }
    }
    return j == len(a)
}

523.连续的子数组和(2)

  • 题目
给定一个包含 非负数 的数组和一个目标 整数 k,编写一个函数来判断该数组是否含有连续的子数组,
其大小至少为 2,且总和为 k 的倍数,即总和为 n*k,其中 n 也是一个整数。
示例 1:输入:[23,2,4,6,7], k = 6 输出:True
解释:[2,4] 是一个大小为 2 的子数组,并且和为 6。
示例 2:输入:[23,2,6,4,7], k = 6 输出:True
解释:[23,2,6,4,7]是大小为 5 的子数组,并且和为 42。
说明:
    数组的长度不会超过 10,000 。
    你可以认为所有数字总和在 32 位有符号整数范围内。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 前缀和-暴力法 O(n^2) O(n)
func checkSubarraySum(nums []int, k int) bool {
    if len(nums) == 0 {
        return false
    }
    m := make(map[int]int)
    m[0] = -1
    sum := 0
    for i := 0; i < len(nums); i++ {
        sum = sum + nums[i]
        if k != 0 {
            sum = sum % k
        }
        if _, ok := m[sum]; ok {
            // 确保数组大小至少为2
            if i-m[sum] >= 2 {
                return true
            }
        } else {
            m[sum] = i
        }
    }
    return false
}

# 2
func checkSubarraySum(nums []int, k int) bool {
    if len(nums) == 0 {
        return false
    }
    arr := make([]int, len(nums))
    arr[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        arr[i] = arr[i-1] + nums[i]
    }
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            sum := arr[j] - arr[i] + nums[i]
            if sum == k || (k != 0 && sum%k == 0) {
                return true
            }
        }
    }
    return false
}

524.通过删除字母匹配到字典里最长单词(2)

  • 题目
给你一个字符串 s 和一个字符串数组 dictionary 作为字典,找出并返回字典中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个,返回长度最长且字典序最小的字符串。如果答案不存在,则返回空字符串。
示例 1:输入:s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] 输出:"apple"
示例 2:输入:s = "abpcplea", dictionary = ["a","b","c"] 输出:"a"
提示:1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序+子序列 O(n^2) O(1)
02 子序列 O(n^2) O(n)
func findLongestWord(s string, dictionary []string) string {
    sort.Slice(dictionary, func(i, j int) bool {
        if len(dictionary[i]) == len(dictionary[j]) {
            return dictionary[i] < dictionary[j]
        }
        return len(dictionary[i]) > len(dictionary[j])
    })
    for i := 0; i < len(dictionary); i++ {
        if isSubsequence(dictionary[i], s) {
            return dictionary[i]
        }
    }
    return ""
}

// leetcode392.判断子序列
func isSubsequence(s string, t string) bool {
    if len(s) > len(t) {
        return false
    }
    i := 0
    j := 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

# 2
func findLongestWord(s string, dictionary []string) string {
    res := ""
    for i := 0; i < len(dictionary); i++ {
        if isSubsequence(dictionary[i], s) {
            if len(dictionary[i]) > len(res) ||
                (len(dictionary[i]) == len(res) && dictionary[i] < res) {
                res = dictionary[i]
            }
        }
    }
    return res
}

// leetcode392.判断子序列
func isSubsequence(s string, t string) bool {
    if len(s) > len(t) {
        return false
    }
    i := 0
    j := 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

525.连续数组(1)

  • 题目
给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组(的长度)。
示例 1:输入: [0,1] 输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:输入: [0,1,0] 输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
注意:给定的二进制数组的长度不会超过50000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n) O(n)
func findMaxLength(nums []int) int {
    res := 0
    m := make(map[int]int)
    m[0] = -1
    total := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            total--
        } else {
            total++
        }
        if first, ok := m[total]; !ok {
            m[total] = i
        } else {
            if i-first > res {
                res = i - first
            }
        }
    }
    return res
}

526.优美的排列(2)

  • 题目
假设有从 1 到 N 的N个整数,如果从这N个数字中成功构造出一个数组,
使得数组的第 i位 (1 <= i <= N) 满足如下两个条件中的一个,我们就称这个数组为一个优美的排列。条件:
第i位的数字能被i整除
i 能被第 i 位上的数字整除
现在给定一个整数 N,请问可以构造多少个优美的排列?
示例1:输入: 2 输出: 2
解释: 
第 1 个优美的排列是 [1, 2]:
  第 1 个位置(i=1)上的数字是1,1能被 i(i=1)整除
  第 2 个位置(i=2)上的数字是2,2能被 i(i=2)整除
第 2 个优美的排列是 [2, 1]:
  第 1 个位置(i=1)上的数字是2,2能被 i(i=1)整除
  第 2 个位置(i=2)上的数字是1,i(i=2)能被 1 整除
说明:N 是一个正整数,并且不会超过15。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 回溯 O(n^n) O(n!)
02 回溯 O(n^n) O(n)
var res [][]int

func countArrangement(n int) int {
    res = make([][]int, 0)
    dfs(n, make([]int, 0), make([]bool, n+1))
    fmt.Println(res)
    return len(res)
}

func dfs(n int, path []int, visited []bool) {
    if len(path) == n {
        temp := make([]int, len(path))
        copy(temp, path)
        res = append(res, temp)
        return
    }
    for i := 1; i <= n; i++ {
        index := len(path) + 1
        if visited[i] == false && (i%index == 0 || index%i == 0) {
            visited[i] = true
            dfs(n, append(path, i), visited)
            visited[i] = false
        }
    }
}

# 2
var res int

func countArrangement(n int) int {
    res = 0
    dfs(n, make([]int, 0), make([]bool, n+1))
    return res
}

func dfs(n int, path []int, visited []bool) {
    if len(path) == n {
        res++
        return
    }
    for i := 1; i <= n; i++ {
        index := len(path) + 1
        if visited[i] == false && (i%index == 0 || index%i == 0) {
            visited[i] = true
            dfs(n, append(path, i), visited)
            visited[i] = false
        }
    }
}

528.按权重随机选择(1)

  • 题目
给定一个正整数数组w ,其中w[i]代表下标 i的权重(下标从 0 开始),
请写一个函数pickIndex,它可以随机地获取下标 i,选取下标 i的概率与w[i]成正比。
例如,对于 w = [1, 3],挑选下标 0 的概率为 1 / (1 + 3)= 0.25 (即,25%),
而选取下标 1 的概率为 3 / (1 + 3)= 0.75(即,75%)。
也就是说,选取下标 i 的概率为 w[i] / sum(w) 。
示例 1:输入:["Solution","pickIndex"] [[[1]],[]]输出: [null,0]
解释:Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0,因为数组中只有一个元素,所以唯一的选择是返回下标 0。
示例 2:输入: ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] 
[[[1,3]],[],[],[],[],[]]
输出:[null,1,1,1,1,0]
解释:Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1,返回下标 1,返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0,返回下标 0,返回该下标概率为 1/4 。
由于这是一个随机问题,允许多个答案,因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。
提示:1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex将被调用不超过10000次
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前缀和+二分查找 O(n) O(n)
type Solution struct {
    nums  []int
    total int
}

func Constructor(w []int) Solution {
    total := 0
    arr := make([]int, len(w)) // 前缀和
    for i := 0; i < len(w); i++ {
        total = total + w[i]
        arr[i] = total
    }
    return Solution{
        nums:  arr,
        total: total,
    }
}

func (this *Solution) PickIndex() int {
    target := rand.Intn(this.total)
    left, right := 0, len(this.nums)
    for left < right {
        mid := left + (right-left)/2
        if this.nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

529.扫雷游戏(2)

  • 题目
让我们一起来玩扫雷游戏!
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷,'E' 代表一个未挖出的空方块,
'B' 代表没有相邻(上,下,左,右,和所有4个对角线)地雷的已挖出的空白方块,
数字('1' 到 '8')表示有多少地雷与这块已挖出的方块相邻,'X' 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中('M'或者'E')的下一个点击位置(行和列索引),根据以下规则,
返回相应位置被点击后对应的面板:
    如果一个地雷('M')被挖出,游戏就结束了- 把它改为 'X'。
    如果一个没有相邻地雷的空方块('E')被挖出,修改它为('B'),
    并且所有和其相邻的未挖出方块都应该被递归地揭露。
    如果一个至少与一个地雷相邻的空方块('E')被挖出,修改它为数字('1'到'8'),表示相邻地雷的数量。
    如果在此次点击中,若无更多方块可被揭露,则返回面板。
示例 1:输入: [['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
输出: [['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
解释:示例 2:输入: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
输出: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
解释:
注意:输入矩阵的宽和高的范围为 [1,50]。
    点击的位置只能是未被挖出的方块 ('M' 或者 'E'),这也意味着面板至少包含一个可点击的方块。
    输入面板不会是游戏结束的状态(即有地雷已被挖出)。
    简单起见,未提及的规则在这个问题中可被忽略。
    例如,当游戏结束时你不需要挖出所有地雷,考虑所有你可能赢得游戏或标记方块的情况。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n^2)
02 广度优先搜索 O(n^2) O(n^2)
var dx = []int{-1, 1, 0, 0, 1, 1, -1, -1}
var dy = []int{0, 0, -1, 1, 1, -1, 1, -1}

func updateBoard(board [][]byte, click []int) [][]byte {
    x, y := click[0], click[1]
    if board[x][y] == 'M' {
        board[x][y] = 'X'
    } else {
        dfs(board, x, y)
    }
    return board
}

func dfs(board [][]byte, x, y int) {
    count := 0
    for i := 0; i < 8; i++ {
        newX := dx[i] + x
        newY := dy[i] + y
        if newX < 0 || newX >= len(board) || newY < 0 || newY >= len(board[0]) {
            continue
        }
        if board[newX][newY] == 'M' {
            count++
        }
    }
    if count > 0 {
        board[x][y] = byte(count + '0')
    } else {
        board[x][y] = 'B'
        for i := 0; i < 8; i++ {
            newX := dx[i] + x
            newY := dy[i] + y
            if newX < 0 || newX >= len(board) ||
                newY < 0 || newY >= len(board[0]) ||
                board[newX][newY] != 'E' {
                continue
            }
            dfs(board, newX, newY)
        }
    }
}

# 2
var dx = []int{-1, 1, 0, 0, 1, 1, -1, -1}
var dy = []int{0, 0, -1, 1, 1, -1, 1, -1}

func updateBoard(board [][]byte, click []int) [][]byte {
    x, y := click[0], click[1]
    if board[x][y] == 'M' {
        board[x][y] = 'X'
    } else {
        bfs(board, x, y)
    }
    return board
}

func bfs(board [][]byte, x, y int) {
    visited := make([][]bool, len(board))
    for i := 0; i < len(board); i++ {
        visited[i] = make([]bool, len(board[i]))
    }
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{x, y})
    visited[x][y] = true
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        count := 0
        a := node[0]
        b := node[1]
        for j := 0; j < 8; j++ {
            newX := dx[j] + a
            newY := dy[j] + b
            if newX < 0 || newX >= len(board) ||
                newY < 0 || newY >= len(board[0]) ||
                visited[newX][newY] == true {
                continue
            }
            if board[newX][newY] == 'M' {
                count++
            }
        }
        if count > 0 {
            board[a][b] = byte(count + '0')
        } else {
            board[a][b] = 'B'
            for j := 0; j < 8; j++ {
                newX := dx[j] + a
                newY := dy[j] + b
                if newX < 0 || newX >= len(board) ||
                    newY < 0 || newY >= len(board[0]) ||
                    board[newX][newY] != 'E' ||
                    visited[newX][newY] == true {
                    continue
                }
                queue = append(queue, [2]int{newX, newY})
                visited[newX][newY] = true
            }
        }
    }
}

537.复数乘法(2)

  • 题目
给定两个表示复数的字符串。
返回表示它们乘积的字符串。注意,根据定义 i2 = -1 。
示例 1:输入: "1+1i", "1+1i" 输出: "0+2i"
解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ,你需要将它转换为 0+2i 的形式。
示例 2:输入: "1+-1i", "1+-1i" 输出: "0+-2i"
解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ,你需要将它转换为 0+-2i 的形式。 
注意:输入字符串不包含额外的空格。
输入字符串将以a+bi 的形式给出,其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(1) O(1)
02 内置函数 O(1) O(1)
func complexNumberMultiply(a string, b string) string {
    a1, a2 := getValue(a)
    b1, b2 := getValue(b)
    return fmt.Sprintf("%d+%di", a1*b1-a2*b2, a1*b2+a2*b1)
}

func getValue(str string) (a, b int) {
    arr := strings.Split(str, "+")
    a, _ = strconv.Atoi(arr[0])
    b, _ = strconv.Atoi(arr[1][:len(arr[1])-1])
    return a, b
}

# 2
func complexNumberMultiply(a string, b string) string {
    var a1, a2, b1, b2 int
    fmt.Sscanf(a, "%d+%di", &a1, &a2)
    fmt.Sscanf(b, "%d+%di", &b1, &b2)
    return fmt.Sprintf("%d+%di", a1*b1-a2*b2, a1*b2+a2*b1)
}

539.最小时间差(2)

  • 题目
给定一个 24 小时制(小时:分钟 "HH:MM")的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1:输入:timePoints = ["23:59","00:00"] 输出:1
示例 2:输入:timePoints = ["00:00","23:59","00:00"]输出:0
提示:2 <= timePoints <= 2 * 104
timePoints[i] 格式为 "HH:MM"
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(n)
02 排序 O(nlog(n)) O(n)
func findMinDifference(timePoints []string) int {
    m := make(map[int]bool)
    for i := 0; i < len(timePoints); i++ {
        value := getValue(timePoints[i])
        if _, ok := m[value]; ok {
            return 0
        }
        m[value] = true
    }
    arr := make([]int, 0)
    for k := range m {
        arr = append(arr, k)
    }
    sort.Ints(arr)
    res := math.MaxInt32
    arr = append(arr, arr[0]+1440)
    for i := 1; i < len(arr); i++ {
        if res > arr[i]-arr[i-1] {
            res = arr[i] - arr[i-1]
        }
    }
    return res
}

func getValue(str string) int {
    hour, _ := strconv.Atoi(str[:2])
    minute, _ := strconv.Atoi(str[3:])
    return hour*60 + minute
}

# 2
func findMinDifference(timePoints []string) int {
    arr := make([]int, 0)
    for i := 0; i < len(timePoints); i++ {
        value := getValue(timePoints[i])
        arr = append(arr, value)
    }
    sort.Ints(arr)
    res := math.MaxInt32
    arr = append(arr, arr[0]+1440)
    for i := 1; i < len(arr); i++ {
        if res > arr[i]-arr[i-1] {
            res = arr[i] - arr[i-1]
        }
    }
    return res
}

func getValue(str string) int {
    hour, _ := strconv.Atoi(str[:2])
    minute, _ := strconv.Atoi(str[3:])
    return hour*60 + minute
}

540.有序数组中的单一元素(3)

  • 题目
给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。
示例 1:输入: [1,1,2,3,3,4,4,8,8]输出: 2
示例 2:输入: [3,3,7,7,10,11,11]输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 二分查找 O(log(n)) O(1)
03 异或 O(n) O(1)
func singleNonDuplicate(nums []int) int {
    for i := 0; i < len(nums)-1; i = i + 2 {
        if nums[i] != nums[i+1] {
            return nums[i]
        }
    }
    return nums[len(nums)-1]
}

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

# 3
func singleNonDuplicate(nums []int) int {
    res := 0
    for i := 0; i < len(nums); i++ {
        res = res ^ nums[i]
    }
    return res
}

542.01矩阵(3)

  • 题目
给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1: 输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2: 输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
    给定矩阵的元素个数不超过 10000。
    给定矩阵中至少有一个元素是 0。
    矩阵中的元素只在四个方向上相邻: 上、下、左、右。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
02 广度优先搜索 O(n^2) O(n^2)
03 动态规划 O(n^2) O(1)
func updateMatrix(matrix [][]int) [][]int {
    n := len(matrix)
    m := len(matrix[0])
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
        for j := 0; j < m; j++ {
            if matrix[i][j] == 1 {
                dp[i][j] = math.MaxInt32 / 10
                if i > 0 {
                    dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
                }
                if j > 0 {
                    dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
                }
            } else {
                dp[i][j] = 0
            }
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := m - 1; j >= 0; j-- {
            if dp[i][j] > 1 {
                if i < n-1 {
                    dp[i][j] = min(dp[i][j], dp[i+1][j]+1)
                }
                if j < m-1 {
                    dp[i][j] = min(dp[i][j], dp[i][j+1]+1)
                }
            }
        }
    }
    return dp
}

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

# 2
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}

func updateMatrix(matrix [][]int) [][]int {
    n := len(matrix)
    m := len(matrix[0])
    queue := make([][2]int, 0)
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if matrix[i][j] == 0 {
                queue = append(queue, [2]int{i, j})
            } else {
                matrix[i][j] = -1
            }
        }
    }
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for i := 0; i < 4; i++ {
            x := node[0] + dx[i]
            y := node[1] + dy[i]
            if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] == -1 {
                matrix[x][y] = matrix[node[0]][node[1]] + 1
                queue = append(queue, [2]int{x, y})
            }
        }
    }
    return matrix
}

# 3
func updateMatrix(matrix [][]int) [][]int {
    n := len(matrix)
    m := len(matrix[0])
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if matrix[i][j] == 1 {
                matrix[i][j] = math.MaxInt32 / 10
                if i > 0 {
                    matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1)
                }
                if j > 0 {
                    matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1)
                }
            } else {
                matrix[i][j] = 0
            }
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := m - 1; j >= 0; j-- {
            if matrix[i][j] > 1 {
                if i < n-1 {
                    matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1)
                }
                if j < m-1 {
                    matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1)
                }
            }
        }
    }
    return matrix
}

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

547.省份数量(3)

  • 题目
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,
且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,
而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1:输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]输出:2
示例 2:输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出:3
提示:1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 并查集 O(n^2) O(n)
02 递归 O(n^2) O(n)
03 广度优先搜索 O(n^2) O(n)
func findCircleNum(M [][]int) int {
    n := len(M)
    fa = Init(n)
    count = n
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if M[i][j] == 1 {
                union(i, j)
            }
        }
    }
    return getCount()
}

var fa []int
var count int

// 初始化
func Init(n int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    count = n
    return arr
}

// 查询
func find(x int) int {
    if fa[x] == x {
        return x
    }
    // 路径压缩
    fa[x] = find(fa[x])
    return fa[x]
}

// 合并
func union(i, j int) {
    x, y := find(i), find(j)
    if x != y {
        fa[x] = y
        count--
    }
}

func query(i, j int) bool {
    return find(i) == find(j)
}

func getCount() int {
    return count
}

# 2
var arr []bool

func findCircleNum(M [][]int) int {
    n := len(M)
    arr = make([]bool, n)
    res := 0
    for i := 0; i < n; i++ {
        if arr[i] == false {
            dfs(M, i)
            res++
        }
    }
    return res
}

func dfs(M [][]int, index int) {
    for i := 0; i < len(M); i++ {
        if arr[i] == false && M[index][i] == 1 {
            arr[i] = true
            dfs(M, i)
        }
    }
}

# 3
func findCircleNum(M [][]int) int {
    n := len(M)
    arr := make([]bool, n)
    res := 0
    queue := make([]int, 0)
    for i := 0; i < n; i++ {
        if arr[i] == false {
            queue = append(queue, i)
            for len(queue) > 0 {
                node := queue[0]
                queue = queue[1:]
                arr[node] = true
                for j := 0; j < n; j++ {
                    if M[node][j] == 1 && arr[j] == false {
                        queue = append(queue, j)
                    }
                }
            }
            res++
        }
    }
    return res
}

553.最优除法(1)

  • 题目
给定一组正整数,相邻的整数之间将会进行浮点除法操作。例如,[2,3,4] -> 2 / 3 / 4 。
但是,你可以在任意位置添加任意数目的括号,来改变算数的优先级。
你需要找出怎么添加括号,才能得到最大的结果,并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
示例:输入: [1000,100,10,2] 输出: "1000/(100/10/2)"
解释:1000/(100/10/2) = 1000/((100/10)/2) = 200
但是,以下加粗的括号 "1000/((100/10)/2)" 是冗余的,
因为他们并不影响操作的优先级,所以你需要返回 "1000/(100/10/2)"。
其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
说明:输入数组的长度在 [1, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(n)
 func optimalDivision(nums []int) string {
     res := make([]string,0)
     for i := 0; i < len(nums); i++{
         res = append(res, strconv.Itoa(nums[i]))
     }
     if len(res) < 3{
         return strings.Join(res, "/")
     }
     return res[0]+"/("+strings.Join(res[1:],"/") + ")"
 }

554.砖墙(1)

  • 题目
你的面前有一堵矩形的、由多行砖块组成的砖墙。这些砖块高度相同但是宽度不同。
你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。
你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。
示例:输入: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]
输出: 2
解释: 提示:每一行砖块的宽度之和应该相等,并且不能超过 INT_MAX。
每一行砖块的数量在[1,10,000] 范围内,墙的高度在[1,10,000] 范围内,总的砖块数量不超过 20,000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2) O(n)
func leastBricks(wall [][]int) int {
    maxCount := 0
    m := make(map[int]int)
    for i := 0; i < len(wall); i++ {
        index := 0
        for j := 0; j < len(wall[i])-1; j++ {
            index = index + wall[i][j]
            m[index]++ // 保留去除开头和结尾的位置(空隙地方)
            if maxCount <= m[index] {
                maxCount = m[index]
            }
        }
    }
    return len(wall) - maxCount
}

556.下一个更大元素III(2)

  • 题目
给你一个正整数n ,请你找出符合条件的最小整数,其由重新排列 n中存在的每位数字组成,并且其值大于 n 。
如果不存在这样的正整数,则返回 -1 。
注意 ,返回的整数应当是一个 32 位整数 ,如果存在满足题意的答案,但不是 32 位整数 ,同样返回 -1 。
示例 1:输入:n = 12 输出:21
示例 2:输入:n = 21 输出:-1
提示:1 <= n <= 231 - 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(log(n)) O(log(n))
02 遍历 O(log(n)) O(log(n))
func nextGreaterElement(n int) int {
    arr := make([]int, 0)
    for n > 0 {
        arr = append(arr, n%10)
        n = n / 10
    }
    reverse(arr, 0, len(arr)-1)
    arr = nextPermutation(arr)
    if arr == nil {
        return -1
    }
    res := 0
    for i := 0; i < len(arr); i++ {
        res = res*10 + arr[i]
        if res > math.MaxInt32 {
            return -1
        }
    }
    return res
}

// leetcode31.下一个排列
func nextPermutation(nums []int) []int {
    n := len(nums)
    left := n - 2
    // 以12385764为例,从后往前找到5<7 的升序情况,目标值为左边的数5
    for left >= 0 && nums[left] >= nums[left+1] {
        left--
    }
    if left >= 0 { // 存在升序的情况
        right := n - 1
        // 从后往前,找到第一个大于目标值的数,如6>5,然后交换
        for right >= 0 && nums[right] <= nums[left] {
            right--
        }
        nums[left], nums[right] = nums[right], nums[left]
    } else {
        return nil
    }
    reverse(nums, left+1, n-1)
    return nums
}

func reverse(nums []int, left, right int) {
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

# 2
func nextGreaterElement(n int) int {
    nums := []byte(strconv.Itoa(n))
    length := len(nums)
    left := length - 2
    // 以12385764为例,从后往前找到5<7 的升序情况,目标值为左边的数5
    for left >= 0 && nums[left] >= nums[left+1] {
        left--
    }
    if left >= 0 { // 存在升序的情况
        right := length - 1
        // 从后往前,找到第一个大于目标值的数,如6>5,然后交换
        for right >= 0 && nums[right] <= nums[left] {
            right--
        }
        nums[left], nums[right] = nums[right], nums[left]
    } else {
        return -1
    }
    left = left + 1
    right := length - 1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
    res, _ := strconv.Atoi(string(nums))
    if res > math.MaxInt32 {
        return -1
    }
    return res
}

558.四叉树交集(1)

  • 题目
二进制矩阵中的所有元素不是 0 就是 1 。
给你两个四叉树,quadTree1 和 quadTree2。其中 quadTree1 表示一个 n * n 二进制矩阵,
而 quadTree2 表示另一个 n * n 二进制矩阵。
请你返回一个表示 n * n 二进制矩阵的四叉树,它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。
注意,当 isLeaf 为 False 时,你可以把 True 或者 False 赋值给节点,两种值都会被判题机制 接受 。
四叉树数据结构中,每个内部节点只有四个子节点。此外,每个节点都有两个属性:
val:储存叶子结点所代表的区域的值。1 对应 True,0 对应 False;
isLeaf: 当这个节点是一个叶子结点时为 True,如果它有 4 个子节点则为 False 。
class Node {
    public boolean val;
  public boolean isLeaf;
  public Node topLeft;
  public Node topRight;
  public Node bottomLeft;
  public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树:
如果当前网格的值相同(即,全为 0 或者全为 1),将 isLeaf 设为 True ,
将 val 设为网格相应的值,并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同,将 isLeaf 设为 False, 将 val 设为任意值,然后如下图所示,将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容,可以参考 wiki 。
四叉树格式:
输出为使用层序遍历后四叉树的序列化形式,其中 null 表示路径终止符,其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ,则表示它在列表[isLeaf, val] 中的值为 1 ;
如果 isLeaf 或者 val 的值为 False ,则表示值为 0 。
示例 1:输入:quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]], 
quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
输出:[[0,0],[1,1],[1,1],[1,1],[1,0]]
解释:quadTree1 和 quadTree2 如上所示。由四叉树所表示的二进制矩阵也已经给出。
如果我们对这两个矩阵进行按位逻辑或运算,则可以得到下面的二进制矩阵,由一个作为结果的四叉树表示。
注意,我们展示的二进制矩阵仅仅是为了更好地说明题意,你无需构造二进制矩阵来获得结果四叉树。
示例 2:输入:quadTree1 = [[1,0]], quadTree2 = [[1,0]] 输出:[[1,0]]
解释:两个数所表示的矩阵大小都为 1*1,值全为 0 
结果矩阵大小为 1*1,值全为 0 。
示例 3:输入:quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]] , quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]
输出:[[1,1]]
示例 4:输入:quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]],
quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
输出:[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
示例 5:输入:quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]], 
quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]
输出:[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]
提示:quadTree1 和 quadTree2 都是符合题目要求的四叉树,每个都代表一个 n * n 的矩阵。
n == 2^x ,其中 0 <= x <= 9.
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(n)
func intersect(quadTree1 *Node, quadTree2 *Node) *Node {
    res := &Node{}
    if quadTree1.IsLeaf == true { // 叶子节点
        if quadTree1.Val == true {
            return quadTree1
        }
        return quadTree2
    }
    if quadTree2.IsLeaf == true { // 叶子节点
        if quadTree2.Val == true {
            return quadTree2
        }
        return quadTree1
    }
    tL := intersect(quadTree1.TopLeft, quadTree2.TopLeft)
    tR := intersect(quadTree1.TopRight, quadTree2.TopRight)
    bL := intersect(quadTree1.BottomLeft, quadTree2.BottomLeft)
    bR := intersect(quadTree1.BottomRight, quadTree2.BottomRight)
    // 叶子节点判断
    if tL.IsLeaf == true && tR.IsLeaf == true && bL.IsLeaf == true && bR.IsLeaf == true &&
        tL.Val == tR.Val && tR.Val == bL.Val && bL.Val == bR.Val {
        res.IsLeaf = true
        res.Val = tL.Val // 4个值都相同
        return res
    }
    res.TopLeft = tL
    res.TopRight = tR
    res.BottomLeft = bL
    res.BottomRight = bR
    res.Val = false
    res.IsLeaf = false
    return res
}

560.和为K的子数组(4)

  • 题目
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明:数组的长度为 [1, 20,000]。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(1)
02 前缀和-遍历 O(n^2) O(n)
03 前缀和-哈希辅助 O(n) O(n)
04 前缀和-哈希辅助 O(n) O(n)
func subarraySum(nums []int, k int) int {
    res := 0
    for i := 0; i < len(nums); i++ {
        sum := 0
        for j := i; j < len(nums); j++ {
            sum = sum + nums[j]
            if sum == k {
                res++
            }
        }
    }
    return res
}

# 2
func subarraySum(nums []int, k int) int {
    if len(nums) == 0 {
        return 0
    }
    res := 0
    arr := make([]int, len(nums)+1)
    arr[0] = 0
    for i := 1; i <= len(nums); i++ {
        arr[i] = arr[i-1] + nums[i-1]
    }
    for i := 0; i <= len(nums); i++ {
        for j := 0; j < i; j++ {
            if arr[i]-arr[j] == k {
                res++
            }
        }
    }
    return res
}

# 3
func subarraySum(nums []int, k int) int {
    res := 0
    m := make(map[int]int)
    m[0] = 1 // 保证第一个k的存在
    sum := 0
    // sum[i:j]= sum[0:j]-sum[0:i],把sum[i:j]设为k,
    // 于是可以转化为sum[0:j]-k=sum[0:i]
    for i := 0; i < len(nums); i++ {
        sum = sum + nums[i]
        if _, ok := m[sum-k]; ok {
            res = res + m[sum-k]
        }
        m[sum]++
    }
    return res
}

# 4
func subarraySum(nums []int, k int) int {
    res := 0
    m := make(map[int][]int)
    m[0] = []int{-1} // 保证第一个k的存在
    sum := 0
    // sum[i:j]= sum[0:j]-sum[0:i],把sum[i:j]设为k,
    // 于是可以转化为sum[0:j]-k=sum[0:i]
    for i := 0; i < len(nums); i++ {
        sum = sum + nums[i]
        if _, ok := m[sum-k]; ok {
            res = res + len(m[sum-k])
            // 输出满足条件的子数组下标
            // for _, v := range m[sum-k] {
            //    fmt.Println(v+1, i)
            // }
        }
        m[sum] = append(m[sum], i)
    }
    return res
}

565.数组嵌套(4)

  • 题目
索引从0开始长度为N的数组A,包含0到N - 1的所有整数。找到最大的集合S并返回其大小,
其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素,S的下一个元素应该是A[A[i]],
之后是A[A[A[i]]]... 以此类推,不断添加直到S出现重复的元素。
示例1:输入: A = [5,4,0,3,1,6,2] 输出: 4
解释:  A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
提示:N是[1, 20,000]之间的整数。
A中不含有重复的元素。
A中的元素大小在[0, N-1]之间。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 哈希辅助 O(n) O(n)
03 遍历交换 O(n) O(1)
04 并查集 O(n) O(n)
func arrayNesting(nums []int) int {
    m := make(map[int]bool)
    res := 0
    for i := 0; i < len(nums); i++ {
        if m[nums[i]] == true {
            continue
        }
        count := 0
        cur := i
        for {
            count++
            m[cur] = true
            cur = nums[cur]
            if cur == i {
                break
            }
        }
        if count > res {
            res = count
        }
    }
    return res
}

# 2
func arrayNesting(nums []int) int {
    m := make(map[int]bool)
    res := 0
    for i := 0; i < len(nums); i++ {
        if m[nums[i]] == true {
            continue
        }
        count := 0
        cur := i
        for {
            count++
            m[cur] = true
            cur = nums[cur]
            if m[cur] == true {
                break
            }
        }
        if count > res {
            res = count
        }
    }
    return res
}

# 3
func arrayNesting(nums []int) int {
    res := 0
    for i := 0; i < len(nums); i++ {
        count := 1
        for nums[i] != i {
            count++
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
        }
        if count > res {
            res = count
        }
    }
    return res
}

# 4
func arrayNesting(nums []int) int {
    res := 0
    fa = Init(len(nums))
    for i := 0; i < len(nums); i++ {
        union(i, nums[i])
    }
    m := make(map[int]int)
    for i := 0; i < len(fa); i++ {
        m[find(i)]++
    }
    for _, v := range m {
        if v > res {
            res = v
        }
    }
    return res
}

var fa []int

// 初始化
func Init(n int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    return arr
}

// 查询
func find(x int) int {
    if fa[x] == x {
        return x
    }
    // 路径压缩
    fa[x] = find(fa[x])
    return fa[x]
}

// 合并
func union(i, j int) {
    x, y := find(i), find(j)
    if x != y {
        fa[x] = y
    }
}

567.字符串的排列(2)

  • 题目
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:输入: s1 = "ab" s2 = "eidbaooo" 输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:输入: s1= "ab" s2 = "eidboaoo" 输出: False
注意:输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 滑动窗口 O(n) O(1)
02 滑动窗口 O(n) O(1)
func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    arr1, arr2 := [26]int{}, [26]int{}
    for i := 0; i < len(s1); i++ {
        arr1[s1[i]-'a']++
        arr2[s2[i]-'a']++
    }
    for i := 0; i < len(s2)-len(s1); i++ {
        if arr1 == arr2 {
            return true
        }
        arr2[s2[i]-'a']--
        arr2[s2[i+len(s1)]-'a']++
    }
    return arr1 == arr2
}

# 2
func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    m1, m2 := make(map[byte]int), make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        m1[s1[i]-'a']++
        m2[s2[i]-'a']++
    }
    for i := 0; i < len(s2)-len(s1); i++ {
        if compare(m1, m2) {
            return true
        }
        m2[s2[i]-'a']--
        if m2[s2[i]-'a'] == 0 {
            delete(m2, s2[i]-'a')
        }
        m2[s2[i+len(s1)]-'a']++
    }
    return compare(m1, m2)
}

func compare(m1, m2 map[byte]int) bool {
    if len(m1) != len(m2) {
        return false
    }
    for k := range m1 {
        if m2[k] != m1[k] {
            return false
        }
    }
    return true
}

576.出界的路径数(2)

  • 题目
给定一个 m × n 的网格和一个球。球的起始坐标为(i,j),你可以将球移到相邻的单元格内,
或者往上、下、左、右四个方向上移动使球穿过网格边界。但是,你最多可以移动N次。
找出可以将球移出边界的路径数量。答案可能非常大,返回 结果 mod 109+ 7 的值。
示例 1:输入: m = 2, n = 2, N = 2, i = 0, j = 0 输出: 6
解释:
示例 2:输入: m = 1, n = 3, N = 3, i = 0, j = 1 输出: 12
解释:
说明:球一旦出界,就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n^3) O(n^3)
02 动态规划 O(n^3) O(n^3)
var dp [60][60][60]int
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007

func findPaths(m int, n int, N int, i int, j int) int {
    dp = [60][60][60]int{}
    for i := 0; i < 60; i++ {
        for j := 0; j < 60; j++ {
            for k := 0; k < 60; k++ {
                dp[i][j][k] = -1
            }
        }
    }
    return dfs(m, n, i+1, j+1, N) // 下标取正
}

func dfs(m, n, i, j, k int) int {
    if k < 0 { // 次数够了
        return 0
    }
    if i < 1 || i > m || j < 1 || j > n { // 出界次数+1
        return 1
    }
    if dp[i][j][k] != -1 {
        return dp[i][j][k]
    }
    dp[i][j][k] = 0
    for a := 0; a < 4; a++ { // 上下左右4个方向
        x := i + dx[a]
        y := j + dy[a]
        dp[i][j][k] = (dp[i][j][k] + dfs(m, n, x, y, k-1)) % mod
    }
    return dp[i][j][k]
}

# 2
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007

func findPaths(m int, n int, N int, i int, j int) int {
    dp := [60][60][60]int{}
    for k := 1; k <= N; k++ {
        for a := 0; a < m; a++ {
            for b := 0; b < n; b++ {
                for i := 0; i < 4; i++ {
                    x := a + dx[i]
                    y := b + dy[i]
                    if x < 0 || x >= m || y < 0 || y >= n { // 出界次数+1
                        dp[a][b][k]++
                    } else {
                        dp[a][b][k] = (dp[a][b][k] + dp[x][y][k-1]) % mod
                    }
                }
            }
        }
    }
    return dp[i][j][N] % mod
}

583.两个字符串的删除操作(3)

  • 题目
给定两个单词word1和word2,找到使得word1和word2相同所需的最小步数,
每步可以删除任意一个字符串中的一个字符。
示例:输入: "sea", "eat" 输出: 2
解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"
提示:给定单词的长度不超过500。
给定单词中的字符只含有小写字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
02 动态规划 O(n^2) O(n^2)
03 递归 O(n^2) O(n^2)
func minDistance(word1 string, word2 string) int {
    a, b := len(word1), len(word2)
    // 最长公共子序列
    dp := make([][]int, a+1)
    for i := 0; i <= a; i++ {
        dp[i] = make([]int, b+1)
    }
    for i := 1; i <= a; i++ {
        for j := 1; j <= b; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            }
        }
    }
    return a + b - 2*dp[a][b]
}

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

# 2
func minDistance(word1 string, word2 string) int {
    a, b := len(word1), len(word2)
    dp := make([][]int, a+1)
    for i := 0; i <= a; i++ {
        dp[i] = make([]int, b+1)
        dp[i][0] = i
    }
    for i := 0; i <= b; i++ {
        dp[0][i] = i
    }
    for i := 1; i <= a; i++ {
        for j := 1; j <= b; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
            }
        }
    }
    return dp[a][b]
}

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

# 3
var m [][]int

func minDistance(word1 string, word2 string) int {
    a, b := len(word1), len(word2)
    m = make([][]int, a+1)
    for i := 0; i <= a; i++ {
        m[i] = make([]int, b+1)
        for j := 0; j <= b; j++ {
            m[i][j] = -1
        }
    }
    total := dfs(word1, word2, 0, 0)
    return a + b - 2*total
}

func dfs(word1 string, word2 string, i, j int) int {
    if len(word1) == i || len(word2) == j {
        return 0
    }
    if m[i][j] > -1 {
        return m[i][j]
    }
    if word1[i] == word2[j] {
        m[i][j] = dfs(word1, word2, i+1, j+1) + 1
    } else {
        m[i][j] = max(dfs(word1, word2, i, j+1), dfs(word1, word2, i+1, j))
    }
    return m[i][j]
}

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

592.分数加减运算(1)

  • 题目
给定一个表示分数加减运算表达式的字符串,你需要返回一个字符串形式的计算结果。这个结果应该是不可约分的分数,即最简分数。
如果最终结果是一个整数,例如2,你需要将它转换成分数形式,其分母为1。所以在上述例子中, 2应该被转换为2/1。
示例1:输入:"-1/2+1/2" 输出: "0/1"
示例 2:输入:"-1/2+1/2+1/3" 输出: "1/3"
示例 3:输入:"1/3-1/2" 输出: "-1/6"
示例 4:输入:"5/3+1/3" 输出: "2/1"
说明:输入和输出字符串只包含'0' 到'9'的数字,以及'/', '+' 和'-'。
输入和输出分数格式均为±分子/分母。如果输入的第一个分数或者输出的分数是正数,则'+'会被省略掉。
输入只包含合法的最简分数,每个分数的分子与分母的范围是[1,10]。如果分母是1,意味着这个分数实际上是一个整数。
输入的分数个数范围是 [1,10]。
最终结果的分子与分母保证是 32 位整数范围内的有效整数。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(nlog(n)) O(n)
func fractionAddition(expression string) string {
    s := strings.ReplaceAll(expression, "-", "+-") // 替换-为+-
    s = strings.ReplaceAll(s, "/", "+")            // 替换/为+
    temp := strings.Split(s, "+")                  // 根据+切割
    arr := make([]int, 0)
    for i := 0; i < len(temp); i++ {
        if temp[i] == "" { // 第一个数的分子如果为负数,+切割会为空
            continue
        }
        value, _ := strconv.Atoi(temp[i])
        arr = append(arr, value)
    }
    a, b := 0, 1
    for i := 0; i < len(arr); i = i + 2 { // 遍历每个数:分子+分母
        c, d := arr[i], arr[i+1]
        // a/b+c/d=ad/bd+bc/bd=(ad+bc)/bd
        a = a*d + b*c
        b = b * d
        g := gcd(a, b)
        if g < 0 { // 约分为负数,需要转换为正数,这样确保分母一直为正数
            g = -g
        }
        a, b = a/g, b/g
    }
    return fmt.Sprintf("%d/%d", a, b)
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

593.有效的正方形(2)

  • 题目
给定二维空间中四点的坐标,返回四点是否可以构造一个正方形。
一个点的坐标(x,y)由一个有两个整数的整数数组表示。
示例:输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] 输出: True
注意:所有输入整数都在 [-10000,10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角(90度角)。
输入点没有顺序。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 几何 O(1) O(1)
02 几何 O(1) O(1)
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
    m := make(map[int]int)
    m[getDis(p1, p2)]++
    m[getDis(p1, p3)]++
    m[getDis(p1, p4)]++
    m[getDis(p2, p3)]++
    m[getDis(p2, p4)]++
    m[getDis(p3, p4)]++
    a, b := 0, 0
    for k, v := range m {
        if v == 2 {
            a = k
        } else if v == 4 {
            b = k
        } else {
            return false
        }
    }
    return len(m) == 2 && a == 2*b
}

func getDis(a, b []int) int {
    return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}

# 2
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
    arr := make([]int, 0)
    arr = append(arr, getDis(p1, p2))
    arr = append(arr, getDis(p1, p3))
    arr = append(arr, getDis(p1, p4))
    arr = append(arr, getDis(p2, p3))
    arr = append(arr, getDis(p2, p4))
    arr = append(arr, getDis(p3, p4))
    sort.Ints(arr)
    return arr[0] > 0 && arr[0] == arr[3] && arr[4] == arr[5] && arr[0]*2 == arr[4]
}

func getDis(a, b []int) int {
    return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}

0501-0600-Hard

502.IPO(2)

  • 题目
假设 力扣(LeetCode)即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司,
力扣 希望在 IPO 之前开展一些项目以增加其资本。 
由于资源有限,它只能在 IPO 之前完成最多 k 个不同的项目。
帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给定若干个项目。对于每个项目 i,它都有一个纯利润 Pi,并且需要最小的资本 Ci 来启动相应的项目。
最初,你有 W 资本。当你完成一个项目时,你将获得纯利润,且利润将被添加到你的总资本中。
总而言之,从给定项目中选择最多 k 个不同项目的列表,以最大化最终资本,并输出最终可获得的最多资本。
示例 1:输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
输出: 4
解释:由于你的初始资本为 0,你尽可以从 0 号项目开始。
在完成后,你将获得 1 的利润,你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目,所以你需要完成 2 号项目以获得最大的资本。
因此,输出最后最大化的资本,为 0 + 1 + 3 = 4。
注意:假设所有输入数字都是非负整数。
    表示利润和资本的数组的长度不超过 50000。
    答案保证在 32 位有符号整数范围内。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双堆 O(nlog(n)) O(n)
02 排序 O(nlog(n)) O(n)
func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
    maxProfit := &ProfitNode{}
    minCapital := &CapitalNode{}
    heap.Init(maxProfit)
    heap.Init(minCapital)
    for i := 0; i < len(Profits); i++ {
        heap.Push(minCapital, Node{
            Profits: Profits[i],
            Capital: Capital[i],
        })
    }
    for i := 0; i < k; i++ {
        for minCapital.Len() > 0 {
            node := heap.Pop(minCapital).(Node)
            if node.Capital <= W {
                heap.Push(maxProfit, node)
            } else {
                heap.Push(minCapital, node)
                break
            }
        }
        if maxProfit.Len() == 0 {
            return W
        }
        node := heap.Pop(maxProfit).(Node)
        W = W + node.Profits
    }
    return W
}

type Node struct {
    Profits int
    Capital int
}

type ProfitNode []Node

func (h ProfitNode) Len() int {
    return len(h)
}

// 小根堆<,大根堆变换方向>
func (h ProfitNode) Less(i, j int) bool {
    return h[i].Profits > h[j].Profits
}

func (h ProfitNode) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *ProfitNode) Push(x interface{}) {
    *h = append(*h, x.(Node))
}

func (h *ProfitNode) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

type CapitalNode []Node

func (h CapitalNode) Len() int {
    return len(h)
}

// 小根堆<,大根堆变换方向>
func (h CapitalNode) Less(i, j int) bool {
    return h[i].Capital < h[j].Capital
}

func (h CapitalNode) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *CapitalNode) Push(x interface{}) {
    *h = append(*h, x.(Node))
}

func (h *CapitalNode) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

# 2
type Node struct {
    profit  int
    capital int
}

func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
    arr := make([]Node, 0)
    for i := 0; i < len(Profits); i++ {
        arr = append(arr, Node{
            profit:  Profits[i],
            capital: Capital[i],
        })
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i].profit > arr[j].profit
    })
    index := 0
    for k > 0 {
        if index == len(arr) {
            return W
        }
        // 挑选一个满足条件的项目,利润最大即可
        if arr[index].capital <= W {
            k--
            W = W + arr[index].profit
            arr = append(arr[:index], arr[index+1:]...)
            index = 0
            continue
        }
        index++
    }
    return W
}

514.自由之路(2)

  • 题目
电子游戏“辐射4”中,任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘,
并使用表盘拼写特定关键词才能开门。
给定一个字符串ring,表示刻在外环上的编码;给定另一个字符串key,表示需要拼写的关键词。
您需要算出能够拼写关键词中所有字符的最少步数。
最初,ring的第一个字符与12:00方向对齐。
您需要顺时针或逆时针旋转 ring 以使key的一个字符在 12:00 方向对齐,
然后按下中心按钮,以此逐个拼写完key中的所有字符。
旋转ring拼出 key 字符key[i]的阶段中:
您可以将ring顺时针或逆时针旋转一个位置,计为1步。
旋转的最终目的是将字符串ring的一个字符与 12:00 方向对齐,并且这个字符必须等于字符key[i] 。
如果字符key[i]已经对齐到12:00方向,您需要按下中心按钮进行拼写,这也将算作1 步。
按完之后,您可以开始拼写key的下一个字符(下一阶段), 直至完成所有拼写。
示例:输入: ring = "godding", key = "gd" 输出: 4
解释: 对于 key 的第一个字符 'g',已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd',我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。
提示:ring 和key的字符串长度取值范围均为1 至100;
两个字符串中都只有小写字符,并且均可能存在重复字符;
字符串key一定可以由字符串 ring旋转拼出。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^3) O(n^2)
02 递归 O(n^3) O(n^2)
func findRotateSteps(ring string, key string) int {
    maxValue := math.MaxInt32 / 10
    n := len(key)
    m := len(ring)
    dp := make([][]int, n) // dp[i][j] => key[:i+1],ring[:j+1]的最少步数
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
        for j := 0; j < m; j++ {
            dp[i][j] = maxValue
        }
    }
    arr := [26][]int{}
    for i := 0; i < len(ring); i++ {
        value := int(ring[i] - 'a')
        arr[value] = append(arr[value], i)
    }
    for _, v := range arr[key[0]-'a'] {
        dp[0][v] = min(v, m-v) + 1 // 移到次数
    }
    for i := 1; i < n; i++ {
        for _, j := range arr[key[i]-'a'] { // 枚举当前字母位置
            for _, k := range arr[key[i-1]-'a'] { // 枚举上一个字母位置
                minValue := min(abs(j-k), m-abs(j-k))
                dp[i][j] = min(dp[i][j], dp[i-1][k]+minValue+1)
            }
        }
    }
    res := math.MaxInt32
    for i := 0; i < m; i++ {
        res = min(res, dp[n-1][i])
    }
    return res
}

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

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

# 2
var dp [][]int
var arr [26][]int

func findRotateSteps(ring string, key string) int {
    n := len(key)
    m := len(ring)
    dp = make([][]int, n) // dp[i][j] => key[:i+1],ring[:j+1]的最少步数
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
        for j := 0; j < m; j++ {
            dp[i][j] = -1
        }
    }
    arr = [26][]int{}
    for i := 0; i < len(ring); i++ {
        value := int(ring[i] - 'a')
        arr[value] = append(arr[value], i)
    }
    return n + dfs(key, ring, 0, 0)
}

func dfs(key, ring string, keyIndex, ringIndex int) int {
    if keyIndex == len(key) {
        return 0
    }
    if dp[keyIndex][ringIndex] != -1 {
        return dp[keyIndex][ringIndex]
    }
    cur := int(key[keyIndex] - 'a')
    res := math.MaxInt32
    for _, v := range arr[cur] {
        minValue := min(abs(ringIndex-v), len(ring)-abs(ringIndex-v))
        res = min(res, minValue+dfs(key, ring, keyIndex+1, v))
    }
    dp[keyIndex][ringIndex] = res
    return res
}

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

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

517.超级洗衣机(1)

  • 题目
假设有 n台超级洗衣机放在同一排上。开始的时候,每台洗衣机内可能有一定量的衣服,也可能是空的。
在每一步操作中,你可以选择任意 m(1 ≤ m ≤ n)台洗衣机,与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量,请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。
如果不能使每台洗衣机中衣物的数量相等,则返回 -1。
示例 1:输入: [1,0,5] 输出: 3
解释: 第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   
示例 2:输入: [0,3,0] 输出: 2
解释:  第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     
示例 3:输入: [0,2,0] 输出: -1
解释:  不可能让所有三个洗衣机同时剩下相同数量的衣物。
提示:n 的范围是 [1, 10000]。
在每台超级洗衣机中,衣物数量的范围是 [0, 1e5]。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(1)
 func findMinMoves(machines []int) int {
     n := len(machines)
     sum := 0
     for i := 0; i < n; i++ {
         sum = sum + machines[i]
     }
     if sum%n != 0 { // 先判断
         return -1
     }
     per := sum / n // 最终每个洗衣机里面的衣服数
     for i := 0; i < n; i++ {
         machines[i] = machines[i] - per // 计算每个洗衣机需要拿出或者需要放入的衣服数
     }
     maxValue := 0
     curSum := 0
     res := 0
     // 注意:选择任意m台,不要求连续
     // 2种情况:
     // 1、数组的最大值:是取出,每次一件,会有最大值的次数
     // 2、前缀和的最大绝对值:前面多余或者需要的数量
     for i := 0; i < n; i++ {
         curSum = curSum + machines[i]              // 前缀和:需要移动curSum件衣服到当前节点
         maxValue = max(maxValue, abs(curSum))      // 需要移动的最大值
         res = max(res, max(maxValue, machines[i])) // 取:数组的最大值和数组前缀和的绝对值的最大值中的较大值
     }
     return res
 }

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

 func abs(a int) int {
     if a < 0 {
         return -a
     }
     return a
 }

535.TinyURL的加密与解密(2)

  • 题目
TinyURL是一种URL简化服务, 比如:当你输入一个URLhttps://leetcode.com/problems/design-tinyurl时,
它将返回一个简化的URLhttp://tinyurl.com/4e9iAk.
要求:设计一个 TinyURL 的加密encode和解密decode的方法。
你的加密和解密算法如何设计和运作是没有限制的,你只需要保证一个URL可以被加密成一个TinyURL,
并且这个TinyURL可以用解密方法恢复成原本的URL。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(1) O(n)
02 哈希辅助 O(1) O(n)
type Codec struct {
    m     map[string]string
    index int
}

func Constructor() Codec {
    return Codec{
        m:     make(map[string]string),
        index: 1,
    }
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
    res := "http://tinyurl.com/" + strconv.Itoa(this.index)
    this.m[res] = longUrl
    this.index++
    return res
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
    return this.m[shortUrl]
}

# 2
type Codec struct {
    m     map[string]string
    index int
}

func Constructor() Codec {
    return Codec{
        m:     make(map[string]string),
        index: 1,
    }
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
    str := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    res := "http://tinyurl.com/"
    this.index++
    count := this.index
    temp := make([]byte, 0)
    for count > 0 {
        temp = append(temp, str[count%62])
        count = count / 62
    }
    res = res + string(temp)
    this.m[res] = longUrl
    return res
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
    return this.m[shortUrl]
}

546.移除盒子

题目

给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。
每一轮你可以移除具有相同颜色的连续 k 个盒子(k>= 1),这样一轮之后你将得到 k * k 个积分。
当你将所有盒子都去掉之后,求你能获得的最大积分和。
示例 1:输入:boxes = [1,3,2,2,2,3,4,3,1] 输出:23
解释:[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)
示例 2:输入:boxes = [1,1,1] 输出:9
示例 3:输入:boxes = [1] 输出:1
提示:1 <= boxes.length <= 100
1 <= boxes[i]<= 100

解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(1)


552.学生出勤记录II(1)

  • 题目
给定一个正整数n,返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 
答案可能非常大,你只需返回结果mod 109 + 7的值。
学生出勤记录是只包含以下三个字符的字符串:
'A' : Absent,缺勤
'L' : Late,迟到
'P' : Present,到场
如果记录不包含多于一个'A'(缺勤)或超过两个连续的'L'(迟到),则该记录被视为可奖励的。
示例 1:输入: n = 2 输出: 8 
解释:有8个长度为2的记录将被视为可奖励:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励,因为缺勤次数超过一次。
注意:n 的值不会超过100000。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(1)
var mod = 1000000007

func checkRecord(n int) int {
    dp := [6]int{}
    dp[0] = 1 // 0A 0L
    dp[1] = 1 // 0A 1L
    dp[2] = 0 // 0A 2L
    dp[3] = 1 // 1A 0L
    dp[4] = 0 // 1A 1L
    dp[5] = 0 // 1A 2L
    for i := 2; i <= n; i++ {
        temp := [6]int{}
        temp[0] = (dp[0] + dp[1] + dp[2]) % mod                         // +P
        temp[1] = dp[0]                                                 // +L
        temp[2] = dp[1]                                                 // +L
        temp[3] = (dp[0] + dp[1] + dp[2] + dp[3] + dp[4] + dp[5]) % mod // 0、1、2+A,3、4、5+P
        temp[4] = dp[3]                                                 // +L
        temp[5] = dp[4]                                                 // +L
        dp = temp
    }
    res := 0
    for i := 0; i < len(dp); i++ {
        res = (res + dp[i]) % 1000000007
    }
    return res
}

600.不含连续1的非负整数(1)

  • 题目
给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续的1的个数。
示例 1:输入: 5 输出: 5
解释: 下面是带有相应二进制表示的非负整数<= 5:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中,只有整数3违反规则(有两个连续的1),其他5个满足规则。
说明: 1 <= n <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(log(n)) O(log(n))
func findIntegers(n int) int {
    dp := make(map[int]int) // dp[i]=>高度为i,根节点为0的满二叉树,不包含连续1的路径数量(下标从1开始)
    dp[1] = 1               // 高度为1的时候,只有0等1种情况
    dp[2] = 2               // 高度为2的时候,有00、01等2种情况
    for i := 3; i <= 32; i++ {
        dp[i] = dp[i-1] + dp[i-2] // 左子树(0)+右子树的左子树(10)的数量
    }
    res := 0
    prev := 0
    for i := 32; i >= 1; i-- { // 从最高位开始遍历进行替换(下标从1开始)
        if n&(1<<(i-1)) > 0 { // 第i位为1,替换该位,前缀不变
            // 1xxx1xx => 0xxxxxx => 该位变为0
            // 1xxx1xx => 1xxx0xx => 该位变为0,前缀不变
            res = res + dp[i] // 高度为i:高度=i,根节点为0的都小于n(把i位的1替换为0)
            if prev == 1 {    // 出现连续1退出,比如后面使用1011xx的前缀就不满足题目要求了
                break
            }
            prev = 1
        } else {
            prev = 0
        }
        if i == 1 { // 如果能走到最后1位,也要算上n,说明n也满足条件(小于等于n,即n也算1次)
            res++
        }
    }
    return res
}
Copyright © Zhi2014 2023 all right reserved,powered by Gitbook该文件修订时间: 2023-10-23 15:20:51

results matching ""

    No results matching ""