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 {
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 {
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
}
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 {
left = b + 1
}
if b >= right {
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 {
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 {
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
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) {
sentence1, sentence2 = sentence2, sentence1
}
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)
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)
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 {
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++ {
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 {
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++ {
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[k], arr[k+1] = arr[k+1], arr[k]
res++
}
break
}
}
}
}
return res
}
func nextPermutation(nums []byte) {
n := len(nums)
left := n - 2
for left >= 0 && nums[left] >= nums[left+1] {
left--
}
if left >= 0 {
right := n - 1
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)
right := make([]int, n)
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)
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)
} 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
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 {
count := 0
for i := 0; i < n; i++ {
if int(s[i]-'0') == i%2 {
count++
}
}
res = min(res, count/2)
}
if b == (n+1)/2 && a == n/2 {
count := 0
for i := 0; i < n; i++ {
if int(s[i]-'0') != i%2 {
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[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 {
count--
}
if dp[i-minJump+1] == true {
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[0] = 1
arr := make([]int, n)
for i := 0; i < minJump; i++ {
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{}
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
}
}
}
for j := 1; j <= n; j++ {
for k := 1; k <= j; k++ {
a := dp[1][k-1] + 1
b := dp[2][j-k] + 1
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)
for j := 1; j < n+1; j++ {
dp[j] = math.MaxInt32
}
for j := 1; j <= n; j++ {
for k := 1; k <= j; k++ {
a := k
b := dp[j-k] + 1
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
}
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
}
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
size int
}
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++
}
}
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 {
if temp.next[value] != nil {
res = res + temp.next[value].size
}
temp = temp.next[1-value]
} else {
temp = temp.next[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) |
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 {
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
}
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]
arr[a] = append(arr[a], b)
degree[b]++
}
queue := make([]int, 0)
for i := 0; i < n; i++ {
if degree[i] == 0 {
queue = append(queue, i)
}
}
dp := make([][26]int, n)
count := 0
for len(queue) > 0 {
count++
node := queue[0]
queue = queue[1:]
dp[node][int(colors[node]-'a')]++
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
for i := 0; i < len(count); i++ {
if count[i] > 0 {
for j := 1; i*j <= 100000; j++ {
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)
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]
b := ((i - 1) * dp[i-1][j]) % 1000000007
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
}