2101-2200-Easy

2108.找出数组中的第一个回文字符串(1)

  • 题目
给你一个字符串数组 words ,找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串,返回一个 空字符串 "" 。
回文字符串 的定义为:如果一个字符串正着读和反着读一样,那么该字符串就是一个 回文字符串 。
示例 1:输入:words = ["abc","car","ada","racecar","cool"] 输出:"ada"
解释:第一个回文字符串是 "ada" 。
注意,"racecar" 也是回文字符串,但它不是第一个。
示例 2:输入:words = ["notapalindrome","racecar"] 输出:"racecar"
解释:第一个也是唯一一个回文字符串是 "racecar" 。
示例 3:输入:words = ["def","ghi"] 输出:""
解释:不存在回文字符串,所以返回一个空字符串。
提示:1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func firstPalindrome(words []string) string {
    for i := 0; i < len(words); i++ {
        if isPalindrome(words[i]) == true {
            return words[i]
        }
    }
    return ""
}

func isPalindrome(a string) bool {
    i, j := 0, len(a)-1
    for i < j {
        if a[i] != a[j] {
            return false
        }
        i++
        j--
    }
    return true
}

2103.环和杆(2)

  • 题目
总计有 n 个环,环的颜色可以是红、绿、蓝中的一种。这些环分布穿在 10 根编号为 0 到 9 的杆上。
给你一个长度为 2n 的字符串 rings ,表示这 n 个环在杆上的分布。rings 中每两个字符形成一个 颜色位置对 ,用于描述每个环:
第 i 对中的 第一个 字符表示第 i 个环的 颜色('R'、'G'、'B')。
第 i 对中的 第二个 字符表示第 i 个环的 位置,也就是位于哪根杆上('0' 到 '9')。
例如,"R3G2B1" 表示:共有 n == 3 个环,红色的环在编号为 3 的杆上,绿色的环在编号为 2 的杆上,蓝色的环在编号为 1 的杆上。
找出所有集齐 全部三种颜色 环的杆,并返回这种杆的数量。
示例 1:输入:rings = "B0B6G0R6R0R6G9" 输出:1
解释:- 编号 0 的杆上有 3 个环,集齐全部颜色:红、绿、蓝。
- 编号 6 的杆上有 3 个环,但只有红、蓝两种颜色。
- 编号 9 的杆上只有 1 个绿色环。
因此,集齐全部三种颜色环的杆的数目为 1 。
示例 2:输入:rings = "B0R0G0R9R0B0G0" 输出:1
解释:- 编号 0 的杆上有 6 个环,集齐全部颜色:红、绿、蓝。
- 编号 9 的杆上只有 1 个红色环。
因此,集齐全部三种颜色环的杆的数目为 1 。
示例 3:输入:rings = "G4"输出:0
解释:只给了一个环,因此,不存在集齐全部三种颜色环的杆。
提示:rings.length == 2 * n
1 <= n <= 100
如 i 是 偶数 ,则rings[i] 的值可以取 'R'、'G' 或 'B'(下标从 0 开始计数)
如 i 是 奇数 ,则rings[i] 的值可以取 '0' 到 '9' 中的一个数字(下标从 0 开始计数)
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历+位运算 O(n) O(1)
02 遍历+哈希 O(n) O(1)
func countPoints(rings string) int {
    m := map[byte]int{
        'R': 1,
        'G': 2,
        'B': 4,
    }
    arr := make([]int, 10)
    for i := 0; i < len(rings); i = i + 2 {
        v := int(rings[i+1] - '0')
        arr[v] = arr[v] | m[rings[i]]
    }
    res := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] == 7 {
            res++
        }
    }
    return res
}

# 2
func countPoints(rings string) int {
    m := make(map[byte]map[byte]bool)
    for i := 0; i < 10; i++ {
        m[byte(i+'0')] = make(map[byte]bool)
    }
    for i := 0; i < len(rings); i = i + 2 {
        m[rings[i+1]][rings[i]] = true
    }
    res := 0
    for _, v := range m {
        if len(v) == 3 {
            res++
        }
    }
    return res
}

2114.句子中的最多单词数(2)

  • 题目
一个 句子由一些 单词以及它们之间的单个空格组成,句子的开头和结尾不会有多余空格。
给你一个字符串数组sentences,其中sentences[i]表示单个 句子。
请你返回单个句子里 单词的最多数目。
示例 1:输入:sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
输出:6
解释:- 第一个句子 "alice and bob love leetcode" 总共有 5 个单词。
- 第二个句子 "i think so too" 总共有 4 个单词。
- 第三个句子 "this is great thanks very much" 总共有 6 个单词。
所以,单个句子中有最多单词数的是第三个句子,总共有 6 个单词。
示例 2:输入:sentences = ["please wait", "continue to fight", "continue to win"]输出:3
解释:可能有多个句子有相同单词数。
这个例子中,第二个句子和第三个句子(加粗斜体)有相同数目的单词数。
提示:1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i]只包含小写英文字母和' '。
sentences[i]的开头和结尾都没有空格。
sentences[i]中所有单词由单个空格隔开。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 遍历 O(n) O(1)
func mostWordsFound(sentences []string) int {
    res := 0
    for i := 0; i < len(sentences); i++ {
        arr := strings.Fields(sentences[i])
        if len(arr) > res {
            res = len(arr)
        }
    }
    return res
}

# 2

func mostWordsFound(sentences []string) int {
    res := 0
    for i := 0; i < len(sentences); i++ {
        count := strings.Count(sentences[i], " ") + 1
        if count > res {
            res = count
        }
    }
    return res
}

2119.反转两次的数字(1)

  • 题目
反转 一个整数意味着倒置它的所有位。
例如,反转 2021 得到 1202 。反转 12300 得到 321 ,不保留前导零 。
给你一个整数 num ,反转 num 得到 reversed1 ,接着反转 reversed1 得到 reversed2 。
如果 reversed2 等于 num ,返回 true ;否则,返回 false 。
示例 1:输入:num = 526 输出:true
解释:反转 num 得到 625 ,接着反转 625 得到 526 ,等于 num 。
示例 2:输入:num = 1800 输出:false
解释:反转 num 得到 81 ,接着反转 81 得到 18 ,不等于 num 。 
示例 3:输入:num = 0 输出:true
解释:反转 num 得到 0 ,接着反转 0 得到 0 ,等于 num 。
提示:0 <= num <= 106
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(1) O(1)
func isSameAfterReversals(num int) bool {
    return num == 0 || num%10 != 0
}

2124.检查是否所有A都在B之前(2)

  • 题目
给你一个 仅 由字符 'a' 和 'b' 组成的字符串 s 。
如果字符串中 每个 'a' 都出现在 每个 'b' 之前,返回 true ;否则,返回 false 。
示例 1:输入:s = "aaabbb" 输出:true
解释:'a' 位于下标 0、1 和 2 ;而 'b' 位于下标 3、4 和 5 。
因此,每个 'a' 都出现在每个 'b' 之前,所以返回 true 。
示例 2:输入:s = "abab" 输出:false
解释:存在一个 'a' 位于下标 2 ,而一个 'b' 位于下标 1 。
因此,不能满足每个 'a' 都出现在每个 'b' 之前,所以返回 false 。
示例 3:输入:s = "bbb" 输出:true
解释:不存在 'a' ,因此可以视作每个 'a' 都出现在每个 'b' 之前,所以返回 true 。
提示:1 <= s.length <= 100
s[i] 为 'a' 或 'b'
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(n)
02 内置函数 O(n) O(1)
func checkString(s string) bool {
    arr := []byte(s)
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] < arr[j]
    })
    return string(arr) == s
}

# 2
func checkString(s string) bool {
    return strings.Contains(s, "ba") == false
}

2129.将标题首字母大写(1)

  • 题目
给你一个字符串title,它由单个空格连接一个或多个单词组成,每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写:
如果单词的长度为1或者2,所有字母变成小写。
否则,将单词首字母大写,剩余字母变成小写。
请你返回 大写后的title。
示例 1:输入:title = "capiTalIze tHe titLe" 输出:"Capitalize The Title"
解释:由于所有单词的长度都至少为 3 ,将每个单词首字母大写,剩余字母变为小写。
示例 2:输入:title = "First leTTeR of EACH Word" 出:"First Letter of Each Word"
解释:单词 "of" 长度为 2 ,所以它保持完全小写。
其他单词长度都至少为 3 ,所以其他单词首字母大写,剩余字母小写。
示例 3:输入:title = "i lOve leetcode" 出:"i Love Leetcode"
解释:单词 "i" 长度为 1 ,所以它保留小写。
其他单词长度都至少为 3 ,所以其他单词首字母大写,剩余字母小写。
提示:1 <= title.length <= 100
title由单个空格隔开的单词组成,且不含有任何前导或后缀空格。
每个单词由大写和小写英文字母组成,且都是 非空的。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
 func capitalizeTitle(title string) string {
     arr := strings.Fields(title)
     for i := 0; i < len(arr); i++ {
         arr[i] = strings.ToLower(arr[i])
         if len(arr[i]) > 2 {
             arr[i] = strings.Title(arr[i])
         }
     }
     return strings.Join(arr, " ")
 }

2133.检查是否每一行每一列都包含全部整数(1)

  • 题目
对一个大小为 n x n 的矩阵而言,如果其每一行和每一列都包含从 1 到 n 的 全部 整数(含 1 和 n),则认为该矩阵是一个 有效 矩阵。
给你一个大小为 n x n 的整数矩阵 matrix ,请你判断矩阵是否为一个有效矩阵:如果是,返回 true ;否则,返回 false 。
示例 1:输入:matrix = [[1,2,3],[3,1,2],[2,3,1]] 输出:true
解释:在此例中,n = 3 ,每一行和每一列都包含数字 1、2、3 。
因此,返回 true 。
示例 2:输入:matrix = [[1,1,1],[1,2,3],[1,2,3]] 输出:false
解释:在此例中,n = 3 ,但第一行和第一列不包含数字 2 和 3 。
因此,返回 false 。
提示:n == matrix.length == matrix[i].length
1 <= n <= 100
1 <= matrix[i][j] <= n
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2) O(n)
func checkValid(matrix [][]int) bool {
    n, m := len(matrix), len(matrix[0])
    for i := 0; i < n; i++ {
        visited := make(map[int]bool)
        for j := 0; j < m; j++ {
            if visited[matrix[i][j]] == true {
                return false
            }
            visited[matrix[i][j]] = true
        }
    }
    for j := 0; j < m; j++ {
        visited := make(map[int]bool)
        for i := 0; i < n; i++ {
            if visited[matrix[i][j]] == true {
                return false
            }
            visited[matrix[i][j]] = true
        }
    }
    return true
}

2138.将字符串拆分为若干长度为k的组(1)

  • 题目
字符串 s 可以按下述步骤划分为若干长度为 k 的组:
第一组由字符串中的前 k 个字符组成,第二组由接下来的 k 个字符串组成,依此类推。每个字符都能够成为 某一个 组的一部分。
对于最后一组,如果字符串剩下的字符 不足 k 个,需使用字符 fill 来补全这一组字符。
注意,在去除最后一个组的填充字符 fill(如果存在的话)并按顺序连接所有的组后,所得到的字符串应该是 s 。
给你一个字符串 s ,以及每组的长度 k 和一个用于填充的字符 fill ,
按上述步骤处理之后,返回一个字符串数组,该数组表示 s 分组后 每个组的组成情况 。
示例 1:输入:s = "abcdefghi", k = 3, fill = "x" 输出:["abc","def","ghi"]
解释:前 3 个字符是 "abc" ,形成第一组。
接下来 3 个字符是 "def" ,形成第二组。
最后 3 个字符是 "ghi" ,形成第三组。
由于所有组都可以由字符串中的字符完全填充,所以不需要使用填充字符。
因此,形成 3 组,分别是 "abc"、"def" 和 "ghi" 。
示例 2:输入:s = "abcdefghij", k = 3, fill = "x" 出:["abc","def","ghi","jxx"]
解释:与前一个例子类似,形成前三组 "abc"、"def" 和 "ghi" 。
对于最后一组,字符串中仅剩下字符 'j' 可以用。为了补全这一组,使用填充字符 'x' 两次。
因此,形成 4 组,分别是 "abc"、"def"、"ghi" 和 "jxx" 。
提示:1 <= s.length <= 100
s 仅由小写英文字母组成
1 <= k <= 100
fill 是一个小写英文字母
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func divideString(s string, k int, fill byte) []string {
    n := len(s)
    res := make([]string, 0)
    for i := 0; i < n; i = i + k {
        if i+k <= n {
            res = append(res, s[i:i+k])
        } else {
            res = append(res, s[i:]+strings.Repeat(string(fill), k-(n-i)))
        }
    }
    return res
}

2144.打折购买糖果的最小开销(1)

  • 题目
一家商店正在打折销售糖果。每购买 两个糖果,商店会 免费送一个糖果。
免费送的糖果唯一的限制是:它的价格需要小于等于购买的两个糖果价格的 较小值。
比方说,总共有 4个糖果,价格分别为1,2,3和4,一位顾客买了价格为2 和3的糖果,那么他可以免费获得价格为 1的糖果,
但不能获得价格为4的糖果。
给你一个下标从 0开始的整数数组cost,其中cost[i]表示第i个糖果的价格,请你返回获得 所有糖果的 最小总开销。
示例 1:输入:cost = [1,2,3] 输出:5
解释:我们购买价格为 2 和 3 的糖果,然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一方案。
注意,我们不能购买价格为 1 和 3 的糖果,并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
示例 2:输入:cost = [6,5,7,9,2,2] 输出:23
解释:最小总开销购买糖果方案为:
- 购买价格为 9 和 7 的糖果
- 免费获得价格为 6 的糖果
- 购买价格为 5 和 2 的糖果
- 免费获得价格为 2 的最后一个糖果
因此,最小总开销为 9 + 7 + 5 + 2 = 23 。
示例 3:输入:cost = [5,5] 输出:10
解释:由于只有 2 个糖果,我们需要将它们都购买,而且没有免费糖果。
所以总最小开销为 5 + 5 = 10 。
提示:1 <= cost.length <= 100
1 <= cost[i] <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
func minimumCost(cost []int) int {
    sort.Slice(cost, func(i, j int) bool {
        return cost[i] > cost[j]
    })
    res := 0
    for i := 0; i < len(cost); i++ {
        if i%3 != 2 {
            res = res + cost[i]
        }
    }
    return res
}

2148.元素计数(2)

  • 题目
给你一个整数数组 nums ,统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。
示例 1:输入:nums = [11,7,2,15] 输出:2
解释:元素 7 :严格较小元素是元素 2 ,严格较大元素是元素 11 。
元素 11 :严格较小元素是元素 7 ,严格较大元素是元素 15 。
总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
示例 2:输入:nums = [-3,3,3,90] 输出:2
解释:元素 3 :严格较小元素是元素 -3 ,严格较大元素是元素 90 。
由于有两个元素的值为 3 ,总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
提示:1 <= nums.length <= 100
-105 <= nums[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
02 遍历 O(n) O(1)
func countElements(nums []int) int {
    sort.Ints(nums)
    minValue, maxValue := nums[0], nums[len(nums)-1]
    res := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != minValue && nums[i] != maxValue {
            res++
        }
    }
    return res
}

# 2
func countElements(nums []int) int {
    minValue, maxValue := nums[0], nums[0]
    minCount, maxCount := 1, 1
    for i := 1; i < len(nums); i++ {
        if nums[i] > maxValue {
            maxValue = nums[i]
            maxCount = 1
        } else if nums[i] == maxValue {
            maxCount++
        }
        if nums[i] < minValue {
            minValue = nums[i]
            minCount = 1
        } else if nums[i] == minValue {
            minCount++
        }
    }
    if maxValue == minValue {
        return 0
    }
    return len(nums) - maxCount - minCount
}

2154.将找到的值乘以2(2)

  • 题目
给你一个整数数组 nums ,另给你一个整数 original ,这是需要在 nums 中搜索的第一个数字。
接下来,你需要按下述步骤操作:
如果在 nums 中找到 original ,将 original乘以 2 ,得到新 original(即,令 original = 2 * original)。
否则,停止这一过程。
只要能在数组中找到新 original ,就对新 original 继续 重复 这一过程。
返回 original 的 最终 值。
示例 1:输入:nums = [5,3,6,1,12], original = 3 输出:24
解释: - 3 能在 nums 中找到。3 * 2 = 6 。
- 6 能在 nums 中找到。6 * 2 = 12 。
- 12 能在 nums 中找到。12 * 2 = 24 。
- 24 不能在 nums 中找到。因此,返回 24 。
示例 2:输入:nums = [2,7,9], original = 4 输出:4
解释:- 4 不能在 nums 中找到。因此,返回 4 。
提示:1 <= nums.length <= 1000
1 <= nums[i], original <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希 O(n) O(n)
02 排序 O(nlog(n)) O(1)
func findFinalValue(nums []int, original int) int {
    m := make(map[int]bool)
    for i := 0; i < len(nums); i++ {
        m[nums[i]] = true
    }
    for m[original] == true {
        original = original * 2
    }
    return original
}

# 2
func findFinalValue(nums []int, original int) int {
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        if nums[i] == original {
            original = original * 2
        }
    }
    return original
}

2160.拆分数位后四位数字的最小和(1)

  • 题目
给你一个四位正整数num。请你使用 num中的 数位 ,将num拆成两个新的整数new1和new2。
new1 和new2中可以有前导 0,且num中 所有数位都必须使用。
比方说,给你num = 2932,你拥有的数位包括:两个2,一个9和一个3。
一些可能的[new1, new2]数对为[22, 93],[23, 92],[223, 9] 和[2, 329]。
请你返回可以得到的new1和 new2的 最小和。
示例 1:输入:num = 2932 输出:52
解释:可行的 [new1, new2] 数对为 [29, 23] ,[223, 9] 等等。
最小和为数对 [29, 23] 的和:29 + 23 = 52 。
示例 2:输入:num = 4009 输出:13
解释:可行的 [new1, new2] 数对为 [0, 49] ,[490, 0] 等等。
最小和为数对 [4, 9] 的和:4 + 9 = 13 。
提示:1000 <= num <= 9999
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(1) O(1)
func minimumSum(num int) int {
    arr := make([]int, 0)
    for num > 0 {
        arr = append(arr, num%10)
        num = num / 10
    }
    sort.Ints(arr)
    return 10*(arr[0]+arr[1]) + arr[2] + arr[3]
}

2164.对奇偶下标分别排序(1)

  • 题目
