1801-1900-Easy

1805.字符串中不同整数的数目(2)

  • 题目
给你一个字符串 word ,该字符串由数字和小写英文字母组成。
请你用空格替换每个不是数字的字符。例如,"a123bc34d8ef34" 将会变成 " 123 34 8 34" 。
注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):"123"、"34"、"8" 和 "34" 。
返回对 word 完成替换后形成的 不同 整数的数目。
只有当两个整数的 不含前导零 的十进制表示不同, 才认为这两个整数也不同。
示例 1:输入:word = "a123bc34d8ef34" 输出:3
解释:不同的整数有 "123"、"34" 和 "8" 。注意,"34" 只计数一次。
示例 2:输入:word = "leet1234code234" 输出:2
示例 3:输入:word = "a1b01c001" 输出:1
解释:"1"、"01" 和 "001" 视为同一个整数的十进制表示,因为在比较十进制值时会忽略前导零的存在。
提示:1 <= word.length <= 1000
word 由数字和小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
02 遍历 O(n) O(n)
func numDifferentIntegers(word string) int {
    m := make(map[string]bool)
    arr := strings.FieldsFunc(word, func(r rune) bool {
        return 'a' <= r && r <= 'z'
    })
    for i := 0; i < len(arr); i++ {
        s := strings.Trim(arr[i], " ")
        for len(s) > 0 && s[0] == '0' {
            s = s[1:]
        }
        m[s] = true
    }
    return len(m)
}

# 2
func numDifferentIntegers(word string) int {
    m := make(map[int]bool)
    for i := 0; i < len(word); i++ {
        if '0' <= word[i] && word[i] <= '9' {
            value := int(word[i] - '0')
            for i+1 < len(word) && '0' <= word[i+1] && word[i+1] <= '9' {
                i++
                value = value*10 + int(word[i]-'0')
            }
            m[value] = true
        }
    }
    return len(m)
}

1812.判断国际象棋棋盘中一个格子的颜色(2)

  • 题目
给你一个坐标coordinates,它是一个字符串,表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。
如果所给格子的颜色是白色,请你返回true,如果是黑色,请返回false。
给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母,第二个字符是数字。
示例 1:输入:coordinates = "a1" 输出:false
解释:如上图棋盘所示,"a1" 坐标的格子是黑色的,所以返回 false 。
示例 2:输入:coordinates = "h3" 输出:true
解释:如上图棋盘所示,"h3" 坐标的格子是白色的,所以返回 true 。
示例 3:输入:coordinates = "c7" 输出:false
提示:coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 计算 O(1) O(1)
02 计算 O(1) O(1)
func squareIsWhite(coordinates string) bool {
    a := int(coordinates[0] - 'a')
    b := int(coordinates[1] - '1')
    return (a+b)%2 != 0
}

# 2
func squareIsWhite(coordinates string) bool {
    // a => 97  1 => 49
    return (coordinates[0]+coordinates[1])%2 != 0
}

1816.截断句子(2)

  • 题目
句子 是一个单词列表,列表中的单词之间用单个空格隔开,且不存在前导或尾随空格。
每个单词仅由大小写英文字母组成(不含标点符号)。
例如,"Hello World"、"HELLO" 和 "hello world hello world" 都是句子。
给你一个句子 s和一个整数 k,请你将 s截断 ,使截断后的句子仅含 前 k个单词。
返回 截断 s后得到的句子。
示例 1:输入:s = "Hello how are you Contestant", k = 4 输出:"Hello how are you"
解释:s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]
前 4 个单词为 ["Hello", "how", "are", "you"]
因此,应当返回 "Hello how are you"
示例 2:输入:s = "What is the solution to this problem", k = 4
输出:"What is the solution"
解释:s 中的单词为 ["What", "is" "the", "solution", "to", "this", "problem"]
前 4 个单词为 ["What", "is", "the", "solution"]
因此,应当返回 "What is the solution"
示例 3:输入:s = "chopper is not a tanuki", k = 5 输出:"chopper is not a tanuki"
提示:1 <= s.length <= 500
k 的取值范围是 [1, s 中单词的数目]
s 仅由大小写英文字母和空格组成
s 中的单词之间由单个空格隔开
不存在前导或尾随空格
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
02 遍历 O(n) O(1)
func truncateSentence(s string, k int) string {
    arr := strings.Split(s, " ")
    if k < len(arr) {
        return strings.Join(arr[:k], " ")
    }
    return s
}

# 2
func truncateSentence(s string, k int) string {
    count := 0
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            count++
            if count == k {
                return s[:i]
            }
        }
    }
    return s
}

1822.数组元素积的符号(1)

  • 题目
已知函数signFunc(x) 将会根据 x 的正负返回特定值:
如果 x 是正数,返回 1 。
如果 x 是负数,返回 -1 。
如果 x 是等于 0 ,返回 0 。
给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。
返回 signFunc(product) 。
示例 1:输入:nums = [-1,-2,-3,-4,3,2,1] 输出:1
解释:数组中所有值的乘积是 144 ,且 signFunc(144) = 1
示例 2:输入:nums = [1,5,0,2,-3] 输出:0
解释:数组中所有值的乘积是 0 ,且 signFunc(0) = 0
示例 3:输入:nums = [-1,1,-1,1,-1] 输出:-1
解释:数组中所有值的乘积是 -1 ,且 signFunc(-1) = -1
提示:1 <= nums.length <= 1000
-100 <= nums[i] <= 100
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func arraySign(nums []int) int {
    res := 1
    for i := 0; i < len(nums); i++ {
        if nums[i] < 0 {
            res = -res
        } else if nums[i] == 0 {
            return 0
        }
    }
    return res
}

1827.最少操作使数组递增(2)

  • 题目
给你一个整数数组nums(下标从 0 开始)。每一次操作中,你可以选择数组中一个元素,并将它增加1。
比方说,如果nums = [1,2,3],你可以选择增加nums[1]得到nums = [1,3,3]。
请你返回使 nums严格递增的 最少操作次数。
我们称数组nums是 严格递增的,当它满足对于所有的0 <= i < nums.length - 1都有
nums[i] < nums[i+1]。一个长度为 1的数组是严格递增的一种特殊情况。
示例 1:输入:nums = [1,1,1] 输出:3
解释:你可以进行如下操作:
1) 增加 nums[2] ,数组变为 [1,1,2] 。
2) 增加 nums[1] ,数组变为 [1,2,2] 。
3) 增加 nums[2] ,数组变为 [1,2,3] 。
示例 2:输入:nums = [1,5,2,4,1] 输出:14
示例 3:输入:nums = [8] 输出:0
提示:1 <= nums.length <= 5000
1 <= nums[i] <= 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
func minOperations(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }
    res := 0
    for i := 1; i < n; i++ {
        if nums[i-1] >= nums[i] {
            res = res + nums[i-1] + 1 - nums[i]
            nums[i] = nums[i-1] + 1
        }
    }
    return res
}

# 2
func minOperations(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }
    res := 0
    target := nums[0]
    for i := 1; i < n; i++ {
        if target >= nums[i] {
            res = res + target + 1 - nums[i]
            target = target + 1
        } else {
            target = nums[i]
        }
    }
    return res
}

1832.判断句子是否为全字母句(3)

  • 题目
全字母句 指包含英语字母表中每个字母至少一次的句子。
给你一个仅由小写英文字母组成的字符串 sentence ,请你判断sentence 是否为 全字母句 。
如果是,返回 true ;否则,返回 false 。
示例 1:输入:sentence = "thequickbrownfoxjumpsoverthelazydog" 输出:true
解释:sentence 包含英语字母表中每个字母至少一次。
示例 2:输入:sentence = "leetcode" 输出:false
提示:1 <= sentence.length <= 1000
sentence 由小写英语字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 位运算 O(n) O(1)
03 哈希 O(n) O(1)
func checkIfPangram(sentence string) bool {
    arr := [26]int{}
    for i := 0; i < len(sentence); i++ {
        arr[int(sentence[i]-'a')]++
    }
    for i := 0; i < 26; i++ {
        if arr[i] == 0 {
            return false
        }
    }
    return true
}

# 2
func checkIfPangram(sentence string) bool {
    res := 0
    target := 1 << 26 -1
    for i := 0; i < len(sentence); i++{
        res = res |  1 << (sentence[i]-'a')
    }
    return res == target
}

# 3
func checkIfPangram(sentence string) bool {
    m := make(map[byte]int)
    for i := 0; i < len(sentence); i++ {
        m[sentence[i]-'a']++
    }
    return len(m) == 26
}

1837.K进制表示下的各位数字总和(1)

  • 题目
给你一个整数 n(10 进制)和一个基数 k ,请你将 n 从 10 进制表示转换为 k 进制表示,
计算并返回转换后各位数字的 总和 。
转换后,各位数字应当视作是 10 进制数字,且它们的总和也应当按 10 进制表示返回。
示例 1:输入:n = 34, k = 6 输出:9
解释:34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。
示例 2:输入:n = 10, k = 10 输出:1
解释:n 本身就是 10 进制。 1 + 0 = 1 。
提示:1 <= n <= 100
2 <= k <= 10
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟 O(log(n)) O(1)
func sumBase(n int, k int) int {
    res := 0
    for n > 0 {
        res = res + n%k
        n = n / k
    }
    return res
}

1844.将所有数字用字符替换(1)

  • 题目
给你一个下标从 0开始的字符串 s,它的 偶数 下标处为小写英文字母,奇数下标处为数字。
定义一个函数shift(c, x),其中c是一个字符且x是一个数字,函数返回字母表中c后面第 x个字符。
比方说,shift('a', 5) = 'f'和shift('x', 0) = 'x'。
对于每个 奇数下标i,你需要将数字s[i] 用shift(s[i-1], s[i])替换。
请你替换所有数字以后,将字符串 s返回。题目 保证shift(s[i-1], s[i])不会超过 'z'。
示例 1:输入:s = "a1c1e1" 输出:"abcdef"
解释:数字被替换结果如下:
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('c',1) = 'd'
- s[5] -> shift('e',1) = 'f'
示例 2:输入:s = "a1b2c3d4e" 输出:"abbdcfdhe"
解释:数字被替换结果如下:
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('b',2) = 'd'
- s[5] -> shift('c',3) = 'f'
- s[7] -> shift('d',4) = 'h'
提示:1 <= s.length <= 100
s只包含小写英文字母和数字。
对所有 奇数 下标处的i,满足shift(s[i-1], s[i]) <= 'z'。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func replaceDigits(s string) string {
    res := []byte(s)
    for i := 1; i < len(s); i = i + 2 {
        res[i] = s[i-1] + s[i] - '0'
    }
    return string(res)
}

1848.到目标元素的最小距离(1)

  • 题目
给你一个整数数组 nums (下标 从 0 开始 计数)以及两个整数 target 和 start ,请你找出一个下标 i ,
满足 nums[i] == target 且 abs(i - start) 最小化 。注意:abs(x) 表示 x 的绝对值。
返回 abs(i - start) 。
题目数据保证 target 存在于 nums 中。
示例 1:输入:nums = [1,2,3,4,5], target = 5, start = 3 输出:1
解释:nums[4] = 5 是唯一一个等于 target 的值,所以答案是 abs(4 - 3) = 1 。
示例 2:输入:nums = [1], target = 1, start = 0 输出:0
解释:nums[0] = 1 是唯一一个等于 target 的值,所以答案是 abs(0 - 0) = 1 。
示例 3:输入:nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0 输出:0
解释:nums 中的每个值都是 1 ,但 nums[0] 使 abs(i - start) 的结果得以最小化,所以答案是 abs(0 - 0) = 0 。
提示:1 <= nums.length <= 1000
1 <= nums[i] <= 104
0 <= start < nums.length
target 存在于 nums 中
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func getMinDistance(nums []int, target int, start int) int {
    res := math.MaxInt32
    for i := 0; i < len(nums); i++ {
        if nums[i] == target {
            res = min(res, abs(i-start))
        }
    }
    return res
}

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

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

1854.人口最多的年份(2)

  • 题目
给你一个二维整数数组 logs ,其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。
年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足:
x 在闭区间 [birthi, deathi - 1] 内。注意,人不应当计入他们死亡当年的人口中。
返回 人口最多 且 最早 的年份。
示例 1:输入:logs = [[1993,1999],[2000,2010]] 输出:1993
解释:人口最多为 1 ,而 1993 是人口为 1 的最早年份。
示例 2:输入:logs = [[1950,1961],[1960,1971],[1970,1981]] 输出:1960
解释: 人口最多为 2 ,分别出现在 1960 和 1970 。
其中最早年份是 1960 。
提示:1 <= logs.length <= 100
1950 <= birthi < deathi <= 2050
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 差分数组 O(n) O(1)
02 暴力法 O(n^2) O(1)
func maximumPopulation(logs [][]int) int {
    arr := [101]int{}
    for i := 0; i < len(logs); i++ {
        a, b := logs[i][0], logs[i][1]
        arr[a-1950]++
        arr[b-1950]--
    }
    res := 0
    sum := 0
    count := 0
    for i := 0; i < len(arr); i++ {
        sum = sum + arr[i]
        if sum > count {
            count = sum
            res = i + 1950
        }
    }
    return res
}

# 2
func maximumPopulation(logs [][]int) int {
    arr := [101]int{}
    for i := 0; i < len(logs); i++ {
        a, b := logs[i][0], logs[i][1]
        for j := a; j < b; j++ {
            arr[j-1950]++
        }
    }
    res := 0
    count := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] > count {
            count = arr[i]
            res = i + 1950
        }
    }
    return res
}

1859.将句子排序(2)

  • 题目
一个 句子指的是一个序列的单词用单个空格连接起来,且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。
我们可以给一个句子添加 从 1 开始的单词位置索引 ,并且将句子中所有单词打乱顺序。
比方说,句子"This is a sentence"可以被打乱顺序得到"sentence4 a3 is2 This1"或者"is2 sentence4 This1 a3"。
给你一个 打乱顺序的句子s,它包含的单词不超过9个,请你重新构造并得到原本顺序的句子。
示例 1:输入:s = "is2 sentence4 This1 a3"
输出:"This is a sentence"
解释:将 s 中的单词按照初始位置排序,得到 "This1 is2 a3 sentence4" ,然后删除数字。
示例 2:输入:s = "Myself2 Me1 I4 and3"
输出:"Me Myself and I"
解释:将 s 中的单词按照初始位置排序,得到 "Me1 Myself2 and3 I4" ,然后删除数字。
提示:2 <= s.length <= 200
s只包含小写和大写英文字母、空格以及从1到9的数字。
s中单词数目为1到9个。
s中的单词由单个空格分隔。
s不包含任何前导或者后缀空格。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序+内置函数 O(nlog(n)) O(n)
02 内置函数 O(n) O(n)
func sortSentence(s string) string {
    arr := strings.Split(s, " ")
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][len(arr[i])-1] < arr[j][len(arr[j])-1]
    })
    for i := 0; i < len(arr); i++ {
        arr[i] = arr[i][:len(arr[i])-1]
    }
    return strings.Join(arr, " ")
}

# 2
func sortSentence(s string) string {
    arr := strings.Split(s, " ")
    temp := make([]string, len(arr)+1)
    for i := 0; i < len(arr); i++ {
        index, _ := strconv.Atoi(string(arr[i][len(arr[i])-1]))
        temp[index] = arr[i][:len(arr[i])-1]
    }
    return strings.Join(temp[1:], " ")
}

1863.找出所有子集的异或总和再求和(4)

  • 题目
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果;如果数组为 空 ,则异或总和为 0 。
例如,数组[2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ,请你求出 nums 中每个 子集 的 异或总和 ,计算并返回这些值相加之 和 。
注意:在本题中,元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是:从 b 删除几个(也可能不删除)元素能够得到 a 。
示例 1:输入:nums = [1,3] 输出:6
解释:[1,3] 共有 4 个子集:
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6
示例 2:输入:nums = [5,1,6] 输出:28
解释:[5,1,6] 共有 8 个子集:
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
示例 3:输入:nums = [3,4,5,6,7,8] 输出:480
解释:每个子集的全部异或总和值之和为 480 。
提示:1 <= nums.length <= 12
1 <= nums[i] <= 20
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 子集-回溯 O(n*2^n) O(1)
02 位运算 O(n*2^n) O(1)
03 位运算 O(n*2^n) O(1)
04 数学 O(n) O(1)
var res int

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

func dfs(nums []int, sum int, index int) {
    if index >= len(nums) {
        res = res + sum
        return
    }
    dfs(nums, sum, index+1)
    dfs(nums, sum^nums[index], index+1)
}

# 2
func subsetXORSum(nums []int) int {
    res := 0
    n := len(nums)
    left := 1 << n
    right := 1 << (n + 1)
    for i := left; i < right; i++ {
        sum := 0
        for j := 0; j < n; j++ {
            if i&(1<<j) != 0 {
                sum = sum ^ nums[j]
            }
        }
        res = res + sum
    }
    return res
}

# 3
func subsetXORSum(nums []int) int {
    res := 0
    n := len(nums)
    total := 1 << n
    for i := 0; i < total; i++ {
        sum := 0
        for j := 0; j < n; j++ {
            if (i>>j)&1 == 1 {
                sum = sum ^ nums[j]
            }
        }
        res = res + sum
    }
    return res
}

# 4
func subsetXORSum(nums []int) int {
    // 对于任意一位,2^n个子集异或结果中
    // 如果nums中任何一个数字在这一位上都是0,则任何一个子集的异或结果在这一位上都是0
    // 如果nums中有一个数字在这一位上是1,则所有子集异或结果中在这一位上,一半是0,一半是1
    n := len(nums)
    temp := 0
    for i := 0; i < n; i++ {
        temp = temp | nums[i]
    }
    return temp << (n - 1)
}

1869.哪种连续子字符串更长(3)

  • 题目
给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串,返回 true ;
否则,返回 false 。
例如,s = "110100010" 中,由 1 组成的最长连续子字符串的长度是 2 ,由 0 组成的最长连续子字符串的长度是 3 。
注意,如果字符串中不存在 0 ,此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。
示例 1:输入:s = "1101" 输出:true
解释:由 1 组成的最长连续子字符串的长度是 2:"1101"
由 0 组成的最长连续子字符串的长度是 1:"1101"
由 1 组成的子字符串更长,故返回 true 。
示例 2:输入:s = "111000" 输出:false
解释:由 1 组成的最长连续子字符串的长度是 3:"111000"
由 0 组成的最长连续子字符串的长度是 3:"111000"
由 1 组成的子字符串不比由 0 组成的子字符串长,故返回 false 。
示例 3:输入:s = "110100010" 输出:false
解释:由 1 组成的最长连续子字符串的长度是 2:"110100010"
由 0 组成的最长连续子字符串的长度是 3:"110100010"
由 1 组成的子字符串不比由 0 组成的子字符串长,故返回 false 。
提示:1 <= s.length <= 100
s[i] 不是 '0' 就是 '1'
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
03 内置函数 O(n) O(n)
func checkZeroOnes(s string) bool {
    a, b := 0, 0
    prev := uint8(' ')
    count := 0
    for i := 0; i < len(s); i++ {
        if s[i] == prev {
            count++
        } else {
            if prev == '0' {
                a = max(a, count)
            } else if prev == '1' {
                b = max(b, count)
            }
            count = 1
        }
        prev = s[i]
    }
    if prev == '0' {
        a = max(a, count)
    } else if prev == '1' {
        b = max(b, count)
    }
    return b > a
}

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

# 2
func checkZeroOnes(s string) bool {
    a, b := 0, 0
    aMax, bMax := 0, 0
    for i := 0; i < len(s); i++ {
        if s[i] == '0' {
            a++
            b = 0
        } else if s[i] == '1' {
            a = 0
            b++
        }
        aMax = max(aMax, a)
        bMax = max(bMax, b)
    }
    return bMax > aMax
}

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

# 3
func checkZeroOnes(s string) bool {
    a, b := 0, 0
    for _, v := range strings.Split(s, "1") {
        b = max(b, len(v))
    }
    for _, v := range strings.Split(s, "0") {
        a = max(a, len(v))
    }
    return b > a
}

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

1876.长度为三且各字符不同的子字符串(1)

  • 题目
如果一个字符串不含有任何重复字符,我们称这个字符串为 好字符串。
给你一个字符串 s,请你返回 s中长度为 3的 好子字符串 的数量。
注意,如果相同的好子字符串出现多次,每一次都应该被记入答案之中。
子字符串 是一个字符串中连续的字符序列。
示例 1:输入:s = "xyzzaz" 输出:1
解释:总共有 4 个长度为 3 的子字符串:"xyz","yzz","zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。
示例 2:输入:s = "aababcabc" 输出:4
解释:总共有 7 个长度为 3 的子字符串:"aab","aba","bab","abc","bca","cab" 和 "abc" 。
好子字符串包括 "abc","bca","cab" 和 "abc" 。
提示:1 <= s.length <= 100
s只包含小写英文字母。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func countGoodSubstrings(s string) int {
    res := 0
    for i := 2; i < len(s); i++ {
        if s[i-2] != s[i-1] && s[i-2] != s[i] && s[i-1] != s[i] {
            res++
        }
    }
    return res
}

1880.检查某单词是否等于两单词之和(2)

  • 题目
字母的 字母值 取决于字母在字母表中的位置,从 0 开始 计数。即,'a' -> 0、'b' -> 1、'c' -> 2,以此类推。
对某个由小写字母组成的字符串s 而言,其 数值 就等于将 s 中每个字母的 字母值 按顺序 连接 并 转换 成对应整数。
例如,s = "acb" ,依次连接每个字母的字母值可以得到 "021" ,转换为整数得到 21 。
给你三个字符串 firstWord、secondWord 和 targetWord ,每个字符串都由从 'a' 到 'j' (含'a' 和 'j' )的小写英文字母组成。
如果firstWord 和 secondWord 的 数值之和 等于 targetWord 的数值,返回 true ;否则,返回 false 。
示例 1:输入:firstWord = "acb", secondWord = "cba", targetWord = "cdb" 输出:true
解释:firstWord 的数值为 "acb" -> "021" -> 21
secondWord 的数值为 "cba" -> "210" -> 210
targetWord 的数值为 "cdb" -> "231" -> 231
由于 21 + 210 == 231 ,返回 true
示例 2:输入:firstWord = "aaa", secondWord = "a", targetWord = "aab" 输出:false
解释:firstWord 的数值为 "aaa" -> "000" -> 0
secondWord 的数值为 "a" -> "0" -> 0
targetWord 的数值为 "aab" -> "001" -> 1
由于 0 + 0 != 1 ,返回 false
示例 3:输入:firstWord = "aaa", secondWord = "a", targetWord = "aaaa" 输出:true
解释:firstWord 的数值为 "aaa" -> "000" -> 0
secondWord 的数值为 "a" -> "0" -> 0
targetWord 的数值为 "aaaa" -> "0000" -> 0
由于 0 + 0 == 0 ,返回 true
提示:1 <= firstWord.length, secondWord.length, targetWord.length <= 8
firstWord、secondWord 和 targetWord 仅由从 'a' 到 'j' (含'a' 和 'j' )的小写英文字母组成。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
func isSumEqual(firstWord string, secondWord string, targetWord string) bool {
    a := 0
    b := 0
    c := 0
    for i := 0; i < len(firstWord); i++ {
        a = a*10 + int(firstWord[i]-'a')
    }
    for i := 0; i < len(secondWord); i++ {
        b = b*10 + int(secondWord[i]-'a')
    }
    for i := 0; i < len(targetWord); i++ {
        c = c*10 + int(targetWord[i]-'a')
    }
    return a+b == c
}

# 2
func isSumEqual(firstWord string, secondWord string, targetWord string) bool {
    return getValue(firstWord)+getValue(secondWord) == getValue(targetWord)
}

func getValue(str string) int {
    res := 0
    for i := 0; i < len(str); i++ {
        res = res*10 + int(str[i]-'a')
    }
    return res
}

1886.判断矩阵经轮转后是否一致(1)

  • 题目
给你两个大小为 n x n 的二进制矩阵 mat 和 target 。
现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ,如果能够使 mat 与target 一致,返回 true ;否则,返回 false 。
示例 1:输入:mat = [[0,1],[1,0]], target = [[1,0],[0,1]] 输出:true
解释:顺时针轮转 90 度一次可以使 mat 和 target 一致。
示例 2:输入:mat = [[0,1],[1,1]], target = [[1,0],[0,1]] 输出:false
解释:无法通过轮转矩阵中的元素使 equal 与 target 一致。
示例 3:输入:mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]] 输出:true
解释:顺时针轮转 90 度两次可以使 mat 和 target 一致。
提示:n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] 和 target[i][j] 不是 0 就是 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(n^2)
func findRotation(mat [][]int, target [][]int) bool {
    for i := 0; i < 4; i++ {
        rotate(mat)
        if compare(mat, target) == true {
            return true
        }
    }
    return false
}

// leetcode 48.旋转图像
func rotate(matrix [][]int) {
    n := len(matrix)
    arr := make([][]int, n)
    for i := 0; i < n; i++ {
        arr[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            arr[j][n-1-i] = matrix[i][j]
        }
    }
    copy(matrix, arr)
}

func compare(a, b [][]int) bool {
    n := len(a)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if a[i][j] != b[i][j] {
                return false
            }
        }
    }
    return true
}

1893.检查是否区域内所有整数都被覆盖(3)

  • 题目
给你一个二维整数数组ranges和两个整数left和right。
每个ranges[i] = [starti, endi]表示一个从starti到endi的闭区间。
如果闭区间[left, right]内每个整数都被ranges中至少一个区间覆盖,那么请你返回true,否则返回false。
已知区间 ranges[i] = [starti, endi] ,如果整数 x 满足 starti <= x <= endi,那么我们称整数x被覆盖了。
示例 1:输入:ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5 输出:true
解释:2 到 5 的每个整数都被覆盖了:
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。
示例 2:输入:ranges = [[1,10],[10,20]], left = 21, right = 21 输出:false
解释:21 没有被任何一个区间覆盖。
提示:1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(n)
02 差分数组 O(n) O(n)
03 遍历 O(n) O(1)
func isCovered(ranges [][]int, left int, right int) bool {
    arr := make([]bool, 51)
    for i := 0; i < len(ranges); i++ {
        a, b := ranges[i][0], ranges[i][1]
        for j := a; j <= b; j++ {
            arr[j] = true
        }
    }
    for i := left; i <= right; i++ {
        if arr[i] == false {
            return false
        }
    }
    return true
}

# 2
func isCovered(ranges [][]int, left int, right int) bool {
    arr := make([]int, 52)
    for i := 0; i < len(ranges); i++ {
        a, b := ranges[i][0], ranges[i][1]
        arr[a]++
        arr[b+1]--
    }
    sum := 0
    for i := 0; i <= 50; i++ {
        sum = sum + arr[i]
        if left <= i && i <= right && sum <= 0 {
            return false
        }
    }
    return true
}

# 3
func isCovered(ranges [][]int, left int, right int) bool {
    for i := 0; i < len(ranges); i++ {
        a, b := ranges[i][0], ranges[i][1]
        if a <= left { // a到left已经覆盖:left移动到b后面
            left = b + 1
        }
        if b >= right { // right到b已经覆盖:right移动到a前面
            right = a - 1
        }
        if left > right {
            return true
        }
    }
    return false
}

1897.重新分配字符使所有字符串都相等(1)

  • 题目
给你一个字符串数组 words(下标 从 0 开始 计数)。
在一步操作中,需先选出两个 不同 下标 i 和 j,其中 words[i] 是一个非空字符串,
接着将 words[i] 中的 任一 字符移动到 words[j] 中的 任一 位置上。
如果执行任意步操作可以使 words 中的每个字符串都相等,返回 true ;否则,返回 false 。
示例 1:输入:words = ["abc","aabc","bc"] 输出:true
解释:将 words[1] 中的第一个 'a' 移动到 words[2] 的最前面。
使 words[1] = "abc" 且 words[2] = "abc" 。
所有字符串都等于 "abc" ,所以返回 true 。
示例 2:输入:words = ["ab","a"] 输出:false
解释:执行操作无法使所有字符串都相等。
提示:1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 由小写英文字母组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
func makeEqual(words []string) bool {
    arr := [26]int{}
    n := len(words)
    for i := 0; i < n; i++ {
        for j := 0; j < len(words[i]); j++ {
            arr[int(words[i][j]-'a')]++
        }
    }
    for i := 0; i < 26; i++ {
        if arr[i]%n != 0 {
            return false
        }
    }
    return true
}

1801-1900-Medium

1801.积压订单中的订单总数(1)

  • 题目
给你一个二维整数数组 orders ,其中每个 orders[i] = [pricei, amounti, orderTypei] 
表示有 amounti 笔类型为orderTypei 、价格为pricei 的订单。
订单类型 orderTypei 可以分为两种:
0 表示这是一批采购订单 buy
1 表示这是一批销售订单 sell
注意,orders[i] 表示一批共计 amounti 笔的独立订单,这些订单的价格和类型相同。
对于所有有效的 i ,由 orders[i] 表示的所有订单提交时间均早于 orders[i+1] 表示的所有订单。
存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时,会发生以下情况:
如果该订单是一笔采购订单 buy ,则可以查看积压订单中价格 最低 的销售订单 sell 。
如果该销售订单 sell 的价格 低于或等于 当前采购订单 buy 的价格,
则匹配并执行这两笔订单,并将销售订单 sell 从积压订单中删除。否则,采购订单 buy 将会添加到积压订单中。
反之亦然,如果该订单是一笔销售订单 sell ,则可以查看积压订单中价格 最高 的采购订单 buy 。
如果该采购订单 buy 的价格 高于或等于 当前销售订单 sell 的价格,
则匹配并执行这两笔订单,并将采购订单 buy 从积压订单中删除。否则,销售订单 sell 将会添加到积压订单中。
输入所有订单后,返回积压订单中的 订单总数 。由于数字可能很大,所以需要返回对 109 + 7 取余的结果。
示例 1:输入:orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]] 输出:6
解释:输入订单后会发生下述情况:
- 提交 5 笔采购订单,价格为 10 。没有销售订单,所以这 5 笔订单添加到积压订单中。
- 提交 2 笔销售订单,价格为 15 。没有采购订单的价格大于或等于 15 ,所以这 2 笔订单添加到积压订单中。
- 提交 1 笔销售订单,价格为 25 。没有采购订单的价格大于或等于 25 ,所以这 1 笔订单添加到积压订单中。
- 提交 4 笔采购订单,价格为 30 。前 2 笔采购订单与价格最低(价格为 15)的 2 笔销售订单匹配,
从积压订单中删除这 2 笔销售订单。第 3 笔采购订单与价格最低的 1 笔销售订单匹配,销售订单价格为 25 ,
从积压订单中删除这 1 笔销售订单。积压订单中不存在更多销售订单,所以第 4 笔采购订单需要添加到积压订单中。
最终,积压订单中有 5 笔价格为 10 的采购订单,和 1 笔价格为 30 的采购订单。
所以积压订单中的订单总数为 6 。
示例 2:输入:orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]] 输出:999999984
解释:输入订单后会发生下述情况:
- 提交 109 笔销售订单,价格为 7 。没有采购订单,所以这 109 笔订单添加到积压订单中。
- 提交 3 笔采购订单,价格为 15 。这些采购订单与价格最低(价格为 7 )的 3 笔销售订单匹配,
从积压订单中删除这 3 笔销售订单。
- 提交 999999995 笔采购订单,价格为 5 。销售订单的最低价为 7 ,
所以这 999999995 笔订单添加到积压订单中。
- 提交 1 笔销售订单,价格为 5 。这笔销售订单与价格最高(价格为 5 )的 1 笔采购订单匹配,
从积压订单中删除这 1 笔采购订单。
最终,积压订单中有 (1000000000-3) 笔价格为 7 的销售订单,和 (999999995-1) 笔价格为 5 的采购订单。
所以积压订单中的订单总数为 1999999991 ,等于 999999984 % (109 + 7) 。
提示:1 <= orders.length <= 105
orders[i].length == 3
1 <= pricei, amounti <= 109
orderTypei 为 0 或 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双堆 O(nlog(n)) O(n)
func getNumberOfBacklogOrders(orders [][]int) int {
    res := 0
    buyHeap := make(BuyHeap, 0)
    sellHeap := make(SellHeap, 0)
    heap.Init(&buyHeap)
    heap.Init(&sellHeap)
    for i := 0; i < len(orders); i++ {
        price := orders[i][0]
        count := orders[i][1]
        typeInt := orders[i][2]
        if typeInt == 1 { // sell
            for buyHeap.Len() > 0 {
                node := heap.Pop(&buyHeap).(Node)
                if node.price < price {
                    heap.Push(&buyHeap, node)
                    break
                }
                if node.count > count { // 数量大于
                    node.count = node.count - count
                    count = 0
                    heap.Push(&buyHeap, node)
                    break
                }
                count = count - node.count
            }
            if count > 0 {
                heap.Push(&sellHeap, Node{
                    count: count,
                    price: price,
                })
            }
        } else { // buy
            for sellHeap.Len() > 0 {
                node := heap.Pop(&sellHeap).(Node)
                if node.price > price {
                    heap.Push(&sellHeap, node)
                    break
                }
                if node.count > count { // 数量小于
                    node.count = node.count - count
                    count = 0
                    heap.Push(&sellHeap, node)
                    break
                }
                count = count - node.count
            }
            if count > 0 {
                heap.Push(&buyHeap, Node{
                    count: count,
                    price: price,
                })
            }
        }
    }
    for buyHeap.Len() > 0 {
        node := heap.Pop(&buyHeap).(Node)
        res = res + node.count
    }
    for sellHeap.Len() > 0 {
        node := heap.Pop(&sellHeap).(Node)
        res = res + node.count
    }
    return res % 1000000007
}

type Node struct {
    count int
    price int
}
type SellHeap []Node

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

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

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

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

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

type BuyHeap []Node

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

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

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

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

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

1802.有界数组中指定下标处的最大值(2)

  • 题目
给你三个正整数 n、index 和 maxSum 。
你需要构造一个同时满足下述所有条件的数组 nums(下标 从 0 开始 计数):
nums.length == n
nums[i] 是 正整数 ,其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ,其中 0 <= i < n-1
nums 中所有元素之和不超过 maxSum
nums[index] 的值被 最大化
返回你所构造的数组中的 nums[index] 。
注意:abs(x) 等于 x 的前提是 x >= 0 ;否则,abs(x) 等于 -x 。
示例 1:输入:n = 4, index = 2,  maxSum = 6 输出:2
解释:数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
示例 2:输入:n = 6, index = 1,  maxSum = 10 输出:3
提示:1 <= n <= maxSum <= 109
0 <= index < n
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(log(n)) O(1)
02 二分查找 O(log(n)) O(1)
func maxValue(n int, index int, maxSum int) int {
    if n == 1 {
        return maxSum
    }
    res := 1
    leftTotal, rightTotal := index, n-index-1
    left, right := 1, maxSum
    for left < right {
        mid := left + (right-left)/2
        l := getTotal(mid, leftTotal)
        r := getTotal(mid, rightTotal)
        if l+r+mid <= maxSum {
            left = mid + 1
            res = mid
        } else {
            right = mid
        }
    }
    return res
}

func getTotal(high int, total int) int {
    need := high - 1
    if need >= total {
        return total * (need + high - total) / 2
    }
    return need*(1+need)/2 + total - need
}

# 2
func maxValue(n int, index int, maxSum int) int {
    res := 1
    leftTotal, rightTotal := index, n-index-1
    left, right := 1, maxSum+1
    for left < right {
        mid := left + (right-left)/2
        l := getTotal(mid, leftTotal)
        r := getTotal(mid, rightTotal)
        if l+r+mid <= maxSum {
            left = mid + 1
            res = mid
        } else {
            right = mid
        }
    }
    return res
}

func getTotal(high int, total int) int {
    need := high - 1
    if need >= total {
        return total * (need + high - total) / 2
    }
    return need*(1+need)/2 + total - need
}

1806.还原排列的最少操作步数(3)

  • 题目
给你一个偶数 n,已知存在一个长度为 n 的排列 perm ,其中 perm[i] == i(下标 从 0 开始 计数)。
一步操作中,你将创建一个新数组 arr ,对于每个 i :
如果 i % 2 == 0 ,那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 ,那么 arr[i] = perm[n / 2 + (i - 1) / 2]
然后将 arr赋值给 perm 。
要想使 perm 回到排列初始值,至少需要执行多少步操作?返回最小的 非零 操作步数。
示例 1:输入:n = 2 输出:1
解释:最初,perm = [0,1]
第 1步操作后,perm = [0,1]
所以,仅需执行 1 步操作
示例 2:输入:n = 4 输出:2
解释:最初,perm = [0,1,2,3]
第 1步操作后,perm = [0,2,1,3]
第 2步操作后,perm = [0,1,2,3]
所以,仅需执行 2 步操作
示例 3:输入:n = 6 输出:4
提示:2 <= n <= 1000
n是一个偶数
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(n)
02 暴力法 O(n^2) O(n)
03 循环 O(n) O(1)
func reinitializePermutation(n int) int {
    res := 0
    target := make([]int, n)
    perm := make([]int, n)
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        perm[i] = i
    }
    copy(target, perm)
    for {
        for i := 0; i < n; i++ {
            if i%2 == 0 {
                arr[i] = perm[i/2]
            } else {
                arr[i] = perm[n/2+(i-1)/2]
            }
        }
        res++
        if reflect.DeepEqual(target, arr) {
            break
        }
        copy(perm, arr)
    }
    return res
}