给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值:
按 非递增 顺序排列 nums 奇数下标 上的所有值。
举个例子,如果排序前 nums = [4,1,2,3] ,对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 1 和 3 的值按照非递增顺序重排。
按 非递减 顺序排列 nums 偶数下标 上的所有值。
举个例子,如果排序前 nums = [4,1,2,3] ,对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。
返回重排 nums 的值之后形成的数组。
示例 1:输入:nums = [4,1,2,3] 输出:[2,3,4,1]
解释:首先,按非递增顺序重排奇数下标(1 和 3)的值。
所以,nums 从 [4,1,2,3] 变为 [4,3,2,1] 。
然后,按非递减顺序重排偶数下标(0 和 2)的值。
所以,nums 从 [4,1,2,3] 变为 [2,3,4,1] 。
因此,重排之后形成的数组是 [2,3,4,1] 。
示例 2:输入:nums = [2,1] 输出:[2,1]
解释:由于只有一个奇数下标和一个偶数下标,所以不会发生重排。
形成的结果数组是 [2,1] ,和初始数组一样。 
提示:1 <= nums.length <= 100
1 <= nums[i] <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组 O(nlog(n)) O(n)
func sortEvenOdd(nums []int) []int {
    even, odd := make([]int, 0), make([]int, 0)
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            even = append(even, nums[i])
        } else {
            odd = append(odd, nums[i])
        }
    }
    sort.Ints(even)
    sort.Slice(odd, func(i, j int) bool {
        return odd[i] > odd[j]
    })
    for i := 0; i < len(even); i++ {
        nums[2*i] = even[i]
    }
    for i := 0; i < len(odd); i++ {
        nums[2*i+1] = odd[i]
    }
    return nums
}

2169.得到0的操作数(2)

  • 题目
给你两个 非负 整数 num1 和 num2 。
每一步 操作中,如果 num1 >= num2 ,你必须用 num1 减 num2 ;否则,你必须用 num2 减 num1 。
例如,num1 = 5 且 num2 = 4 ,应该用num1 减 num2 ,因此,得到 num1 = 1 和 num2 = 4 。
然而,如果 num1 = 4且 num2 = 5 ,一步操作后,得到 num1 = 4 和 num2 = 1 。
返回使 num1 = 0 或 num2 = 0 的 操作数 。
示例 1:输入:num1 = 2, num2 = 3 输出:3
解释:- 操作 1 :num1 = 2 ,num2 = 3 。由于 num1 < num2 ,num2 减 num1 得到 num1 = 2 ,num2 = 3 - 2 = 1 。
- 操作 2 :num1 = 2 ,num2 = 1 。由于 num1 > num2 ,num1 减 num2 。
- 操作 3 :num1 = 1 ,num2 = 1 。由于 num1 == num2 ,num1 减 num2 。
此时 num1 = 0 ,num2 = 1 。由于 num1 == 0 ,不需要再执行任何操作。
所以总操作数是 3 。
示例 2:输入:num1 = 10, num2 = 10 输出:1
解释:- 操作 1 :num1 = 10 ,num2 = 10 。由于 num1 == num2 ,num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ,num2 = 10 。由于 num1 == 0 ,不需要再执行任何操作。
所以总操作数是 1 。
提示:0 <= num1, num2 <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学-辗转相除 O(log(n)) O(1)
02 模拟 O(n) O(1)
func countOperations(num1 int, num2 int) int {
    res := 0
    for num1 > 0 {
        res = res + num2/num1
        num1, num2 = num2%num1, num1
    }
    return res
}

# 2
func countOperations(num1 int, num2 int) int {
    res := 0
    for num1 > 0 && num2 > 0 {
        if num1 >= num2 {
            num1 = num1 - num2
        } else {
            num2 = num2 - num1
        }
        res++
    }
    return res
}

2176.统计数组中相等且可以被整除的数对(1)

  • 题目
给你一个下标从 0开始长度为 n的整数数组nums和一个整数k,
请你返回满足0 <= i < j < n,nums[i] == nums[j] 且(i * j)能被k整除的数对(i, j)的数目。
示例 1:输入:nums = [3,1,2,2,2,1,3], k = 2 输出:4
解释:总共有 4 对数符合所有要求:
- nums[0] == nums[6] 且 0 * 6 == 0 ,能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ,能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ,能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ,能被 2 整除。
示例 2:输入:nums = [1,2,3,4], k = 1 输出:0
解释:由于数组中没有重复数值,所以没有数对 (i,j) 符合所有要求。
提示:1 <= nums.length <= 100
1 <= nums[i], k <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
func countPairs(nums []int, k int) int {
    res := 0
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] && i*j%k == 0 {
                res++
            }
        }
    }
    return res
}

2180.统计各位数字之和为偶数的整数个数(2)

  • 题目
给你一个正整数 num ,请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。
正整数的 各位数字之和 是其所有位上的对应数字相加的结果。
示例 1:输入:num = 4 输出:2
解释:只有 2 和 4 满足小于等于 4 且各位数字之和为偶数。    
示例 2:输入:num = 30 输出:14
解释:只有 14 个整数满足小于等于 30 且各位数字之和为偶数,分别是: 
2、4、6、8、11、13、15、17、19、20、22、24、26 和 28 。
提示:1 <= num <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(nlog(n)) O(1)
02 数学 O(log(n)) O(1)
func countEven(num int) int {
    res := 0
    for i := 2; i <= num; i++ {
        sum := 0
        temp := i
        for temp > 0 {
            sum = sum + temp%10
            temp = temp / 10
        }
        if sum%2 == 0 {
            res++
        }
    }
    return res
}

# 2
func countEven(num int) int {
    a := num / 10 * 5 // 每10包含5个数
    b := 0            // 十位以上的数字之和
    for temp := num / 10; temp > 0; temp = temp / 10 {
        b = b + temp%10
    }
    if b%2 == 0 { // 偶数
        return a + (num%10+2)/2 - 1
    }
    return a + (num%10+1)/2 - 1
}

2185.统计包含给定前缀的字符串(2)

  • 题目
给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为 前缀 的字符串的数目。
字符串 s 的 前缀 就是 s 的任一前导连续字符串。
示例 1:输入:words = ["pay","attention","practice","attend"], pref = "at" 输出:2
解释:以 "at" 作为前缀的字符串有两个,分别是:"attention" 和 "attend" 。
示例 2:输入:words = ["leetcode","win","loops","success"], pref = "code" 输出:0
解释:不存在以 "code" 作为前缀的字符串。
提示:1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] 和 pref 由小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(1)
02 遍历 O(n) O(1)
func prefixCount(words []string, pref string) int {
    res := 0
    for i := 0; i < len(words); i++ {
        if strings.HasPrefix(words[i], pref) {
            res++
        }
    }
    return res
}

# 2
func prefixCount(words []string, pref string) int {
    res := 0
    for i := 0; i < len(words); i++ {
        if len(words[i]) >= len(pref) && words[i][:len(pref)] == pref {
            res++
        }
    }
    return res
}

2190.数组中紧跟key之后出现最频繁的数字(2)

  • 题目
给你一个下标从 0开始的整数数组nums,同时给你一个整数key,它在nums出现过。
统计在 nums数组中紧跟着 key后面出现的不同整数target的出现次数。换言之,target的出现次数为满足以下条件的 i的数目:
0 <= i <= n - 2
nums[i] == key且
nums[i + 1] == target。
请你返回出现 最多次数的target。测试数据保证出现次数最多的 target是唯一的。
示例 1:输入:nums = [1,100,200,1,100], key = 1 输出:100
解释:对于 target = 100 ,在下标 1 和 4 处出现过 2 次,且都紧跟着 key 。
没有其他整数在 key 后面紧跟着出现,所以我们返回 100 。
示例 2:输入:nums = [2,2,2,2,3], key = 2 输出:2
解释:对于 target = 2 ,在下标 1 ,2 和 3 处出现过 3 次,且都紧跟着 key 。
对于 target = 3 ,在下标 4 出出现过 1 次,且紧跟着 key 。
target = 2 是紧跟着 key 之后出现次数最多的数字,所以我们返回 2 。
提示:2 <= nums.length <= 1000
1 <= nums[i] <= 1000
测试数据保证答案是唯一的。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希 O(n) O(n)
02 哈希 O(n) O(n)
func mostFrequent(nums []int, key int) int {
    m := make(map[int]int)
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] == key {
            m[nums[i+1]]++
        }
    }
    res, count := 0, 0
    for k, v := range m {
        if v > count {
            count = v
            res = k
        }
    }
    return res
}

# 2
func mostFrequent(nums []int, key int) int {
    m := make(map[int]int)
    res, count := 0, 0
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] == key {
            m[nums[i+1]]++
            if m[nums[i+1]] > count {
                count = m[nums[i+1]]
                res = nums[i+1]
            }
        }
    }
    return res
}

2191.将杂乱无章的数字排序(1)

  • 题目
给你一个下标从 0开始的整数数组mapping,它表示一个十进制数的映射规则,
mapping[i] = j表示这个规则下将数位i映射为数位 j。
一个整数 映射后的值为将原数字每一个数位 i(0 <= i <= 9)映射为mapping[i]。
另外给你一个整数数组nums,请你将数组nums中每个数按照它们映射后对应数字非递减顺序排序后返回。
注意:如果两个数字映射后对应的数字大小相同,则将它们按照输入中的 相对顺序排序。
nums中的元素只有在排序的时候需要按照映射后的值进行比较,返回的值应该是输入的元素本身。
示例 1:输入:mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38] 输出:[338,38,991]
解释:将数字 991 按照如下规则映射:
1. mapping[9] = 6 ,所有数位 9 都会变成 6 。
2. mapping[1] = 9 ,所有数位 1 都会变成 8 。
所以,991 映射的值为 669 。
338 映射为 007 ,去掉前导 0 后得到 7 。
38 映射为 07 ,去掉前导 0 后得到 7 。
由于 338 和 38 映射后的值相同,所以它们的前后顺序保留原数组中的相对位置关系,338 在 38 的前面。
所以,排序后的数组为 [338,38,991] 。
示例 2:输入:mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123] 输出:[123,456,789]
解释:789 映射为 789 ,456 映射为 456 ,123 映射为 123 。所以排序后数组为 [123,456,789] 。
提示:mapping.length == 10
0 <= mapping[i] <= 9
mapping[i]的值 互不相同。
1 <= nums.length <= 3 * 104
0 <= nums[i] < 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 自定义排序 O(nlog(n)) O(1)
func sortJumbled(mapping []int, nums []int) []int {
    sort.SliceStable(nums, func(i, j int) bool {
        return transfer(mapping, nums[i]) < transfer(mapping, nums[j])
    })
    return nums
}

func transfer(mapping []int, num int) int {
    res := 0
    if num == 0 {
        return mapping[0]
    }
    v := 1
    for ; num > 0; num = num / 10 {
        res = res + mapping[num%10]*v
        v = v * 10
    }
    return res
}

2194.Excel表中某个范围内的单元格(1)

  • 题目
Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示,其中:
<col> 即单元格的列号 c 。用英文字母表中的 字母 标识。
例如,第 1 列用 'A' 表示,第 2 列用 'B' 表示,第 3 列用 'C' 表示,以此类推。
<row> 即单元格的行号 r 。第 r 行就用 整数 r 标识。
给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ,
其中 <col1> 表示 c1 列,<row1> 表示 r1 行,<col2> 表示 c2 列,<row2> 表示 r2 行,并满足 r1 <= r2 且 c1 <= c2 。
找出所有满足r1 <= x <= r2 且 c1 <= y <= c2 的单元格,并以列表形式返回。
单元格应该按前面描述的格式用 字符串 表示,并以 非递减 顺序排列(先按列排,再按行排)。
示例 1:输入:s = "K1:L2" 输出:["K1","K2","L1","L2"]
解释:上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。
示例 2:输入:s = "A1:F1" 输出:["A1","B1","C1","D1","E1","F1"]
解释:上图显示了列表中应该出现的单元格。 
红色箭头指示单元格的出现顺序。
提示:s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s 由大写英文字母、数字、和 ':' 组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(n^2)
func cellsInRange(s string) []string {
    res := make([]string, 0)
    for i := s[0]; i <= s[3]; i++ {
        for j := s[1]; j <= s[4]; j++ {
            res = append(res, string(i)+string(j))
        }
    }
    return res
}

2200.找出数组中的所有K近邻下标(2)

  • 题目
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。
K 近邻下标 是 nums 中的一个下标 i ,并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。
以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
示例 1:输入:nums = [3,4,9,1,3,9,5], key = 9, k = 1 输出:[1,2,3,4,5,6]
解释:因此,nums[2] == key 且 nums[5] == key 。
- 对下标 0 ,|0 - 2| > k 且 |0 - 5| > k ,所以不存在 j 使得 |0 - j| <= k 且 nums[j] == key 。
所以 0 不是一个 K 近邻下标。
- 对下标 1 ,|1 - 2| <= k 且 nums[2] == key ,所以 1 是一个 K 近邻下标。
- 对下标 2 ,|2 - 2| <= k 且 nums[2] == key ,所以 2 是一个 K 近邻下标。
- 对下标 3 ,|3 - 2| <= k 且 nums[2] == key ,所以 3 是一个 K 近邻下标。
- 对下标 4 ,|4 - 5| <= k 且 nums[5] == key ,所以 4 是一个 K 近邻下标。
- 对下标 5 ,|5 - 5| <= k 且 nums[5] == key ,所以 5 是一个 K 近邻下标。
- 对下标 6 ,|6 - 5| <= k 且 nums[5] == key ,所以 6 是一个 K 近邻下标。
因此,按递增顺序返回 [1,2,3,4,5,6] 。 
示例 2:输入:nums = [2,2,2,2,2], key = 2, k = 2 输出:[0,1,2,3,4]
解释:对 nums 的所有下标 i ,总存在某个下标 j 使得 |i - j| <= k 且 nums[j] == key ,所以每个下标都是一个 K 近邻下标。 
因此,返回 [0,1,2,3,4] 。
提示:1 <= nums.length <= 1000
1 <= nums[i] <= 1000
key 是数组 nums 中的一个整数
1 <= k <= nums.length
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
02 遍历 O(n) O(1)
func findKDistantIndices(nums []int, key int, k int) []int {
    n := len(nums)
    res := make([]int, 0)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if nums[j] == key && abs(i-j) <= k {
                res = append(res, i)
                break
            }
        }
    }
    return res
}

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

# 2
func findKDistantIndices(nums []int, key int, k int) []int {
    n := len(nums)
    res := make([]int, 0)
    right := 0
    for j := 0; j < n; j++ {
        if nums[j] == key {
            left := max(right, j-k)   // 往前k or 已经访问过的
            right = min(n-1, j+k) + 1 // 更新
            for i := left; i < right; i++ {
                res = append(res, i)
            }
        }
    }
    return res
}

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

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

2101-2200-Medium

2101.引爆最多的炸弹(2)

  • 题目
给你一个炸弹列表。一个炸弹的 爆炸范围定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 0开始的二维整数数组bombs表示,其中bombs[i] = [xi, yi, ri]。
xi 和yi表示第 i个炸弹的 X 和 Y 坐标,ri表示爆炸范围的 半径。
你需要选择引爆 一个炸弹。当这个炸弹被引爆时,所有 在它爆炸范围内的炸弹都会被引爆,
这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
给你数组bombs,请你返回在引爆一个炸弹的前提下,最多能引爆的炸弹数目。
示例 1:输入:bombs = [[2,1,3],[6,1,4]] 输出:2
解释:上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹,右边的炸弹不会被影响。
但如果我们引爆右边的炸弹,两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。
示例 2:输入:bombs = [[1,1,5],[10,10,5]] 输出:1
解释:引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。
示例 3:输入:bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]] 输出:5
解释:最佳引爆炸弹为炸弹 0 ,因为:
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。
提示:1 <= bombs.length<= 100
bombs[i].length == 3
1 <= xi, yi, ri <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n^3) O(n^2)
02 深度优先搜索 O(n^3) O(n^2)
func maximumDetonation(bombs [][]int) int {
    n := len(bombs)
    arr := make([][]int, n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && judge(bombs[i][0], bombs[i][1], bombs[j][0], bombs[j][1], bombs[i][2]) == true {
                arr[i] = append(arr[i], j)
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        count := 1
        visited := make([]bool, n)
        queue := make([]int, 0)
        queue = append(queue, i)
        visited[i] = true
        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            for j := 0; j < len(arr[node]); j++ {
                next := arr[node][j]
                if visited[next] == false {
                    count++
                    queue = append(queue, next)
                    visited[next] = true
                }
            }
        }
        if count > res {
            res = count
        }
    }
    return res
}

func judge(a, b, c, d, r int) bool {
    return r*r >= (a-c)*(a-c)+(b-d)*(b-d)
}

# 2
var arr [][]int
var count int

func maximumDetonation(bombs [][]int) int {
    n := len(bombs)
    arr = make([][]int, n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && judge(bombs[i][0], bombs[i][1], bombs[j][0], bombs[j][1], bombs[i][2]) == true {
                arr[i] = append(arr[i], j)
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        count = 0
        dfs(i, make([]bool, n))
        if count > res {
            res = count
        }
    }
    return res
}

func dfs(start int, visited []bool) {
    visited[start] = true
    count++
    for i := 0; i < len(arr[start]); i++ {
        next := arr[start][i]
        if visited[next] == false {
            dfs(next, visited)
        }
    }
}

func judge(a, b, c, d, r int) bool {
    return r*r >= (a-c)*(a-c)+(b-d)*(b-d)
}

2104.子数组范围和(2)

  • 题目
给你一个整数数组 nums 。nums 中,子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
示例 1:输入:nums = [1,2,3]输出:4
解释:nums 的 6 个子数组如下所示:
[1],范围 = 最大 - 最小 = 1 - 1 = 0 
[2],范围 = 2 - 2 = 0
[3],范围 = 3 - 3 = 0
[1,2],范围 = 2 - 1 = 1
[2,3],范围 = 3 - 2 = 1
[1,2,3],范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
示例 2:输入:nums = [1,3,3]输出:4
解释:nums 的 6 个子数组如下所示:
[1],范围 = 最大 - 最小 = 1 - 1 = 0
[3],范围 = 3 - 3 = 0
[3],范围 = 3 - 3 = 0
[1,3],范围 = 3 - 1 = 2
[3,3],范围 = 3 - 3 = 0
[1,3,3],范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
示例 3:输入:nums = [4,-2,-3,4,1]输出:59
解释:nums 中所有子数组范围的和是 59
提示:1 <= nums.length <= 1000
-109 <= nums[i] <= 109
进阶:你可以设计一种时间复杂度为 O(n) 的解决方案吗?
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(1)
02 单调栈 O(n) O(n)
func subArrayRanges(nums []int) int64 {
    res := int64(0)
    for i := 0; i < len(nums); i++ {
        minValue, maxValue := nums[i], nums[i]
        for j := i + 1; j < len(nums); j++ {
            if nums[j] > maxValue {
                maxValue = nums[j]
            }
            if nums[j] < minValue {
                minValue = nums[j]
            }
            res = res + int64(maxValue-minValue)
        }
    }
    return res
}

# 2
func subArrayRanges(nums []int) int64 {
    return int64(sumSubarrayMaxs(nums)) - int64(sumSubarrayMins(nums))
}

// leetcode907_子数组的最小值之和
func sumSubarrayMins(arr []int) int {
    res := 0
    stack := make([]int, 0) // 递增栈
    stack = append(stack, -1)
    total := 0
    for i := 0; i < len(arr); i++ {
        for len(stack) > 1 && arr[i] < arr[stack[len(stack)-1]] { // 小于栈顶
            prev := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            total = total - arr[prev]*(prev-stack[len(stack)-1])
        }
        stack = append(stack, i)
        total = total + arr[i]*(i-stack[len(stack)-2])
        res = res + total
    }
    return res
}

func sumSubarrayMaxs(arr []int) int {
    res := 0
    stack := make([]int, 0) // 递减栈
    stack = append(stack, -1)
    total := 0
    for i := 0; i < len(arr); i++ {
        for len(stack) > 1 && arr[i] > arr[stack[len(stack)-1]] { // 大于栈顶
            prev := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            total = total - arr[prev]*(prev-stack[len(stack)-1])
        }
        stack = append(stack, i)
        total = total + arr[i]*(i-stack[len(stack)-2])
        res = res + total
    }
    return res
}

2105.给植物浇水II(2)

  • 题目
Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行,从左到右进行标记,编号从 0 到 n - 1 。
其中,第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐,最初是满的 。他们按下面描述的方式完成浇水:
Alice 按 从左到右 的顺序给植物浇水,从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水,从植物 n - 1 开始。
他们 同时 给植物浇水。
如果没有足够的水 完全 浇灌下一株植物,他 / 她会立即重新灌满浇水罐。
不管植物需要多少水,浇水所耗费的时间都是一样的。
不能 提前重新灌满水罐。
每株植物都可以由 Alice 或者 Bob 来浇水。
如果 Alice 和 Bob 到达同一株植物,那么当前水罐中水更多的人会给这株植物浇水。
如果他俩水量相同,那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ,数组由 n 个整数组成。
其中,plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和capacityB 分别表示 Alice 和 Bob 水罐的容量。
返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
示例 1:输入:plants = [2,2,3,3], capacityA = 5, capacityB = 5 输出:1
解释:- 最初,Alice 和 Bob 的水罐中各有 5 单元水。
- Alice 给植物 0 浇水,Bob 给植物 3 浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。
- Alice 有足够的水给植物 1 ,所以她直接浇水。Bob 的水不够给植物 2 ,所以他先重新装满水,再浇水。
所以,两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。
示例 2:输入:plants = [2,2,3,3], capacityA = 3, capacityB = 4 输出:2
解释:- 最初,Alice 的水罐中有 3 单元水,Bob 的水罐中有 4 单元水。
- Alice 给植物 0 浇水,Bob 给植物 3 浇水。
- Alice 和 Bob 现在都只有 1 单元水,并分别需要给植物 1 和植物 2 浇水。
- 由于他们的水量均不足以浇水,所以他们重新灌满水罐再进行浇水。
所以,两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。
示例 3:输入:plants = [5], capacityA = 10, capacityB = 8 输出:0
解释:- 只有一株植物
- Alice 的水罐有 10 单元水,Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多,她会给这株植物浇水。
所以,两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。
示例 4:输入:plants = [1,2,4,4,5], capacityA = 6, capacityB = 5 输出:2
解释:- 最初,Alice 的水罐中有 6 单元水,Bob 的水罐中有 5 单元水。
- Alice 给植物 0 浇水,Bob 给植物 4 浇水。
- Alice 和 Bob 现在分别剩下 5 单元和 0 单元水。
- Alice 有足够的水给植物 1 ,所以她直接浇水。Bob 的水不够给植物 3 ,所以他先重新装满水,再浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 1 单元水。
- 由于 Alice 的水更多,所以由她给植物 2 浇水。然而,她水罐里的水不够给植物 2 ,所以她先重新装满水,再浇水。 
所以,两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 1 + 0 = 2 。
示例 5:输入:plants = [2,2,5,2,2], capacityA = 5, capacityB = 5 输出:1
解释:Alice 和 Bob 都会到达中间的植物,并且此时他俩剩下的水量相同,所以 Alice 会给这株植物浇水。
由于她到达时只剩下 1 单元水,所以需要重新灌满水罐。
这是唯一一次需要重新灌满水罐的情况。所以,两人浇灌所有植物过程中重新灌满水罐的次数 = 1 。
提示:n == plants.length
1 <= n <= 105
1 <= plants[i] <= 106
max(plants[i]) <= capacityA, capacityB <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟 O(n) O(1)
func minimumRefill(plants []int, capacityA int, capacityB int) int {
    res := 0
    i, j := 0, len(plants)-1
    a, b := capacityA, capacityB
    for i <= j {
        if i == j { // 相等
            if a >= b && a < plants[i] {
                res++
            }
            if a < b && b < plants[i] {
                res++
            }
            return res
        }
        if a < plants[i] {
            res++
            a = capacityA - plants[i]
        } else {
            a = a - plants[i]
        }
        i++
        if b < plants[j] {
            res++
            b = capacityB - plants[j]
        } else {
            b = b - plants[j]
        }
        j--
    }
    return res
}

2109.向字符串添加空格(1)

  • 题目
给你一个下标从 0 开始的字符串 s ,以及一个下标从 0 开始的整数数组 spaces 。
数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。
例如,s = "EnjoyYourCoffee" 且 spaces = [5, 9] ,那么我们需要在 'Y' 和 'C' 之前添加空格,
这两个字符分别位于下标 5 和下标 9 。因此,最终得到 "Enjoy Your Coffee" 。
请你添加空格,并返回修改后的字符串。
示例 1:输入:s = "LeetcodeHelpsMeLearn", spaces = [8,13,15] 输出:"Leetcode Helps Me Learn"
解释:下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。
示例 2:输入:s = "icodeinpython", spaces = [1,5,7,9] 输出:"i code in py thon"
解释:下标 1、5、7 和 9 对应 "icodeinpython" 中加粗斜体字符。
接着在这些字符前添加空格。
示例 3:输入:s = "spacing", spaces = [0,1,2,3,4,5,6] 输出:" s p a c i n g"
解释:字符串的第一个字符前可以添加空格。
提示:1 <= s.length <= 3 * 105
s 仅由大小写英文字母组成
1 <= spaces.length <= 3 * 105
0 <= spaces[i] <= s.length - 1
spaces 中的所有值 严格递增
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func addSpaces(s string, spaces []int) string {
    res := make([]byte, 0)
    if len(spaces) == 0 {
        return s
    }
    j := 0
    for i := 0; i < len(s); i++ {
        if j < len(spaces) && i == spaces[j] {
            res = append(res, ' ')
            j++
        }
        res = append(res, s[i])
    }
    return string(res)
}

2110.股票平滑下跌阶段的数目(1)

  • 题目
给你一个整数数组prices,表示一支股票的历史每日股价,其中prices[i]是这支股票第i天的价格。
一个 平滑下降的阶段定义为:对于连续一天或者多天,每日股价都比 前一日股价恰好少 1,这个阶段第一天的股价没有限制。
请你返回 平滑下降阶段的数目。
示例 1:输入:prices = [3,2,1,4] 输出:7
解释:总共有 7 个平滑下降阶段:
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意,仅一天按照定义也是平滑下降阶段。
示例 2:输入:prices = [8,6,7,7] 输出:4
解释:总共有 4 个连续平滑下降阶段:[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ,所以 [8,6] 不是平滑下降阶段。
示例 3:输入:prices = [1] 输出:1
解释:总共有 1 个平滑下降阶段:[1]
提示:1 <= prices.length <= 105
1 <= prices[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func getDescentPeriods(prices []int) int64 {
    res := int64(1)
    if len(prices) == 1 {
        return 1
    }
    count := int64(1)
    for i := 1; i < len(prices); i++ {
        if prices[i-1]-prices[i] == 1 {
            count++
        } else {
            count = int64(1)
        }
        res = res + count
    }
    return res
}

2115.从给定原材料中找到所有可以做出的菜(1)

  • 题目
你有 n道不同菜的信息。给你一个字符串数组recipes和一个二维字符串数组ingredients。
第i道菜的名字为recipes[i],如果你有它所有的原材料ingredients[i],
那么你可以做出这道菜。一道菜的原材料可能是另一道菜,也就是说ingredients[i]可能包含recipes中另一个字符串。
同时给你一个字符串数组supplies,它包含你初始时拥有的所有原材料,每一种原材料你都有无限多。
请你返回你可以做出的所有菜。你可以以 任意顺序返回它们。
注意两道菜在它们的原材料中可能互相包含。
示例 1:输入:recipes = ["bread"], ingredients = [["yeast","flour"]], 
supplies = ["yeast","flour","corn"]输出:["bread"]
解释:我们可以做出 "bread" ,因为我们有原材料 "yeast" 和 "flour" 。
示例 2:输入:recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], 
supplies = ["yeast","flour","meat"] 输出:["bread","sandwich"]
解释:我们可以做出 "bread" ,因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ,因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
示例 3:输入:recipes = ["bread","sandwich","burger"], 
ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], 
supplies = ["yeast","flour","meat"] 输出:["bread","sandwich","burger"]
解释:我们可以做出 "bread" ,因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ,因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
我们可以做出 "burger" ,因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。
示例 4:输入:recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"] 输出:[]
解释:我们没法做出任何菜,因为我们只有原材料 "yeast" 。
提示:n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j]和supplies[k]只包含小写英文字母。
所有recipes 和supplies中的值互不相同。
ingredients[i]中的字符串互不相同。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 拓扑排序 O(n) O(n)
func findAllRecipes(recipes []string, ingredients [][]string, supplies []string) []string {
    res := make([]string, 0)
    arr := make(map[string][]string)
    inDegree := make(map[string]int)
    for i := 0; i < len(recipes); i++ {
        a := recipes[i]
        for j := 0; j < len(ingredients[i]); j++ {
            b := ingredients[i][j] // b=>a 原材料=>菜
            arr[b] = append(arr[b], a)
            inDegree[a]++ // 菜的入度+1
        }
    }
    for len(supplies) > 0 {
        b := supplies[0]
        supplies = supplies[1:]
        for i := 0; i < len(arr[b]); i++ {
            a := arr[b][i]
            inDegree[a]--
            if inDegree[a] == 0 { // 入度=0,代表该菜的原材料都有
                res = append(res, a)
                supplies = append(supplies, a)
            }
        }
    }
    return res
}

2116.判断一个括号字符串是否有效(1)

  • 题目
一个括号字符串是只由'(' 和')'组成的非空字符串。如果一个字符串满足下面 任意一个条件,那么它就是有效的:
字符串为().
它可以表示为 AB(A与B连接),其中A 和B都是有效括号字符串。
它可以表示为(A),其中A是一个有效括号字符串。
给你一个括号字符串s和一个字符串locked,两者长度都为n。locked是一个二进制字符串,只包含'0'和'1'。对于locked中每一个下标i :
如果locked[i]是'1',你 不能改变s[i]。
如果locked[i]是'0',你可以将s[i]变为'('或者')'。
如果你可以将 s变为有效括号字符串,请你返回true,否则返回false。
示例 1:输入:s = "))()))", locked = "010100" 输出:true
解释:locked[1] == '1' 和 locked[3] == '1' ,所以我们无法改变 s[1] 或者 s[3] 。
我们可以将 s[0] 和 s[4] 变为 '(' ,不改变 s[2] 和 s[5] ,使 s 变为有效字符串。
示例 2:输入:s = "()()", locked = "0000" 输出:true
解释:我们不需要做任何改变,因为 s 已经是有效字符串了。
示例 3:输入:s = ")", locked = "0" 输出:false
解释:locked 允许改变 s[0] 。
但无论将 s[0] 变为 '(' 或者 ')' 都无法使 s 变为有效字符串。
提示:n == s.length == locked.length
1 <= n <= 105
s[i]要么是'('要么是')'。
locked[i] 要么是'0'要么是'1' 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func canBeValid(s string, locked string) bool {
    if len(s)%2 == 1 {
        return false
    }
    var arr []byte
    for i := 0; i < len(locked); i++ {
        if locked[i] == '1' {
            arr = append(arr, s[i])
        } else {
            arr = append(arr, '*')
        }
    }
    return checkValidString(string(arr))
}

// leetcode678.有效的括号字符串
func checkValidString(s string) bool {
    // 第1次把星号当左括号看
    left, right := 0, 0
    for i := 0; i < len(s); i++ {
        if s[i] == ')' {
            right++
        } else {
            left++
        }
        if right > left {
            return false
        }
    }
    // 第2次把星号当右括号看
    left, right = 0, 0
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '(' {
            left++
        } else {
            right++
        }
        if left > right {
            return false
        }
    }
    return true
}

2120.执行所有后缀指令(1)

  • 题目
现有一个 n x n 大小的网格,左上角单元格坐标 (0, 0) ,右下角单元格坐标 (n - 1, n - 1) 。
给你整数 n 和一个整数数组 startPos ,
其中 startPos = [startrow, startcol] 表示机器人最开始在坐标为 (startrow, startcol) 的单元格上。
另给你一个长度为 m 、下标从 0 开始的字符串 s ,其中 s[i] 是对机器人的第 i 条指令:
'L'(向左移动),'R'(向右移动),'U'(向上移动)和 'D'(向下移动)。
机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾,但在满足下述条件之一时,机器人将会停止:
下一条指令将会导致机器人移动到网格外。
没有指令可以执行。
返回一个长度为 m 的数组 answer ,其中 answer[i] 是机器人从第 i条指令 开始,可以执行的 指令数目 。
示例 1:输入:n = 3, startPos = [0,1], s = "RRDDLU" 输出:[1,5,4,3,1,0]
解释:机器人从 startPos 出发,并从第 i 条指令开始执行:
- 0: "RRDDLU" 在移动到网格外之前,只能执行一条 "R" 指令。
- 1:  "RDDLU" 可以执行全部五条指令,机器人仍在网格内,最终到达 (0, 0) 。
- 2:   "DDLU" 可以执行全部四条指令,机器人仍在网格内,最终到达 (0, 0) 。
- 3:    "DLU" 可以执行全部三条指令,机器人仍在网格内,最终到达 (0, 0) 。
- 4:     "LU" 在移动到网格外之前,只能执行一条 "L" 指令。
- 5:      "U" 如果向上移动,将会移动到网格外。
示例 2:输入:n = 2, startPos = [1,1], s = "LURD" 输出:[4,1,0,0]
解释:- 0: "LURD"
- 1:  "URD"
- 2:   "RD"
- 3:    "D"
示例 3:输入:n = 1, startPos = [0,0], s = "LRUD" 输出:[0,0,0,0]
解释:无论机器人从哪条指令开始执行,都会移动到网格外。
提示:m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= startrow, startcol < n
s 由 'L'、'R'、'U' 和 'D' 组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟 O(n^2) O(n)
func executeInstructions(n int, startPos []int, s string) []int {
    res := make([]int, 0)
    for i := 0; i < len(s); i++ {
        count := 0
        a, b := startPos[0], startPos[1]
        for j := i; j < len(s); j++ {
            switch s[j] {
            case 'L':
                b--
            case 'R':
                b++
            case 'U':
                a--
            case 'D':
                a++
            }
            if 0 <= a && a < n && 0 <= b && b < n {
                count++
            } else {
                break
            }
        }
        res = append(res, count)
    }
    return res
}

2121.相同元素的间隔之和(2)

  • 题目
给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。
arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地,arr[i] 和 arr[j] 之间的间隔是 |i - j| 。
返回一个长度为 n 的数组intervals ,
其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素(与 arr[i] 的值相同)的 间隔之和 。
注意:|x| 是 x 的绝对值。
示例 1:输入:arr = [2,1,3,1,2,3,3] 输出:[4,2,7,2,4,4,5]
解释:- 下标 0 :另一个 2 在下标 4 ,|0 - 4| = 4
- 下标 1 :另一个 1 在下标 3 ,|1 - 3| = 2
- 下标 2 :另两个 3 在下标 5 和 6 ,|2 - 5| + |2 - 6| = 7
- 下标 3 :另一个 1 在下标 1 ,|3 - 1| = 2
- 下标 4 :另一个 2 在下标 0 ,|4 - 0| = 4
- 下标 5 :另两个 3 在下标 2 和 6 ,|5 - 2| + |5 - 6| = 4
- 下标 6 :另两个 3 在下标 2 和 5 ,|6 - 2| + |6 - 5| = 5
示例 2:输入:arr = [10,5,10,10] 输出:[5,0,3,4]
解释:
- 下标 0 :另两个 10 在下标 2 和 3 ,|0 - 2| + |0 - 3| = 5
- 下标 1 :只有这一个 5 在数组中,所以到相同元素的间隔之和是 0
- 下标 2 :另两个 10 在下标 0 和 3 ,|2 - 0| + |2 - 3| = 3
- 下标 3 :另两个 10 在下标 0 和 2 ,|3 - 0| + |3 - 2| = 4
提示:n == arr.length
1 <= n <= 105
1 <= arr[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 分组+前缀和 O(n) O(n)
02 分组+遍历 O(n) O(n)
func getDistances(arr []int) []int64 {
    n := len(arr)
    res := make([]int64, n)
    m := make(map[int][]int) // 对相同数字进行分组
    for i := 0; i < n; i++ {
        m[arr[i]] = append(m[arr[i]], i)
    }
    for _, v := range m { // 分组
        arr := getSumAbsoluteDifferences(v)
        for i := 0; i < len(v); i++ {
            res[v[i]] = int64(arr[i])
        }
    }
    return res
}

// leetcode1685.有序数组中差绝对值之和
func getSumAbsoluteDifferences(nums []int) []int {
    n := len(nums)
    res := make([]int, 0)
    arr := make([]int, 0)
    sum := 0
    for i := 0; i < n; i++ {
        sum = sum + nums[i]
        arr = append(arr, sum)
    }
    res = append(res, sum-n*nums[0])
    for i := 1; i < n; i++ {
        left := nums[i]*i - arr[i-1]              // 左边和
        right := (sum - arr[i]) - nums[i]*(n-1-i) // 右边和
        res = append(res, left+right)
    }
    return res
}

# 2
func getDistances(arr []int) []int64 {
    n := len(arr)
    res := make([]int64, n)
    m := make(map[int][]int) // 对相同数字进行分组
    for i := 0; i < n; i++ {
        m[arr[i]] = append(m[arr[i]], i)
    }
    for _, v := range m { // 分组
        arr := getSumAbsoluteDifferences(v)
        for i := 0; i < len(v); i++ {
            res[v[i]] = int64(arr[i])
        }
    }
    return res
}

// leetcode1685.有序数组中差绝对值之和
func getSumAbsoluteDifferences(nums []int) []int {
    n := len(nums)
    res := make([]int, 0)
    right := 0 // 右边和
    left := 0  // 左边和
    for i := 1; i < n; i++ {
        right = right + (nums[i] - nums[0])
    }
    res = append(res, right)
    for i := 1; i < n; i++ {
        diff := nums[i] - nums[i-1]
        left = left + diff*i
        right = right - diff*(n-i)
        res = append(res, left+right)
    }
    return res
}

2125.银行中的激光束数量(2)

  • 题目
银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ,
表示银行的平面图,这是一个大小为 m x n 的二维矩阵。 
bank[i] 表示第 i 行的设备分布,由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的,而 '1' 表示单元格有一个安全设备。
对任意两个安全设备而言,如果同时 满足下面两个条件,则二者之间存在 一个 激光束:
两个设备位于两个 不同行 :r1 和 r2 ,其中 r1 < r2 。
满足r1 < i < r2的 所有行i,都没有安全设备 。
激光束是独立的,也就是说,一个激光束既不会干扰另一个激光束,也不会与另一个激光束合并成一束。
返回银行中激光束的总数量。
示例 1:输入:bank = ["011001","000000","010100","001000"] 输出:8
解释:在下面每组设备对之间,存在一条激光束。总共是 8 条激光束:
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
注意,第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备,这不满足第 2 个条件。
示例 2:输入:bank = ["000","111","000"] 输出:0
解释:不存在两个位于不同行的设备
提示:m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] 为 '0' 或 '1'
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
02 遍历 O(n^2) O(1)
func numberOfBeams(bank []string) int {
    res := 0
    prev := 0
    n, m := len(bank), len(bank[0])
    for i := 0; i < n; i++ {
        cur := 0
        for j := 0; j < m; j++ {
            if bank[i][j] == '1' {
                cur++
            }
        }
        if cur == 0 {
            continue
        }
        res = res + cur*prev
        prev = cur
    }
    return res
}