# 2
func reinitializePermutation(n int) int {
    res := 0
    target := make([]int, n)
    perm := make([]int, n)
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        perm[i] = i
    }
    copy(target, perm)
    for {
        for i := 0; i < n; i++ {
            if i%2 == 0 {
                arr[i] = perm[i/2]
            } else {
                arr[i] = perm[n/2+(i-1)/2]
            }
        }
        res++
        flag := true
        for i := 0; i < n; i++ {
            if arr[i] != target[i] {
                flag = false
                break
            }
        }
        if flag == true {
            break
        }
        copy(perm, arr)
    }
    return res
}

# 3
func reinitializePermutation(n int) int {
    res := 0
    target := 1
    // 反向思路,只考虑1的变换
    for {
        if target*2 < n {
            target = target * 2
        } else {
            target = target*2 + 1 - n
        }
        res++
        if target == 1 {
            break
        }
    }
    return res
}

1807.替换字符串中的括号内容(1)

  • 题目
给你一个字符串s,它包含一些括号对,每个括号中包含一个 非空的键。
比方说,字符串"(name)is(age)yearsold"中,有两个括号对,分别包含键"name" 和"age"。
你知道许多键对应的值,这些关系由二维字符串数组knowledge表示,
其中knowledge[i] = [keyi, valuei],表示键keyi对应的值为valuei。
你需要替换 所有的括号对。当你替换一个括号对,且它包含的键为keyi时,你需要:
将keyi和括号用对应的值valuei替换。
如果从 knowledge中无法得知某个键对应的值,你需要将keyi和括号用问号"?"替换(不需要引号)。
knowledge中每个键最多只会出现一次。s中不会有嵌套的括号。
请你返回替换 所有括号对后的结果字符串。
示例 1:输入:s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
输出:"bobistwoyearsold"
解释:键 "name" 对应的值为 "bob" ,所以将 "(name)" 替换为 "bob" 。
键 "age" 对应的值为 "two" ,所以将 "(age)" 替换为 "two" 。
示例 2:输入:s = "hi(name)", knowledge = [["a","b"]] 输出:"hi?"
解释:由于不知道键 "name" 对应的值,所以用 "?" 替换 "(name)" 。
示例 3:输入:s = "(a)(a)(a)aaa", knowledge = [["a","yes"]] 输出:"yesyesyesaaa"
解释:相同的键在 s 中可能会出现多次。
键 "a" 对应的值为 "yes" ,所以将所有的 "(a)" 替换为 "yes" 。
注意,不在括号里的 "a" 不需要被替换。
示例 4:输入:s = "(a)(b)", knowledge = [["a","b"],["b","a"]] 输出:"ba"
提示:1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.length <= 10
s只包含小写英文字母和圆括号'('和')'。
s中每一个左圆括号'('都有对应的右圆括号')'。
s中每对括号内的键都不会为空。
s中不会有嵌套括号对。
keyi和valuei只包含小写英文字母。
knowledge中的keyi不会重复。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
func evaluate(s string, knowledge [][]string) string {
    m := make(map[string]string)
    for i := 0; i < len(knowledge); i++ {
        a, b := knowledge[i][0], knowledge[i][1]
        m[a] = b
    }
    res := ""
    left := -1
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            left = i
        } else if s[i] == ')' {
            str := s[left+1 : i]
            if v, ok := m[str]; ok {
                res = res + v
            } else {
                res = res + "?"
            }
            left = -1
        } else if left == -1 {
            res = res + string(s[i])
        }
    }
    return res
}

1813.句子相似性III(1)

  • 题目
一个句子是由一些单词与它们之间的单个空格组成,且句子的开头和结尾没有多余空格。
比方说,"Hello World","HELLO","hello world hello world"都是句子。
每个单词都 只包含大写和小写英文字母。
如果两个句子sentence1 和sentence2,
可以通过往其中一个句子插入一个任意的句子(可以是空句子)而得到另一个句子,那么我们称这两个句子是 相似的。
比方说,sentence1 = "Hello my name is Jane" 且sentence2 = "Hello Jane",
我们可以往 sentence2中"Hello" 和"Jane"之间插入"my name is"得到 sentence1。
给你两个句子sentence1 和sentence2,如果sentence1 和sentence2 是相似的,
请你返回true,否则返回false。
示例 1:输入:sentence1 = "My name is Haley", sentence2 = "My Haley" 输出:true
解释:可以往 sentence2 中 "My" 和 "Haley" 之间插入 "name is" ,得到 sentence1 。
示例 2:输入:sentence1 = "of", sentence2 = "A lot of words" 输出:false
解释:没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。
示例 3:输入:sentence1 = "Eating right now", sentence2 = "Eating" 输出:true
解释:可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。
示例 4:输入:sentence1 = "Luky", sentence2 = "Lucccky" 输出:false
提示:1 <= sentence1.length, sentence2.length <= 100
sentence1和sentence2都只包含大小写英文字母和空格。
sentence1和sentence2中的单词都只由单个空格隔开。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(n)
func areSentencesSimilar(sentence1 string, sentence2 string) bool {
    if len(sentence1) > len(sentence2) { // 交换保证 1 < 2
        sentence1, sentence2 = sentence2, sentence1
    }
    // 4种情况:
    // 1、全等: AB = AB
    // 2、头部等于:AXX = A
    // 3、尾部等于:XXA = A
    // 4、首尾相等:AXXB = AB
    a := strings.Fields(sentence1)
    b := strings.Fields(sentence2)
    i, j := 0, 0
    for i < len(a) && a[i] == b[i] { // 从开头统计
        i++
    }
    for 0 <= len(a)-1-j && a[len(a)-1-j] == b[len(b)-1-j] { // 从结尾统计
        j++
    }
    return i+j >= len(a) // 大于等于较短的长度
}

1814.统计一个数组中好对子的数目(1)

  • 题目
给你一个数组nums,数组中只包含非负整数。定义rev(x)的值为将整数x各个数字位反转得到的结果。
比方说rev(123) = 321,rev(120) = 21。我们称满足下面条件的下标对(i, j) 是好的:
0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
请你返回好下标对的数目。由于结果可能会很大,请将结果对109 + 7取余后返回。
示例 1:输入:nums = [42,11,1,97] 输出:2
解释:两个坐标对为:
 - (0,3):42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2):11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。
示例 2:输入:nums = [13,10,35,24,76] 输出:4
提示:1 <= nums.length <= 105
0 <= nums[i] <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
func countNicePairs(nums []int) int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        m[nums[i]-reverse(nums[i])]++
    }
    res := 0
    for _, v := range m {
        res = (res + v*(v-1)/2) % 1000000007
    }
    return res
}

func reverse(num int) int {
    res := 0
    for num > 0 {
        res = res*10 + num%10
        num = num / 10
    }
    return res
}

1817.查找用户活跃分钟数(1)

  • 题目
给你用户在 LeetCode 的操作日志,和一个整数 k 。日志用一个二维整数数组 logs 表示,
其中每个 logs[i] = [IDi, timei] 表示 ID 为 IDi 的用户在 timei 分钟时执行了某个操作。
多个用户 可以同时执行操作,单个用户可以在同一分钟内执行 多个操作 。
指定用户的 用户活跃分钟数(user active minutes,UAM) 定义为用户对 LeetCode 执行操作的 唯一分钟数 。
即使一分钟内执行多个操作,也只能按一分钟计数。
请你统计用户活跃分钟数的分布情况,统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer ,
对于每个 j(1 <= j <= k),answer[j] 表示 用户活跃分钟数 等于 j 的用户数。
返回上面描述的答案数组 answer 。
示例 1:输入:logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5 输出:[0,2,0,0,0]
解释:
ID=0 的用户执行操作的分钟分别是:5 、2 和 5 。因此,该用户的用户活跃分钟数为 2(分钟 5 只计数一次)
ID=1 的用户执行操作的分钟分别是:2 和 3 。因此,该用户的用户活跃分钟数为 2
2 个用户的用户活跃分钟数都是 2 ,answer[2] 为 2 ,其余 answer[j] 的值都是 0
示例 2:输入:logs = [[1,1],[2,2],[2,3]], k = 4 输出:[1,1,0,0]
解释: ID=1 的用户仅在分钟 1 执行单个操作。因此,该用户的用户活跃分钟数为 1
ID=2 的用户执行操作的分钟分别是:2 和 3 。因此,该用户的用户活跃分钟数为 2
1 个用户的用户活跃分钟数是 1 ,1 个用户的用户活跃分钟数是 2 
因此,answer[1] = 1 ,answer[2] = 1 ,其余的值都是 0
提示:1 <= logs.length <= 104
0 <= IDi <= 109
1 <= timei <= 105
k 的取值范围是 [用户的最大用户活跃分钟数, 105]
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
func findingUsersActiveMinutes(logs [][]int, k int) []int {
    m := make(map[int]map[int]int)
    for i := 0; i < len(logs); i++{
        a, b := logs[i][0], logs[i][1]
        if _, ok := m[a]; ok == false{
            m[a] = make(map[int]int)
        }
        m[a][b]++
    }
    res := make([]int, k)
    for _, v := range m{
        value := len(v)
        res[value-1]++
    }
    return res
}

1818.绝对差值和(1)

  • 题目
给你两个正整数数组 nums1 和 nums2 ,数组的长度都是 n 。
数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|(0 <= i < n)的 
总和(下标从 0 开始)。
你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素,以 最小化 绝对差值和。
在替换数组 nums1 中最多一个元素 之后 ,返回最小绝对差值和。
因为答案可能很大,所以需要对 109 + 7 取余 后返回。
|x| 定义为:如果 x >= 0 ,值为 x ,或者
如果 x <= 0 ,值为 -x
示例 1:输入:nums1 = [1,7,5], nums2 = [2,3,5] 输出:3
解释:有两种可能的最优方案:
- 将第二个元素替换为第一个元素:[1,7,5] => [1,1,5] ,或者
- 将第二个元素替换为第三个元素:[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3
示例 2:输入:nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] 输出:0
解释:nums1 和 nums2 相等,所以不用替换元素。绝对差值和为 0
示例 3:输入:nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4] 输出:20
解释:将第一个元素替换为第二个元素:[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
提示:n == nums1.length
n == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序+二分查找 O(nlog(n)) O(n)
func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
    arr := make([]int, len(nums1))
    sum := 0
    for i := 0; i < len(nums1); i++ {
        arr[i] = nums1[i]
        sum = (sum + abs(nums1[i]-nums2[i])) % 1000000007
    }
    sort.Ints(arr)
    maxValue := 0
    for i := 0; i < len(arr); i++ {
        if nums1[i] == nums2[i] {
            continue
        }
        b := nums2[i]
        target := search(arr, b)
        maxValue = max(maxValue, abs(nums1[i]-b)-abs(target-b))
    }
    return (sum - maxValue+ 1000000007) % 1000000007
}

func search(arr []int, target int) int {
    res := 0
    if arr[0] > target {
        return arr[0]
    }
    if arr[len(arr)-1] < target {
        return arr[len(arr)-1]
    }
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if target < arr[mid] {
            right = mid - 1
            if abs(res-target) > abs(target-arr[mid]) {
                res = arr[mid]
            }
        } else if target == arr[mid] {
            return target
        } else if target > arr[mid] {
            left = mid + 1
            if abs(res-target) > abs(target-arr[mid]) {
                res = arr[mid]
            }
        }
    }
    return res
}

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

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

1823.找出游戏的获胜者(2)

  • 题目
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。
确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,
从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则:
从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴,计数时需要 包含 起始时的那位小伙伴。
逐个绕圈进行计数,一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子,并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴,从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始,回到步骤 2 继续执行。
否则,圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ,和一个整数 k ,返回游戏的获胜者。
示例 1:输入:n = 5, k = 2 输出:3
解释:游戏运行步骤如下:
1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴,也就是小伙伴 1 和 2 。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴,也就是小伙伴 3 和 4 。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴,也就是小伙伴 5 和 1 。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴,也就是小伙伴 3 和 5 。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
示例 2:输入:n = 6, k = 5 输出:1
解释:小伙伴离开圈子的顺序:5、4、6、2、3 。小伙伴 1 是游戏的获胜者。
提示:1 <= k <= n <= 500
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 约瑟夫环 O(n) O(1)
02 模拟 O(n^2) O(n)
func findTheWinner(n int, k int) int {
    idx := 0
    for i := 2; i <= n; i++ {
        idx = (idx + k) % i
    }
    return idx + 1
}

# 2
func findTheWinner(n int, k int) int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    last := 0
    for len(arr) > 1 {
        index := (last + k - 1) % len(arr)
        arr = remove(arr, index)
        last = index
    }
    return arr[0] + 1
}

func remove(arr []int, index int) []int {
    if index == 0 {
        return arr[1:]
    }
    if index == len(arr)-1 {
        return arr[:len(arr)-1]
    }
    return append(arr[:index], arr[index+1:]...)
}

1824.最少侧跳次数(2)

  • 题目
给你一个长度为n的3 跑道道路,它总共包含n + 1个点,编号为0到n。
一只青蛙从0号点第二条跑道出发,它想要跳到点n处。然而道路上可能有一些障碍。
给你一个长度为 n + 1的数组obstacles,其中obstacles[i](取值范围从 0 到 3)
表示在点 i处的obstacles[i]跑道上有一个障碍。
如果obstacles[i] == 0,那么点i处没有障碍。任何一个点的三条跑道中最多有一个障碍。
比方说,如果obstacles[2] == 1,那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i跳到点 i + 1且跑道不变的前提是点 i + 1的同一跑道上没有障碍。
为了躲避障碍,这只青蛙也可以在同一个点处侧跳到 另外一条跑道(这两条跑道可以不相邻),
但前提是跳过去的跑道该点处没有障碍。
比方说,这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2出发,并想到达点 n处的 任一跑道 ,请你返回 最少侧跳次数。
注意:点 0处和点 n处的任一跑道都不会有障碍。
示例 1:输入:obstacles = [0,1,2,3,0] 输出:2 
解释:最优方案如上图箭头所示。总共有 2 次侧跳(红色箭头)。
注意,这只青蛙只有当侧跳时才可以跳过障碍(如上图点 2 处所示)。
示例 2:输入:obstacles = [0,1,1,3,3,0] 输出:0
解释:跑道 2 没有任何障碍,所以不需要任何侧跳。
示例 3:输入:obstacles = [0,2,1,0,3,0] 输出:2
解释:最优方案如上图所示。总共有 2 次侧跳。
提示:obstacles.length == n + 1
1 <= n <= 5 * 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(n)
02 动态规划 O(n) O(n)
func minSideJumps(obstacles []int) int {
    n := len(obstacles)
    dp := make([][3]int, n) // dp[i][j] 到达第i,下标为j的跑道最少次数
    for i := 0; i < n; i++ {
        for j := 0; j < 3; j++ {
            dp[i][j] = math.MaxInt32 / 10
        }
    }
    dp[0][0] = 1
    dp[0][1] = 0
    dp[0][2] = 1
    for i := 1; i < n; i++ {
        // 当前位置无障碍物,继承之前的次数,次数不变
        if obstacles[i] != 1 {
            dp[i][0] = dp[i-1][0]
        }
        if obstacles[i] != 2 {
            dp[i][1] = dp[i-1][1]
        }
        if obstacles[i] != 3 {
            dp[i][2] = dp[i-1][2]
        }
        // 从其它位置跳过来
        if obstacles[i] != 1 {
            dp[i][0] = min(dp[i][0], min(dp[i][1], dp[i][2])+1)
        }
        if obstacles[i] != 2 {
            dp[i][1] = min(dp[i][1], min(dp[i][0], dp[i][2])+1)
        }
        if obstacles[i] != 3 {
            dp[i][2] = min(dp[i][2], min(dp[i][0], dp[i][1])+1)
        }
    }
    return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]))
}

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

# 2
func minSideJumps(obstacles []int) int {
    n := len(obstacles)
    dp := make([][3]int, n) // dp[i][j] 到达第i,下标为j的跑道最少次数
    for i := 0; i < n; i++ {
        for j := 0; j < 3; j++ {
            dp[i][j] = math.MaxInt32 / 10
        }
    }
    dp[0][0] = 1
    dp[0][1] = 0
    dp[0][2] = 1
    for i := 1; i < n; i++ {
        if obstacles[i] == 0 { // 没有障碍物,从其它2条道跳过来
            dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])+1)
            dp[i][1] = min(dp[i-1][1], min(dp[i-1][0], dp[i-1][2])+1)
            dp[i][2] = min(dp[i-1][2], min(dp[i-1][0], dp[i-1][1])+1)
        } else {
            a := obstacles[i] - 1
            b := (obstacles[i]) % 3
            c := (obstacles[i] + 1) % 3
            dp[i][a] = math.MaxInt32 / 10 // 不可达
            dp[i][b] = min(dp[i-1][b], dp[i-1][c]+1)
            dp[i][c] = min(dp[i-1][c], dp[i-1][b]+1)
        }

    }
    return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]))
}

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

1828.统计一个圆中点的数目(1)

  • 题目
给你一个数组points,其中points[i] = [xi, yi],表示第i个点在二维平面上的坐标。
多个点可能会有 相同的坐标。
同时给你一个数组queries,其中queries[j] = [xj, yj, rj],
表示一个圆心在(xj, yj)且半径为rj的圆。
对于每一个查询queries[j],计算在第 j个圆 内点的数目。
如果一个点在圆的 边界上,我们同样认为它在圆内。
请你返回一个数组answer,其中answer[j]是第j个查询的答案。
示例 1: 输入:points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出:[3,2,2]
解释:所有的点和圆如上图所示。
queries[0] 是绿色的圆,queries[1] 是红色的圆,queries[2] 是蓝色的圆。
示例 2:输入:points = [[1,1],[2,2],[3,3],[4,4],[5,5]], 
queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]] 输出:[2,3,2,4]
解释:所有的点和圆如上图所示。
queries[0] 是绿色的圆,queries[1] 是红色的圆,queries[2] 是蓝色的圆,queries[3] 是紫色的圆。
提示:1 <= points.length <= 500
points[i].length == 2
0 <= xi, yi <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= xj, yj <= 500
1 <= rj <= 500
所有的坐标都是整数。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(n)
func countPoints(points [][]int, queries [][]int) []int {
    n := len(queries)
    res := make([]int, n)
    for i := 0; i < n; i++ {
        count := 0
        for j := 0; j < len(points); j++ {
            if judge(queries[i], points[j]) == true {
                count++
            }
        }
        res[i] = count
    }
    return res
}

func judge(query []int, point []int) bool {
    x, y, r := query[0], query[1], query[2]
    x1, y1 := point[0], point[1]
    return (x-x1)*(x-x1)+(y-y1)*(y-y1) <= r*r
}

1829.每个查询的最大异或值(2)

  • 题目
给你一个 有序数组nums,它由n个非负整数组成,同时给你一个整数maximumBit。
你需要执行以下查询 n次:
找到一个非负整数k < 2maximumBit,
使得nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k的结果 最大化。
k是第 i个查询的答案。
从当前数组nums删除最后一个元素。
请你返回一个数组answer,其中answer[i]是第i个查询的结果。
示例 1:输入:nums = [0,1,1,3], maximumBit = 2 输出:[0,3,2,3]
解释:查询的答案如下:
第一个查询:nums = [0,1,1,3],k = 0,因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。
第二个查询:nums = [0,1,1],k = 3,因为 0 XOR 1 XOR 1 XOR 3 = 3 。
第三个查询:nums = [0,1],k = 2,因为 0 XOR 1 XOR 2 = 3 。
第四个查询:nums = [0],k = 3,因为 0 XOR 3 = 3 。
示例 2:输入:nums = [2,3,4,7], maximumBit = 3 输出:[5,2,6,5]
解释:查询的答案如下:
第一个查询:nums = [2,3,4,7],k = 5,因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
第二个查询:nums = [2,3,4],k = 2,因为 2 XOR 3 XOR 4 XOR 2 = 7 。
第三个查询:nums = [2,3],k = 6,因为 2 XOR 3 XOR 6 = 7 。
第四个查询:nums = [2],k = 5,因为 2 XOR 5 = 7 。
示例 3:输入:nums = [0,1,2,2,5,7], maximumBit = 3 输出:[4,3,6,4,6,7]
提示:nums.length == n
1 <= n <= 105
1 <= maximumBit <= 20
0 <= nums[i] < 2maximumBit
nums中的数字已经按升序排好序。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历-位运算 O(n) O(n)
02 遍历-位运算 O(n) O(n)
func getMaximumXor(nums []int, maximumBit int) []int {
    n := len(nums)
    res := make([]int, n)
    temp := nums[0]
    res[n-1] = temp
    for i := 1; i < n; i++ {
        temp = temp ^ nums[i]
        res[n-1-i] = temp
    }
    target := 1<<maximumBit - 1
    for i := 0; i < n; i++ {
        res[i] = res[i] ^ target
    }
    return res
}

# 2
func getMaximumXor(nums []int, maximumBit int) []int {
    n := len(nums)
    res := make([]int, 0)
    temp := nums[0]
    for i := 1; i < n; i++ {
        temp = temp ^ nums[i]
    }
    target := 1<<maximumBit - 1
    for i := n - 1; i >= 0; i-- {
        res = append(res, temp^target)
        temp = temp ^ nums[i]
    }
    return res
}

1833.雪糕的最大数量(1)

  • 题目
夏日炎炎,小男孩 Tony 想买一些雪糕消消暑。
商店中新到 n 支雪糕,用长度为 n 的数组 costs 表示雪糕的定价,其中 costs[i] 表示第 i 支雪糕的现金价格。
Tony 一共有 coins 现金可以用于消费,他想要买尽可能多的雪糕。
给你价格数组 costs 和现金量 coins ,请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
注意:Tony 可以按任意顺序购买雪糕。
示例 1:输入:costs = [1,3,2,4,1], coins = 7 输出:4
解释:Tony 可以买下标为 0、1、2、4 的雪糕,总价为 1 + 3 + 2 + 1 = 7
示例 2:输入:costs = [10,6,8,7,7,8], coins = 5 输出:0
解释:Tony 没有足够的钱买任何一支雪糕。
示例 3:输入:costs = [1,6,3,1,2,5], coins = 20 输出:6
解释:Tony 可以买下所有的雪糕,总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。
提示:costs.length == n
1 <= n <= 105
1 <= costs[i] <= 105
1 <= coins <= 108
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(1)
func maxIceCream(costs []int, coins int) int {
    sort.Ints(costs)
    for i := 0; i < len(costs); i++ {
        if costs[i] <= coins {
            coins = coins - costs[i]
        } else {
            return i
        }
    }
    return len(costs)
}

1834.单线程CPU(1)

  • 题目
给你一个二维数组 tasks ,用于表示 n项从 0 到 n - 1 编号的任务。
其中 tasks[i] = [enqueueTimei, processingTimei] 意味着
第 i项任务将会于 enqueueTimei 时进入任务队列,需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ,同一时间只能执行 最多一项 任务,该 CPU 将会按照下述方式运行:
如果 CPU 空闲,且任务队列中没有需要执行的任务,则 CPU 保持空闲状态。
如果 CPU 空闲,但任务队列中有需要执行的任务,则 CPU 将会选择 执行时间最短 的任务开始执行。
如果多个任务具有同样的最短执行时间,则选择下标最小的任务开始执行。
一旦某项任务开始执行,CPU 在 执行完整个任务 前都不会停止。
CPU 可以在完成一项任务后,立即开始执行一项新任务。
返回 CPU 处理任务的顺序。
示例 1:输入:tasks = [[1,2],[2,4],[3,2],[4,1]] 输出:[0,2,3,1]
解释:事件按下述流程运行: 
- time = 1 ,任务 0 进入任务队列,可执行任务项 = {0}
- 同样在 time = 1 ,空闲状态的 CPU 开始执行任务 0 ,可执行任务项 = {}
- time = 2 ,任务 1 进入任务队列,可执行任务项 = {1}
- time = 3 ,任务 2 进入任务队列,可执行任务项 = {1, 2}
- 同样在 time = 3 ,CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ,可执行任务项 = {1}
- time = 4 ,任务 3 进入任务队列,可执行任务项 = {1, 3}
- time = 5 ,CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ,可执行任务项 = {1}
- time = 6 ,CPU 完成任务 3 并开始执行任务 1 ,可执行任务项 = {}
- time = 10 ,CPU 完成任务 1 并进入空闲状态
示例 2:输入:tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] 输出:[4,3,2,0,1]
解释:事件按下述流程运行: 
- time = 7 ,所有任务同时进入任务队列,可执行任务项  = {0,1,2,3,4}
- 同样在 time = 7 ,空闲状态的 CPU 开始执行任务 4 ,可执行任务项 = {0,1,2,3}
- time = 9 ,CPU 完成任务 4 并开始执行任务 3 ,可执行任务项 = {0,1,2}
- time = 13 ,CPU 完成任务 3 并开始执行任务 2 ,可执行任务项 = {0,1}
- time = 18 ,CPU 完成任务 2 并开始执行任务 0 ,可执行任务项 = {1}
- time = 28 ,CPU 完成任务 0 并开始执行任务 1 ,可执行任务项 = {}
- time = 40 ,CPU 完成任务 1 并进入空闲状态
提示:tasks.length == n
1 <= n <= 105
1 <= enqueueTimei, processingTimei <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(log(n)) O(1)
func getOrder(tasks [][]int) []int {
    n := len(tasks)
    res := make([]int, 0)
    arr := make([]Node, 0)
    for i := 0; i < n; i++ {
        arr = append(arr, Node{
            Id:             i,
            StartTime:      tasks[i][0],
            ProcessingTime: tasks[i][1],
        })
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i].StartTime < arr[j].StartTime
    })
    nodeHeap := make(NodeHeap, 0)
    heap.Init(&nodeHeap)
    curTime := 0
    cur := 0
    for i := 0; i < n; i++ { // 每次处理1个任务
        if nodeHeap.Len() == 0 { // 空任务
            curTime = max(curTime, tasks[arr[cur].Id][0]) // 时间移动
        }
        for ; cur < n && arr[cur].StartTime <= curTime; cur++ { // 加入优先队列:将小于等于时间戳的任务加入堆
            heap.Push(&nodeHeap, arr[cur])
        }
        node := heap.Pop(&nodeHeap).(Node)      // 选择任务:选择处理时间小的任务
        curTime = curTime + node.ProcessingTime // 时间处理
        res = append(res, node.Id)
    }
    return res
}

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

type Node struct {
    Id             int
    StartTime      int
    ProcessingTime int
}

type NodeHeap []Node

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

// 小根堆<,大根堆变换方向>
func (h NodeHeap) Less(i, j int) bool {
    if h[i].ProcessingTime == h[j].ProcessingTime {
        return h[i].Id < h[j].Id
    }
    return h[i].ProcessingTime < h[j].ProcessingTime
}

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

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

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

1838.最高频元素的频数(3)

  • 题目
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums 和一个整数 k 。在一步操作中,你可以选择 nums 的一个下标,
并将该下标对应元素的值增加 1 。
执行最多 k 次操作后,返回数组中最高频元素的 最大可能频数 。
示例 1:输入:nums = [1,2,4], k = 5 输出:3
解释:对第一个元素执行 3 次递增操作,对第二个元素执 2 次递增操作,此时 nums = [4,4,4] 。
4 是数组中最高频元素,频数是 3 。
示例 2:输入:nums = [1,4,8,13], k = 5 输出:2
解释:存在多种最优解决方案:
- 对第一个元素执行 3 次递增操作,此时 nums = [4,4,8,13] 。4 是数组中最高频元素,频数是 2 。
- 对第二个元素执行 4 次递增操作,此时 nums = [1,8,8,13] 。8 是数组中最高频元素,频数是 2 。
- 对第三个元素执行 5 次递增操作,此时 nums = [1,4,13,13] 。13 是数组中最高频元素,频数是 2 。
示例 3:输入:nums = [3,9,6], k = 2 输出:1
提示:1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 前缀和+双指针 O(nlog(n)) O(n)
02 排序+双指针 O(nlog(n)) O(1)
03 前缀和+内置函数 O(nlog(n)) O(n)
func maxFrequency(nums []int, k int) int {
    n := len(nums)
    sort.Ints(nums)
    arr := make([]int, n+1)
    for i := 1; i <= n; i++ {
        arr[i] = arr[i-1] + nums[i-1]
    }
    res := 1
    i := 0
    for j := 0; j < n; j++ {
        for nums[j]*(j-i)-(arr[j]-arr[i]) > k {
            i++
        }
        if j-i+1 > res {
            res = j - i + 1
        }
    }
    return res
}

# 2
func maxFrequency(nums []int, k int) int {
    n := len(nums)
    sort.Ints(nums)
    res := 1
    total := 0
    i := 0
    for j := 1; j < n; j++ {
        total = total + (nums[j]-nums[j-1])*(j-i) // 累加
        for total > k {
            total = total - (nums[j] - nums[i]) // 不满足,要减去
            i++
        }
        if j-i+1 > res {
            res = j - i + 1
        }
    }
    return res
}

# 3
func maxFrequency(nums []int, k int) int {
    n := len(nums)
    sort.Ints(nums)
    arr := make([]int, n+1)
    for i := 1; i <= n; i++ {
        arr[i] = arr[i-1] + nums[i-1]
    }
    res := 1
    for j := 0; j < n; j++ {
        i := sort.Search(j, func(i int) bool {
            return nums[j]*(j-i)-(arr[j]-arr[i]) <= k
        })
        if j-i+1 > res {
            res = j - i + 1
        }
    }
    return res
}

1839.所有元音按顺序排布的最长子字符串(1)

  • 题目
当一个字符串满足如下条件时,我们称它是 美丽的:
所有 5 个英文元音字母('a','e','i','o','u')都必须至少出现一次。
这些元音字母的顺序都必须按照 字典序升序排布(也就是说所有的 'a'都在 'e'前面,
所有的 'e'都在 'i'前面,以此类推)
比方说,字符串"aeiou" 和"aaaaaaeiiiioou"都是 美丽的,
但是"uaeio","aeoiu"和"aaaeeeooo"不是美丽的。
给你一个只包含英文元音字母的字符串word,请你返回word 中 最长美丽子字符串的长度。
如果不存在这样的子字符串,请返回 0。
子字符串 是字符串中一个连续的字符序列。
示例 1:输入:word = "aeiaaioaaaaeiiiiouuuooaauuaeiu" 输出:13
解释:最长子字符串是 "aaaaeiiiiouuu" ,长度为 13 。
示例 2:输入:word = "aeeeiiiioooauuuaeiou" 输出:5
解释:最长子字符串是 "aeiou" ,长度为 5 。
示例 3:输入:word = "a" 输出:0
解释:没有美丽子字符串,所以返回 0 。
提示:1 <= word.length <= 5 * 105
word只包含字符'a','e','i','o'和'u'。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 滑动窗口 O(n) O(1)
func longestBeautifulSubstring(word string) int {
    res := 0
    count := 1
    i := 0
    for j := 1; j < len(word); j++ { // 题目保证了全是目标元素,而且顺序是有序的
        if word[j] < word[j-1] { // 大小不对,窗口右移,重新计数
            i = j
            count = 1
        } else if word[j] > word[j-1] {
            count++
        }
        if count == 5 { // 长度为5
            res = max(res, j-i+1)
        }
    }
    return res
}

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

1845.座位预约管理系统(1)

  • 题目