# 2
func numberOfBeams(bank []string) int {
    res := 0
    prev := 0
    for i := 0; i < len(bank); i++ {
        cur := strings.Count(bank[i], "1")
        if cur > 0 {
            res = res + cur*prev
            prev = cur
        }
    }
    return res
}

2126.摧毁小行星(1)

  • 题目
给你一个整数mass,它表示一颗行星的初始质量。再给你一个整数数组asteroids,其中asteroids[i]是第i颗小行星的质量。
你可以按 任意顺序重新安排小行星的顺序,然后让行星跟它们发生碰撞。
如果行星碰撞时的质量 大于等于小行星的质量,那么小行星被 摧毁,并且行星会 获得这颗小行星的质量。否则,行星将被摧毁。
如果所有小行星 都能被摧毁,请返回 true,否则返回 false。
示例 1:输入:mass = 10, asteroids = [3,9,19,5,21] 输出:true
解释:一种安排小行星的方式为 [9,19,5,3,21] :
- 行星与质量为 9 的小行星碰撞。新的行星质量为:10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为:19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为:38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为:43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为:46 + 21 = 67
所有小行星都被摧毁。
示例 2:输入:mass = 5, asteroids = [4,9,23,4] 输出:false
解释:行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后,质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小,所以无法摧毁最后一颗小行星。
提示:1 <= mass <= 105
1 <= asteroids.length <= 105
1 <= asteroids[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
func asteroidsDestroyed(mass int, asteroids []int) bool {
    sort.Ints(asteroids)
    temp := int64(mass)
    for i := 0; i < len(asteroids); i++ {
        if int64(asteroids[i]) < temp {
            return false
        }
        temp = temp + int64(asteroids[i])
    }
    return true
}

2130.链表最大孪生和(2)

  • 题目
在一个大小为n且 n为偶数 的链表中,对于0 <= i <= (n / 2) - 1的 i,
第i个节点(下标从 0开始)的孪生节点为第(n-1-i)个节点 。
比方说,n = 4那么节点0是节点 3的孪生节点,节点 1是节点 2的孪生节点。这是长度为 n = 4的链表中所有的孪生节点。
孪生和定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点head,请你返回链表的 最大孪生和。
示例1:输入:head = [5,4,2,1] 输出:6
解释:节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以,链表的最大孪生和是 6 。
示例 2:输入:head = [4,2,2,3] 出:7
解释:链表中的孪生节点为:
- 节点 0 是节点 3 的孪生节点,孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点,孪生和为 2 + 2 = 4 。
所以,最大孪生和为 max(7, 4) = 7 。
示例 3:输入:head = [1,100000] 出:100001
解释:链表中只有一对孪生节点,孪生和为 1 + 100000 = 100001 。
提示:链表的节点数目是[2, 105]中的偶数。
1 <= Node.val <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(n)
02 快慢指针+反转链表 O(n) O(1)
func pairSum(head *ListNode) int {
    arr := make([]int, 0)
    for head != nil {
        arr = append(arr, head.Val)
        head = head.Next
    }
    res := 0
    for i := 0; i < len(arr)/2; i++ {
        res = max(res, arr[i]+arr[len(arr)-1-i])
    }
    return res
}

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

# 2
func pairSum(head *ListNode) int {
    res := 0
    slow, fast := head, head.Next
    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    slow = reverseList(slow.Next)
    fast = head
    for slow != nil {
        res = max(res, fast.Val+slow.Val)
        fast = fast.Next
        slow = slow.Next
    }
    return res
}

func reverseList(head *ListNode) *ListNode {
    var result *ListNode
    var temp *ListNode
    for head != nil {
        temp = head.Next
        head.Next = result
        result = head
        head = temp
    }
    return result
}

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

2131.连接两字母单词得到的最长回文串(1)

  • 题目
给你一个字符串数组words。words中每个元素都是一个包含 两个小写英文字母的单词。
请你从 words中选择一些元素并按 任意顺序连接它们,并得到一个 尽可能长的回文串。每个元素 至多只能使用一次。
请你返回你能得到的最长回文串的 长度。如果没办法得到任何一个回文串,请你返回 0。
回文串指的是从前往后和从后往前读一样的字符串。
示例 1:输入:words = ["lc","cl","gg"] 输出:6
解释:一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ,长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。
示例 2:输入:words = ["ab","ty","yt","lc","cl","ab"] 输出:8
解释:最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ,长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。
示例 3:输入:words = ["cc","ll","xx"]
输出:2 解释:最长回文串是 "cc" ,长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。
提示:1 <= words.length <= 105
words[i].length == 2
words[i]仅包含小写英文字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(n)
func longestPalindrome(words []string) int {
    res := 0
    m := make(map[string]int)
    for i := 0; i < len(words); i++ {
        m[words[i]]++
    }
    // 相同:偶数次数都可以用上;多个奇数出现次数的只能用1个奇数次数
    // 不同:取反后取最小次数
    mid := false
    for k, v := range m {
        str := string(k[1]) + string(k[0])
        if k == str { // 相同
            if v%2 == 1 { // 奇数个aa可以拿1个放在中间
                mid = true
            }
            res = res + 2*(v/2*2)
        } else {
            res = res + 2*min(v, m[str]) // 最少的1方
        }
    }
    if mid == true { // 有中间的+2
        res = res + 2
    }
    return res
}

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

2134.最少交换次数来组合所有的1II(2)

  • 题目
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组,可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 nums ,返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
示例 1:输入:nums = [0,1,0,1,1,0,0] 输出:1
解释:这里列出一些能够将所有 1 聚集在一起的方案:
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次(利用数组的环形特性)。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此,需要的最少交换次数为 1 。
示例 2:输入:nums = [0,1,1,1,0,0,1,1,0] 输出:2
解释:这里列出一些能够将所有 1 聚集在一起的方案:
[1,1,1,0,0,0,0,1,1] 交换 2 次(利用数组的环形特性)。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此,需要的最少交换次数为 2 。
示例 3:输入:nums = [1,1,0,0,1] 输出:0
解释:得益于数组的环形特性,所有的 1 已经聚集在一起。
因此,需要的最少交换次数为 0 。
提示:1 <= nums.length <= 105
nums[i] 为 0 或者 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 滑动窗口 O(n) O(1)
02 滑动窗口 O(n) O(n)
func minSwaps(nums []int) int {
    n := len(nums)
    count := 0 // 1的个数=>滑动窗口的大小
    for i := 0; i < n; i++ {
        if nums[i] == 1 {
            count++
        }
    }
    res := 0 // 枚举所有起点,统计滑动窗口内0的个数
    for i := 0; i < count; i++ {
        if nums[i] == 0 {
            res++
        }
    }
    temp := res
    for i := 0; i < n-1; i++ {
        if nums[i] == 0 { // 左边
            temp--
        }
        if nums[(i+count)%n] == 0 { // 右边
            temp++
        }
        res = min(res, temp)
    }
    return res
}

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

# 2
func minSwaps(nums []int) int {
    n := len(nums)
    count := 0 // 1的个数=>滑动窗口的大小
    for i := 0; i < n; i++ {
        if nums[i] == 1 {
            count++
        }
    }
    res := n // 枚举所有起点,统计滑动窗口内0的个数
    nums = append(nums, nums...)
    sum := 0
    for i := 0; i < len(nums); i++ {
        sum = sum + (1 - nums[i])
        if i >= count {
            sum = sum - (1 - nums[i-count])
            res = min(res, sum)
        }
    }
    return res
}

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

2135.统计追加字母可以获得的单词数(2)

  • 题目
给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。
对于 targetWords 中的每个字符串,检查是否能够从 startWords 中选出一个字符串,执行一次 转换操作,
得到的结果与当前targetWords 字符串相等。
转换操作 如下面两步所述:
追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
例如,如果字符串为 "abc" ,那么字母 'd'、'e' 或 'y' 都可以加到该字符串末尾,但 'a' 就不行。
如果追加的是 'd' ,那么结果字符串为 "abcd" 。
重排 新字符串中的字母,可以按 任意 顺序重新排布字母。
例如,"abcd" 可以重排为 "acbd"、"bacd"、"cbda",以此类推。注意,它也可以重排为 "abcd" 自身。
找出 targetWords 中有多少字符串能够由startWords 中的 任一 字符串执行上述转换操作获得。
返回 targetWords 中这类 字符串的数目 。
注意:你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。
startWords 中的字符串在这一过程中 不 发生实际变更。
示例 1:输入:startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] 输出:2
解释:
- 为了形成 targetWords[0] = "tack" ,可以选用 startWords[1] = "act" ,追加字母 'k' ,并重排 "actk" 为 "tack" 。
- startWords 中不存在可以用于获得 targetWords[1] = "act" 的字符串。
  注意 "act" 确实存在于 startWords ,但是 必须 在重排前给这个字符串追加一个字母。
- 为了形成 targetWords[2] = "acti" ,可以选用 startWords[1] = "act" ,追加字母 'i' ,并重排 "acti" 为 "acti" 自身。
示例 2:输入:startWords = ["ab","a"], targetWords = ["abc","abcd"] 输出:1
解释:- 为了形成 targetWords[0] = "abc" ,可以选用 startWords[0] = "ab" ,追加字母 'c' ,并重排为 "abc" 。
- startWords 中不存在可以用于获得 targetWords[1] = "abcd" 的字符串。
提示:1 <= startWords.length, targetWords.length <= 5 * 104
1 <= startWords[i].length, targetWords[j].length <= 26
startWords 和 targetWords 中的每个字符串都仅由小写英文字母组成
在 startWords 或 targetWords 的任一字符串中,每个字母至多出现一次
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 枚举 O(n) O(n)
02 枚举 O(n) O(n)
func wordCount(startWords []string, targetWords []string) int {
    m := make(map[int]bool)
    for i := 0; i < len(startWords); i++ {
        status := getStatus(startWords[i])
        for j := 0; j < 26; j++ { // 枚举所有操作后的状态
            if (status>>j)&1 == 0 {
                m[status|(1<<j)] = true
            }
        }
    }
    res := 0
    for i := 0; i < len(targetWords); i++ {
        if m[getStatus(targetWords[i])] == true {
            res++
        }
    }
    return res
}

func getStatus(str string) int {
    status := 0
    for i := 0; i < len(str); i++ {
        v := int(str[i] - 'a')
        status = status | (1 << v)
    }
    return status
}

# 2
func wordCount(startWords []string, targetWords []string) int {
    m := make(map[int]bool)
    for i := 0; i < len(startWords); i++ {
        status := getStatus(startWords[i])
        m[status] = true
    }
    res := 0
    for i := 0; i < len(targetWords); i++ {
        status := getStatus(targetWords[i])
        for j := 0; j < len(targetWords[i]); j++ {
            v := int(targetWords[i][j] - 'a')
            if m[status^(1<<v)] == true { // 去除字符
                res++
                break
            }
        }
    }
    return res
}

func getStatus(str string) int {
    status := 0
    for i := 0; i < len(str); i++ {
        v := int(str[i] - 'a')
        status = status | (1 << v)
    }
    return status
}

2139.得到目标值的最少行动次数(1)

  • 题目
你正在玩一个整数游戏。从整数 1 开始,期望得到整数 target 。
在一次行动中,你可以做下述两种操作之一:
递增,将当前整数的值加 1(即, x = x + 1)。
加倍,使当前整数的值翻倍(即,x = 2 * x)。
在整个游戏过程中,你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles ,返回从 1 开始得到 target 需要的最少行动次数。
示例 1:输入:target = 5, maxDoubles = 0 输出:4
解释:一直递增 1 直到得到 target 。
示例 2:输入:target = 19, maxDoubles = 2 输出:7
解释:最初,x = 1 。
递增 3 次,x = 4 。
加倍 1 次,x = 8 。
递增 1 次,x = 9 。
加倍 1 次,x = 18 。
递增 1 次,x = 19 。
示例 3:输入:target = 10, maxDoubles = 4 输出:4
解释:最初,x = 1 。 
递增 1 次,x = 2 。 
加倍 1 次,x = 4 。 
递增 1 次,x = 5 。 
加倍 1 次,x = 10 。 
提示:1 <= target <= 109
0 <= maxDoubles <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(log(n)) O(1)
func minMoves(target int, maxDoubles int) int {
    res := 0
    // 方向操作:从大到小,优先减半
    for maxDoubles > 0 && target != 1 {
        res++
        if target%2 == 1 { // 奇数减去1
            target--
        } else { // 偶数/2
            maxDoubles--
            target = target / 2
        }
    }
    res = res + (target - 1)
    return res
}

2140.解决智力问题(2)

  • 题目
给你一个下标从 0开始的二维整数数组questions,其中questions[i] = [pointsi, brainpoweri]。
这个数组表示一场考试里的一系列题目,你需要 按顺序(也就是从问题 0开始依次解决),针对每个问题选择 解决或者 跳过操作。
解决问题 i将让你 获得pointsi的分数,但是你将 无法解决接下来的brainpoweri个问题
(即只能跳过接下来的 brainpoweri个问题)。如果你跳过问题i,你可以对下一个问题决定使用哪种操作。
比方说,给你questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
如果问题0被解决了, 那么你可以获得3分,但你不能解决问题1 和2。
如果你跳过问题0,且解决问题1,你将获得 4 分但是不能解决问题2 和3。
请你返回这场考试里你能获得的 最高分数。
示例 1:输入:questions = [[3,2],[4,3],[4,4],[2,5]] 输出:5
解释:解决问题 0 和 3 得到最高分。
- 解决问题 0 :获得 3 分,但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 :获得 2 分
总得分为:3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
示例 2:输入:questions = [[1,1],[2,2],[3,3],[4,4],[5,5]] 输出:7
解释:解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 :获得 2 分,但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 :获得 5 分
总得分为:2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。
提示:1 <= questions.length <= 105
questions[i].length == 2
1 <= pointsi, brainpoweri <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(n)
02 动态规划 O(n) O(n)
func mostPoints(questions [][]int) int64 {
    n := len(questions)
    dp := make([]int, n+1) // dp[i] => 解决第i道题后的最高分数
    // 反向
    for i := n - 1; i >= 0; i-- {
        next := min(n, i+questions[i][1]+1)
        dp[i] = max(dp[i+1], dp[next]+questions[i][0])
    }
    return int64(dp[0])
}

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

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

# 2
func mostPoints(questions [][]int) int64 {
    n := len(questions)
    dp := make([]int, n+1) // dp[i] => 解决第i道题后的最高分数
    for i := 0; i < n; i++ {
        next := min(n, i+questions[i][1]+1)
        dp[i+1] = max(dp[i+1], dp[i])                   // 跳过
        dp[next] = max(dp[next], dp[i]+questions[i][0]) // 不跳过
    }
    return int64(dp[n])
}

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

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

2145.统计隐藏数组数目(1)

  • 题目
给你一个下标从 0开始且长度为 n的整数数组differences,它表示一个长度为n + 1的隐藏数组相邻元素之间的差值。
更正式的表述为:我们将隐藏数组记作hidden,那么differences[i] = hidden[i + 1] - hidden[i]。
同时给你两个整数lower 和upper,它们表示隐藏数组中所有数字的值都在 闭区间[lower, upper]之间。
比方说,differences = [1, -3, 4],lower = 1,upper = 6,
那么隐藏数组是一个长度为 4且所有值都在1和6(包含两者)之间的数组。
[3, 4, 1, 5] 和[4, 5, 2, 6]都是符合要求的隐藏数组。
[5, 6, 3, 7]不符合要求,因为它包含大于 6的元素。
[1, 2, 3, 4]不符合要求,因为相邻元素的差值不符合给定数据。
请你返回 符合要求的隐藏数组的数目。如果没有符合要求的隐藏数组,请返回 0。
示例 1:输入:differences = [1,-3,4], lower = 1, upper = 6 输出:2
解释:符合要求的隐藏数组为:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
所以返回 2 。
示例 2:输入:differences = [3,-4,5,1,-2], lower = -4, upper = 5 输出:4
解释:符合要求的隐藏数组为:
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
所以返回 4 。
示例 3:输入:differences = [4,-7,2], lower = 3, upper = 6 输出:0
解释:没有符合要求的隐藏数组,所以返回 0 。
提示:n == differences.length
1 <= n <= 105
-105 <= differences[i] <= 105
-105 <= lower <= upper <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func numberOfArrays(differences []int, lower int, upper int) int {
    sum := 0
    maxValue, minValue := 0, 0
    for i := 0; i < len(differences); i++ {
        sum = sum + differences[i]
        maxValue = max(maxValue, sum)
        minValue = min(minValue, sum)
    }
    return max(0, upper-lower+1-(maxValue-minValue))
}

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

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

2146.价格范围内最高排名的K样物品(2)

  • 题目