请你设计一个管理 n个座位预约的系统,座位编号从1到n。
请你实现SeatManager类:
SeatManager(int n)初始化一个SeatManager对象,它管理从 1到 n编号的n个座位。所有座位初始都是可预约的。
int reserve()返回可以预约座位的最小编号,此座位变为不可预约。
void unreserve(int seatNumber)将给定编号seatNumber对应的座位变成可以预约。
示例 1:输入:["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", 
"reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
输出: [null, 1, 2, null, 2, 3, 4, 5, null]
解释:
SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ,有 5 个座位。
seatManager.reserve();    // 所有座位都可以预约,所以返回最小编号的座位,也就是 1 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ,返回最小编号的座位,也就是 2 。
seatManager.unreserve(2); // 将座位 2 变为可以预约,现在可预约的座位为 [2,3,4,5] 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ,返回最小编号的座位,也就是 2 。
seatManager.reserve();    // 可以预约的座位为 [3,4,5] ,返回最小编号的座位,也就是 3 。
seatManager.reserve();    // 可以预约的座位为 [4,5] ,返回最小编号的座位,也就是 4 。
seatManager.reserve();    // 唯一可以预约的是座位 5 ,所以返回 5 。
seatManager.unreserve(5); // 将座位 5 变为可以预约,现在可预约的座位为 [5] 。
提示:1 <= n <= 105
1 <= seatNumber <= n
每一次对reserve的调用,题目保证至少存在一个可以预约的座位。
每一次对unreserve的调用,题目保证seatNumber在调用函数前都是被预约状态。
对reserve 和unreserve的调用总共不超过105次。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 O(nlog(n)) O(n)
type SeatManager struct {
    intHeap IntHeap
}

func Constructor(n int) SeatManager {
    intHeap := make(IntHeap, 0)
    heap.Init(&intHeap)
    for i := 1; i <= n; i++ {
        heap.Push(&intHeap, i)
    }
    return SeatManager{intHeap: intHeap}
}

func (this *SeatManager) Reserve() int {
    top := heap.Pop(&this.intHeap).(int)
    return top
}

func (this *SeatManager) Unreserve(seatNumber int) {
    heap.Push(&this.intHeap, seatNumber)
}

type IntHeap []int

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

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

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

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

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

1846.减小和重新排列数组后的最大元素(2)

  • 题目
给你一个正整数数组arr。请你对 arr执行一些操作(也可以不进行任何操作),使得数组满足以下条件:
arr中 第一个元素必须为1。
任意相邻两个元素的差的绝对值 小于等于1,也就是说,对于任意的 1 <= i < arr.length(数组下标从 0 开始),
都满足abs(arr[i] - arr[i - 1]) <= 1。abs(x)为x的绝对值。
你可以执行以下 2 种操作任意次:
减小 arr中任意元素的值,使其变为一个 更小的正整数。
重新排列arr中的元素,你可以以任意顺序重新排列。
请你返回执行以上操作后,在满足前文所述的条件下,arr中可能的 最大值。
示例 1:输入:arr = [2,2,1,2,1] 输出:2
解释:我们可以重新排列 arr 得到 [1,2,2,2,1] ,该数组满足所有条件。
arr 中最大元素为 2 。
示例 2:输入:arr = [100,1,1000] 输出:3
解释:一个可行的方案如下:
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ,满足所有条件。
arr 中最大元素为 3 。
示例 3:输入:arr = [1,2,3,4,5] 输出:5
解释:数组已经满足所有条件,最大元素为 5 。
提示:1 <= arr.length <= 105
1 <= arr[i] <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
02 排序 O(nlog(n)) O(1)
func maximumElementAfterDecrementingAndRearranging(arr []int) int {
    sort.Ints(arr)
    n := len(arr)
    arr[0] = 1
    for i := 1; i < n; i++ {
        arr[i] = min(arr[i], arr[i-1]+1)
    }
    return arr[n-1]
}

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

# 2
func maximumElementAfterDecrementingAndRearranging(arr []int) int {
    sort.Ints(arr)
    res := 0
    for i := 0; i < len(arr); i++ {
        if res < arr[i] {
            res++
        }
    }
    return res
}

1849.将字符串拆分为递减的连续值(3)

  • 题目
给你一个仅由数字组成的字符串 s 。
请你判断能否将 s 拆分成两个或者多个 非空子字符串 ,使子字符串的 数值 按 降序 排列,且每两个 相邻子字符串 的数值之 差 等于 1 。
例如,字符串 s = "0090089" 可以拆分成 ["0090", "089"] ,数值为 [90,89] 。
这些数值满足按降序排列,且相邻值相差 1 ,这种拆分方法可行。
另一个例子中,字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"] 或 ["0", "0", "1"] 。
然而,所有这些拆分方法都不可行,因为对应数值分别是 [0,1]、[0,1] 和 [0,0,1] ,都不满足按降序排列的要求。
如果可以按要求拆分 s ,返回 true ;否则,返回 false 。
子字符串 是字符串中的一个连续字符序列。
示例 1:输入:s = "1234" 输出:false
解释:不存在拆分 s 的可行方法。
示例 2:输入:s = "050043" 输出:true
解释:s 可以拆分为 ["05", "004", "3"] ,对应数值为 [5,4,3] 。
满足按降序排列,且相邻值相差 1 。
示例 3:输入:s = "9080701" 输出:false
解释:不存在拆分 s 的可行方法。
示例 4:输入:s = "10009998" 输出:true
解释:s 可以拆分为 ["100", "099", "98"] ,对应数值为 [100,99,98] 。
满足按降序排列,且相邻值相差 1 。
提示:1 <= s.length <= 20
s 仅由数字组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 递归 O(n^2) O(n)
02 递归 O(n^2) O(n)
03 遍历 O(n^2) O(n)
func splitString(s string) bool {
    for i := 0; i < len(s); i++ {
        value, _ := strconv.Atoi(s[:i+1])
        if s[i+1:] != "" && dfs(s[i+1:], value-1) == true {
            return true
        }
    }
    return false
}

func dfs(s string, target int) bool {
    value, _ := strconv.Atoi(s)
    if s == "" || value == target {
        return true
    }
    for i := 0; i < len(s); i++ {
        v, _ := strconv.Atoi(s[:i+1])
        if v < target {
            continue
        }
        if v > target {
            return false
        }
        if v == target {
            if dfs(s[i+1:], target-1) == true {
                return true
            }
            return false
        }
    }
    return false
}

# 2
func splitString(s string) bool {
    return dfs([]byte(s), 0, 0, 0)
}

func dfs(arr []byte, index int, count int, target int) bool {
    if index == len(arr) {
        return count > 1
    }
    value := 0
    for i := index; i < len(arr); i++ {
        value = value*10 + int(arr[i]-'0')
        if count == 0 || value == target-1 {
            if dfs(arr, i+1, count+1, value) == true {
                return true
            }
        }
    }
    return false
}

# 3
func splitString(s string) bool {
    n := len(s)
    for i := 0; i < n-1; i++ {
        a, _ := strconv.Atoi(s[0 : i+1])
        index := i
        for j := i + 1; j < n; j++ {
            b, _ := strconv.Atoi(s[index+1 : j+1])
            c, _ := strconv.Atoi(s[index+1 : n])
            if c == a-1 {
                return true
            }
            if b == a-1 {
                index = j
                a = b
                c, _ := strconv.Atoi(s[index+1 : n])
                if c == a-1 {
                    return true
                }
            } else if b > a-1 {
                break
            }
        }
    }
    return false
}

1850.邻位交换的最小次数(1)

  • 题目
给你一个表示大整数的字符串 num ,和一个整数 k 。
如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ,则称这个整数为 妙数 。
可能存在很多妙数,但是只需要关注 值最小 的那些。
例如,num = "5489355142" :
第 1 个最小妙数是 "5489355214"
第 2 个最小妙数是 "5489355241"
第 3 个最小妙数是 "5489355412"
第 4 个最小妙数是 "5489355421"
返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。
测试用例是按存在第 k 个最小妙数而生成的。
示例 1:输入:num = "5489355142", k = 4 输出:2
解释:第 4 个最小妙数是 "5489355421" ,要想得到这个数字:
- 交换下标 7 和下标 8 对应的位:"5489355142" -> "5489355412"
- 交换下标 8 和下标 9 对应的位:"5489355412" -> "5489355421"
示例 2:输入:num = "11112", k = 4 输出:4
解释:第 4 个最小妙数是 "21111" ,要想得到这个数字:
- 交换下标 3 和下标 4 对应的位:"11112" -> "11121"
- 交换下标 2 和下标 3 对应的位:"11121" -> "11211"
- 交换下标 1 和下标 2 对应的位:"11211" -> "12111"
- 交换下标 0 和下标 1 对应的位:"12111" -> "21111"
示例 3:输入:num = "00123", k = 1 输出:1
解释:第 1 个最小妙数是 "00132" ,要想得到这个数字:
- 交换下标 3 和下标 4 对应的位:"00123" -> "00132"
提示:2 <= num.length <= 1000
1 <= k <= 1000
num 仅由数字组成
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟+贪心 O(n^2) O(n)
func getMinSwaps(num string, k int) int {
    target := []byte(num)
    n := len(target)
    res := 0
    for i := 1; i <= k; i++ { // 求接下来的第k个排列
        nextPermutation(target)
    }
    // 统计交换次数
    arr := []byte(num)
    for i := 0; i < n; i++ {
        if arr[i] != target[i] {
            for j := i + 1; j < n; j++ {
                if arr[j] == target[i] { // 找到交换
                    for k := j - 1; k >= i; k-- { // 把arr[j]交换到前面去
                        arr[k], arr[k+1] = arr[k+1], arr[k]
                        res++
                    }
                    break
                }
            }
        }
    }
    return res
}

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

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

1855.下标对中的最大距离(3)

  • 题目
给你两个 非递增 的整数数组 nums1和 nums2,数组下标均 从 0 开始 计数。
下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。
如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ,则称之为 有效 下标对,该下标对的 距离 为 j - i。
返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对,返回 0 。
一个数组 arr ,如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立,那么该数组是一个 非递增 数组。
示例 1:输入:nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] 输出:2
解释:有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ,对应下标对 (2,4) 。
示例 2:输入:nums1 = [2,2,2], nums2 = [10,10,1] 输出:1
解释:有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ,对应下标对 (0,1) 。
示例 3:输入:nums1 = [30,29,19,5], nums2 = [25,25,25,25,25] 输出:2
解释:有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ,对应下标对 (2,4) 。
示例 4:输入:nums1 = [5,4], nums2 = [3,2] 输出:0
解释:不存在有效下标对,所以返回 0 。
提示:1 <= nums1.length <= 105
1 <= nums2.length <= 105
1 <= nums1[i], nums2[j] <= 105
nums1 和 nums2 都是 非递增 数组
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 二分查找 O(nlog(n)) O(1)
03 双指针 O(n) O(1)
func maxDistance(nums1 []int, nums2 []int) int {
    res := 0
    i := 0
    for j := 0; j < len(nums2); j++ {
        for i < len(nums1) && nums2[j] < nums1[i] {
            i++
        }
        if i < len(nums1) {
            if j-i > res {
                res = j - i
            }
        }
    }
    return res
}

# 2
func maxDistance(nums1 []int, nums2 []int) int {
    res := 0
    for j := 0; j < len(nums2); j++ {
        n := min(j, len(nums1))
        i := sort.Search(n, func(i int) bool {
            return nums1[i] <= nums2[j]
        })
        if i < n {
            if j-i > res {
                res = j - i
            }
        }
    }
    return res
}

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

# 3
func maxDistance(nums1 []int, nums2 []int) int {
    res := 0
    j := 0
    for i := 0; i < len(nums1); i++ {
        for j < len(nums2) && nums1[i] <= nums2[j] {
            j++
        }
        if j-i-1 > res {
            res = j - i - 1
        }
    }
    return res
}

1856.子数组最小乘积的最大值(2)

  • 题目
一个数组的 最小乘积定义为这个数组中 最小值乘以数组的 和。
比方说,数组[3,2,5](最小值是2)的最小乘积为2 * (3+2+5) = 2 * 10 = 20。
给你一个正整数数组nums,请你返回nums任意非空子数组的最小乘积的最大值。
由于答案可能很大,请你返回答案对109 + 7取余的结果。
请注意,最小乘积的最大值考虑的是取余操作 之前的结果。
题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数保存。
子数组定义为一个数组的 连续部分。
示例 1:输入:nums = [1,2,3,2] 输出:14
解释:最小乘积的最大值由子数组 [2,3,2] (最小值是 2)得到。
2 * (2+3+2) = 2 * 7 = 14 。
示例 2:输入:nums = [2,3,3,1,2] 输出:18
解释:最小乘积的最大值由子数组 [3,3] (最小值是 3)得到。
3 * (3+3) = 3 * 6 = 18 。
示例 3:输入:nums = [3,1,5,6,4,2] 输出:60
解释:最小乘积的最大值由子数组 [5,6,4] (最小值是 4)得到。
4 * (5+6+4) = 4 * 15 = 60 。
提示:1 <= nums.length <= 105
1 <= nums[i] <= 107
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 单调栈+前缀和 O(n) O(n)
02 单调栈+前缀和 O(n) O(n)
var mod = 1000000007

func maxSumMinProduct(nums []int) int {
    res := 0
    n := len(nums)
    arr := make([]int, n+1) // 前缀和
    for i := 1; i <= n; i++ {
        arr[i] = arr[i-1] + nums[i-1]
    }
    left := make([]int, n)  // 左侧最近的严格小于nums[i]的元素下标
    right := make([]int, n) // 右侧最近的小于等于nums[i]的元素下标
    for i := 0; i < n; i++ {
        left[i] = 0      // 默认是最左边
        right[i] = n - 1 // 默认是最右边
    }
    stack := make([]int, 0) // 单调递减栈
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] >= nums[i] {
            right[stack[len(stack)-1]] = i - 1
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            left[i] = stack[len(stack)-1] + 1
        }
        stack = append(stack, i)
    }
    for i := 0; i < n; i++ {
        target := (arr[right[i]+1] - arr[left[i]]) * nums[i]
        res = max(res, target)
    }
    return res % mod
}

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

# 2
var mod = 1000000007

func maxSumMinProduct(nums []int) int {
    res := 0
    n := len(nums)
    arr := make([]int, n+1) // 前缀和
    for i := 1; i <= n; i++ {
        arr[i] = arr[i-1] + nums[i-1]
    }
    left, right := make([]int, n), make([]int, n)
    for i := 0; i < n; i++ {
        left[i] = -1 // 默认是最左边
        right[i] = n // 默认是最右边
    }
    stack := make([]int, 0) // 双栈:leetcode 84.柱状图中最大的矩形
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            right[stack[len(stack)-1]] = i
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    stack = make([]int, 0)
    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            left[stack[len(stack)-1]] = i
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    for i := 0; i < n; i++ {
        target := (arr[right[i]] - arr[left[i]+1]) * nums[i]
        res = max(res, target)
    }
    return res % mod
}

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

1860.增长的内存泄露(2)

  • 题目
给你两个整数memory1 和memory2分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。
在第i秒(秒数从 1 开始),有 i位内存被分配到剩余内存较多的内存条(如果两者一样多,则分配到第一个内存条)。
如果两者剩余内存都不足 i位,那么程序将 意外退出。
请你返回一个数组,包含 [crashTime, memory1crash, memory2crash],
其中crashTime是程序意外退出的时间(单位为秒),memory1crash 和memory2crash分别是两个内存条最后剩余内存的位数。
示例 1:输入:memory1 = 2, memory2 = 2 输出:[3,1,0]
解释:内存分配如下:
- 第 1 秒,内存条 1 被占用 1 位内存。内存条 1 现在有 1 位剩余可用内存。
- 第 2 秒,内存条 2 被占用 2 位内存。内存条 2 现在有 0 位剩余可用内存。
- 第 3 秒,程序意外退出,两个内存条分别有 1 位和 0 位剩余可用内存。
示例 2:输入:memory1 = 8, memory2 = 11 输出:[6,0,4]
解释:内存分配如下:
- 第 1 秒,内存条 2 被占用 1 位内存,内存条 2 现在有 10 位剩余可用内存。
- 第 2 秒,内存条 2 被占用 2 位内存,内存条 2 现在有 8 位剩余可用内存。
- 第 3 秒,内存条 1 被占用 3 位内存,内存条 1 现在有 5 位剩余可用内存。
- 第 4 秒,内存条 2 被占用 4 位内存,内存条 2 现在有 4 位剩余可用内存。
- 第 5 秒,内存条 1 被占用 5 位内存,内存条 1 现在有 0 位剩余可用内存。
- 第 6 秒,程序意外退出,两个内存条分别有 0 位和 4 位剩余可用内存。
提示:0 <= memory1, memory2 <= 231 - 1
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟 O(n^1/2) O(1)
02 模拟 O(n^1/2) O(1)
func memLeak(memory1 int, memory2 int) []int {
    i := 1
    for {
        if i <= memory1 || i <= memory2 {
            if memory1 < memory2 {
                memory2 = memory2 - i
            } else {
                memory1 = memory1 - i
            }
        } else {
            break
        }
        i++
    }
    return []int{i, memory1, memory2}
}

# 2
func memLeak(memory1 int, memory2 int) []int {
    i := 1
    for ; i <= memory1 || i <= memory2; i++ {
        if memory1 < memory2 {
            memory2 = memory2 - i
        } else {
            memory1 = memory1 - i
        }
    }
    return []int{i, memory1, memory2}
}

1861.旋转盒子(3)

  • 题目
给你一个m x n的字符矩阵box,它表示一个箱子的侧视图。箱子的每一个格子可能为:
'#'表示石头
'*'表示固定的障碍物
'.'表示空位置
这个箱子被 顺时针旋转 90 度,由于重力原因,部分石头的位置会发生改变。
每个石头会垂直掉落,直到它遇到障碍物,另一个石头或者箱子的底部。
重力 不会影响障碍物的位置,同时箱子旋转不会产生惯性,也就是说石头的水平位置不会发生改变。
题目保证初始时box中的石头要么在一个障碍物上,要么在另一个石头上,要么在箱子的底部。
请你返回一个n x m的矩阵,表示按照上述旋转后,箱子内的结果。
示例 1:输入:box = [["#",".","#"]]
输出:[["."],
     ["#"],
     ["#"]]
示例 2:输入:box = [["#",".","*","."],
           ["#","#","*","."]]
输出:[["#","."],
     ["#","#"],
     ["*","*"],
     [".","."]]
示例 3:输入:box = [["#","#","*",".","*","."],
           ["#","#","#","*",".","."],
           ["#","#","#",".","#","."]]
输出:[[".","#","#"],
     [".","#","#"],
     ["#","#","*"],
     ["#","*","."],
     ["#",".","*"],
     ["#",".","."]]
提示:m == box.length
n == box[i].length
1 <= m, n <= 500
box[i][j]只可能是'#','*'或者'.'。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟 O(n^2) O(n^2)
02 模拟 O(n^2) O(n^2)
03 模拟 O(n^2) O(n^2)
func rotateTheBox(box [][]byte) [][]byte {
    n, m := len(box), len(box[0])
    res := make([][]byte, m)
    for i := 0; i < m; i++ {
        res[i] = make([]byte, n)
        for j := 0; j < n; j++ {
            res[i][j] = '.'
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            count := 0 // 统计一行中#的个数
            for ; j < m && box[i][j] != '*'; j++ {
                if box[i][j] == '#' {
                    count++
                }
            }
            if j < m {
                res[j][n-1-i] = '*' // 填充*
            }
            // 移动# => 填充#
            for k := j - 1; count > 0; k-- {
                res[k][n-1-i] = '#'
                count--
            }
        }
    }
    return res
}

# 2
func rotateTheBox(box [][]byte) [][]byte {
    n, m := len(box), len(box[0])
    for i := 0; i < n; i++ {
        queue := make([]int, 0)
        for j := m - 1; j >= 0; j-- {
            if box[i][j] == '*' {
                queue = make([]int, 0) // 维护可移动的y坐标
            } else if box[i][j] == '#' {
                if len(queue) > 0 { // 石头落下
                    first := queue[0]        // 最右边能落下的位置
                    queue = queue[1:]        // 退出队列
                    box[i][first] = '#'      // 落下
                    box[i][j] = '.'          // 原位置为空
                    queue = append(queue, j) // 置空后进入队列
                }
            } else {
                queue = append(queue, j)
            }
        }
    }
    res := make([][]byte, m)
    for i := 0; i < m; i++ {
        res[i] = make([]byte, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            res[j][n-1-i] = box[i][j]
        }
    }
    return res
}

# 3
func rotateTheBox(box [][]byte) [][]byte {
    n, m := len(box), len(box[0])
    for i := 0; i < n; i++ {
        last := m - 1 // 最后1个空位
        for j := m - 1; j >= 0; j-- {
            if box[i][j] == '*' {
                last = j - 1 // 有障碍,最后空位更新
            } else if box[i][j] == '#' {
                if last > j { // 可以移动
                    box[i][last] = '#'
                    box[i][j] = '.'
                    last--
                } else { // 当前位置不可以移动
                    last = j - 1
                }
            }
        }
    }
    res := make([][]byte, m)
    for i := 0; i < m; i++ {
        res[i] = make([]byte, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            res[j][n-1-i] = box[i][j]
        }
    }
    return res
}

1864.构成交替字符串需要的最小交换次数(1)

  • 题目
给你一个二进制字符串 s ,现需要将其转化为一个 交替字符串 。
请你计算并返回转化所需的 最小 字符交换次数,如果无法完成转化,返回 -1 。
交替字符串 是指:相邻字符之间不存在相等情况的字符串。例如,字符串 "010" 和 "1010" 属于交替字符串,但 "0100" 不是。
任意两个字符都可以进行交换,不必相邻 。
示例 1:输入:s = "111000" 输出:1
解释:交换位置 1 和 4:"111000" -> "101010" ,字符串变为交替字符串。
示例 2:输入:s = "010" 输出:0
解释:字符串已经是交替字符串了,不需要交换。
示例 3:输入:s = "1110" 输出:-1
提示:1 <= s.length <= 1000
s[i] 的值为 '0' 或 '1'
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 分情况讨论 O(n) O(1)
func minSwaps(s string) int {
    a, b := strings.Count(s, "1"), strings.Count(s, "0")
    if a-b > 1 || b-a > 1 {
        return -1
    }
    n := len(s)
    res := math.MaxInt32
    if a == (n+1)/2 && b == n/2 { // 以1开头:1010xxx
        count := 0
        for i := 0; i < n; i++ {
            if int(s[i]-'0') == i%2 { // 0在偶数下标位置,1在奇数下标位置
                count++
            }
        }
        res = min(res, count/2)
    }
    if b == (n+1)/2 && a == n/2 { // 以0开头:0101xxx
        count := 0
        for i := 0; i < n; i++ {
            if int(s[i]-'0') != i%2 { // 1在偶数下标位置,0在奇数下标位置
                count++
            }
        }
        res = min(res, count/2)
    }
    return res
}

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

1865.找出和为指定值的下标对(1)

  • 题目
给你两个整数数组 nums1 和 nums2 ,请你实现一个支持下述两类查询的数据结构:
累加 ,将一个正整数加到 nums2 中指定下标对应元素上。
计数 ,统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目
(0 <= i < nums1.length 且 0 <= j < nums2.length)。
实现 FindSumPairs 类:
FindSumPairs(int[] nums1, int[] nums2) 使用整数数组nums1 和 nums2 初始化 FindSumPairs 对象。
void add(int index, int val) 将 val 加到 nums2[index] 上,即,执行 nums2[index] += val 。
int count(int tot) 返回满足nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。
示例:输入:
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出:[null, 8, null, 2, 1, null, null, 11]
解释:FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ,
下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ;下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ;下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ;下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 
满足 2 + 5 = 7 ,下标对 (5,3), (5,5) 满足 3 + 4 = 7
提示:1 <= nums1.length <= 1000
1 <= nums2.length <= 105
1 <= nums1[i] <= 109
1 <= nums2[i] <= 105
0 <= index < nums2.length
1 <= val <= 105
1 <= tot <= 109
最多调用add 和 count 函数各 1000 次
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
type FindSumPairs struct {
    nums1, nums2 []int
    m            map[int]int
}

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
    m := make(map[int]int)
    for i := 0; i < len(nums2); i++ {
        m[nums2[i]]++
    }
    return FindSumPairs{
        nums1: nums1,
        nums2: nums2,
        m:     m,
    }
}

func (this *FindSumPairs) Add(index int, val int) {
    this.m[this.nums2[index]]--
    this.nums2[index] = this.nums2[index] + val
    this.m[this.nums2[index]]++
}

func (this *FindSumPairs) Count(tot int) int {
    res := 0
    for i := 0; i < len(this.nums1); i++ {
        res = res + this.m[tot-this.nums1[i]]
    }
    return res
}

1870.准时到达的列车最小时速(1)

  • 题目
给你一个浮点数 hour ,表示你到达办公室可用的总通勤时间。要到达办公室,你必须按给定次序乘坐 n 趟列车。
另给你一个长度为 n 的整数数组 dist ,其中 dist[i] 表示第 i 趟列车的行驶距离(单位是千米)。
每趟列车均只能在整点发车,所以你可能需要在两趟列车之间等待一段时间。
例如,第 1 趟列车需要 1.5 小时,那你必须再等待 0.5 小时,搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速(单位:千米每小时),如果无法准时到达,则返回 -1 。
生成的测试用例保证答案不超过 107 ,且 hour 的 小数点后最多存在两位数字 。
示例 1:输入:dist = [1,3,2], hour = 6 输出:1
解释:速度为 1 时:
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达,可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达,可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。
示例 2:输入:dist = [1,3,2], hour = 2.7 输出:3
解释:速度为 3 时:
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达,故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达,可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。
示例 3:输入:dist = [1,3,2], hour = 1.9 输出:-1
解释:不可能准时到达,因为第 3 趟列车最早是在第 2 小时发车。
提示:n == dist.length
1 <= n <= 105
1 <= dist[i] <= 105
1 <= hour <= 109
hours 中,小数点后最多存在两位数字
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(nlog(n)) O(1)
func minSpeedOnTime(dist []int, hour float64) int {
    n := len(dist)
    if float64(n-1) > hour {
        return -1
    }
    left, right := 1, math.MaxInt32
    for left <= right {
        mid := left + (right-left)/2
        if judge(dist, float64(mid)) <= hour {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

func judge(arr []int, speed float64) float64 {
    n := len(arr)
    res := float64(0)
    for i := 0; i < n-1; i++ {
        res = res + math.Ceil(float64(arr[i])/speed) // 向上取整
    }
    res = res + float64(arr[n-1])/speed // 注意:最后一个不需要等待
    return res
}

1871.跳跃游戏VII(4)

  • 题目
给你一个下标从 0 开始的二进制字符串s和两个整数minJump 和maxJump。
一开始,你在下标0处,且该位置的值一定为'0'。
当同时满足如下条件时,你可以从下标i移动到下标j处:
i + minJump <= j <= min(i + maxJump, s.length - 1)且 s[j] == '0'.
如果你可以到达 s的下标s.length - 1处,请你返回true,否则返回false。
示例 1:输入:s = "011010", minJump = 2, maxJump = 3 输出:true
解释:
第一步,从下标 0 移动到下标 3 。
第二步,从下标 3 移动到下标 5 。
示例 2:输入:s = "01101110", minJump = 2, maxJump = 3 输出:false
提示:2 <= s.length <= 105
s[i]要么是'0',要么是'1'
s[0] == '0'
1 <= minJump <= maxJump < s.length
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 动态规划+滑动窗口 O(n) O(n)
03 动态规划+前缀和 O(n) O(n)
04 差分数组 O(n) O(n)
func canReach(s string, minJump int, maxJump int) bool {
    n := len(s)
    if s[n-1] == '1' {
        return false
    }
    minDis, maxDis := 0, 0 // 更新最后可达到的最小+最大坐标的范围
    for i := 0; i < n-1; i++ {
        if s[i] == '0' && minDis <= i && i <= maxDis {
            minDis = i + minJump
            maxDis = i + maxJump
        }
        if minDis <= n-1 && n-1 <= maxDis {
            return true
        }
    }
    return false
}

# 2
func canReach(s string, minJump int, maxJump int) bool {
    n := len(s)
    if s[n-1] == '1' {
        return false
    }
    dp := make([]bool, n) // dp[i] => 下标i是否可达
    dp[0] = true
    count := 1 // 滑动窗口里面可达数量
    for i := minJump; i < n; i++ {
        if s[i] == '0' && count > 0 { // 当前可达
            dp[i] = true
        }
        if maxJump <= i && dp[i-maxJump] == true { // 滑动窗口左端点:-1
            count--
        }
        if dp[i-minJump+1] == true { // 滑动窗口右端点:+1
            count++
        }
    }
    return dp[n-1]
}

# 3
func canReach(s string, minJump int, maxJump int) bool {
    n := len(s)
    if s[n-1] == '1' {
        return false
    }
    dp := make([]int, n) // dp[i] => 下标i是否可达
    dp[0] = 1
    arr := make([]int, n)
    for i := 0; i < minJump; i++ { // 前缀和从minJump开始
        arr[i] = 1
    }
    for i := minJump; i < n; i++ {
        left := i - maxJump
        right := i - minJump
        if s[i] == '0' {
            var total int
            if left <= 0 {
                total = arr[right]
            } else {
                total = arr[right] - arr[left-1]
            }
            if total > 0 { // 通过前缀和计算,范围内存在多少满足条件的坐标
                dp[i] = 1
            }
        }
        arr[i] = arr[i-1] + dp[i]
    }
    return dp[n-1] > 0
}

# 4
func canReach(s string, minJump int, maxJump int) bool {
    n := len(s)
    if s[n-1] == '1' {
        return false
    }
    arr := make([]int, n+1)
    arr[0] = 1
    arr[1] = -1
    sum := 0
    for i := 0; i < n; i++ {
        sum = sum + arr[i]
        if s[i] == '0' && sum > 0 {
            arr[min(i+minJump, n)]++
            arr[min(i+maxJump+1, n)]--
        }
    }
    return sum > 0 // 计算范围内可达到最后有几个坐标满足条件
}

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

1877.数组中最大数对和的最小值(1)

  • 题目
一个数对(a,b)的 数对和等于a + b。最大数对和是一个数对数组中最大的数对和。
比方说,如果我们有数对(1,5),(2,3)和(4,4),最大数对和为max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8。
给你一个长度为 偶数n的数组nums,请你将 nums中的元素分成 n / 2个数对,使得:
nums中每个元素恰好在 一个数对中,且
最大数对和的值 最小。
请你在最优数对划分的方案下,返回最小的 最大数对和。
示例 1:输入:nums = [3,5,2,3] 输出:7
解释:数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
示例 2:输入:nums = [3,5,4,2,4,6] 输出:8
解释:数组中的元素可以分为数对 (3,5),(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。
提示:n == nums.length
2 <= n <= 105
n是 偶数。
1 <= nums[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(1)
func minPairSum(nums []int) int {
    n := len(nums)
    sort.Ints(nums)
    res := 0
    for i := 0; i < n/2; i++ {
        res = max(res, nums[i]+nums[n-1-i])
    }
    return res
}

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

1878.矩阵中最大的三个菱形和(2)

  • 题目
给你一个m x n的整数矩阵grid。
菱形和 指的是 grid中一个正菱形 边界上的元素之和。
本题中的菱形必须为正方形旋转45度,且四个角都在一个格子当中。
下图是四个可行的菱形,每个菱形和应该包含的格子都用了相应颜色标注在图中。
注意,菱形可以是一个面积为 0 的区域,如上图中右下角的紫色菱形所示。
请你按照 降序返回 grid中三个最大的互不相同的菱形和。如果不同的和少于三个,则将它们全部返回。
示例 1:输入:grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]] 输出:[228,216,211]
解释:最大的三个菱形和如上图所示。
- 蓝色:20 + 3 + 200 + 5 = 228
- 红色:200 + 2 + 10 + 4 = 216
- 绿色:5 + 200 + 4 + 2 = 211
示例 2:输入:grid = [[1,2,3],[4,5,6],[7,8,9]] 输出:[20,9,8]
解释:最大的三个菱形和如上图所示。
- 蓝色:4 + 2 + 6 + 8 = 20
- 红色:9 (右下角红色的面积为 0 的菱形)
- 绿色:8 (下方中央面积为 0 的菱形)
示例 3:输入:grid = [[7,7,7]] 输出:[7]
解释:所有三个可能的菱形和都相同,所以返回 [7] 。
提示:m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^4) O(n^2)
02 遍历+前缀和 O(n^3) O(n^2)
func getBiggestThree(grid [][]int) []int {
    arr := make([]int, 0)
    n, m := len(grid), len(grid[0])
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            arr = append(arr, grid[i][j]) // 单独一个
            for k := 1; k < n; k++ {      // 枚举增加的长度
                left := i - k
                right := i + k
                button := j + 2*k
                mid := j + k
                if left < 0 || right > n-1 || button > m-1 {
                    break
                }
                sum := 0
                b := mid
                for a := left; a < i; a++ { // 左到上
                    sum = sum + grid[a][b]
                    b--
                }
                for a := i; a < right; a++ { // 上到右
                    sum = sum + grid[a][b]
                    b++
                }
                for a := right; a > i; a-- { // 右到下
                    sum = sum + grid[a][b]
                    b++
                }
                for a := i; a > left; a-- { // 下到左
                    sum = sum + grid[a][b]
                    b--
                }
                arr = append(arr, sum)
            }
        }
    }
    sort.Ints(arr)
    res := make([]int, 0)
    res = append(res, arr[len(arr)-1])
    for i := len(arr) - 2; i >= 0; i-- {
        if arr[i] != arr[i+1] && len(res) < 3 {
            res = append(res, arr[i])
        }
    }
    return res
}

# 2
func getBiggestThree(grid [][]int) []int {
    arr := make([]int, 0)
    n, m := len(grid), len(grid[0])
    sum1, sum2 := make([][]int, n+2), make([][]int, n+2)
    for i := 0; i <= n+1; i++ {
        sum1[i], sum2[i] = make([]int, m+2), make([]int, m+2)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            sum1[i][j] = sum1[i-1][j-1] + grid[i-1][j-1] // 下到右的斜线
            sum2[i][j] = sum2[i-1][j+1] + grid[i-1][j-1] // 下到左的斜线
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            arr = append(arr, grid[i][j])      // 单独一个
            for k := i + 2; k < n; k = k + 2 { // 上下长度
                aX, aY := i, j               // 上顶点
                bX, bY := k, j               // 下顶点
                cX, cY := (i+k)/2, j-(k-i)/2 // 左顶点
                dX, dY := (i+k)/2, j+(k-i)/2 // 右顶点
                if cY < 0 || dY >= m {
                    break
                }
                sum := (sum2[cX+1][cY+1] - sum2[aX+1-1][aY+1+1]) + // 左到上
                    (sum2[bX+1][bY+1] - sum2[dX+1-1][dY+1+1]) + // 下到右
                    (sum1[bX+1][bY+1] - sum1[cX+1-1][cY+1-1]) + // 下到左
                    (sum1[dX+1][dY+1] - sum1[aX+1-1][aY+1-1]) - // 右到上
                    (grid[aX][aY] + grid[bX][bY] + grid[cX][cY] + grid[dX][dY])
                arr = append(arr, sum)
            }
        }
    }
    sort.Ints(arr)
    res := make([]int, 0)
    res = append(res, arr[len(arr)-1])
    for i := len(arr) - 2; i >= 0; i-- {
        if arr[i] != arr[i+1] && len(res) < 3 {
            res = append(res, arr[i])
        }
    }
    return res
}

1881.插入后的最大值(1)

  • 题目
给你一个非常大的整数 n 和一个整数数字 x ,大整数 n用一个字符串表示。
n 中每一位数字和数字 x 都处于闭区间 [1, 9] 中,且 n 可能表示一个 负数 。
你打算通过在 n 的十进制表示的任意位置插入 x 来 最大化 n 的 数值。但 不能 在负号的左边插入 x 。
例如,如果 n = 73 且 x = 6 ,那么最佳方案是将 6 插入 7 和 3 之间,使 n = 763 。
如果 n = -55 且 x = 2 ,那么最佳方案是将 2 插在第一个 5 之前,使 n = -255 。
返回插入操作后,用字符串表示的n 的最大值。
示例 1:输入:n = "99", x = 9 输出:"999"
解释:不管在哪里插入 9 ,结果都是相同的。
示例 2:输入:n = "-13", x = 2 输出:"-123"
解释:向 n 中插入 x 可以得到 -213、-123 或者 -132 ,三者中最大的是 -123 。
提示:1 <= n.length <= 105
1 <= x <= 9
n中每一位的数字都在闭区间 [1, 9] 中。
n代表一个有效的整数。
当 n 表示负数时,将会以字符 '-' 开始。
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
func maxValue(n string, x int) string {
    if strings.Contains(n, "-") {
        for i := 1; i < len(n); i++ {
            if x < int(n[i]-'0') {
                return n[:i] + string(x+'0') + n[i:]
            }
        }
    } else {
        for i := 0; i < len(n); i++ {
            if x > int(n[i]-'0') {
                return n[:i] + string(x+'0') + n[i:]
            }
        }
    }
    return n + string(x+'0')
}

1882.使用服务器处理任务(1)

  • 题目
给你两个 下标从 0 开始 的整数数组 servers 和 tasks ,长度分别为 n和 m。
servers[i] 是第i台服务器的 权重 ,而 tasks[j] 是处理第j项任务 所需要的时间(单位:秒)。
你正在运行一个仿真系统,在处理完所有任务后,该系统将会关闭。每台服务器只能同时处理一项任务。
第 0 项任务在第 0 秒可以开始处理,相应地,第 j 项任务在第 j秒可以开始处理。
处理第 j 项任务时,你需要为它分配一台 权重最小 的空闲服务器。
如果存在多台相同权重的空闲服务器,请选择 下标最小 的服务器。
如果一台空闲服务器在第 t 秒分配到第 j 项任务,那么在 t + tasks[j] 时它将恢复空闲状态。
如果没有空闲服务器,则必须等待,直到出现一台空闲服务器,并 尽可能早地处理剩余任务。 
如果有多项任务等待分配,则按照 下标递增 的顺序完成分配。
如果同一时刻存在多台空闲服务器,可以同时将多项任务分别分配给它们。
构建长度为m 的答案数组 ans ,其中 ans[j] 是第 j 项任务分配的服务器的下标。
返回答案数组 ans。
示例 1:输入:servers = [3,3,2], tasks = [1,2,3,2,1,2] 输出:[2,2,0,2,1,2]
解释:事件按时间顺序如下:
- 0 秒时,第 0 项任务加入到任务队列,使用第 2 台服务器处理到 1 秒。
- 1 秒时,第 2 台服务器空闲,第 1 项任务加入到任务队列,使用第 2 台服务器处理到 3 秒。
- 2 秒时,第 2 项任务加入到任务队列,使用第 0 台服务器处理到 5 秒。
- 3 秒时,第 2 台服务器空闲,第 3 项任务加入到任务队列,使用第 2 台服务器处理到 5 秒。
- 4 秒时,第 4 项任务加入到任务队列,使用第 1 台服务器处理到 5 秒。
- 5 秒时,所有服务器都空闲,第 5 项任务加入到任务队列,使用第 2 台服务器处理到 7 秒。
示例 2:输入:servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1] 输出:[1,4,1,4,1,3,2]
解释:事件按时间顺序如下:
- 0 秒时,第 0 项任务加入到任务队列,使用第 1 台服务器处理到 2 秒。
- 1 秒时,第 1 项任务加入到任务队列,使用第 4 台服务器处理到 2 秒。
- 2 秒时,第 1 台和第 4 台服务器空闲,第 2 项任务加入到任务队列,使用第 1 台服务器处理到 4 秒。
- 3 秒时,第 3 项任务加入到任务队列,使用第 4 台服务器处理到 7 秒。
- 4 秒时,第 1 台服务器空闲,第 4 项任务加入到任务队列,使用第 1 台服务器处理到 9 秒。
- 5 秒时,第 5 项任务加入到任务队列,使用第 3 台服务器处理到 7 秒。
- 6 秒时,第 6 项任务加入到任务队列,使用第 2 台服务器处理到 7 秒。
提示:servers.length == n
tasks.length == m
1 <= n, m <= 2 * 105
1 <= servers[i], tasks[j] <= 2 * 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 双堆 O(nlog(n)) O(n)
func assignTasks(servers []int, tasks []int) []int {
    res := make([]int, 0)
    n := len(servers)
    waitHeap := make(WaitHeap, 0)
    heap.Init(&waitHeap)
    runHeap := make(RunHeap, 0)
    heap.Init(&runHeap)
    for i := 0; i < n; i++ {
        heap.Push(&waitHeap, Node{
            Id:   i,
            Rank: servers[i],
        })
    }
    curTime := 0
    for i := 0; i < len(tasks); i++ {
        curTime = max(curTime, i)
        if waitHeap.Len() == 0 { // 无服务器可用,时间移动
            endTime := runHeap[0].EndTime // 最小的结束时间的出来
            for runHeap.Len() > 0 && runHeap[0].EndTime == endTime {
                node := heap.Pop(&runHeap).(Node)
                heap.Push(&waitHeap, node)
            }
            curTime = max(curTime, endTime)
        } else {
            for runHeap.Len() > 0 && runHeap[0].EndTime <= curTime {
                node := heap.Pop(&runHeap).(Node)
                heap.Push(&waitHeap, node)
            }
        }
        node := heap.Pop(&waitHeap).(Node)
        res = append(res, node.Id)
        heap.Push(&runHeap, Node{
            Id:      node.Id,
            Rank:    node.Rank,
            EndTime: curTime + tasks[i],
        })
    }
    return res
}

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