给你一个下标从 0开始的二维整数数组grid,它的大小为m x n,表示一个商店中物品的分布图。数组中的整数含义为:
0表示无法穿越的一堵墙。
1表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
从一个格子走到上下左右相邻格子花费1步。
同时给你一个整数数组pricing 和start,其中pricing = [low, high] 且start = [row, col],
表示你开始位置为(row, col),同时你只对物品价格在闭区间[low, high]之内的物品感兴趣。同时给你一个整数k。
你想知道给定范围 内且 排名最高的 k件物品的 位置。排名按照优先级从高到低的以下规则制定:
距离:定义为从start到一件物品的最短路径需要的步数(较近距离的排名更高)。
价格:较低价格的物品有更高优先级,但只考虑在给定范围之内的价格。
行坐标:较小行坐标的有更高优先级。
列坐标:较小列坐标的有更高优先级。
请你返回给定价格内排名最高的 k件物品的坐标,将它们按照排名排序后返回。
如果给定价格内少于 k件物品,那么请将它们的坐标全部返回。
示例 1:输入:grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
输出:[[0,1],[1,1],[2,1]]
解释:起点为 (0,0) 。
价格范围为 [2,5] ,我们可以选择的物品坐标为 (0,1),(1,1),(2,1) 和 (2,2) 。
这些物品的排名为:
- (0,1) 距离为 1
- (1,1) 距离为 2
- (2,1) 距离为 3
- (2,2) 距离为 4
所以,给定价格范围内排名最高的 3 件物品的坐标为 (0,1),(1,1) 和 (2,1) 。
示例 2:输入:grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
输出:[[2,1],[1,2]]
解释:起点为 (2,3) 。
价格范围为 [2,3] ,我们可以选择的物品坐标为 (0,1),(1,1),(1,2) 和 (2,1) 。
这些物品的排名为: 
- (2,1) 距离为 2 ,价格为 2
- (1,2) 距离为 2 ,价格为 3
- (1,1) 距离为 3
- (0,1) 距离为 4
所以,给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。
示例 3:输入:grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出:[[2,1],[2,0]]
解释:起点为 (0,0) 。
价格范围为 [2,3] ,我们可以选择的物品坐标为 (2,0) 和 (2,1) 。
这些物品的排名为:
- (2,1) 距离为 5
- (2,0) 距离为 6
所以,给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。
注意,k = 3 但给定价格范围内只有 2 件物品。
提示:m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= grid[i][j] <= 105
pricing.length == 2
2 <= low <= high <= 105
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n^2*log(n)) O(n^2)
02 广度优先搜索 O(n^2*log(n)) O(n^2)
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
    n, m := len(grid), len(grid[0])
    arr := make([][]int, 0) // [dis, price, x, y]
    queue := make([][]int, 0)
    queue = append(queue, []int{start[0], start[1], 0})                                   // [x,y,dis]
    if pricing[0] <= grid[start[0]][start[1]] && grid[start[0]][start[1]] <= pricing[1] { // 起点
        arr = append(arr, []int{0, grid[start[0]][start[1]], start[0], start[1]})
    }
    grid[start[0]][start[1]] = 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        x, y, dis := node[0], node[1], node[2]
        for i := 0; i < 4; i++ {
            newX := x + dx[i]
            newY := y + dy[i]
            if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] > 0 {
                if pricing[0] <= grid[newX][newY] && grid[newX][newY] <= pricing[1] {
                    arr = append(arr, []int{dis + 1, grid[newX][newY], newX, newY})
                }
                queue = append(queue, []int{newX, newY, dis + 1})
                grid[newX][newY] = 0
            }
        }
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][0] == arr[j][0] {
            if arr[i][1] == arr[j][1] {
                if arr[i][2] == arr[j][2] {
                    return arr[i][3] < arr[j][3]
                }
                return arr[i][2] < arr[j][2]
            }
            return arr[i][1] < arr[j][1]
        }
        return arr[i][0] < arr[j][0]
    })
    res := make([][]int, 0)
    for i := 0; i < k && i < len(arr); i++ {
        res = append(res, []int{arr[i][2], arr[i][3]})
    }
    return res
}

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

func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
    n, m := len(grid), len(grid[0])
    arr := make([][]int, 0) // [dis, price, x, y]
    queue := make([][]int, 0)
    queue = append(queue, []int{start[0], start[1], 0})  // [x,y,dis]
    grid[start[0]][start[1]] = -grid[start[0]][start[1]] // 置反
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        x, y, dis := node[0], node[1], node[2]
        if pricing[0] <= -grid[x][y] && -grid[x][y] <= pricing[1] { // 起点判断
            arr = append(arr, []int{dis, -grid[x][y], x, y})
        }
        for i := 0; i < 4; i++ {
            newX := x + dx[i]
            newY := y + dy[i]
            if 0 <= newX && newX < n && 0 <= newY && newY < m && grid[newX][newY] > 0 {
                queue = append(queue, []int{newX, newY, dis + 1})
                grid[newX][newY] = -grid[newX][newY]
            }
        }
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][0] == arr[j][0] {
            if arr[i][1] == arr[j][1] {
                if arr[i][2] == arr[j][2] {
                    return arr[i][3] < arr[j][3]
                }
                return arr[i][2] < arr[j][2]
            }
            return arr[i][1] < arr[j][1]
        }
        return arr[i][0] < arr[j][0]
    })
    res := make([][]int, 0)
    for i := 0; i < k && i < len(arr); i++ {
        res = append(res, []int{arr[i][2], arr[i][3]})
    }
    return res
}

2149.按符号重排数组(1)

  • 题目
给你一个下标从 0 开始的整数数组 nums ,数组长度为 偶数 ,由数目相等的正整数和负整数组成。
你需要 重排 nums 中的元素,使修改后的数组满足下述条件:
任意连续 的两个整数 符号相反
对于符号相同的所有整数,保留 它们在 nums 中的 顺序 。
重排后数组以正整数开头。
重排元素满足上述条件后,返回修改后的数组。
示例 1:输入:nums = [3,1,-2,-5,2,-4] 输出:[3,-2,1,-5,2,-4]
解释:nums 中的正整数是 [3,1,2] ,负整数是 [-2,-5,-4] 。
重排的唯一可行方案是 [3,-2,1,-5,2,-4],能满足所有条件。
像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的,因为不满足一个或者多个条件。 
示例 2:输入:nums = [-1,1] 输出:[1,-1]
解释:1 是 nums 中唯一一个正整数,-1 是 nums 中唯一一个负整数。
所以 nums 重排为 [1,-1] 。
提示:2 <= nums.length <= 2 * 105
nums.length 是 偶数
1 <= |nums[i]| <= 105
nums 由 相等 数量的正整数和负整数组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func rearrangeArray(nums []int) []int {
    res := make([]int, len(nums))
    i, j := 0, 1
    for k := 0; k < len(nums); k++ {
        if nums[k] > 0 {
            res[i] = nums[k]
            i = i + 2
        } else {
            res[j] = nums[k]
            j = j + 2
        }
    }
    return res
}

2150.找出数组中的所有孤独数字(2)

  • 题目
给你一个整数数组 nums 。如果数字 x 在数组中仅出现 一次 ,
且没有 相邻 数字(即,x + 1 和 x - 1)出现在数组中,则认为数字 x 是 孤独数字 。
返回 nums 中的 所有 孤独数字。你可以按 任何顺序 返回答案。
示例 1:输入:nums = [10,6,5,8] 输出:[10,8]
解释:- 10 是一个孤独数字,因为它只出现一次,并且 9 和 11 没有在 nums 中出现。
- 8 是一个孤独数字,因为它只出现一次,并且 7 和 9 没有在 nums 中出现。
- 5 不是一个孤独数字,因为 6 出现在 nums 中,反之亦然。
因此,nums 中的孤独数字是 [10, 8] 。
注意,也可以返回 [8, 10] 。
示例 2:输入:nums = [1,3,5,3] 输出:[1,5]
解释:- 1 是一个孤独数字,因为它只出现一次,并且 0 和 2 没有在 nums 中出现。
- 5 是一个孤独数字,因为它只出现一次,并且 4 和 6 没有在 nums 中出现。
- 3 不是一个孤独数字,因为它出现两次。
因此,nums 中的孤独数字是 [1, 5] 。
注意,也可以返回 [5, 1] 。
提示:1 <= nums.length <= 105
0 <= nums[i] <= 106
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 排序 O(nlog(n)) O(n)
func findLonely(nums []int) []int {
    res := make([]int, 0)
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]]++
    }
    for k, v := range m {
        if v == 1 && m[k-1] == 0 && m[k+1] == 0 {
            res = append(res, k)
        }
    }
    return res
}

# 2
func findLonely(nums []int) []int {
    res := make([]int, 0)
    nums = append(nums, math.MinInt32)
    nums = append(nums, math.MaxInt32)
    sort.Ints(nums)
    for i := 1; i < len(nums)-1; i++ {
        if nums[i]-nums[i-1] > 1 && nums[i+1]-nums[i] > 1 {
            res = append(res, nums[i])
        }
    }
    return res
}

2155.分组得分最高的所有下标(2)

  • 题目
给你一个下标从 0 开始的二进制数组 nums ,数组长度为 n 。
nums 可以按下标 i( 0 <= i <= n )拆分成两个数组(可能为空):numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素(包括 0 和 i - 1 ),
而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素(包括 i 和 n - 1 )。
如果 i == 0 ,numsleft 为 空 ,而 numsright 将包含 nums 中的所有元素。
如果 i == n ,numsleft 将包含 nums 中的所有元素,而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1:输入:nums = [0,0,1,0] 输出:[2,4]
解释:按下标分组
- 0 :numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
- 1 :numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
- 2 :numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
- 3 :numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 4 :numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意,答案 [4,2] 也被视为正确答案。
示例 2:输入:nums = [0,0,0] 输出:[3]
解释:按下标分组
- 0 :numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。
- 1 :numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。
- 2 :numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 3 :numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
只有下标 3 可以得到最高的分组得分 3 。
示例 3:输入:nums = [1,1] 输出:[0]
解释:按下标分组
- 0 :numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。
- 1 :numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。
- 2 :numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。
只有下标 0 可以得到最高的分组得分 2 。
提示:n == nums.length
1 <= n <= 105
nums[i] 为 0 或 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
func maxScoreIndices(nums []int) []int {
    res := []int{0}
    sum := 0
    maxValue := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            sum++
        } else {
            sum--
        }
        if sum > maxValue {
            maxValue = sum
            res = []int{i + 1}
        } else if sum == maxValue {
            res = append(res, i+1)
        }
    }
    return res
}

# 2
func maxScoreIndices(nums []int) []int {
    res := []int{0}
    left, right := 0, 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 1 {
            right++
        }
    }
    maxValue := left + right
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            left++
        } else {
            right--
        }
        if left+right > maxValue {
            maxValue = left + right
            res = []int{i + 1}
        } else if left+right == maxValue {
            res = append(res, i+1)
        }
    }
    return res
}

2156.查找给定哈希值的子串(1)

  • 题目
给定整数 p和 m,一个长度为 k且下标从 0开始的字符串s的哈希值按照如下函数计算:
hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
其中val(s[i])表示s[i]在字母表中的下标,从val('a') = 1 到val('z') = 26。
给你一个字符串s和整数power,modulo,k和hashValue。
请你返回 s中 第一个 长度为 k的 子串sub,满足hash(sub, power, modulo) == hashValue。
测试数据保证一定 存在至少一个这样的子串。
子串 定义为一个字符串中连续非空字符组成的序列。
示例 1:输入:s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0 输出:"ee"
解释:"ee" 的哈希值为 hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 。
"ee" 是长度为 2 的第一个哈希值为 0 的子串,所以我们返回 "ee" 。
示例 2:输入:s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32 输出:"fbx"
解释:"fbx" 的哈希值为 hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32 。
"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串,所以我们返回 "fbx" 。
注意,"bxz" 的哈希值也为 32 ,但是它在字符串中比 "fbx" 更晚出现。
提示:1 <= k <= s.length <= 2 * 104
1 <= power, modulo <= 109
0 <= hashValue < modulo
s只包含小写英文字母。
测试数据保证一定 存在满足条件的子串。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(n) O(1)
func subStrHash(s string, power int, modulo int, k int, hashValue int) string {
    n := len(s)
    p := 1   // power的k次方
    sum := 0 // 和
    // 第一个长度为k的结果
    for i := n - 1; i >= n-k; i-- {
        p = p * power % modulo
        a := int(s[i]-'a') + 1
        sum = (a + sum*power) % modulo
    }
    res := s[n-k:] // 题目保证至少有1个
    // 逆序计算:滑动窗口
    for i := n - k - 1; i >= 0; i-- {
        a := int(s[i]-'a') + 1 + sum*power      // k+1位
        b := (int(s[i+k]-'a') + 1) * p % modulo // s[i+k]*power^k
        // 模p运算:分配律
        // (a+b) % mod  = (a%mod + b%mod) % mod
        // (a-b) % mod  = (a%mod - b%mod ) % mod
        // (a-b) % mod  = (a%mod - b%mod + mod ) % mod:go有负数,+mod再mod
        sum = (a - b + modulo) % modulo
        if sum == hashValue {
            res = s[i : i+k]
        }
    }
    return res
}

2161.根据给定数字划分数组(3)

  • 题目
给你一个下标从 0开始的整数数组nums和一个整数pivot。请你将nums重新排列,使得以下条件均成立:
所有小于pivot的元素都出现在所有大于pivot的元素之前。
所有等于pivot的元素都出现在小于和大于 pivot的元素 中间。
小于 pivot的元素之间和大于 pivot的元素之间的 相对顺序不发生改变。
更正式的,考虑每一对pi,pj,pi是初始时位置 i元素的新位置,pj是初始时位置j元素的新位置。
对于小于pivot的元素,如果i < j且nums[i] < pivot 和nums[j] < pivot都成立,那么pi < pj也成立。
类似的,对于大于pivot的元素,如果i < j 且nums[i] > pivot 和nums[j] > pivot都成立,那么pi < pj。
请你返回重新排列 nums数组后的结果数组。
示例 1:输入:nums = [9,12,5,10,14,3,10], pivot = 10 输出:[9,5,3,10,10,12,14]
解释:元素 9 ,5 和 3 小于 pivot ,所以它们在数组的最左边。
元素 12 和 14 大于 pivot ,所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ,
它们在结果数组中的相对顺序需要保留。
示例 2:输入:nums = [-3,4,3,2], pivot = 2 输出:[-3,2,4,3]
解释:元素 -3 小于 pivot ,所以在数组的最左边。
元素 4 和 3 大于 pivot ,所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ,它们在结果数组中的相对顺序需要保留。
提示:1 <= nums.length <= 105
-106 <= nums[i] <= 106
pivot等于nums中的一个元素。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针+反转 O(n) O(n)
02 遍历 O(n) O(n)
03 遍历 O(n) O(n)
func pivotArray(nums []int, pivot int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := 0; i < n; i++ {
        res[i] = pivot
    }
    left, right := 0, n-1
    for i := 0; i < n; i++ {
        if nums[i] < pivot {
            res[left] = nums[i]
            left++
        } else if nums[i] > pivot {
            res[right] = nums[i]
            right--
        }
    }
    reverse(res[right+1:]) // 反转后面顺序
    return res
}

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

# 2
func pivotArray(nums []int, pivot int) []int {
    n := len(nums)
    res := make([]int, 0)
    for i := 0; i < n; i++ {
        if nums[i] < pivot {
            res = append(res, nums[i])
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] == pivot {
            res = append(res, nums[i])
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] > pivot {
            res = append(res, nums[i])
        }
    }
    return res
}

# 3
func pivotArray(nums []int, pivot int) []int {
    n := len(nums)
    a, b, c := make([]int, 0), make([]int, 0), make([]int, 0)
    for i := 0; i < n; i++ {
        if nums[i] < pivot {
            a = append(a, nums[i])
        } else if nums[i] == pivot {
            b = append(b, nums[i])
        } else {
            c = append(c, nums[i])
        }
    }
    return append(a, append(b, c...)...)
}

2162.设置时间的最少代价(2)

  • 题目
常见的微波炉可以设置加热时间,且加热时间满足以下条件:
至少为 1秒钟。
至多为99分99秒。
你可以 最多输入4 个数字来设置加热时间。如果你输入的位数不足 4 位,微波炉会自动加 前缀0来补足 4 位。
微波炉会将设置好的四位数中,前两位当作分钟数,后两位当作秒数。它们所表示的总时间就是加热时间。比方说:
你输入9 5 4(三个数字),被自动补足为0954,并表示9分54秒。
你输入0 0 0 8(四个数字),表示0分8秒。
你输入8 0 9 0,表示80分90秒。
你输入8 1 3 0,表示81分30秒。
给你整数startAt,moveCost,pushCost和targetSeconds。
一开始,你的手指在数字startAt处。将手指移到任何其他数字,需要花费moveCost的单位代价。
每输入你手指所在位置的数字一次,需要花费pushCost的单位代价。
要设置targetSeconds秒的加热时间,可能会有多种设置方法。你想要知道这些方法中,总代价最小为多少。
请你能返回设置targetSeconds秒钟加热时间需要花费的最少代价。
请记住,虽然微波炉的秒数最多可以设置到 99秒,但一分钟等于60秒。
示例 1:输入:startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600 输出:6
解释:以下为设置加热时间的所有方法。
- 1 0 0 0 ,表示 10 分 0 秒。
 手指一开始就在数字 1 处,输入 1 (代价为 1),移到 0 处(代价为 2),
 输入 0(代价为 1),输入 0(代价为 1),输入 0(代价为 1)。
 总代价为:1 + 2 + 1 + 1 + 1 = 6 。这是所有方案中的最小代价。
- 0 9 6 0,表示 9 分 60 秒。它也表示 600 秒。
 手指移到 0 处(代价为 2),输入 0 (代价为 1),移到 9 处(代价为 2),
 输入 9(代价为 1),移到 6 处(代价为 2),输入 6(代价为 1),移到 0 处(代价为 2),输入 0(代价为 1)。
 总代价为:2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12 。
- 9 6 0,微波炉自动补全为 0960 ,表示 9 分 60 秒。
 手指移到 9 处(代价为 2),输入 9 (代价为 1),移到 6 处(代价为 2),
 输入 6(代价为 1),移到 0 处(代价为 2),输入 0(代价为 1)。
 总代价为:2 + 1 + 2 + 1 + 2 + 1 = 9 。
示例 2:输入:startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76 输出:6
解释:最优方案为输入两个数字 7 6,表示 76 秒。
手指移到 7 处(代价为 1),输入 7 (代价为 2),移到 6 处(代价为 1),输入 6(代价为 2)。
总代价为:1 + 2 + 1 + 2 = 6
其他可行方案为 0076 ,076 ,0116 和 116 ,但是它们的代价都比 6 大。
提示:0 <= startAt <= 9
1 <= moveCost, pushCost <= 105
1 <= targetSeconds <= 6039
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 枚举 O(1) O(1)
func minCostSetTime(startAt int, moveCost int, pushCost int, targetSeconds int) int {
    m, s := targetSeconds/60, targetSeconds%60
    a := cost(startAt, moveCost, pushCost, m, s)      // 目标1
    b := cost(startAt, moveCost, pushCost, m-1, s+60) // 目标2
    return min(a, b)
}

func cost(startAt int, moveCost int, pushCost int, m, s int) int {
    res := 0
    if m < 0 || m > 99 || s < 0 || s > 99 {
        return math.MaxInt32
    }
    arr := []int{m / 10, m % 10, s / 10, s % 10}
    i := 0 // 需要忽略0后的起始位置(前面0不需要输入)
    for i < 4 && arr[i] == 0 {
        i++
    }
    for j := i; j < 4; j++ { // 从i开始
        if startAt != arr[j] { // 不相同需要移动
            startAt = arr[j]
            res = res + moveCost // 移动
        }
        res = res + pushCost
    }

    return res
}

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

2165.重排数字的最小值(1)

  • 题目