type Node struct {
    Id      int
    Rank    int // 权重
    EndTime int
}

// 运行堆
type RunHeap []Node

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

// 小根堆<,大根堆变换方向>
func (h RunHeap) Less(i, j int) bool {
    return h[i].EndTime < h[j].EndTime // 按照时间排序
}

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

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

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

// 等待堆
type WaitHeap []Node

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

// 小根堆<,大根堆变换方向>
func (h WaitHeap) Less(i, j int) bool {
    if h[i].Rank == h[j].Rank {
        return h[i].Id < h[j].Id
    }
    return h[i].Rank < h[j].Rank
}

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

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

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

1884.鸡蛋掉落-两枚鸡蛋(2)

  • 题目
给你 2枚相同 的鸡蛋,和一栋从第 1层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ,满足0 <= f <= n ,任何从 高于 f 的楼层落下的鸡蛋都 会碎 ,
从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。
每次操作,你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下(满足1 <= x <= n)。
如果鸡蛋碎了,你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎,则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少?
示例 1:输入:n = 2 输出:2
解释:我们可以将第一枚鸡蛋从 1 楼扔下,然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了,可知 f = 0;
如果第二枚鸡蛋碎了,但第一枚没碎,可知 f = 1;
否则,当两个鸡蛋都没碎时,可知 f = 2。
示例 2:输入:n = 100 输出:14
解释:一种最优的策略是:
- 将第一枚鸡蛋从 9 楼扔下。如果碎了,那么 f 在 0 和 8 之间。
将第二枚从 1 楼扔下,然后每扔一次上一层楼,在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎,那么再把第一枚鸡蛋从 22 层扔下。如果碎了,那么 f 在 9 和 21 之间。
将第二枚鸡蛋从 10 楼扔下,然后每扔一次上一层楼,在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉,则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 
99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何,最多需要扔 14 次来确定 f 。
提示:1 <= n <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划-二维 O(n^2) O(n)
02 动态规划-一维 O(n^2) O(n)
func twoEggDrop(n int) int {
    dp := [3][]int{} // dp[i][j] 有i枚鸡蛋,验证j层楼需要的最少操作次数
    for i := 0; i < 3; i++ {
        dp[i] = make([]int, n+1)
        for j := 1; j < n+1; j++ {
            dp[i][j] = math.MaxInt32
            if i == 1 {
                dp[1][j] = j // 1个鸡蛋,需要j次
            }
        }
    }
    // 值为0
    // dp[1][0], dp[2][0] = 0,0
    for j := 1; j <= n; j++ {
        for k := 1; k <= j; k++ { //
            // a := k              //  假设在k层破碎:剩下1枚鸡蛋,求k-1层结果,(k-1)+1
            a := dp[1][k-1] + 1 //  假设在k层破碎。剩下1枚鸡蛋 求k-1层结果
            b := dp[2][j-k] + 1 //  假设在k层没有破碎:剩余2枚鸡蛋求j-k层结果
            dp[2][j] = min(dp[2][j], max(a, b))
        }
    }
    return dp[2][n]
}

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
}

# 2
func twoEggDrop(n int) int {
    dp := make([]int, n+1) // dp[j]验证j层楼需要的最少操作次数
    for j := 1; j < n+1; j++ {
        dp[j] = math.MaxInt32
    }
    // 值为0
    // dp[0] = 0
    for j := 1; j <= n; j++ {
        for k := 1; k <= j; k++ {
            a := k           //  假设在k层破碎:剩下1枚鸡蛋,求k-1层结果,(k-1)+1
            b := dp[j-k] + 1 //  假设在k层没有破碎:剩余2枚鸡蛋求j-k层结果
            dp[j] = min(dp[j], max(a, b))
        }
    }
    return dp[n]
}

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
}

1887.使数组元素相等的减少操作次数(2)

  • 题目
给你一个整数数组 nums ,你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤:
找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i (下标从 0 开始计数)。
如果有多个元素都是最大值,则取最小的 i 。
找出 nums 中的 下一个最大 值,这个值 严格小于 largest ,记为 nextLargest 。
将 nums[i] 减少到 nextLargest 。
返回使 nums 中的所有元素相等的操作次数。
示例 1:输入:nums = [5,1,3] 输出:3
解释:需要 3 次操作使 nums 中的所有元素相等:
1. largest = 5 下标为 0 。nextLargest = 3 。将 nums[0] 减少到 3 。nums = [3,1,3] 。
2. largest = 3 下标为 0 。nextLargest = 1 。将 nums[0] 减少到 1 。nums = [1,1,3] 。
3. largest = 3 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1] 。
示例 2:输入:nums = [1,1,1] 输出:0
解释:nums 中的所有元素已经是相等的。
示例 3:输入:nums = [1,1,2,2,3] 输出:4
解释:需要 4 次操作使 nums 中的所有元素相等:
1. largest = 3 下标为 4 。nextLargest = 2 。将 nums[4] 减少到 2 。nums = [1,1,2,2,2] 。
2. largest = 2 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1,2,2] 。 
3. largest = 2 下标为 3 。nextLargest = 1 。将 nums[3] 减少到 1 。nums = [1,1,1,1,2] 。 
4. largest = 2 下标为 4 。nextLargest = 1 。将 nums[4] 减少到 1 。nums = [1,1,1,1,1] 。
提示:1 <= nums.length <= 5 * 104
1 <= nums[i] <= 5 * 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(1)
02 排序遍历 O(nlog(n)) O(1)
func reductionOperations(nums []int) int {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] > nums[j]
    })
    res := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            res = res + i
        }
    }
    return res
}

# 2

func reductionOperations(nums []int) int {
    sort.Ints(nums)
    res := 0
    count := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            count++
        }
        res = res + count
    }
    return res
}

1888.使二进制字符串字符交替的最少反转次数

题目



解题思路

No. 思路 时间复杂度 空间复杂度
01 模拟 O(n) O(1)


1894.找到需要补充粉笔的学生编号(1)

  • 题目
一个班级里有n个学生,编号为 0到 n - 1。每个学生会依次回答问题,编号为 0的学生先回答,然后是编号为 1的学生,
以此类推,直到编号为 n - 1的学生,然后老师会重复这个过程,重新从编号为 0的学生开始回答问题。
给你一个长度为 n且下标从 0开始的整数数组chalk和一个整数k。一开始粉笔盒里总共有k支粉笔。
当编号为i的学生回答问题时,他会消耗 chalk[i]支粉笔。如果剩余粉笔数量 严格小于chalk[i],那么学生 i需要 补充粉笔。
请你返回需要 补充粉笔的学生 编号。
示例 1:输入:chalk = [5,1,5], k = 22
输出:0
解释:学生消耗粉笔情况如下:
- 编号为 0 的学生使用 5 支粉笔,然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔,然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔,然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔,然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔,然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔,然后 k = 0 。
编号为 0 的学生没有足够的粉笔,所以他需要补充粉笔。
示例 2:输入:chalk = [3,4,1,2], k = 25 输出:1
解释:学生消耗粉笔情况如下:
- 编号为 0 的学生使用 3 支粉笔,然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔,然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔,然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔,然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔,然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔,然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔,然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔,然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔,然后 k = 2 。
编号为 1 的学生没有足够的粉笔,所以他需要补充粉笔。
提示:chalk.length == n
1 <= n <= 105
1 <= chalk[i] <= 105
1 <= k <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 模拟 O(n) O(1)
func chalkReplacer(chalk []int, k int) int {
    res := 0
    n := len(chalk)
    sum := 0
    for i := 0; i < n; i++ {
        sum = sum + chalk[i]
    }
    k = k % sum // 求余
    for i := 0; i < n; i++ {
        if k < chalk[i] {
            return i
        }
        k = k - chalk[i]
    }
    return res
}

1895.最大的幻方(2)

  • 题目
一个k x k的幻方指的是一个k x k填满整数的方格阵,且每一行、每一列以及两条对角线的和 全部相等。
幻方中的整数 不需要互不相同。显然,每个1 x 1的方格都是一个幻方。
给你一个m x n的整数矩阵grid,请你返回矩阵中最大幻方的尺寸(即边长 k)。
示例 1:输入:grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]] 输出:3
解释:最大幻方尺寸为 3 。
每一行,每一列以及两条对角线的和都等于 12 。
- 每一行的和:5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和:5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和:5+4+3 = 6+4+2 = 12
示例 2:输入:grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]] 输出:2
提示:m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 106
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 枚举+前缀和 O(n^4) O(n^2)
02 枚举+前缀和 O(n^4) O(n^2)
func largestMagicSquare(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    rowArr := make([][]int, n) // 行前缀和
    colArr := make([][]int, n) // 列前缀和
    for i := 0; i < n; i++ {
        rowArr[i] = make([]int, m)
        colArr[i] = make([]int, m)
    }
    for i := 0; i < n; i++ {
        rowArr[i][0] = grid[i][0]
        for j := 1; j < m; j++ {
            rowArr[i][j] = rowArr[i][j-1] + grid[i][j]
        }
    }
    for j := 0; j < m; j++ {
        colArr[0][j] = grid[0][j]
        for i := 1; i < n; i++ {
            colArr[i][j] = colArr[i-1][j] + grid[i][j]
        }
    }
    for length := min(n, m); length >= 2; length-- { // 枚举边长
        for i := 0; i+length <= n; i++ {
            for j := 0; j+length <= m; j++ {
                var target int // 以行目标和
                if j == 0 {
                    target = rowArr[i][j+length-1]
                } else {
                    target = rowArr[i][j+length-1] - rowArr[i][j-1]
                }
                flag := true
                for k := i + 1; k < i+length; k++ { // 继续检查行
                    var temp int
                    if j == 0 {
                        temp = rowArr[k][j+length-1]
                    } else {
                        temp = rowArr[k][j+length-1] - rowArr[k][j-1]
                    }
                    if temp != target {
                        flag = false
                        break
                    }
                }
                if flag == false {
                    continue
                }
                for k := j; k < j+length; k++ { // 检查列
                    var temp int
                    if i == 0 {
                        temp = colArr[i+length-1][k]
                    } else {
                        temp = colArr[i+length-1][k] - colArr[i-1][k]
                    }
                    if temp != target {
                        flag = false
                        break
                    }
                }
                if flag == false {
                    continue
                }
                var left, right int // 左右对角线
                for k := 0; k < length; k++ {
                    left = left + grid[i+k][j+k]
                    right = right + grid[i+k][j+length-1-k]
                }
                if target == left && target == right {
                    return length
                }
            }
        }
    }
    return 1
}

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

# 2
func largestMagicSquare(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    rowArr := make([][]int, n+1)   // 行前缀和
    colArr := make([][]int, n+1)   // 列前缀和
    leftArr := make([][]int, n+1)  // 对角线
    rightArr := make([][]int, n+1) // 对角线
    for i := 0; i <= n; i++ {
        rowArr[i] = make([]int, m+1)
        colArr[i] = make([]int, m+1)
        leftArr[i] = make([]int, m+1)
        rightArr[i] = make([]int, m+1)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            rowArr[i][j+1] = rowArr[i][j] + grid[i][j]
            colArr[i+1][j] = colArr[i][j] + grid[i][j]
            leftArr[i+1][j+1] = leftArr[i][j] + grid[i][j]
            rightArr[i+1][j] = rightArr[i][j+1] + grid[i][j]
        }
    }
    for length := min(n, m); length >= 2; length-- { // 枚举边长
        for i := 0; i+length <= n; i++ {
            for j := 0; j+length <= m; j++ {
                target := leftArr[i+length][j+length] - leftArr[i][j]
                if rightArr[i+length][j]-rightArr[i][j+length] != target {
                    continue
                }
                flag := true
                for k := i; k < i+length; k++ { // 检查行
                    temp := rowArr[k][j+length] - rowArr[k][j]
                    if temp != target {
                        flag = false
                        break
                    }
                }
                if flag == false {
                    continue
                }
                for k := j; k < j+length; k++ { // 检查列
                    temp := colArr[i+length][k] - colArr[i][k]
                    if temp != target {
                        flag = false
                        break
                    }
                }
                if flag == true {
                    return length
                }
            }
        }
    }
    return 1
}

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

1898.可移除字符的最大数目(3)

  • 题目
给你两个字符串 s 和 p ,其中 p 是 s 的一个 子序列 。
同时,给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组removable ,
该数组是 s 中下标的一个子集(s 的下标也 从 0 开始 计数)。
请你找出一个整数 k(0 <= k <= removable.length),选出removable 中的 前 k 个下标,
然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足:在执行完上述步骤后, p 仍然是 s 的一个 子序列 。
更正式的解释是,对于每个 0 <= i < k ,先标记出位于 s[removable[i]] 的字符,
接着移除所有标记过的字符,然后检查 p 是否仍然是 s 的一个子序列。
返回你可以找出的 最大 k ,满足在移除字符后 p 仍然是 s 的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串,
生成过程中可能会移除原字符串中的一些字符(也可能不移除)但不改变剩余字符之间的相对顺序。
示例 1:输入:s = "abcacb", p = "ab", removable = [3,1,0] 输出:2
解释:在移除下标 3 和 1 对应的字符后,"abcacb" 变成 "accb" 。
"ab" 是 "accb" 的一个子序列。
如果移除下标 3、1 和 0 对应的字符后,"abcacb" 变成 "ccb" ,那么 "ab" 就不再是 s 的一个子序列。
因此,最大的 k 是 2 。
示例 2:输入:s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6] 输出:1
解释:在移除下标 3 对应的字符后,"abcbddddd" 变成 "abcddddd" 。
"abcd" 是 "abcddddd" 的一个子序列。
示例 3:输入:s = "abcab", p = "abc", removable = [0,1,2,3,4] 输出:0
解释:如果移除数组 removable 的第一个下标,"abc" 就不再是 s 的一个子序列。
提示:1 <= p.length <= s.length <= 105
0 <= removable.length < s.length
0 <= removable[i] < s.length
p 是 s 的一个 子字符串
s 和 p 都由小写英文字母组成
removable 中的元素 互不相同
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 二分查找 O(nlog(n)) O(n)
02 二分查找 O(nlog(n)) O(n)
03 内置函数 O(nlog(n)) O(n)
func maximumRemovals(s string, p string, removable []int) int {
    n := len(removable)
    left, right := 0, n
    for left < right {
        mid := left + (right-left)/2
        if judge(s, p, removable, mid) == true {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

// leetcode 392.判断子序列
func judge(s string, p string, removable []int, index int) bool {
    m := make(map[int]bool)
    for i := 0; i < len(removable[:index+1]); i++ {
        m[removable[i]] = true
    }
    i, j := 0, 0
    for i < len(p) && j < len(s) {
        if p[i] == s[j] && m[j] == false {
            i++
        }
        j++
    }
    return i == len(p)
}

# 2
func maximumRemovals(s string, p string, removable []int) int {
    n := len(removable)
    left, right := 0, n+1
    for left < right {
        mid := left + (right-left)/2
        if judge(s, p, removable, mid) == true {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left - 1
}

// leetcode 392.判断子序列
func judge(s string, p string, removable []int, index int) bool {
    m := make(map[int]bool)
    for i := 0; i < len(removable[:index]); i++ {
        m[removable[i]] = true
    }
    i, j := 0, 0
    for i < len(p) && j < len(s) {
        if p[i] == s[j] && m[j] == false {
            i++
        }
        j++
    }
    return i == len(p)
}

# 3
func maximumRemovals(s string, p string, removable []int) int {
    n := len(removable)
    return sort.Search(n, func(index int) bool {
        m := make(map[int]bool)
        for i := 0; i < len(removable[:index+1]); i++ {
            m[removable[i]] = true
        }
        i, j := 0, 0
        for i < len(p) && j < len(s) {
            if p[i] == s[j] && m[j] == false {
                i++
            }
            j++
        }
        return i != len(p)
    })
}

1899.合并若干三元组以形成目标三元组(2)

  • 题目
三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ,其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。
同时,给你一个整数数组 target = [x, y, z] ,表示你想要得到的 三元组 。
为了得到 target ,你需要对 triplets 执行下面的操作 任意次(可能 零 次):
选出两个下标(下标 从 0 开始 计数)i 和 j(i != j),
并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
例如,triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5],
triplets[j] 将会更新为 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5] 。
如果通过以上操作我们可以使得目标 三元组target成为triplets 的一个 元素,则返回 true ;否则,返回 false 。
示例 1:输入:triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] 输出:true
解释:执行下述操作:
- 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。
更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]]
目标三元组 [2,7,5] 现在是 triplets 的一个元素。
示例 2:输入:triplets = [[1,3,4],[2,5,8]], target = [2,5,8] 输出:true
解释:目标三元组 [2,5,8] 已经是 triplets 的一个元素。
示例 3:输入:triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5] 输出:true
解释:执行下述操作:
- 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。
更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。
triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
- 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。
triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。
目标三元组 [5,5,5] 现在是 triplets 的一个元素。
示例 4:输入:triplets = [[3,4,5],[4,5,6]], target = [3,2,5] 输出:false
解释:无法得到 [3,2,5] ,因为 triplets 不含 2 。
提示:1 <= triplets.length <= 105
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
func mergeTriplets(triplets [][]int, target []int) bool {
    x, y, z := target[0], target[1], target[2]
    a, b, c := 0, 0, 0
    for i := 0; i < len(triplets); i++ {
        a1, b1, c1 := triplets[i][0], triplets[i][1], triplets[i][2]
        if a1 <= x && b1 <= y && c1 <= z {
            a = max(a, a1)
            b = max(b, b1)
            c = max(c, c1)
        }
    }
    return a == x && b == y && c == z
}

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

# 2
func mergeTriplets(triplets [][]int, target []int) bool {
    x, y, z := target[0], target[1], target[2]
    a, b, c := false, false, false
    for i := 0; i < len(triplets); i++ {
        a1, b1, c1 := triplets[i][0], triplets[i][1], triplets[i][2]
        if a1 <= x && b1 <= y && c1 <= z {
            if a1 == x {
                a = true
            }
            if b1 == y {
                b = true
            }
            if c1 == z {
                c = true
            }
        }
    }
    return a == true && b == true && c == true
}

1801-1900-Hard

1803.统计异或值在范围内的数对有多少(1)

  • 题目
给你一个整数数组 nums (下标 从 0 开始 计数)以及两个整数:low 和 high ,请返回 漂亮数对 的数目。
漂亮数对 是一个形如 (i, j) 的数对,其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。
示例 1:输入:nums = [1,4,2,7], low = 2, high = 6 输出:6
解释:所有漂亮数对 (i, j) 列出如下:
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5
示例 2:输入:nums = [9,8,4,2,1], low = 5, high = 14 输出:8
解释:所有漂亮数对 (i, j) 列出如下:
    - (0, 2): nums[0] XOR nums[2] = 13
   - (0, 3): nums[0] XOR nums[3] = 11
   - (0, 4): nums[0] XOR nums[4] = 8
   - (1, 2): nums[1] XOR nums[2] = 12
   - (1, 3): nums[1] XOR nums[3] = 10
   - (1, 4): nums[1] XOR nums[4] = 9
   - (2, 3): nums[2] XOR nums[3] = 6
   - (2, 4): nums[2] XOR nums[4] = 5
提示:1 <= nums.length <= 2 * 104
1 <= nums[i] <= 2 * 104
1 <= low <= high <= 2 * 104
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 trie树 O(n) O(n)
 func countPairs(nums []int, low int, high int) int {
     res := 0
     n := len(nums)
     root := &Trie{next: make([]*Trie, 2)}
     for i := 0; i < n; i++ {
         // 先查询,再插入
         res = res + root.Search(nums[i], high+1) - root.Search(nums[i], low)
         root.Insert(nums[i])
     }
     return res
 }

 type Trie struct {
     next []*Trie // 0或者1
     size int     // 次数
 }

 // 插入num
 func (t *Trie) Insert(num int) {
     temp := t
     for i := 31; i >= 0; i-- {
         value := (num >> i) & 1
         if temp.next[value] == nil {
             temp.next[value] = &Trie{
                 next: make([]*Trie, 2),
             }
         }
         temp = temp.next[value]
         temp.size++
     }
 }

 // 查找小于target的数量
 func (t *Trie) Search(num int, target int) int {
     res := 0
     temp := t
     for i := 31; i >= 0; i-- {
         if temp == nil { // 直接返回
             return res
         }
         value := (num >> i) & 1
         targetValue := (target >> i) & 1
         if targetValue > 0 { // target该位为1
             if temp.next[value] != nil {
                 res = res + temp.next[value].size
             }
             temp = temp.next[1-value] // value ^ (1-value) = 1 => 往1-value走
         } else {
             temp = temp.next[value] // value ^ value = 0 // 往value走
         }
     }
     return res
 }

1808.好因子的最大数目(1)

  • 题目
给你一个正整数primeFactors。你需要构造一个正整数n,它满足以下条件:
n质因数(质因数需要考虑重复的情况)的数目 不超过primeFactors个。
n好因子的数目最大化。如果 n的一个因子可以被 n的每一个质因数整除,我们称这个因子是 好因子 。
比方说,如果n = 12,那么它的质因数为[2,2,3],那么6和12是好因子,但3 和4不是。
请你返回n的好因子的数目。由于答案可能会很大,请返回答案对109 + 7取余的结果。
请注意,一个质数的定义是大于 1,且不能被分解为两个小于该数的自然数相乘。
一个数 n的质因子是将 n分解为若干个质因子,且它们的乘积为 n。
示例 1:输入:primeFactors = 5 输出:6
解释:200 是一个可行的 n 。
它有 5 个质因子:[2,2,2,5,5] ,且有 6 个好因子:[10,20,40,50,100,200] 。
不存在别的 n 有至多 5 个质因子,且同时有更多的好因子。
示例 2:输入:primeFactors = 8 输出:18
提示:1 <= primeFactors <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 快速幂 O(log(n)) O(1)
/*
由题意有: n=a1^k1 * a2^k2 *...*an^kn(如12=2^2 * 3^1)
其中
1、a1,a2,...,an是不同的质数(2,3不重复)
2、k1+k2+...+kn <=primeFactors
3、n的好因子,要能被每一个质因数(a1,a2,a3,...,an)整除,即好因子必须含有a1*a2*...*an作为因数
=>好因子的个数 k = k1*k2*...*kn =>求k最大,其中k1+..kn=primeFactors
等价于343题,整数拆分
*/

var mod = 1000000007

func maxNiceDivisors(primeFactors int) int {
    n := primeFactors
    if n <= 3 {
        return n
    }
    if n%3 == 0 {
        return pow(3, n/3) % mod
    } else if n%3 == 1 {
        return pow(3, (n-4)/3) * 4 % mod
    }
    return pow(3, n/3) * 2 % mod
}

func pow(a, b int) int {
    res := 1
    for b > 0 {
        if b%2 == 1 {
            res = res * a % mod
        }
        a = a * a % mod
        b = b / 2
    }
    return res
}

1835.所有数对按位与结果的异或和(2)

  • 题目
列表的 异或和(XOR sum)指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素,那么其 异或和 就等于该元素。
例如,[1,2,3,4] 的 异或和 等于 1 XOR 2 XOR 3 XOR 4 = 4 ,而 [3] 的 异或和 等于 3 。
给你两个下标 从 0 开始 计数的数组 arr1 和 arr2 ,两数组均由非负整数组成。
根据每个(i, j) 数对,构造一个由 arr1[i] AND arr2[j](按位 AND 运算)结果组成的列表。
其中 0 <= i < arr1.length 且 0 <= j < arr2.length 。
返回上述列表的 异或和 。
示例 1:输入:arr1 = [1,2,3], arr2 = [6,5] 输出:0
解释:列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ,
异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。
示例 2:输入:arr1 = [12], arr2 = [4] 输出:4
解释:列表 = [12 AND 4] = [4] ,异或和 = 4 。
提示:1 <= arr1.length, arr2.length <= 105
0 <= arr1[i], arr2[j] <= 109
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 位运算 O(n) O(1)
02 位运算 O(n) O(1)
func getXORSum(arr1 []int, arr2 []int) int {
    res := 0
    n, m := len(arr1), len(arr2)
    for i := 31; i >= 0; i-- {
        a, b := 0, 0
        for j := 0; j < n; j++ {
            if (arr1[j] & (1 << i)) > 0 {
                a++
            }
        }
        for j := 0; j < m; j++ {
            if (arr2[j] & (1 << i)) > 0 {
                b++
            }
        }
        if a%2 == 1 && b%2 == 1 { // 在该位1的次数都为奇数:奇数x奇数=奇数
            res = res | (1 << i)
        }
    }
    return res
}

# 2
func getXORSum(arr1 []int, arr2 []int) int {
    a, b := 0, 0
    for i := 0; i < len(arr1); i++ {
        a = a ^ arr1[i]
    }
    for i := 0; i < len(arr2); i++ {
        b = b ^ arr2[i]
    }
    return a & b // 位与操作:相同位数都是1,则该结果返回1
}

1857.有向图中最大颜色值(1)

  • 题目
给你一个有向图,它含有n个节点和 m条边。节点编号从0 到n - 1。
给你一个字符串colors ,其中colors[i]是小写英文字母,表示图中第 i个节点的 颜色(下标从 0开始)。
同时给你一个二维数组edges,其中edges[j] = [aj, bj]表示从节点aj到节点bj有一条有向边。
图中一条有效 路径是一个点序列x1 -> x2 -> x3 -> ... -> xk,对于所有1 <= i < k,从xi 到xi+1在图中有一条有向边。
路径的 颜色值是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的最大颜色值。如果图中含有环,请返回 -1。
示例 1:输入:colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]] 输出:3
解释:路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点(上图中的红色节点)。
示例 2:输入:colors = "a", edges = [[0,0]] 输出:-1
解释:从 0 到 0 有一个环。
提示:n == colors.length
m == edges.length
1 <= n <= 105
0 <= m <= 105
colors只含有小写英文字母。
0 <= aj, bj< n
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 拓扑排序+动态规划 O(n) O(n)
func largestPathValue(colors string, edges [][]int) int {
    n := len(colors)
    arr := make([][]int, n)  // 邻接表
    degree := 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)
        degree[b]++
    }
    queue := make([]int, 0)
    for i := 0; i < n; i++ {
        if degree[i] == 0 { // 入度为0
            queue = append(queue, i)
        }
    }
    dp := make([][26]int, n) // dp[i][j] => 到节点i颜色j出现的次数
    count := 0
    for len(queue) > 0 {
        count++ // 节点+1
        node := queue[0]
        queue = queue[1:]
        dp[node][int(colors[node]-'a')]++ // 该节点颜色+1
        for i := 0; i < len(arr[node]); i++ {
            next := arr[node][i]
            degree[next]--
            if degree[next] == 0 {
                queue = append(queue, next)
            }
            // 更新次数
            for j := 0; j < 26; j++ {
                dp[next][j] = max(dp[next][j], dp[node][j])
            }
        }
    }
    if count != n { // 判断环
        return -1
    }
    res := 0
    for i := 0; i < n; i++ {
        for j := 0; j < 26; j++ {
            res = max(res, dp[i][j])
        }
    }
    return res
}

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

1862.向下取整数对和(1)

  • 题目
给你一个整数数组nums,请你返回所有下标对0 <= i, j < nums.length的floor(nums[i] / nums[j])结果之和。
由于答案可能会很大,请你返回答案对109 + 7取余的结果。
函数floor()返回输入数字的整数部分。
示例 1:输入:nums = [2,5,9] 输出:10
解释:floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我们计算每一个数对商向下取整的结果并求和得到 10 。
示例 2:输入:nums = [7,7,7,7,7,7,7] 输出:49
提示:1 <= nums.length <= 105
1 <= nums[i] <= 105
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 枚举 O(n^3/2) O(n)
func sumOfFlooredPairs(nums []int) int {
    n := len(nums)
    count := make([]int, 200001)
    for i := 0; i < n; i++ {
        count[nums[i]]++
    }
    arr := make([]int, 200001+1) // 前缀和
    for i := 0; i < len(count); i++ {
        arr[i+1] = arr[i] + count[i]
    }
    res := 0
    // a/b = c
    for i := 0; i < len(count); i++ { // 枚举b
        if count[i] > 0 { // i个数大于0
            for j := 1; i*j <= 100000; j++ { // 枚举c
                // b的个数 X c X 目标范围内的数字个数
                total := count[i] * j * (arr[i*(j+1)] - arr[i*j])
                res = (res + total) % 1000000007
            }
        }
    }
    return res
}

1866.恰有K根木棍可以看到的排列数目(1)

  • 题目
有 n 根长度互不相同的木棍,长度为从 1 到 n 的整数。
请你将这些木棍排成一排,并满足从左侧 可以看到恰好 k 根木棍。
从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。
例如,如果木棍排列为 [1,3,2,5,4] ,那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。
给你 n 和 k ,返回符合题目要求的排列 数目 。由于答案可能很大,请返回对 109 + 7 取余 的结果。
示例 1:输入:n = 3, k = 2 输出:3
解释:[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。
示例 2:输入:n = 5, k = 5 输出:1
解释:[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
可以看到的木棍已经用粗体+斜体标识。
示例 3:输入:n = 20, k = 11 输出:647427950
解释:总共有 647427950 (mod 109 + 7) 种能满足恰好有 11 根木棍可以看到的排列。
提示:1 <= n <= 1000
1 <= k <= n
  • 解题思路
No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
func rearrangeSticks(n int, k int) int {
    dp := make([][]int, n+1) // dp[i][j]代表i根棍子能看到j根;假设每次插入1,假设上一轮的数为:2到n
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, k+1)
    }
    dp[0][0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= k; j++ {
            a := dp[i-1][j-1]                        // i-1根棍子里面已经看到了j-1根,插入到最前面
            b := ((i - 1) * dp[i-1][j]) % 1000000007 // i-1根棍子里面已经看到了j根,插入到除最前面的其它i-1个地方都行
            dp[i][j] = (a + b) % 1000000007
        }
    }
    return dp[n][k]
}

1872.石子游戏VIII

题目

Alice 和 Bob 玩一个游戏,两人轮流操作, Alice 先手。
总共有n个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1,他将执行以下操作:
选择一个整数x > 1,并且 移除最左边的x个石子。
将移除的石子价值之 和累加到该玩家的分数中。
将一个 新的石子放在最左边,且新石子的值为被移除石子值之和。
当只剩下 一个石子时,游戏结束。
Alice 和 Bob 的 分数之差为(Alice 的分数- Bob 的分数)。
Alice 的目标是最大化分数差,Bob 的目标是 最小化分数差。
给你一个长度为 n的整数数组stones,其中stones[i]是 从左边起第i个石子的价值。
请你返回在双方都采用 最优 策略的情况下,Alice 和 Bob 的 分数之差 。
示例 1:输入:stones = [-1,2,-3,4,-5] 输出:5
解释:- Alice 移除最左边的 4 个石子,得分增加 (-1) + 2 + (-3) + 4 = 2 ,并且将一个价值为 2 的石子放在最左边。
stones = [2,-5] 。
- Bob 移除最左边的 2 个石子,得分增加 2 + (-5) = -3 ,并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。
示例 2:输入:stones = [7,-6,5,10,5,-2,-6] 输出:13
解释:- Alice 移除所有石子,得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ,
并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。
示例 3:输入:stones = [-10,-12] 输出:-22
解释:- Alice 只有一种操作,就是移除所有石子。得分增加 (-10) + (-12) = -22 ,并且将一个价值为 -22 的石子放在最左边。
stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。
提示:n == stones.length
2 <= n <= 105
-104 <= stones[i] <= 104

解题思路

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

## 1889.装包裹的最小浪费空间(3)

- 题目

给你n个包裹,你需要把它们装在箱子里,每个箱子装一个包裹。 总共有m个供应商提供 不同尺寸的箱子(每个规格都有无数个箱子)。 如果一个包裹的尺寸 小于等于一个箱子的尺寸,那么这个包裹就可以放入这个箱子之中。 包裹的尺寸用一个整数数组packages表示,其中packages[i]是第i个包裹的尺寸。 供应商用二维数组boxes表示,其中boxes[j]是第 j个供应商提供的所有箱子尺寸的数组。 你想要选择 一个供应商并只使用该供应商提供的箱子,使得 总浪费空间最小。 对于每个装了包裹的箱子,我们定义 浪费的空间等于 箱子的尺寸 - 包裹的尺寸。总浪费空间为所有箱子中浪费空间的总和。 比方说,如果你想要用尺寸数组为[4,8]的箱子装下尺寸为[2,3,5]的包裹, 你可以将尺寸为 2和 3的两个包裹装入两个尺寸为 4的箱子中,同时把尺寸为 5的包裹装入尺寸为 8的箱子中。 总浪费空间为(4-2) + (4-3) + (8-5) = 6。 请你选择 最优箱子供应商,使得 总浪费空间最小。如果 无法 将所有包裹放入箱子中,请你返回 -1。 由于答案可能会 很大,请返回它对109 + 7取余的结果。 示例 1:输入:packages = [2,3,5], boxes = [[4,8],[2,8]] 输出:6 解释:选择第一个供应商最优,用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。 总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。 示例 2:输入:packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]] 输出:-1 解释:没有箱子能装下尺寸为 5 的包裹。 示例 3:输入:packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]] 输出:9 解释:选择第三个供应商最优,用两个尺寸为 5 的箱子,两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。 总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。 提示:n == packages.length m == boxes.length 1 <= n <= 105 1 <= m <= 105 1 <= packages[i] <= 105 1 <= boxes[j].length <= 105 1 <= boxes[j][k] <= 105 sum(boxes[j].length) <= 105 boxes[j]中的元素 互不相同。


- 解题思路

| No.  | 思路                   | 时间复杂度 | 空间复杂度 |
| :----- | :----------------------- | :----------- | :----------- |
| 01   | 排序+二分查找          | O(nlog(n)) | O(1)       |
| 02   | 排序+二分查找+内置函数 | O(nlog(n)) | O(1)       |
| 03   | 排序+前缀和+二分查找   | O(nlog(n)) | O(n)       |

```go
var mod = 1000000007

func minWastedSpace(packages []int, boxes [][]int) int {
    sort.Ints(packages)
    n := len(packages)
    res := math.MaxInt64
    for i := 0; i < len(boxes); i++ {
        temp := boxes[i]
        sort.Ints(temp)
        if temp[len(temp)-1] < packages[n-1] { // 最大箱子无法装最大包裹
            continue
        }
        sum := 0
        left := 0
        for j := 0; j < len(temp); j++ { // 枚举箱子
            right := binarySearch(packages, temp[j]) // 选择当前箱子能装下的位置
            sum = sum + (right-left)*temp[j]         // 累加:个数*箱子大小
            left = right
        }
        res = min(res, sum)
    }
    if res == math.MaxInt64 {
        return -1
    }
    for i := 0; i < n; i++ {
        res = res - packages[i]
    }
    return res % mod
}

// 找到第一个大于target的位置
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] <= target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

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

# 2
var mod = 1000000007

func minWastedSpace(packages []int, boxes [][]int) int {
    sort.Ints(packages)
    n := len(packages)
    res := math.MaxInt64
    for i := 0; i < len(boxes); i++ {
        temp := boxes[i]
        sort.Ints(temp)
        if temp[len(temp)-1] < packages[n-1] { // 最大箱子无法装最大包裹
            continue
        }
        sum := 0
        left := 0
        for j := 0; j < len(temp); j++ { // 枚举箱子
            // 找到第一个大于target的位置
            right := sort.SearchInts(packages, temp[j]+1) // 选择当前箱子能装下的位置
            sum = sum + (right-left)*temp[j]              // 累加:个数*箱子大小
            left = right
        }
        res = min(res, sum)
    }
    if res == math.MaxInt64 {
        return -1
    }
    for i := 0; i < n; i++ {
        res = res - packages[i]
    }
    return res % mod
}

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

# 3
var mod = 1000000007

func minWastedSpace(packages []int, boxes [][]int) int {
    sort.Ints(packages)
    n := len(packages)
    arr := make([]int, n+1)
    for i := 1; i <= n; i++ {
        arr[i] = arr[i-1] + packages[i-1]
    }
    res := math.MaxInt64
    for i := 0; i < len(boxes); i++ {
        temp := boxes[i]
        sort.Ints(temp)
        if temp[len(temp)-1] < packages[n-1] { // 最大箱子无法装最大包裹
            continue
        }
        sum := 0
        left := 0
        for j := 0; j < len(temp); j++ { // 枚举箱子
            right := binarySearch(packages, temp[j], left) // 选择当前箱子能装下的位置
            sum = sum + (right-left)*temp[j] - (arr[right] - arr[left])
            left = right
        }
        res = min(res, sum)
    }
    if res == math.MaxInt64 {
        return -1
    }
    return res % mod
}

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

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
Copyright © Zhi2014 2023 all right reserved,powered by Gitbook该文件修订时间: 2023-10-23 15:20:51

results matching ""

    No results matching ""