给你一个整数 num 。重排 num 中的各位数字,使其值 最小化 且不含 任何 前导零。
返回不含前导零且值最小的重排数字。
注意,重排各位数字后,num 的符号不会改变。
示例 1:输入:num = 310 输出:103
解释:310 中各位数字的可行排列有:013、031、103、130、301、310 。
不含任何前导零且值最小的重排数字是 103 。
示例 2:输入:num = -7605 输出:-7650
解释:-7605 中各位数字的部分可行排列为:-7650、-6705、-5076、-0567。
不含任何前导零且值最小的重排数字是 -7650 。
提示:-1015 <= num <= 1015
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(n)
func smallestNumber(num int64) int64 {
    arr := []byte(strconv.FormatInt(num, 10))
    flag := int64(1)
    if num <= 0 {
        flag = -1
        arr = arr[1:]
    }
    if flag == 1 { // 正数
        sort.Slice(arr, func(i, j int) bool {
            return arr[i] < arr[j]
        })
        i := 0
        for arr[i] == '0' {
            i++
        }
        arr[0], arr[i] = arr[i], arr[0] // 交换第一个非0
    } else {
        sort.Slice(arr, func(i, j int) bool {
            return arr[i] > arr[j]
        })
    }
    res, _ := strconv.ParseInt(string(arr), 10, 64)
    return flag * res
}

2166.设计位集(2)

  • 题目
位集 Bitset 是一种能以紧凑形式存储位的数据结构。
请你实现 Bitset 类。
Bitset(int size) 用 size 个位初始化 Bitset ,所有位都是 0 。
void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ,则不会发生任何改变。
void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ,则不会发生任何改变。
void flip() 翻转 Bitset 中每一位上的值。换句话说,所有值为 0 的位将会变成 1 ,反之亦然。
boolean all() 检查Bitset 中 每一位 的值是否都是 1 。如果满足此条件,返回 true ;否则,返回 false 。
boolean one() 检查Bitset 中 是否至少一位 的值是 1 。如果满足此条件,返回 true ;否则,返回 false 。
int count() 返回 Bitset 中值为 1 的位的 总数 。
String toString() 返回 Bitset 的当前组成情况。注意,在结果字符串中,第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。
示例:输入["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
输出[null, null, null, null, false, null, null, true, null, 2, "01010"]
解释 Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // 将 idx = 3 处的值更新为 1 ,此时 bitset = "00010" 。
bs.fix(1);     // 将 idx = 1 处的值更新为 1 ,此时 bitset = "01010" 。
bs.flip();     // 翻转每一位上的值,此时 bitset = "10101" 。
bs.all();      // 返回 False ,bitset 中的值不全为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ,此时 bitset = "00101" 。
bs.flip();     // 翻转每一位上的值,此时 bitset = "11010" 。
bs.one();      // 返回 True ,至少存在一位的值为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ,此时 bitset = "01010" 。
bs.count();    // 返回 2 ,当前有 2 位的值为 1 。
bs.toString(); // 返回 "01010" ,即 bitset 的当前组成情况。
提示:1 <= size <= 105
0 <= idx <= size - 1
至多调用fix、unfix、flip、all、one、count 和 toString 方法 总共 105 次
至少调用 all、one、count 或 toString 方法一次
至多调用toString 方法 5 次
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组 O(n) O(n)
02 数组 O(n) O(n)
type Bitset struct {
    arr       []int
    count     int // 1的数量
    flipCount int // 反转的次量
}

func Constructor(size int) Bitset {
    return Bitset{
        arr:       make([]int, size),
        count:     0,
        flipCount: 0,
    }
}

func (this *Bitset) Fix(idx int) {
    if (this.flipCount%2 == 0 && this.arr[idx] == 0) ||
        (this.flipCount%2 == 1 && this.arr[idx] == 1) {
        this.count++
        this.arr[idx] = 1 - this.arr[idx]
    }
}

func (this *Bitset) Unfix(idx int) {
    if (this.flipCount%2 == 0 && this.arr[idx] == 1) ||
        (this.flipCount%2 == 1 && this.arr[idx] == 0) {
        this.count--
        this.arr[idx] = 1 - this.arr[idx]
    }
}

func (this *Bitset) Flip() {
    this.flipCount++
    this.count = len(this.arr) - this.count
}

func (this *Bitset) All() bool {
    return len(this.arr) == this.count
}

func (this *Bitset) One() bool {
    return this.count > 0
}

func (this *Bitset) Count() int {
    return this.count
}

func (this *Bitset) ToString() string {
    temp := make([]byte, len(this.arr))
    for i := 0; i < len(this.arr); i++ {
        v := this.arr[i]
        if this.flipCount%2 == 1 {
            v = 1 - v
        }
        temp[i] = byte('0' + v)
    }
    return string(temp)
}

# 2
type Bitset struct {
    arr       []byte
    count     int // 1的数量
    flipCount int // 反转的次量
}

func Constructor(size int) Bitset {
    arr := bytes.Repeat([]byte{'0'}, size)
    return Bitset{
        arr:       arr,
        count:     0,
        flipCount: 0,
    }
}

func (this *Bitset) Fix(idx int) {
    if (this.flipCount%2 == 0 && this.arr[idx] == '0') ||
        (this.flipCount%2 == 1 && this.arr[idx] == '1') {
        this.count++
        this.arr[idx] = '0' + ('1' - this.arr[idx])
    }
}

func (this *Bitset) Unfix(idx int) {
    if (this.flipCount%2 == 0 && this.arr[idx] == '1') ||
        (this.flipCount%2 == 1 && this.arr[idx] == '0') {
        this.count--
        this.arr[idx] = '0' + ('1' - this.arr[idx])
    }
}

func (this *Bitset) Flip() {
    this.flipCount++
    this.count = len(this.arr) - this.count
}

func (this *Bitset) All() bool {
    return len(this.arr) == this.count
}

func (this *Bitset) One() bool {
    return this.count > 0
}

func (this *Bitset) Count() int {
    return this.count
}

func (this *Bitset) ToString() string {
    if this.flipCount%2 == 1 {
        temp := make([]byte, len(this.arr))
        for i := 0; i < len(this.arr); i++ {
            temp[i] = '0' + ('1' - this.arr[i])
        }
        return string(temp)
    }
    return string(this.arr)
}

2170.使数组变成交替数组的最少操作数(2)

  • 题目
给你一个下标从 0 开始的数组 nums ,该数组由 n 个正整数组成。
如果满足下述条件,则数组 nums 是一个 交替数组 :
nums[i - 2] == nums[i] ,其中 2 <= i <= n - 1 。
nums[i - 1] != nums[i] ,其中 1 <= i <= n - 1 。
在一步 操作 中,你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。
返回使数组变成交替数组的 最少操作数 。
示例 1:输入:nums = [3,1,3,2,4,3] 输出:3
解释:使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。
在这种情况下,操作数为 3 。
可以证明,操作数少于 3 的情况下,无法使数组变成交替数组。
示例 2:输入:nums = [1,2,2,2,2] 输出:2
解释:使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1].
在这种情况下,操作数为 2 。
注意,数组不能转换成 [2,2,2,2,2] 。因为在这种情况下,nums[0] == nums[1],不满足交替数组的条件。
提示:1 <= nums.length <= 105
1 <= nums[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希 O(n) O(n)
02 哈希+排序 O(nlog(n)) O(n)
func minimumOperations(nums []int) int {
    m := [2]map[int]int{}
    for i := 0; i < 2; i++ {
        m[i] = make(map[int]int)
    }
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            m[0][nums[i]]++
        } else {
            m[1][nums[i]]++
        }
    }
    a := getMaxValue(m[0])
    b := getMaxValue(m[1])
    if a[0] == b[0] {
        return len(nums) - max(a[1]+b[3], a[3]+b[1])
    }
    return len(nums) - a[1] - b[1]
}

func getMaxValue(m map[int]int) []int {
    firstValue, firstIndex := 0, 0
    secondValue, secondIndex := 0, 0
    for k, v := range m {
        if v > firstValue {
            secondIndex, secondValue = firstIndex, firstValue
            firstIndex, firstValue = k, v
        } else if v > secondValue {
            secondIndex, secondValue = k, v
        }
    }
    return []int{firstIndex, firstValue, secondIndex, secondValue}
}

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

# 2
func minimumOperations(nums []int) int {
    m := [2]map[int]int{}
    for i := 0; i < 2; i++ {
        m[i] = make(map[int]int)
    }
    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            m[0][nums[i]]++
        } else {
            m[1][nums[i]]++
        }
    }
    a := make([][2]int, 0)
    b := make([][2]int, 0)
    for i := 0; i < 2; i++ {
        temp := make([][2]int, 2) // 0补足
        for k, v := range m[i] {
            temp = append(temp, [2]int{k, v})
        }
        sort.Slice(temp, func(i, j int) bool {
            return temp[i][1] > temp[j][1]
        })
        if i%2 == 0 {
            a = temp[:2]
        } else {
            b = temp[:2]
        }
    }
    if a[0][0] == b[0][0] {
        return len(nums) - max(a[0][1]+b[1][1], a[1][1]+b[0][1])
    }
    return len(nums) - a[0][1] - b[0][1]
}

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

2171.拿出最少数目的魔法豆(1)

  • 题目
给你一个 正整数数组beans,其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中拿出一些豆子(也可以不拿出),使得剩下的 非空 袋子中(即 至少还有 一颗魔法豆的袋子)魔法豆的数目相等。
一旦魔法豆从袋子中取出,你不能将它放到任何其他的袋子中。
请你返回你需要拿出魔法豆的 最少数目。
示例 1:输入:beans = [4,1,6,5] 输出:4
解释:- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为:[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为:[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为:[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆,剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。
示例 2:输入:beans = [2,10,3,2] 输出:7
解释:- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为:[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为:[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为:[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆,剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。
提示:1 <= beans.length <= 105
1 <= beans[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
func minimumRemoval(beans []int) int64 {
    n := len(beans)
    sum := int64(0)
    for i := 0; i < n; i++ {
        sum = sum + int64(beans[i])
    }
    res := sum
    sort.Ints(beans)
    for i := 0; i < n; i++ {
        res = min(res, sum-int64(beans[i])*int64(n-i)) // 把较大的n-i个数都变为beans[i]
    }
    return res
}

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

2177.找到和为给定整数的三个连续整数(1)

  • 题目
给你一个整数num,请你返回三个连续的整数,它们的和为num。如果num无法被表示成三个连续整数的和,请你返回一个 空数组。
示例 1:输入:num = 33 输出:[10,11,12]
解释:33 可以表示为 10 + 11 + 12 = 33 。
10, 11, 12 是 3 个连续整数,所以返回 [10, 11, 12] 。
示例 2:输入:num = 4 输出:[]
解释:没有办法将 4 表示成 3 个连续整数的和。
提示:0 <= num <= 1015
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(1) O(1)
func sumOfThree(num int64) []int64 {
    if num%3 == 0 {
        target := num / 3
        return []int64{target - 1, target, target + 1}
    }
    return nil
}

2178.拆分成最多数目的正偶数之和(1)

  • 题目
给你一个整数finalSum。请你将它拆分成若干个互不相同 的正偶数之和,且拆分出来的正偶数数目最多。
比方说,给你finalSum = 12,那么这些拆分是符合要求 的(互不相同的正偶数且和为finalSum):
(2 + 10),(2 + 4 + 6)和(4 + 8)。
它们中,(2 + 4 + 6)包含最多数目的整数。注意finalSum不能拆分成(2 + 2 + 4 + 4),因为拆分出来的整数必须互不相同。
请你返回一个整数数组,表示将整数拆分成 最多 数目的正偶数数组。
如果没有办法将finalSum进行拆分,请你返回一个空数组。你可以按 任意顺序返回这些整数。
示例 1:输入:finalSum = 12 输出:[2,4,6]
解释:以下是一些符合要求的拆分:(2 + 10),(2 + 4 + 6) 和 (4 + 8) 。
(2 + 4 + 6) 为最多数目的整数,数目为 3 ,所以我们返回 [2,4,6] 。
[2,6,4] ,[6,2,4] 等等也都是可行的解。
示例 2:输入:finalSum = 7 输出:[]
解释:没有办法将 finalSum 进行拆分。
所以返回空数组。
示例 3:输入:finalSum = 28 输出:[6,8,2,12]
解释:以下是一些符合要求的拆分:(2 + 26),(6 + 8 + 2 + 12) 和 (4 + 24) 。
(6 + 8 + 2 + 12) 有最多数目的整数,数目为 4 ,所以我们返回 [6,8,2,12] 。
[10,2,4,12] ,[6,2,4,16] 等等也都是可行的解。
提示:1 <= finalSum <= 1010
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(n^(1/2)) O(n^(1/2))
func maximumEvenSplit(finalSum int64) []int64 {
    if finalSum%2 == 1 {
        return nil
    }
    res := make([]int64, 0)
    for i := int64(2); i <= finalSum; i = i + 2 {
        res = append(res, i)
        finalSum = finalSum - i // 减去当前值
    }
    res[len(res)-1] = res[len(res)-1] + finalSum // 剩下数加到最后1位
    return res
}

2181.合并零之间的节点(2)

  • 题目
给你一个链表的头节点 head ,该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ,请你将它们之间的所有节点合并成一个节点,其值是所有已合并节点的值之和。
然后将所有 0 移除,修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
示例 1:输入:head = [0,3,1,0,4,5,2,0] 输出:[4,11]
解释:上图表示输入的链表。修改后的链表包含:
- 标记为绿色的节点之和:3 + 1 = 4
- 标记为红色的节点之和:4 + 5 + 2 = 11
示例 2:输入:head = [0,1,0,3,0,2,2,0] 输出:[1,3,4]
解释:上图表示输入的链表。修改后的链表包含:
- 标记为绿色的节点之和:1 = 1
- 标记为红色的节点之和:3 = 3
- 标记为黄色的节点之和:2 + 2 = 4
提示:列表中的节点数目在范围 [3, 2 * 105] 内
0 <= Node.val <= 1000
不 存在连续两个Node.val == 0 的节点
链表的 开端 和 末尾 节点都满足 Node.val == 0
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(n)
02 遍历 O(n) O(1)
func mergeNodes(head *ListNode) *ListNode {
    temp := make([]int, 0)
    for head != nil {
        temp = append(temp, head.Val)
        head = head.Next
    }
    sum := 0
    arr := make([]int, 0)
    for i := 1; i < len(temp); i++ {
        if temp[i] == 0 && sum != 0 {
            arr = append(arr, sum)
            sum = 0
        } else {
            sum = sum + temp[i]
        }
    }
    res := &ListNode{}
    t := res
    for i := 0; i < len(arr); i++ {
        t.Next = &ListNode{
            Val:  arr[i],
            Next: nil,
        }
        t = t.Next
    }
    return res.Next
}

# 2
func mergeNodes(head *ListNode) *ListNode {
    res := &ListNode{}
    t := res
    sum := 0
    for cur := head.Next; cur != nil; cur = cur.Next {
        if cur.Val == 0 {
            node := &ListNode{
                Val: sum,
            }
            t.Next = node
            t = t.Next
            sum = 0
        } else {
            sum = sum + cur.Val
        }
    }
    return res.Next
}

2182.构造限制重复的字符串(1)

  • 题目
给你一个字符串 s 和一个整数 repeatLimit ,用 s 中的字符构造一个新字符串 repeatLimitedString ,
使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置,字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚,
则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同,那么较长的字符串字典序更大。
示例 1:输入:s = "cczazcc", repeatLimit = 3 输出:"zzcccac"
解释:使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此,没有字母连续出现超过 repeatLimit 次,字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ,所以返回 "zzcccac" 。
注意,尽管 "zzcccca" 字典序更大,但字母 'c' 连续出现超过 3 次,所以它不是一个有效的 repeatLimitedString 。
示例 2:输入:s = "aababab", repeatLimit = 2 输出:"bbabaa"
解释:使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。 
字母 'a' 连续出现至多 2 次。 
字母 'b' 连续出现至多 2 次。 
因此,没有字母连续出现超过 repeatLimit 次,字符串是一个有效的 repeatLimitedString 。 
该字符串是字典序最大的 repeatLimitedString ,所以返回 "bbabaa" 。 
注意,尽管 "bbabaaa" 字典序更大,但字母 'a' 连续出现超过 2 次,所以它不是一个有效的 repeatLimitedString 。
提示:1 <= repeatLimit <= s.length <= 105
s 由小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(n)
func repeatLimitedString(s string, repeatLimit int) string {
    arr := make([]int, 26)
    for i := 0; i < len(s); i++ {
        arr[int(s[i]-'a')]++
    }
    res := make([]byte, 0)
    for i := 25; i >= 0; i-- {
        prev := i - 1
        for {
            count := min(repeatLimit, arr[i])
            arr[i] = arr[i] - count
            res = append(res, bytes.Repeat([]byte{byte('a' + i)}, count)...)
            if arr[i] == 0 { // 用完退出
                break
            }
            for prev >= 0 && arr[prev] == 0 {
                prev--
            }
            if prev < 0 { // 没有次大值退出
                break
            }
            arr[prev]--
            res = append(res, byte('a'+prev)) // 添加次大值
        }
    }
    return string(res)
}

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

2186.使两字符串互为字母异位词的最少步骤数(1)

  • 题目
给你两个字符串 s 和 t 。在一步操作中,你可以给 s 或者 t 追加 任一字符 。
返回使 s 和 t 互为 字母异位词 所需的最少步骤数。
字母异位词 指字母相同但是顺序不同(或者相同)的字符串。
示例 1:输入:s = "leetcode", t = "coats" 输出:7
解释:- 执行 2 步操作,将 "as" 追加到 s = "leetcode" 中,得到 s = "leetcodeas" 。
- 执行 5 步操作,将 "leede" 追加到 t = "coats" 中,得到 t = "coatsleede" 。
"leetcodeas" 和 "coatsleede" 互为字母异位词。
总共用去 2 + 5 = 7 步。
可以证明,无法用少于 7 步操作使这两个字符串互为字母异位词。
示例 2:输入:s = "night", t = "thing" 输出:0
解释:给出的字符串已经互为字母异位词。因此,不需要任何进一步操作。
提示:1 <= s.length, t.length <= 2 * 105
s 和 t 由小写英文字符组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func minSteps(s string, t string) int {
    arr := make([]int, 26)
    for i := 0; i < len(s); i++ {
        arr[int(s[i]-'a')]++
    }
    for i := 0; i < len(t); i++ {
        arr[int(t[i]-'a')]--
    }
    res := 0
    for i := 0; i < 26; i++ {
        res = res + abs(arr[i])
    }
    return res
}

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

2187.完成旅途的最少时间(2)

  • 题目
给你一个数组time,其中time[i]表示第 i辆公交车完成 一趟旅途所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途,也就是说,一辆公交车当前旅途完成后,可以 立马开始下一趟旅途。
每辆公交车 独立运行,也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数totalTrips,表示所有公交车总共需要完成的旅途数目。请你返回完成 至少totalTrips趟旅途需要花费的 最少时间。
示例 1:输入:time = [1,2,3], totalTrips = 5 输出:3
解释:- 时刻 t = 1 ,每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ,每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ,每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。
示例 2:输入:time = [2], totalTrips = 1 输出:2
解释:只有一辆公交车,它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。
提示:1 <= time.length <= 105
1 <= time[i], totalTrips <= 107
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(nlog(n)) O(1)
02 二分查找 O(nlog(n)) O(1)
func minimumTime(time []int, totalTrips int) int64 {
    n := len(time)
    maxValue := 0
    for i := 0; i < n; i++ {
        maxValue = max(maxValue, time[i])
    }
    left := int64(1)
    right := int64(totalTrips) * int64(maxValue)
    for left < right {
        mid := left + (right-left)/2
        if check(time, mid) >= totalTrips {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func check(arr []int, per int64) int {
    count := 0
    for i := 0; i < len(arr); i++ {
        count = count + int(per/int64(arr[i]))
    }
    return count
}

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

# 2
func minimumTime(time []int, totalTrips int) int64 {
    n := len(time)
    maxValue := 0
    for i := 0; i < n; i++ {
        maxValue = max(maxValue, time[i])
    }
    right := totalTrips * maxValue
    return int64(sort.Search(right, func(per int) bool {
        count := 0
        for i := 0; i < len(time); i++ {
            count = count + int(per/time[i])
        }
        return count >= totalTrips
    }))
}

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

2192.有向无环图中一个节点的所有祖先(1)

  • 题目
给你一个正整数n,它表示一个 有向无环图中节点的数目,节点编号为0到n - 1(包括两者)。
给你一个二维整数数组edges,其中edges[i] = [fromi, toi]表示图中一条从fromi到toi的单向边。
请你返回一个数组answer,其中answer[i]是第i个节点的所有祖先,这些祖先节点升序排序。
如果 u通过一系列边,能够到达 v,那么我们称节点 u是节点 v的 祖先节点。
示例 1:输入:n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出:[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释:上图为输入所对应的图。
- 节点 0 ,1 和 2 没有任何祖先。
- 节点 3 有 2 个祖先 0 和 1 。
- 节点 4 有 2 个祖先 0 和 2 。
- 节点 5 有 3 个祖先 0 ,1 和 3 。
- 节点 6 有 5 个祖先 0 ,1 ,2 ,3 和 4 。
- 节点 7 有 4 个祖先 0 ,1 ,2 和 3 。
示例 2:输入:n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出:[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释:上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ,1 和 2 。
- 节点 4 有 4 个祖先 0 ,1 ,2 和 3 。
提示:1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n - 1
fromi != toi
图中不会有重边。
图是 有向 且 无环 的。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 拓扑排序 O(n^2log(n)) O(n^2)
func getAncestors(n int, edges [][]int) [][]int {
    m := make([]map[int]bool, n) // 祖先节点要去重
    for i := 0; i < n; i++ {
        m[i] = make(map[int]bool)
    }
    arr := make([][]int, n)
    inDegree := make([]int, n) // 入度
    for i := 0; i < len(edges); i++ {
        a, b := edges[i][0], edges[i][1] // a=>b
        arr[a] = append(arr[a], b)
        inDegree[b]++
    }
    queue := make([]int, 0)
    for i := 0; i < n; i++ {
        if inDegree[i] == 0 { // 入度为0的
            queue = append(queue, i)
        }
    }
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        for i := 0; i < len(arr[cur]); i++ {
            next := arr[cur][i]
            m[next][cur] = true     // 保存父节点
            for k := range m[cur] { // 把父节点的祖先节点也保存下来
                m[next][k] = true
            }
            inDegree[next]--
            if inDegree[next] == 0 {
                queue = append(queue, next)
            }
        }
    }
    // 排序
    res := make([][]int, n)
    for i := 0; i < n; i++ {
        for k, _ := range m[i] {
            res[i] = append(res[i], k)
        }
        sort.Ints(res[i])
    }
    return res
}

2195.向数组中追加K个整数

题目

给你一个整数数组 nums 和一个整数 k 。
请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数,并使结果数组的元素和 最小 。
返回追加到 nums 中的 k 个整数之和。
示例 1:输入:nums = [1,4,25,10,25], k = 2 输出:5
解释:在该解法中,向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ,这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ,所以返回 5 。
示例 2:输入:nums = [5,6], k = 6 输出:25
解释:在该解法中,向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。
nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ,这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ,所以返回 25 。
提示:1 <= nums.length <= 105
1 <= nums[i], k <= 109

解题思路

No. 思路 时间复杂度 空间复杂度
01 排序+哈希 O(nlog(n)) O(n)
func minimalKSum(nums []int, k int) int64 {
    sum := int64(0)
    sort.Ints(nums)
    m := make(map[int]bool)
    for i := 0; i < len(nums); i++ {
        if m[nums[i]] == false && nums[i] <= k {
            sum = sum + int64(nums[i]) // 存在小于K的,加起来
            k++                        // k+1
        }
        m[nums[i]] = true
    }
    return int64((k+1)*k/2) - sum
}

2196.根据描述创建二叉树(1)

  • 题目
给你一个二维整数数组 descriptions ,其中 descriptions[i] = [parenti, childi, isLefti] 
表示 parenti 是 childi 在 二叉树 中的 父节点,二叉树中各节点的值 互不相同 。此外:
如果 isLefti == 1 ,那么 childi 就是 parenti 的左子节点。
如果 isLefti == 0 ,那么 childi 就是 parenti 的右子节点。
请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
测试用例会保证可以构造出 有效 的二叉树。
示例 1:输入:descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] 输出:[50,20,80,15,17,19]
解释:根节点是值为 50 的节点,因为它没有父节点。
结果二叉树如上图所示。
示例 2:输入:descriptions = [[1,2,1],[2,3,0],[3,4,1]] 输出:[1,2,null,null,3,4]
解释:根节点是值为 1 的节点,因为它没有父节点。 
结果二叉树如上图所示。 
提示:1 <= descriptions.length <= 104
descriptions[i].length == 3
1 <= parenti, childi <= 105
0 <= isLefti <= 1
descriptions 所描述的二叉树是一棵有效二叉树
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希 O(n) O(n)
func createBinaryTree(descriptions [][]int) *TreeNode {
    m := make(map[int]*TreeNode)
    visited := make(map[int]bool) // 保存子节点
    for i := 0; i < len(descriptions); i++ {
        a, b, c := descriptions[i][0], descriptions[i][1], descriptions[i][2]
        if m[a] == nil {
            m[a] = &TreeNode{Val: a}
        }
        if m[b] == nil {
            m[b] = &TreeNode{Val: b}
        }
        if c == 1 {
            m[a].Left = m[b]
        } else {
            m[a].Right = m[b]
        }
        visited[b] = true
    }
    for k := range m {
        if visited[k] == false { // 根节点不属于子节点
            return m[k]
        }
    }
    return nil
}

2101-2200-Hard

2106.摘水果(2)

  • 题目
在一个无限的 x 坐标轴上,有许多水果分布在其中某些位置。
给你一个二维整数数组 fruits ,其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。
fruits 已经按 positioni 升序排列 ,每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初,你位于 startPos 。从任何位置,你可以选择 向左或者向右 走。
在 x 轴上每移动 一个单位 ,就记作 一步 。你总共可以走 最多 k 步。
你每达到一个位置,都会摘掉全部的水果,水果也将从该位置消失(不会再生)。
返回你可以摘到水果的 最大总数 。
示例 1:输入:fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4 输出:9
解释:最佳路线为:
- 向右移动到位置 6 ,摘到 3 个水果
- 向右移动到位置 8 ,摘到 6 个水果
移动 3 步,共摘到 3 + 6 = 9 个水果
示例 2:输入:fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4 输出:14
解释:可以移动最多 k = 4 步,所以无法到达位置 0 和位置 10 。
最佳路线为:
- 在初始位置 5 ,摘到 7 个水果
- 向左移动到位置 4 ,摘到 1 个水果
- 向右移动到位置 6 ,摘到 2 个水果
- 向右移动到位置 7 ,摘到 4 个水果
移动 1 + 3 = 4 步,共摘到 7 + 1 + 2 + 4 = 14 个水果
示例 3:输入:fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2 输出:0
解释:最多可以移动 k = 2 步,无法到达任一有水果的地方
提示:1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
对于任意 i > 0 ,positioni-1 < positioni 均成立(下标从 0 开始计数)
1 <= amounti <= 104
0 <= k <= 2 * 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前缀和+二分查找 O(nlog(n)) O(n)
02 滑动窗口 O(n) O(1)
func maxTotalFruits(fruits [][]int, startPos int, k int) int {
    res := 0
    n := len(fruits)
    sum := make([]int, n+1)
    position := make([]int, n)
    for i := 0; i < n; i++ {
        position[i] = fruits[i][0]
        sum[i+1] = sum[i] + fruits[i][1]
    }
    for i := 0; i <= k/2; i++ { // 尝试所有组合,先i后j
        j := k - 2*i
        res = max(res, getValue(position, sum, startPos-i, startPos+j)) // i往左边、j往右边
        res = max(res, getValue(position, sum, startPos-j, startPos+i)) // i往右边、j往左边
    }
    return res
}

func getValue(arr []int, sum []int, left, right int) int {
    l := sort.Search(len(arr), func(i int) bool {
        return arr[i] >= left // 第一个大于等于left的下标
    })
    r := sort.Search(len(arr), func(i int) bool {
        return arr[i] > right // 第一个大于right的下标
    })
    return sum[r] - sum[l]
}

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

# 2
func maxTotalFruits(fruits [][]int, startPos int, k int) int {
    res := 0
    sum := 0
    i := 0
    for j := 0; j < len(fruits); j++ {
        // 滑动窗口:左右距离+2者最小距离<=k
        for i <= j && (min(abs(startPos-fruits[i][0]), abs(startPos-fruits[j][0]))+
            fruits[j][0]-fruits[i][0]) > k {
            sum = sum - fruits[i][1]
            i++
        }
        sum = sum + fruits[j][1]
        res = max(res, sum)
    }
    return res
}

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

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

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

2111.使数组K递增的最少操作次数(2)

  • 题目
给你一个下标从 0开始包含 n个正整数的数组arr,和一个正整数k。
如果对于每个满足k <= i <= n-1的下标i,都有arr[i-k] <= arr[i],那么我们称arr是 K递增 的。
比方说,arr = [4, 1, 5, 2, 6, 2]对于k = 2是 K 递增的,因为:
arr[0] <= arr[2] (4 <= 5)
arr[1] <= arr[3] (1 <= 2)
arr[2] <= arr[4] (5 <= 6)
arr[3] <= arr[5] (2 <= 2)
但是,相同的数组arr对于k = 1不是 K 递增的(因为arr[0] > arr[1]),
对于k = 3也不是 K 递增的(因为arr[0] > arr[3])。
每一次 操作中,你可以选择一个下标i 并将arr[i] 改成任意正整数。
请你返回对于给定的 k,使数组变成 K 递增的 最少操作次数。
示例 1:输入:arr = [5,4,3,2,1], k = 1 输出:4
解释:对于 k = 1 ,数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9],[1,1,1,1,1],[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ,因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。
示例 2:输入:arr = [4,1,5,2,6,2], k = 2 输出:0
解释:这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ,有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的,我们不需要进行任何操作。
示例 3:输入:arr = [4,1,5,2,6,2], k = 3 输出:2
解释:下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ,且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的,但没有任何一种方法需要的操作次数小于 2 次。
提示:1 <= arr.length <= 105
1 <= arr[i], k <= arr.length
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划+二分查找 O(nlog(n)) O(n)
02 动态规划+二分查找 O(nlog(n)) O(n)
func kIncreasing(arr []int, k int) int {
    res := 0
    for i := 1; i <= k; i++ {
        num := make([]int, 0)
        num = append(num, arr[i-1])
        for j := i - 1; j < len(arr)-k; j = j + k {
            num = append(num, arr[j+k])
        }
        count := lengthOfLIS(num)
        res = res + len(num) - count
    }
    return res
}

func lengthOfLIS(nums []int) int {
    if len(nums) < 2 {
        return len(nums)
    }
    arr := make([]int, 0)
    arr = append(arr, nums[0])
    for i := 1; i < len(nums); i++ {
        index := upperBound(arr, nums[i])
        if index == len(arr) {
            arr = append(arr, nums[i])
        } else {
            arr[index] = nums[i]
        }
    }
    return len(arr)
}

// 返回第一个大于等于target的位置
func upperBound(arr []int, target int) int {
    left, right := 0, len(arr)
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            left = mid + 1 // 收缩左边界
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

# 2
func kIncreasing(arr []int, k int) int {
    res := 0
    for i := 0; i < k; i++ {
        dp := make([]int, 0)
        count := 0
        for j := i; j < len(arr); j = j + k {
            count++
            index := upperBound(dp, arr[j])
            if index == len(dp) {
                dp = append(dp, arr[j])
            } else {
                dp[index] = arr[j]
            }
        }
        res = res + count - len(dp)
    }
    return res
}

// 返回第一个大于等于target的位置
func upperBound(arr []int, target int) int {
    left, right := 0, len(arr)
    for left < right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            left = mid + 1 // 收缩左边界
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

2122.还原原数组(2)

  • 题目
Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。
她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher :
对每个满足 0 <= i < n 的下标 i ,lower[i] = arr[i] - k
对每个满足 0 <= i < n 的下标 i ,higher[i] = arr[i] + k
不幸地是,Alice 丢失了全部三个数组。
但是,她记住了在数组 lower 和 higher 中出现的整数,但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
给你一个由 2n 个整数组成的整数数组 nums ,其中 恰好 n 个整数出现在 lower ,剩下的出现在 higher ,还原并返回 原数组 arr 。
如果出现答案不唯一的情况,返回 任一 有效数组。
注意:生成的测试用例保证存在 至少一个 有效数组 arr 。
示例 1:输入:nums = [2,10,6,4,8,12] 输出:[3,7,11]
解释:如果 arr = [3,7,11] 且 k = 1 ,那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ,这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下,lower = [2,4,6] 且 higher = [8,10,12] 。
示例 2:输入:nums = [1,1,3,3] 输出:[2,2]
解释:如果 arr = [2,2] 且 k = 1 ,那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ,这是 nums 的一个排列。
注意,数组不能是 [1,3] ,因为在这种情况下,获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的,k 必须是一个正整数。
示例 3:输入:nums = [5,435] 输出:[220]
解释:唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下,lower = [5] 且 higher = [435] 。
提示:2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 109
生成的测试用例保证存在 至少一个 有效数组 arr
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 枚举+双指针 O(n^2) O(n)
02 枚举+哈希 O(n^2) O(n)
func recoverArray(nums []int) []int {
    n := len(nums)
    sort.Ints(nums)
    for i := 1; i < n; i++ {
        if nums[i] == nums[0] || (nums[i]-nums[0])%2 == 1 || nums[i] == nums[i-1] {
            continue
        }
        visited := make([]bool, n)
        visited[0], visited[i] = true, true
        res := make([]int, 0)
        k := (nums[i] - nums[0]) / 2
        res = append(res, nums[0]+k)
        left := 1
        right := i
        for j := 2; j <= n/2; j++ { // 还需要遍历n/2-1次
            for visited[left] == true {
                left++
            }
            for right < n && (visited[right] == true || nums[right]-nums[left] != 2*k) {
                right++
            }
            if right == n {
                break
            }
            res = append(res, nums[left]+k)
            visited[left], visited[right] = true, true
        }
        if len(res) == n/2 {
            return res
        }
    }
    return nil
}

# 2
func recoverArray(nums []int) []int {
    n := len(nums)
    sort.Ints(nums)
    for i := 1; i < n; i++ {
        if nums[i] == nums[0] || (nums[i]-nums[0])%2 == 1 || nums[i] == nums[i-1] {
            continue
        }
        // leetcode954.二倍数对数组
        m := make(map[int]int)
        for i := 0; i < n; i++ {
            m[nums[i]]++
        }
        res := make([]int, 0)
        k := (nums[i] - nums[0]) / 2
        for j := 0; j < n; j++ {
            if m[nums[j]] == 0 {
                continue
            }
            if m[nums[j]+2*k] == 0 {
                break
            }
            m[nums[j]]--
            m[nums[j]+2*k]--
            res = append(res, nums[j]+k)
        }
        if len(res) == n/2 {
            return res
        }
    }
    return nil
}

2132.用邮票贴满网格图

题目

给你一个m x n的二进制矩阵grid,每个格子要么为0(空)要么为1(被占据)。
给你邮票的尺寸为stampHeight x stampWidth。我们想将邮票贴进二进制矩阵中,且满足以下限制和要求:
覆盖所有 空格子。
不覆盖任何 被占据的格子。
我们可以放入任意数目的邮票。
邮票可以相互有 重叠部分。
邮票不允许 旋转。
邮票必须完全在矩阵 内。
如果在满足上述要求的前提下,可以放入邮票,请返回true,否则返回false。
示例 1:输入:grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出:true
解释:我们放入两个有重叠部分的邮票(图中标号为 1 和 2),它们能覆盖所有与空格子。
示例 2:输入:grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2  输出:false 
解释:没办法放入邮票覆盖所有的空格子,且邮票不超出网格图以外。
提示:m == grid.length
n == grid[r].length
1 <= m, n <= 105
1 <= m * n <= 2 * 105
grid[r][c] 要么是0,要么是1 。
1 <= stampHeight, stampWidth <= 105

解题思路

No. 思路 时间复杂度 空间复杂度
01 枚举+双指针 O(n^2) O(n)
```

## 2136.全部开花的最早一天(1)

- 题目

你有 n 枚花的种子。每枚种子必须先种下,才能开始生长、开花。播种需要时间,种子的生长也是如此。 给你两个下标从 0 开始的整数数组 plantTime 和 growTime ,每个数组的长度都是 n : plantTime[i] 是 播种 第 i 枚种子所需的 完整天数 。每天,你只能为播种某一枚种子而劳作。 无须 连续几天都在种同一枚种子,但是种子播种必须在你工作的天数达到 plantTime[i] 之后才算完成。 growTime[i] 是第 i 枚种子完全种下后生长所需的 完整天数 。在它生长的最后一天 之后 ,将会开花并且永远 绽放 。 从第 0 开始,你可以按 任意 顺序播种种子。 返回所有种子都开花的 最早 一天是第几天。 示例 1:输入:plantTime = [1,4,3], growTime = [2,3,1] 输出:9 解释:灰色的花盆表示播种的日子,彩色的花盆表示生长的日子,花朵表示开花的日子。 一种最优方案是: 第 0 天,播种第 0 枚种子,种子生长 2 整天。并在第 3 天开花。 第 1、2、3、4 天,播种第 1 枚种子。种子生长 3 整天,并在第 8 天开花。 第 5、6、7 天,播种第 2 枚种子。种子生长 1 整天,并在第 9 天开花。 因此,在第 9 天,所有种子都开花。 示例 2:输入:plantTime = [1,2,3,2], growTime = [2,1,2,1] 输出:9 解释:灰色的花盆表示播种的日子,彩色的花盆表示生长的日子,花朵表示开花的日子。 一种最优方案是: 第 1 天,播种第 0 枚种子,种子生长 2 整天。并在第 4 天开花。 第 0、3 天,播种第 1 枚种子。种子生长 1 整天,并在第 5 天开花。 第 2、4、5 天,播种第 2 枚种子。种子生长 2 整天,并在第 8 天开花。 第 6、7 天,播种第 3 枚种子。种子生长 1 整天,并在第 9 天开花。 因此,在第 9 天,所有种子都开花。 示例 3:输入:plantTime = [1], growTime = [1] 输出:2 解释:第 0 天,播种第 0 枚种子。种子需要生长 1 整天,然后在第 2 天开花。 因此,在第 2 天,所有种子都开花。 提示:n == plantTime.length == growTime.length 1 <= n <= 105 1 <= plantTime[i], growTime[i] <= 104


- 解题思路

| No.  | 思路 | 时间复杂度 | 空间复杂度 |
| :----- | :----- | :----------- | :----------- |
| 01   | 排序 | O(nlog(n)) | O(n)       |

```go
func earliestFullBloom(plantTime []int, growTime []int) int {
    n := len(plantTime)
    arr := make([][]int, n)
    for i := 0; i < n; i++ {
        arr[i] = []int{plantTime[i], growTime[i]}
    }
    sort.Slice(arr, func(i, j int) bool { // 按生长日期降序排序
        return arr[i][1] > arr[j][1]
    })
    res := 0
    sum := 0
    // 播种的总时间不变(串行),生长时间尽可能小(并行)
    for i := 0; i < len(arr); i++ {
        sum = sum + arr[i][0]
        if sum+arr[i][1] > res {
            res = sum + arr[i][1]
        }
    }
    return res
}

2141.同时运行N台电脑的最长时间(4)

  • 题目
你有n台电脑。给你整数n和一个下标从 0开始的整数数组batteries,其中第i个电池可以让一台电脑 运行batteries[i]分钟。
你想使用这些电池让全部n台电脑 同时运行。
一开始,你可以给每台电脑连接 至多一个电池。然后在任意整数时刻,你都可以将一台电脑与它的电池断开连接,并连接另一个电池,
你可以进行这个操作 任意次。
新连接的电池可以是一个全新的电池,也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。
注意,你不能给电池充电。
请你返回你可以让 n台电脑同时运行的 最长分钟数。
示例 1:输入:n = 2, batteries = [3,3,3] 输出:4
解释:一开始,将第一台电脑与电池 0 连接,第二台电脑与电池 1 连接。
2 分钟后,将第二台电脑与电池 1 断开连接,并连接电池 2 。注意,电池 0 还可以供电 1 分钟。
在第 3 分钟结尾,你需要将第一台电脑与电池 0 断开连接,然后连接电池 1 。
在第 4 分钟结尾,电池 1 也被耗尽,第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟,所以我们返回 4 。
示例 2:输入:n = 2, batteries = [1,1,1,1] 输出:2
解释:一开始,将第一台电脑与电池 0 连接,第二台电脑与电池 2 连接。
一分钟后,电池 0 和电池 2 同时耗尽,所以你需要将它们断开连接,并将电池 1 和第一台电脑连接,电池 3 和第二台电脑连接。
1 分钟后,电池 1 和电池 3 也耗尽了,所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟,所以我们返回 2 。
提示:1 <= n <= batteries.length <= 105
1 <= batteries[i] <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(nlog(n)) O(1)
02 二分查找-内置函数 O(nlog(n)) O(1)
03 贪心 O(nlog(n)) O(1)
04 二分查找 O(nlog(n)) O(1)
func maxRunTime(n int, batteries []int) int64 {
    sum := 0
    for i := 0; i < len(batteries); i++ {
        sum = sum + batteries[i]
    }
    left, right := 1, sum/n
    res := 0
    for left <= right {
        mid := left + (right-left)/2
        total := 0
        for j := 0; j < len(batteries); j++ {
            // 假设让n台电脑运行mid分钟
            // 电量>=mid的电池,只能被使用mid分钟,仅能给1台电脑充电
            total = total + min(batteries[j], mid)
        }
        if total >= n*mid {
            res = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return int64(res)
}

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

# 2
func maxRunTime(n int, batteries []int) int64 {
    sum := 0
    for i := 0; i < len(batteries); i++ {
        sum = sum + batteries[i]
    }
    return int64(sort.Search(sum/n, func(target int) bool {
        target++
        total := 0
        for i := 0; i < len(batteries); i++ {
            total = total + min(batteries[i], target)
        }
        return target*n > total
    }))
}

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

# 3
func maxRunTime(n int, batteries []int) int64 {
    sort.Slice(batteries, func(i, j int) bool {
        return batteries[i] > batteries[j]
    })
    sum := 0
    for i := 0; i < len(batteries); i++ {
        sum = sum + batteries[i]
    }
    for i := 0; i < len(batteries); i++ {
        if batteries[i] <= sum/n { // 不够用,返回
            return int64(sum / n)
        }
        sum = sum - batteries[i] // 去除该电池
        n--
    }
    return 0
}

# 4
func maxRunTime(n int, batteries []int) int64 {
    sum := 0
    for i := 0; i < len(batteries); i++ {
        sum = sum + batteries[i]
    }
    left, right := 1, sum/n
    for left <= right {
        mid := left + (right-left)/2
        total := 0
        for j := 0; j < len(batteries); j++ {
            // 假设让n台电脑运行mid分钟
            // 电量>=mid的电池,只能被使用mid分钟,仅能给1台电脑充电
            total = total + min(batteries[j], mid)
        }
        if total >= n*mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return int64(right)
}

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

2147.分隔长廊的方案数(1)

  • 题目
在一个图书馆的长廊里,有一些座位和装饰植物排成一列。给你一个下标从 0开始,长度为 n的字符串corridor,
它包含字母'S' 和'P',其中每个'S'表示一个座位,每个'P'表示一株植物。
在下标 0的左边和下标 n - 1的右边 已经分别各放了一个屏风。你还需要额外放置一些屏风。
每一个位置i - 1 和i之间(1 <= i <= n - 1),至多能放一个屏风。
请你将走廊用屏风划分为若干段,且每一段内都 恰好有两个座位,而每一段内植物的数目没有要求。
可能有多种划分方案,如果两个方案中有任何一个屏风的位置不同,那么它们被视为 不同 方案。
请你返回划分走廊的方案数。由于答案可能很大,请你返回它对109 + 7取余的结果。如果没有任何方案,请返回0。
示例 1:输入:corridor = "SSPPSPS" 输出:3
解释:总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中,每一段都恰好有 两个座位。
示例 2:输入:corridor = "PPSPSP" 输出:1
解释:只有 1 种分隔走廊的方案,就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。
示例 3:输入:corridor = "S" 输出:0
解释:没有任何方案,因为总是有一段无法恰好有 2 个座位。
提示:n == corridor.length
1 <= n <= 105
corridor[i]要么是'S',要么是'P' 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学 O(n) O(1)
var mod = 1000000007

func numberOfWays(corridor string) int {
    res := 1
    prev := -1
    count := 0
    for i := 0; i < len(corridor); i++ {
        if corridor[i] == 'S' {
            count++
            // 统计每2个1组之间有多少可能;相乘即可
            if count >= 3 && count%2 == 1 { // S>=3+奇数
                res = res * (i - prev) % mod
            }
            prev = i // 上一个座位的位置
        }
    }
    if count < 2 || count%2 == 1 {
        return 0
    }
    return res
}

2157.字符串分组

题目

给你一个下标从0开始的字符串数组words。每个字符串都只包含 小写英文字母。words中任意一个子串中,每个字母都至多只出现一次。
如果通过以下操作之一,我们可以从 s1的字母集合得到 s2的字母集合,那么我们称这两个字符串为 关联的:
往s1的字母集合中添加一个字母。
从s1的字母集合中删去一个字母。
将 s1中的一个字母替换成另外任意一个字母(也可以替换为这个字母本身)。
数组words可以分为一个或者多个无交集的 组。一个字符串与一个组如果满足以下 任一条件,它就属于这个组:
它与组内 至少一个其他字符串关联。
它是这个组中 唯一的字符串。
注意,你需要确保分好组后,一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下,分组方案是唯一的。
请你返回一个长度为 2的数组ans:
ans[0]是words分组后的总组数。
ans[1]是字符串数目最多的组所包含的字符串数目。
示例 1:输入:words = ["a","b","ab","cde"] 输出:[2,3]
解释:- words[0] 可以得到 words[1] (将 'a' 替换为 'b')和 words[2] (添加 'b')。
所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] (将 'b' 替换为 'a')和 words[2] (添加 'a')。
所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] (删去 'b')和 words[1] (删去 'a')。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。
所以,words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。
示例 2:输入:words = ["a","ab","abc"] 输出:[1,3]
解释:- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联,所以它们全部在同一个组内。
所以最大的组大小为 3 。
提示:1 <= words.length <= 2 * 104
1 <= words[i].length <= 26
words[i]只包含小写英文字母。
words[i] 中每个字母最多只出现一次。

解题思路

No. 思路 时间复杂度 空间复杂度
01 数学 O(n) O(1)
```

## 2167.移除所有载有违禁货物车厢所需的最少时间(3)

- 题目

给你一个下标从 0 开始的二进制字符串 s ,表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物, 而 s[i] = '1' 表示第 i 节车厢含违禁货物。 作为列车长,你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个: 从列车 左 端移除一节车厢(即移除 s[0]),用去 1 单位时间。 从列车 右 端移除一节车厢(即移除 s[s.length - 1]),用去 1 单位时间。 从列车车厢序列的 任意位置 移除一节车厢,用去 2 单位时间。 返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。 注意,空的列车车厢序列视为没有车厢含违禁货物。 示例 1:输入:s = "1100101" 输出:5 解释:一种从序列中移除所有载有违禁货物的车厢的方法是:

  • 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
  • 从右端移除一节车厢 1 次。所用时间是 1 。
  • 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。 总时间是 2 + 1 + 2 = 5 。 一种替代方法是:
  • 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
  • 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。 总时间也是 2 + 3 = 5 。 5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。 没有其他方法能够用更少的时间移除这些车厢。 示例 2:输入:s = "0010" 输出:2 解释:一种从序列中移除所有载有违禁货物的车厢的方法是:
  • 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。 总时间是 3. 另一种从序列中移除所有载有违禁货物的车厢的方法是:
  • 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。 总时间是 2. 另一种从序列中移除所有载有违禁货物的车厢的方法是:
  • 从右端移除一节车厢 2 次。所用时间是 2 1 = 2 。 总时间是 2. 2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。 没有其他方法能够用更少的时间移除这些车厢。 提示:1 <= s.length <= 2 105 s[i] 为 '0' 或 '1' ```

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n) O(n)
02 前缀和 O(n) O(1)
03 遍历 O(n) O(1)
func minimumTime(s string) int {
    n := len(s)
    res := n
    pre := make([]int, n+1) // 前缀和
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + int(s[i]-'0')
    }
    // left + middle(left,right)*2 + right
    // => i + (n-1-j) + 2*countOne(left,right)
    // => i + (n-1-j) + 2 *(pre[j+1] - pre[i])
    // => (i-2*pre[i]) + (2*pre[j+1]-j) + (n-1)
    // 求最小值
    a := 0
    for j := 0; j < n; j++ {
        a = min(a, j-2*pre[j])
        b := 2*pre[j+1] - j
        res = min(res, a+b+n-1)
    }
    return res
}

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

# 2
func minimumTime(s string) int {
    n := len(s)
    res := n
    // left + middle(left,right)*2 + right
    // => i + (n-1-j) + 2*countOne(left,right)
    // => i + (n-1-j) + 2 *(pre[j+1] - pre[i])
    // => (i-2*pre[i]) + (2*pre[j+1]-j) + (n-1)
    // 求最小值
    a := 0
    sum := 0
    for j := 0; j < n; j++ {
        a = min(a, j-2*sum)
        sum = sum + int(s[j]-'0')
        b := 2*sum - j
        res = min(res, a+b+n-1)
    }
    return res
}

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

# 3
func minimumTime(s string) int {
    n := len(s)
    res := n
    count := 0
    for i := 0; i < n; i++ {
        if s[i] == '1' {
            count = min(count+2, i+1) // left+middle:左边+中间最小值
        }
        res = min(res, count+n-1-i) // (left+middle)+right
    }
    return res
}

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

2183.统计可以被K整除的下标对数目(2)

  • 题目
给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ,返回满足下述条件的下标对 (i, j) 的数目:
0 <= i < j <= n - 1 且 nums[i] * nums[j] 能被 k 整除。
示例 1:输入:nums = [1,2,3,4,5], k = 2 输出:7
解释:共有 7 对下标的对应积可以被 2 整除:
(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)
它们的积分别是 2、4、6、8、10、12 和 20 。
其他下标对,例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ,都无法被 2 整除。    
示例 2:输入:nums = [1,2,3,4], k = 5 输出:0
解释:不存在对应积可以被 5 整除的下标对。
提示:1 <= nums.length <= 105
1 <= nums[i], k <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 数学-最大公约数 O(nlog(n)) O(log(n))
02 数学-最大公约数 O(nlog(n)) O(log(n))
func countPairs(nums []int, k int) int64 {
    res := int64(0)
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[gcd(k, nums[i])]++ // k和nums[i]的最大公约数
    }
    for k1, v1 := range m {
        for k2, v2 := range m {
            // 核心:a*b是k的倍数 => gcd(a,k)*gcd(b,k)是k的倍数
            if k1*k2%k == 0 {
                res = res + int64(v1)*int64(v2) // 组合数
            }
        }
    }
    for i := 0; i < len(nums); i++ {
        if nums[i]*nums[i]%k == 0 { // 本身x本身:不满足要求
            res--
        }
    }
    return res / 2 // 要满足有序要求
}

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

# 2
func countPairs(nums []int, k int) int64 {
    res := int64(0)
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[gcd(k, nums[i])]++ // k和nums[i]的最大公约数
    }
    for k1, v1 := range m {
        for k2, v2 := range m {
            // 核心:a*b是k的倍数 => gcd(a,k)*gcd(b,k)是k的倍数
            if k1*k2%k == 0 {
                if k1 < k2 {
                    res = res + int64(v1)*int64(v2)
                } else if k1 == k2 {
                    res = res + int64(v1)*int64(v1-1)/2
                }
            }
        }
    }
    return res
}

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

2188.完成比赛的最少时间(1)

  • 题目
给你一个下标从 0开始的二维整数数组tires,其中tires[i] = [fi, ri]表示第i种轮胎如果连续使用,
第x圈需要耗时fi * ri(x-1)秒。
比方说,如果fi = 3且ri = 2,且一直使用这种类型的同一条轮胎,
那么该轮胎完成第1圈赛道耗时 3秒,完成第 2圈耗时3 * 2 = 6秒,完成第 3圈耗时3 * 22 = 12秒,依次类推。
同时给你一个整数changeTime和一个整数numLaps。
比赛总共包含numLaps圈,你可以选择 任意一种轮胎开始比赛。每一种轮胎都有 无数条。
每一圈后,你可以选择耗费 changeTime秒 换成任意一种轮胎(也可以换成当前种类的新轮胎)。
请你返回完成比赛需要耗费的 最少时间。
示例 1:输入:tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4 输出:21
解释:第 1 圈:使用轮胎 0 ,耗时 2 秒。
第 2 圈:继续使用轮胎 0 ,耗时 2 * 3 = 6 秒。
第 3 圈:耗费 5 秒换一条新的轮胎 0 ,然后耗时 2 秒完成这一圈。
第 4 圈:继续使用轮胎 0 ,耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。
示例 2:输入:tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5 输出:25
解释:第 1 圈:使用轮胎 1 ,耗时 2 秒。
第 2 圈:继续使用轮胎 1 ,耗时 2 * 2 = 4 秒。
第 3 圈:耗时 6 秒换一条新的轮胎 1 ,然后耗时 2 秒完成这一圈。
第 4 圈:继续使用轮胎 1 ,耗时 2 * 2 = 4 秒。
第 5 圈:耗时 6 秒换成轮胎 0 ,然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。
提示:1 <= tires.length <= 105
tires[i].length == 2
1 <= fi, changeTime <= 105
2 <= ri <= 105
1 <= numLaps <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n)
func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int {
    minArr := make([]int, 20) // 用1个轮胎跑i圈的最小花费
    for i := 0; i < 20; i++ {
        minArr[i] = math.MaxInt32 / 10
    }
    for i := 0; i < len(tires); i++ {
        f, r := tires[i][0], tires[i][1]
        first := f + changeTime // 第一次用该胎的耗费
        sum := first
        for j := 1; f <= first; j++ {
            minArr[j] = min(minArr[j], sum)
            f = f * r
            sum = sum + f
        }
    }
    dp := make([]int, numLaps+1) // dp[i] => 表示跑i圈的最小花费
    for i := 0; i <= numLaps; i++ {
        dp[i] = math.MaxInt32 / 10
    }
    dp[0] = 0
    for i := 1; i <= numLaps; i++ {
        for j := 1; j <= 19 && j <= i; j++ { // 遍历跑i圈换胎
            dp[i] = min(dp[i], dp[i-j]+minArr[j])
        }
    }
    return dp[numLaps] - changeTime // 减去最后一次换胎时间
}

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

2197.替换数组中的非互质数(1)

  • 题目
给你一个整数数组 nums 。请你对数组执行下述操作:
从 nums 中找出 任意 两个 相邻 的 非互质 数。
如果不存在这样的数,终止 这一过程。
否则,删除这两个数,并 替换 为它们的 最小公倍数(Least Common Multiple,LCM)。
只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是,以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
两个数字 x 和 y 满足 非互质数 的条件是:GCD(x, y) > 1 ,其中 GCD(x, y) 是 x 和 y 的 最大公约数 。
示例 1 :输入:nums = [6,4,3,2,7,6,2] 输出:[12,7,6]
解释:- (6, 4) 是一组非互质数,且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数,且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数,且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数,且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在,nums 中不存在相邻的非互质数。
因此,修改后得到的最终数组是 [12,7,6] 。
注意,存在其他方法可以获得相同的最终数组。
示例 2 :输入:nums = [2,2,1,1,3,3,3] 输出:[2,1,1,3]
解释:- (3, 3) 是一组非互质数,且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数,且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数,且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在,nums 中不存在相邻的非互质数。 
因此,修改后得到的最终数组是 [2,1,1,3] 。 
注意,存在其他方法可以获得相同的最终数组。
提示:1 <= nums.length <= 105
1 <= nums[i] <= 105
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(nlog(n)) O(n)
func replaceNonCoprimes(nums []int) []int {
    res := make([]int, 0)
    for i := 0; i < len(nums); i++ {
        v := nums[i]
        for len(res) > 0 {
            if gcd(v, res[len(res)-1]) > 1 {
                v = lcm(v, res[len(res)-1])
                res = res[:len(res)-1]
            } else {
                break
            }
        }
        res = append(res, v)
    }
    return res
}

func lcm(x, y int) int {
    return x * y / gcd(x, y)
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}
Copyright © Zhi2014 2023 all right reserved,powered by Gitbook该文件修订时间: 2023-10-23 15:20:51

results matching ""

    No results matching ""