1601-1700-Easy
1603.设计停车系统(2)
请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类：
ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，
三个参数分别对应每种停车位的数目。
bool addCar(int carType) 检车是否有 carType 对应的停车位。
carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。
一辆车只能停在 carType 对应尺寸的停车位中。
如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。
示例 1：输入：["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
输出：[null, true, true, false, false]
解释：ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ，因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了
提示： 0 <= big, medium, small <= 1000
carType 取值为 1， 2 或 3
最多会调用 addCar 函数 1000 次
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组 |
O(1) |
O(1) |
| 02 |
数组 |
O(1) |
O(1) |
type ParkingSystem struct {
arr [3]int
total [3]int
}
func Constructor(big int, medium int, small int) ParkingSystem {
return ParkingSystem{
arr: [3]int{big, medium, small},
total: [3]int{0, 0, 0},
}
}
func (this *ParkingSystem) AddCar(carType int) bool {
index := carType - 1
if this.total[index] < this.arr[index] {
this.total[index]++
return true
}
return false
}
# 2
type ParkingSystem struct {
arr [3]int
}
func Constructor(big int, medium int, small int) ParkingSystem {
return ParkingSystem{
arr: [3]int{big, medium, small},
}
}
func (this *ParkingSystem) AddCar(carType int) bool {
if this.arr[carType-1] > 0 {
this.arr[carType-1]--
return true
}
return false
}
1608.特殊数组的特征值(3)
给你一个非负整数数组 nums 。
如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，
那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。
否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
示例 1：输入：nums = [3,5] 输出：2
解释：有 2 个元素（3 和 5）大于或等于 2 。
示例 2：输入：nums = [0,0] 输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。
示例 3：输入：nums = [0,4,3,0,4] 输出：3
解释：有 3 个元素大于或等于 3 。
示例 4：输入：nums = [3,6,7,7,0] 输出：-1
提示：1 <= nums.length <= 100
0 <= nums[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
计数排序 |
O(n) |
O(n) |
| 02 |
暴力法 |
O(n^2) |
O(1) |
| 03 |
排序 |
O(nlog(n)) |
O(1) |
func specialArray(nums []int) int {
arr := make([]int, 1001)
for i := 0; i < len(nums); i++ {
arr[nums[i]]++
}
for i := len(arr) - 2; i >= 0; i-- {
arr[i] = arr[i] + arr[i+1]
}
for i := 0; i <= len(nums); i++ {
if arr[i] == i {
return i
}
}
return -1
}
# 2
func specialArray(nums []int) int {
for i := 0; i <= len(nums); i++ {
count := 0
for j := 0; j < len(nums); j++ {
if nums[j] >= i {
count++
}
}
if count == i {
return i
}
}
return -1
}
# 3
func specialArray(nums []int) int {
sort.Ints(nums)
n := len(nums)
if nums[0] >= n {
return n
}
for i := 1; i < n; i++ {
target := n - i
if nums[i] >= target && target > nums[i-1] {
return target
}
}
return -1
}
1614.括号的最大嵌套深度(2)
如果字符串满足一下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
depth("") = 0
depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串
例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），
而 ")(" 、"(()" 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
示例 1：输入：s = "(1+(2*3)+((8)/4))+1" 输出：3
解释：数字 8 在嵌套的 3 层括号中。
示例 2：输入：s = "(1)+((2))+(((3)))" 输出：3
示例 3：输入：s = "1+(2*3)/(2-1)" 输出：1
示例 4：输入：s = "1" 输出：0
提示： 1 <= s.length <= 100
s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
题目数据保证括号表达式 s 是 有效的括号表达式
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
栈辅助 |
O(n) |
O(n) |
func maxDepth(s string) int {
res := 0
count := 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
count++
} else if s[i] == ')' {
if count > res {
res = count
}
count--
}
}
return res
}
# 2
func maxDepth(s string) int {
res := 0
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, s[i])
} else if s[i] == ')' {
stack = stack[:len(stack)-1]
}
if len(stack) > res {
res = len(stack)
}
}
return res
}
1619.删除某些元素后的数组均值(2)
给你一个整数数组arr，请你删除最小5%的数字和最大 5%的数字后，剩余数字的平均值。
与 标准答案误差在10-5的结果都被视为正确结果。
示例 1：输入：arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3] 输出：2.00000
解释：删除数组中最大和最小的元素后，所有元素都等于 2，所以平均值为 2 。
示例 2：输入：arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0] 输出：4.00000
示例 3：输入：arr =[6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,
3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
输出：4.77778
示例 4：输入：arr =[9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,
7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
输出：5.27778
示例 5：输入：arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,
9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,
7,2,10,7,7,8,2,0,1,1]
输出：5.29167
提示：20 <= arr.length <= 1000
arr.length是20的倍数
0 <= arr[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(n) |
| 02 |
排序遍历 |
O(nlog(n)) |
O(1) |
func trimMean(arr []int) float64 {
temp := make([]float64, 0)
for i := 0; i < len(arr); i++ {
temp = append(temp, float64(arr[i]))
}
sort.Float64s(temp)
var sum float64
count := int(float64(len(arr)) * 0.05)
for i := count; i < len(temp)-count; i++ {
sum = sum + temp[i]
}
return sum / float64(len(arr)-2*count)
}
# 2
func trimMean(arr []int) float64 {
n := len(arr)
count := n / 20
sort.Ints(arr)
sum := 0
for i := count; i < n-count; i++ {
sum += arr[i]
}
return float64(sum) / float64(n-2*count)
}
1624.两个相同字符之间的最长子字符串(2)
给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。
如果不存在这样的子字符串，返回 -1 。
子字符串 是字符串中的一个连续字符序列。
示例 1：输入：s = "aa" 输出：0
解释：最优的子字符串是两个 'a' 之间的空子字符串。
示例 2：输入：s = "abca" 输出：2
解释：最优的子字符串是 "bc" 。
示例 3：输入：s = "cbzxy" 输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。
示例 4：输入：s = "cabbac" 输出：4
解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
提示：1 <= s.length <= 300 s 只含小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n) |
O(1) |
| 02 |
暴力法 |
O(n^2) |
O(1) |
func maxLengthBetweenEqualCharacters(s string) int {
m := make(map[byte]int)
res := -1
for i := 0; i < len(s); i++ {
if value, ok := m[s[i]]; ok {
res = max(res, i-value-1)
} else {
m[s[i]] = i
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxLengthBetweenEqualCharacters(s string) int {
res := -1
for i := 0; i < len(s); i++ {
for j := i + 1; j < len(s); j++ {
if s[i] == s[j] {
res = max(res, j-i-1)
}
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1629.按键持续时间最长的键(1)
LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。
给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。
releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。
字符串和数组的 下标都从 0 开始 。
第 0 个键在时间为 0 时被按下，接下来每个键都 恰好 在前一个键松开时被按下。
测试人员想要找出按键 持续时间最长 的键。
第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，
第 0 次按键的持续时间为 releaseTimes[0] 。
注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。
请返回按键 持续时间最长 的键，如果有多个这样的键，则返回 按字母顺序排列最大 的那个键。
示例 1：输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd" 输出："c"
解释：按键顺序和持续时间如下：
按下 'c' ，持续时间 9（时间 0 按下，时间 9 松开）
按下 'b' ，持续时间 29 - 9 = 20（松开上一个键的时间 9 按下，时间 29 松开）
按下 'c' ，持续时间 49 - 29 = 20（松开上一个键的时间 29 按下，时间 49 松开）
按下 'd' ，持续时间 50 - 49 = 1（松开上一个键的时间 49 按下，时间 50 松开）
按键持续时间最长的键是 'b' 和 'c'（第二次按下时），持续时间都是 20
'c' 按字母顺序排列比 'b' 大，所以答案是 'c'
示例 2：输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda" 输出："a"
解释：按键顺序和持续时间如下：
按下 's' ，持续时间 12
按下 'p' ，持续时间 23 - 12 = 11
按下 'u' ，持续时间 36 - 23 = 13
按下 'd' ，持续时间 46 - 36 = 10
按下 'a' ，持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ，持续时间 16
提示： releaseTimes.length == n
keysPressed.length == n
2 <= n <= 1000
0 <= releaseTimes[i] <= 109
releaseTimes[i] < releaseTimes[i+1]
keysPressed 仅由小写英文字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func slowestKey(releaseTimes []int, keysPressed string) byte {
res := 0
maxValue := releaseTimes[0]
for i := 1; i < len(releaseTimes); i++ {
if releaseTimes[i]-releaseTimes[i-1] > maxValue {
maxValue = releaseTimes[i] - releaseTimes[i-1]
res = i
} else if releaseTimes[i]-releaseTimes[i-1] == maxValue &&
keysPressed[i] > keysPressed[res] {
res = i
}
}
return keysPressed[res]
}
1636.按照频率将数组升序排序(1)
给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。
如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
请你返回排序后的数组。
示例 1：输入：nums = [1,1,2,2,2,3] 输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
示例 2：输入：nums = [2,3,1,3,2] 输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。
示例 3：输入：nums = [-1,1,-6,4,5,-6,1,4,1] 输出：[5,-1,4,4,-6,-6,1,1,1]
提示：1 <= nums.length <= 100
-100 <= nums[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
自定义排序 |
O(nlog(n)) |
O(n) |
func frequencySort(nums []int) []int {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
arr := make([][2]int, 0)
for k, v := range m {
arr = append(arr, [2]int{k, v})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][1] == arr[j][1] {
return arr[i][0] > arr[j][0]
}
return arr[i][1] < arr[j][1]
})
res := make([]int, 0)
for i := 0; i < len(arr); i++ {
for j := 0; j < arr[i][1]; j++ {
res = append(res, arr[i][0])
}
}
return res
}
1640.能否连接形成数组(2)
给你一个整数数组 arr ，数组中的每个整数 互不相同 。
另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同 。
请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。
如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。
示例 1：输入：arr = [85], pieces = [[85]]输出：true
示例 2：输入：arr = [15,88], pieces = [[88],[15]] 输出：true
解释：依次连接 [15] 和 [88]
示例 3：输入：arr = [49,18,16], pieces = [[16,18,49]] 输出：false
解释：即便数字相符，也不能重新排列 pieces[0]
示例 4：输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]] 输出：true
解释：依次连接 [91]、[4,64] 和 [78]
示例 5：输入：arr = [1,3,5,7], pieces = [[2,4,6,8]] 输出：false
提示：1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
arr 中的整数 互不相同
pieces 中的整数 互不相同（也就是说，如果将 pieces 扁平化成一维数组，数组中的所有整数互不相同）
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历标记 |
O(n^2) |
O(1) |
| 02 |
哈希辅助 |
O(n) |
O(n) |
func canFormArray(arr []int, pieces [][]int) bool {
for i := 0; i < len(pieces); i++ {
value := pieces[i]
length := len(value)
flag := false
for j := 0; j < len(arr); j++ {
if arr[j] == value[0] {
flag = true
for k := j; k < j+length && k < len(arr); k++ {
if arr[k] != value[k-j] {
return false
} else {
arr[k] = 0
}
}
break
}
}
if flag == false {
return false
}
}
for i := 0; i < len(arr); i++ {
if arr[i] != 0 {
return false
}
}
return true
}
# 2
func canFormArray(arr []int, pieces [][]int) bool {
m := make(map[int]int)
for i := 0; i < len(arr); i++ {
m[arr[i]] = i
}
for i := 0; i < len(pieces); i++ {
if _, ok := m[pieces[i][0]]; !ok {
return false
}
for k := 0; k < len(pieces[i])-1; k++ {
if m[pieces[i][k+1]]-m[pieces[i][k]] != 1 {
return false
}
}
}
return true
}
1646.获取生成数组中的最大值(1)
给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
nums[0] = 0
nums[1] = 1
当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
返回生成数组 nums 中的 最大 值。
示例 1：输入：n = 7 输出：3
解释：根据规则：
nums[0] = 0
nums[1] = 1
nums[(1 * 2) = 2] = nums[1] = 1
nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 * 2) = 4] = nums[2] = 1
nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 * 2) = 6] = nums[3] = 2
nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3
示例 2：输入：n = 2 输出：1
解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1
示例 3：输入：n = 3 输出：2
解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
提示：0 <= n <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func getMaximumGenerated(n int) int {
arr := make([]int, n+3)
arr[0] = 0
arr[1] = 1
res := 0
for i := 0; i <= n; i++ {
if i%2 == 0 {
arr[i] = arr[i/2]
} else {
arr[i] = arr[i/2] + arr[(i+1)/2]
}
if arr[i] > res {
res = arr[i]
}
}
return res
}
1652.拆炸弹(1)
你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为n的循环数组code以及一个密钥k。
为了获得正确的密码，你需要替换掉每一个数字。所有数字会同时被替换。
如果k > 0，将第i个数字用 接下来k个数字之和替换。
如果k < 0，将第i个数字用 之前k个数字之和替换。
如果k == 0，将第i个数字用0替换。
由于code是循环的，code[n-1]下一个元素是code[0]，且code[0]前一个元素是code[n-1]。
给你 循环数组code和整数密钥k，请你返回解密后的结果来拆除炸弹！
示例 1：输入：code = [5,7,1,4], k = 3 输出：[12,10,16,13]
解释：每个数字都被接下来 3 个数字之和替换。
解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。
示例 2：输入：code = [1,2,3,4], k = 0 输出：[0,0,0,0]
解释：当 k 为 0 时，所有数字都被 0 替换。
示例 3：输入：code = [2,4,9,3], k = -2 输出：[12,5,6,13]
解释：解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。
如果 k 是负数，那么和为 之前 的数字。
提示：n == code.length
1 <= n<= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func decrypt(code []int, k int) []int {
n := len(code)
res := make([]int, n)
if k == 0 {
return res
}
for i := 0; i < n; i++ {
sum := 0
for j := 1; j <= abs(k); j++ {
if k > 0 {
sum = sum + code[(i+j+n)%n]
} else {
sum = sum + code[(i-j+n)%n]
}
}
res[i] = sum
}
return res
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
1656.设计有序流(1)
有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。
不存在 id 相同的两个(id, value) 对。
设计一个流，以 任意 顺序获取 n个(id, value)对，并在多次调用时 按 id 递增的顺序 返回一些值。
实现 OrderedStream 类：
OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，
并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1。
否则，返回一个空列表。
示例：输入["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
解释: OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]
提示：1 <= n <= 1000
1 <= id <= n
value.length == 5
value 仅由小写字母组成
每次调用 insert 都会使用一个唯一的 id
恰好调用 n 次 insert
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组 |
O(n) |
O(n) |
type OrderedStream struct {
arr []string
ptr int
}
func Constructor(n int) OrderedStream {
return OrderedStream{
arr: make([]string, n+1),
ptr: 1,
}
}
func (this *OrderedStream) Insert(id int, value string) []string {
res := make([]string, 0)
this.arr[id] = value
if this.ptr < id-1 {
return res
}
for i := this.ptr; i < len(this.arr); i++ {
if this.arr[i] == "" {
break
}
res = append(res, this.arr[i])
this.ptr++
}
return res
}
1662.检查两个字符串数组是否相等(2)
给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。
数组表示的字符串是由数组中的所有元素 按顺序 连接形成的字符串。
示例 1：输入：word1 = ["ab", "c"], word2 = ["a", "bc"] 输出：true
解释：word1 表示的字符串为 "ab" + "c" -> "abc"
word2 表示的字符串为 "a" + "bc" -> "abc"
两个字符串相同，返回 true
示例 2：输入：word1 = ["a", "cb"], word2 = ["ab", "c"] 输出：false
示例 3：输入：word1 = ["abc", "d", "defg"], word2 = ["abcddefg"] 输出：true
提示：1 <= word1.length, word2.length <= 103
1 <= word1[i].length, word2[i].length <= 103
1 <= sum(word1[i].length), sum(word2[i].length) <= 103
word1[i] 和 word2[i] 由小写字母组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
return strings.Join(word1,"") == strings.Join(word2,"")
}
# 2
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
str1 := ""
str2 := ""
for i := 0; i < len(word1); i++ {
str1 = str1 + word1[i]
}
for i := 0; i < len(word2); i++ {
str2 = str2 + word2[i]
}
return str1 == str2
}
1668.最大重复子字符串(1)
给你一个字符串sequence，如果字符串 word连续重复k次形成的字符串是sequence的一个子字符串，
那么单词word 的 重复值为 k 。单词 word的 最大重复值是单词word在sequence中最大的重复值。
如果word不是sequence的子串，那么重复值k为 0 。
给你一个字符串 sequence和 word，请你返回 最大重复值k 。
示例 1：输入：sequence = "ababc", word = "ab" 输出：2
解释："abab" 是 "ababc" 的子字符串。
示例 2：输入：sequence = "ababc", word = "ba" 输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。
示例 3：输入：sequence = "ababc", word = "ac" 输出：0
解释："ac" 不是 "ababc" 的子字符串。
提示：1 <= sequence.length <= 100
1 <= word.length <= 100
sequence 和word都只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
func maxRepeating(sequence string, word string) int {
res := 0
for i := 1; ; i++ {
if strings.Contains(sequence, strings.Repeat(word, i)) == false {
break
} else {
res = i
}
}
return res
}
1672.最富有客户的资产总量(1)
给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i位客户在第 j 家银行托管的资产数量。
返回最富有客户所拥有的 资产总量 。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
示例 1：输入：accounts = [[1,2,3],[3,2,1]] 输出：6
解释：第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。
示例 2：输入：accounts = [[1,5],[7,3],[3,5]] 输出：10
解释：第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的，资产总量是 10
示例 3：输入：accounts = [[2,8,7],[7,1,3],[1,9,5]] 输出：17
提示：m ==accounts.length
n ==accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
func maximumWealth(accounts [][]int) int {
res := 0
for i := 0; i < len(accounts); i++ {
sum := 0
for j := 0; j < len(accounts[i]); j++ {
sum = sum + accounts[i][j]
}
if sum > res {
res = sum
}
}
return res
}
1678.设计Goal解析器(2)
请你设计一个可以解释字符串 command 的 Goal 解析器 。
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。
Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。
然后，按原顺序将经解释得到的字符串连接成一个字符串。
给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。
示例 1：输入：command = "G()(al)" 输出："Goal"
解释：Goal 解析器解释命令的步骤如下所示：
G -> G
() -> o
(al) -> al
最后连接得到的结果是 "Goal"
示例 2：输入：command = "G()()()()(al)" 输出："Gooooal"
示例 3：输入：command = "(al)G(al)()()G" 输出："alGalooG"
提示：1 <= command.length <= 100
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func interpret(command string) string {
command = strings.ReplaceAll(command, "(al)", "al")
command = strings.ReplaceAll(command, "()", "o")
return command
}
# 2
func interpret(command string) string {
res := ""
for i := 0; i < len(command); {
if command[i] == 'G' {
res = res + "G"
i = i + 1
} else if command[i] == '(' {
if command[i+1] == ')' {
res = res + "o"
i = i + 2
} else {
res = res + "al"
i = i + 4
}
}
}
return res
}
1684.统计一致字符串的数目(1)
给你一个由不同字符组成的字符串allowed和一个字符串数组words。
如果一个字符串的每一个字符都在 allowed中，就称这个字符串是 一致字符串。
请你返回words数组中一致字符串的数目。
示例 1：输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"] 输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。
示例 2：输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"] 输出：7
解释：所有字符串都是一致的。
示例 3：输入：allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"] 输出：4
解释：字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。
提示：1 <= words.length <= 104
1 <= allowed.length <= 26
1 <= words[i].length <= 10
allowed中的字符 互不相同。
words[i] 和allowed只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
func countConsistentStrings(allowed string, words []string) int {
res := 0
m := make(map[byte]bool)
for i := 0; i < len(allowed); i++ {
m[allowed[i]] = true
}
for _, word := range words {
flag := true
for i := 0; i < len(word); i++ {
if _, ok := m[word[i]]; !ok {
flag = false
break
}
}
if flag == true {
res++
}
}
return res
}
1688.比赛中的配对次数(2)
给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：
如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。
总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。
总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数，直到决出获胜队伍为止。
示例 1：输入：n = 7 输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6
示例 2：输入：n = 14 输出：13
解释：比赛详情：
- 第 1 轮：队伍数 = 14 ，配对次数 = 7 ，7 支队伍晋级。
- 第 2 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 3 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 4 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13
提示：1 <= n <= 200
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
数学 |
O(1) |
O(1) |
func numberOfMatches(n int) int {
res := 0
for n > 1 {
res = res + n/2
n = n/2 + n%2
}
return res
}
# 2
func numberOfMatches(n int) int {
return n - 1
}
1694.重新格式化电话号码(1)
给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。
请你按下述方式重新格式化电话号码。
首先，删除 所有的空格和破折号。
其次，将数组从左到右 每 3 个一组 分块，直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
2 个数字：单个含 2 个数字的块。
3 个数字：单个含 3 个数字的块。
4 个数字：两个分别含 2 个数字的块。
最后用破折号将这些块连接起来。
注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且 最多 生成两个含 2 个数字的块。
返回格式化后的电话号码。
示例 1：输入：number = "1-23-45 6" 输出："123-456"
解释：数字是 "123456"
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 3 个数字，将它们放入单个含 3 个数字的块。第 2 个块是 "456" 。
连接这些块后得到 "123-456" 。
示例 2：输入：number = "123 4-567" 输出："123-45-67"
解释：数字是 "1234567".
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 4 个数字，所以将它们分成两个含 2 个数字的块。这 2 块分别是 "45" 和 "67" 。
连接这些块后得到 "123-45-67" 。
示例 3：输入：number = "123 4-5678" 输出："123-456-78"
解释：数字是 "12345678" 。
步骤 1：第 1 个块 "123" 。
步骤 2：第 2 个块 "456" 。
步骤 3：剩下 2 个数字，将它们放入单个含 2 个数字的块。第 3 个块是 "78" 。
连接这些块后得到 "123-456-78" 。
示例 4：输入：number = "12" 输出："12"
示例 5：输入：number = "--17-5 229 35-39475 " 输出："175-229-353-94-75"
提示：2 <= number.length <= 100
number 由数字和字符 '-' 及 ' ' 组成。
number 中至少含 2 个数字。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
内置函数 |
O(n) |
O(n) |
func reformatNumber(number string) string {
str := strings.ReplaceAll(number, "-", "")
str = strings.ReplaceAll(str, " ", "")
res := ""
for len(str) > 4 {
res = res + str[:3] + "-"
str = str[3:]
}
if len(str) == 4 {
res = res + str[:2] + "-" + str[2:]
} else {
res = res + str
}
return res
}
1700.无法吃午餐的学生数量(1)
学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。
所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮：
如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列。
否则，这名学生会放弃这个三明治并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组students 和sandwiches，
其中sandwiches[i]是栈里面第i个三明治的类型（i = 0是栈的顶部），
students[j]是初始队列里第j名学生对三明治的喜好（j = 0是队列的最开始位置）。
请你返回无法吃午餐的学生数量。
示例 1：输入：students = [1,1,0,0], sandwiches = [0,1,0,1] 输出：0
解释：- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，
三明治栈为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。
示例 2：输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] 输出：3
提示：1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i]要么是0，要么是1。
students[i]要么是0，要么是1。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func countStudents(students []int, sandwiches []int) int {
a, b := 0, 0
for i := 0; i < len(students); i++ {
if students[i] == 0 {
a++
} else {
b++
}
}
for i := 0; i < len(sandwiches); i++ {
if sandwiches[i] == 0 && a > 0 {
a--
} else if sandwiches[i] == 1 && b > 0 {
b--
} else {
break
}
}
return a + b
}
1601-1700-Medium
1604.警告一小时内使用相同员工卡大于等于三次的人(2)
力扣公司的员工都使用员工卡来开办公室的门。
每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。
如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。
给你字符串数组 keyName 和 keyTime ，
其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。
使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。
请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。
请注意 "10:00" - "11:00" 视为一个小时时间范围内，
而 "23:51" - "00:10" 不被视为一小时内，因为系统记录的是某一天内的使用情况。
示例 1：输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"],
keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出：["daniel"]
解释："daniel" 在一小时内使用了 3 次员工卡（"10:00"，"10:40"，"11:00"）。
示例 2：输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"],
keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出：["bob"]
解释："bob" 在一小时内使用了 3 次员工卡（"21:00"，"21:20"，"21:30"）。
示例 3：输入：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
输出：[]
示例 4：输入：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"],
keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
输出：["clare","leslie"]
提示：1 <= keyName.length, keyTime.length <= 105
keyName.length == keyTime.length
keyTime 格式为 "HH:MM" 。
保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
1 <= keyName[i].length <= 10
keyName[i] 只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希+排序+遍历 |
O(nlog(n)) |
O(n) |
| 02 |
哈希+排序+滑动窗口 |
O(nlog(n)) |
O(n) |
func alertNames(keyName []string, keyTime []string) []string {
m := make(map[string][]int)
for i := 0; i < len(keyName); i++ {
m[keyName[i]] = append(m[keyName[i]], strToInt(keyTime[i]))
}
res := make([]string, 0)
for k, v := range m {
sort.Ints(v)
first := v[0]
second := v[0]
count := 1
for i := 1; i < len(v); i++ {
if v[i] > first && v[i]-first <= 60 {
second = v[i]
count++
} else {
first = second
second = v[i]
count = 2
}
if count >= 3 {
res = append(res, k)
break
}
}
}
sort.Strings(res)
return res
}
func strToInt(str string) int {
arr := strings.Split(str, ":")
hour, _ := strconv.Atoi(arr[0])
minute, _ := strconv.Atoi(arr[1])
return hour*60 + minute
}
# 2
func alertNames(keyName []string, keyTime []string) []string {
m := make(map[string][]int)
for i := 0; i < len(keyName); i++ {
m[keyName[i]] = append(m[keyName[i]], strToInt(keyTime[i]))
}
res := make([]string, 0)
for k, v := range m {
sort.Ints(v)
for i := 0; i < len(v)-2; i++ {
if v[i+2]-v[i] <= 60 {
res = append(res, k)
break
}
}
}
sort.Strings(res)
return res
}
func strToInt(str string) int {
arr := strings.Split(str, ":")
hour, _ := strconv.Atoi(arr[0])
minute, _ := strconv.Atoi(arr[1])
return hour*60 + minute
}
1605.给定行和列的和求可行矩阵(1)
给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和，
colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，
且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。
示例 1：输入：rowSum = [3,8], colSum = [4,7] 输出：[[3,0],
[1,7]]
解释：第 0 行：3 + 0 = 0 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
[3,5]]
示例 2：输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
[6,1,0],
[2,0,8]]
示例 3：输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
[6,0,3]]
示例 4：输入：rowSum = [1,0], colSum = [1]
输出：[[1],
[0]]
示例 5：输入：rowSum = [0], colSum = [0]
输出：[[0]]
提示：1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 108
sum(rows) == sum(columns)
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n^2) |
O(n^2) |
func restoreMatrix(rowSum []int, colSum []int) [][]int {
n := len(rowSum)
m := len(colSum)
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, m)
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
value := min(rowSum[i], colSum[j])
res[i][j] = value
rowSum[i] = rowSum[i] - value
colSum[j] = colSum[j] - value
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1609.奇偶树(1)
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
示例 1：输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，
因此这是一棵奇偶树。
示例 2：输入：root = [5,4,2,3,3,7] 输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
示例 3：输入：root = [5,9,1,3,5,7] 输出：false
解释：1 层上的节点值应为偶数。
示例 4：输入：root = [1]输出：true
示例 5：输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17] 输出：true
提示：树中节点数在范围 [1, 105] 内
1 <= Node.val <= 106
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
层序遍历 |
O(n) |
O(n) |
func isEvenOddTree(root *TreeNode) bool {
queue := make([]*TreeNode, 0)
queue = append(queue, root)
level := 1
for len(queue) > 0 {
length := len(queue)
temp := make([]int, 0)
for i := 0; i < length; i++ {
temp = append(temp, queue[i].Val)
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
}
if level%2 == 0 {
for j := 0; j < len(temp)/2; j++ {
temp[j], temp[len(temp)-1-j] = temp[len(temp)-1-j], temp[j]
}
}
for i := 0; i < len(temp); i++ {
if i < len(temp)-1 && temp[i] >= temp[i+1] {
return false
}
if temp[i]%2 != level%2 {
return false
}
}
queue = queue[length:]
level++
}
return true
}
1615.最大网络秩(1)
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。
每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。
如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
示例 1：输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]] 输出：4
解释：城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。
位于 0 和 1 之间的道路只计算一次。
示例 2：输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]] 输出：5
解释：共有 5 条道路与城市 1 或 2 相连。
示例 3：输入：n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]] 输出：5
解释：2 和 5 的网络秩为 5，注意并非所有的城市都需要连接起来。
提示：2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= ai, bi<= n-1
ai!=bi
每对城市之间 最多只有一条道路相连
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
func maximalNetworkRank(n int, roads [][]int) int {
arr := make([]int, n)
m := make(map[int]int)
for i := 0; i < len(roads); i++ {
a, b := roads[i][0], roads[i][1]
arr[a]++
arr[b]++
m[a*100+b]++
m[b*100+a]++
}
res := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
value := arr[i] + arr[j] - m[i*100+j]
if value > res {
res = value
}
}
}
return res
}
1616.分割两个字符串得到回文串(2)
给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。
由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，
同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。
请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。
比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
请注意， x + y 表示连接字符串 x 和 y 。
示例 1：输入：a = "x", b = "y" 输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
那么 aprefix + bsuffix = "" + "y" = "y" 是回文串。
示例 2：输入：a = "ulacfd", b = "jizalu" 输出：true
解释：在下标为 3 处分割：
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
那么 aprefix + bsuffix = "ula" + "alu" = "ulaalu" 是回文串。
提示：1 <= a.length, b.length <= 105
a.length == b.length
a 和 b 都只包含小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
双指针 |
O(n) |
O(1) |
func checkPalindromeFormation(a string, b string) bool {
if judge(a, b) == true || judge(b, a) == true {
return true
}
return false
}
func judge(a, b string) bool {
left, right := 0, len(a)-1
for left < right {
if a[left] == b[right] {
left++
right--
} else {
break
}
}
var i, j int
i, j = left, right
for i < j {
if b[i] == b[j] {
i++
j--
} else {
break
}
}
if i >= j {
return true
}
i, j = left, right
for i < j {
if a[i] == a[j] {
i++
j--
} else {
break
}
}
if i >= j {
return true
}
return false
}
# 2
func checkPalindromeFormation(a string, b string) bool {
start := len(a)/2 - 1
c := check(a, a, start)
if check(a, b, c) == -1 || check(b, a, c) == -1 {
return true
}
c = check(b, b, start)
if check(a, b, c) == -1 || check(b, a, c) == -1 {
return true
}
return false
}
func check(a, b string, start int) int {
left := start
right := len(a) - 1 - start
for left >= 0 {
if a[left] != b[right] {
break
}
left--
right++
}
return left
}
1620.网络信号最好的坐标(1)
给你一个数组 towers和一个整数 radius，数组中包含一些网络信号塔，
其中towers[i] = [xi, yi, qi]表示第i个网络信号塔的坐标是(xi, yi)且信号强度参数为qi。
所有坐标都是在 X-Y 坐标系内的整数坐标。两个坐标之间的距离用 欧几里得距离计算。
整数radius表示一个塔 能到达的 最远距离。
如果一个坐标跟塔的距离在 radius以内，那么该塔的信号可以到达该坐标。
在这个范围以外信号会很微弱，所以 radius以外的距离该塔是 不能到达的。
如果第 i个塔能到达 (x, y)，那么该塔在此处的信号为⌊qi / (1 + d)⌋，其中d是塔跟此坐标的距离。
一个坐标的 网络信号是所有 能到达该坐标的塔的信号强度之和。
请你返回 网络信号最大的整数坐标点。如果有多个坐标网络信号一样大，请你返回字典序最小的一个坐标。
注意：坐标(x1, y1)字典序比另一个坐标(x2, y2)小：要么x1 < x2，要么x1 == x2 且y1 < y2。
⌊val⌋表示小于等于val的最大整数（向下取整函数）。
示例 1：输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2 输出：[2,1]
解释：坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。
示例 2：输入：towers = [[23,11,21]], radius = 9 输出：[23,11]
示例 3：输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2 输出：[1,2]
示例 4：输入：towers = [[2,1,9],[0,1,9]], radius = 2 输出：[0,1]
解释：坐标 (0, 1) 和坐标 (2, 1) 都是强度最大的位置，但是 (0, 1) 字典序更小。
提示：1 <= towers.length <= 50
towers[i].length == 3
0 <= xi, yi, qi <= 50
1 <= radius <= 50
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n) |
O(1) |
func bestCoordinate(towers [][]int, radius int) []int {
res := []int{0, 0}
maxValue := 0
for i := 0; i <= 50; i++ {
for j := 0; j <= 50; j++ {
sum := 0
for k := 0; k < len(towers); k++ {
a, b, c := towers[k][0], towers[k][1], towers[k][2]
d := (a-i)*(a-i) + (b-j)*(b-j)
if d <= radius*radius {
value := float64(c) / (1 + math.Sqrt(float64(d)))
sum = sum + int(math.Floor(value))
}
}
if sum > maxValue {
maxValue = sum
res = []int{i, j}
}
}
}
return res
}
1621.大小为K的不重叠线段的数目(2)
给你一维空间的n个点，其中第i个点（编号从0 到n-1）位于x = i处，
请你找到恰好k个不重叠线段且每个线段至少覆盖两个点的方案数。
线段的两个端点必须都是整数坐标。
这k个线段不需要全部覆盖全部n个点，且它们的端点可以重合。
请你返回 k个不重叠线段的方案数。由于答案可能很大，请将结果对109 + 7取余 后返回。
示例 1：输入：n = 4, k = 2 输出：5
解释：如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，
{(1,2),(2,3)}，{(0,1),(1,2)} 。
示例 2：输入：n = 3, k = 1 输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。
示例 3：输入：n = 30, k = 7 输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。
示例 4：输入：n = 5, k = 3 输出：7
示例 5：输入：n = 3, k = 2 输出：1
提示：2 <= n <= 1000
1 <= k <= n-1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
数学-组合 |
O(n) |
O(1) |
var mod = 1000000007
func numberOfSets(n int, k int) int {
dp := make([][][2]int, n)
for i := 0; i < n; i++ {
dp[i] = make([][2]int, n)
}
dp[0][0][0] = 1
for i := 1; i < n; i++ {
for j := 0; j <= k; j++ {
dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % mod
dp[i][j][1] = dp[i-1][j][1]
if j > 0 {
dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][0] + dp[i-1][j-1][1]) % mod
}
}
}
return (dp[n-1][k][0] + dp[n-1][k][1]) % mod
}
# 2
# 2
var mod = 1000000007
func numberOfSets(n int, k int) int {
return C(n+k-1, 2*k)
}
func C(n, m int) int {
a := multiMod(n, n-m+1)
b := multiMod(m, 1)
return a * powMod(b, mod-2) % mod
}
func multiMod(n, m int) int {
res := 1
for i := m; i <= n; i++ {
res = (res * i) % mod
}
return res
}
func powMod(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
}
1625.执行操作后字典序最小的字符串(2)
给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。
你可以在 s 上按任意顺序多次执行下面两个操作之一：
累加：将 a 加到 s 中所有下标为奇数的元素上（下标从 0 开始）。数字一旦超过 9 就会变成 0，如此循环往复。
例如，s = "3456" 且 a = 5，则执行此操作后 s 变成 "3951"。
轮转：将 s 向右轮转 b 位。例如，s = "3456" 且 b = 1，则执行此操作后 s 变成 "6345"。
请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：
在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。
例如，"0158” 字典序比 "0190" 小，因为不同的第一个位置是在第三个字符，显然 '5' 出现在 '9' 之前。
示例 1：输入：s = "5525", a = 9, b = 2 输出："2050"
解释：执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"
无法获得字典序小于 "2050" 的字符串。
示例 2：输入：s = "74", a = 5, b = 1 输出："24"
解释：执行操作如下：
初态："74"
轮转："47"
累加："42"
轮转："24"
无法获得字典序小于 "24" 的字符串。
示例 3：输入：s = "0011", a = 4, b = 2 输出："0011"
解释：无法获得字典序小于 "0011" 的字符串。
示例 4：输入：s = "43987654", a = 7, b = 3 输出："00553311"
提示：2 <= s.length <= 100
s.length 是偶数
s 仅由数字 0 到 9 组成
1 <= a <= 9
1 <= b <= s.length - 1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索 |
O(n^2) |
O(n) |
| 02 |
广度优先搜索 |
O(n^2) |
O(n) |
var m map[string]bool
var res string
func findLexSmallestString(s string, a int, b int) string {
res = s
m = make(map[string]bool)
dfs(s, a, b)
return res
}
func dfs(s string, a, b int) {
if m[s] == true {
return
}
m[s] = true
if s < res {
res = s
}
dfs(add(s, a), a, b)
dfs(s[b:]+s[:b], a, b)
}
func add(s string, a int) string {
res := []byte(s)
for i := 1; i < len(s); i = i + 2 {
res[i] = byte('0' + (int(s[i]-'0')+a)%10)
}
return string(res)
}
# 2
func findLexSmallestString(s string, a int, b int) string {
res := s
m := make(map[string]bool)
queue := make([]string, 0)
queue = append(queue, s)
for len(queue) > 0 {
str := queue[0]
queue = queue[1:]
if m[str] == true {
continue
}
m[str] = true
if str < res {
res = str
}
queue = append(queue, str[b:]+str[:b])
queue = append(queue, add(str, a))
}
return res
}
func add(s string, a int) string {
res := []byte(s)
for i := 1; i < len(s); i = i + 2 {
res[i] = byte('0' + (int(s[i]-'0')+a)%10)
}
return string(res)
}
1626.无矛盾的最佳球队(1)
假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。
球队的得分是球队中所有球员的分数 总和 。
然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。
如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。
请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
示例 1：输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5] 输出：34
解释：你可以选中所有球员。
示例 2：输入：scores = [4,5,6,5], ages = [2,1,2,1] 输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。
示例 3：输入：scores = [1,2,3,5], ages = [8,9,10,1] 输出：6
解释：最佳的选择是前 3 名球员。
提示： 1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 10^6
1 <= ages[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
func bestTeamScore(scores []int, ages []int) int {
arr := make([][2]int, 0)
for i := 0; i < len(ages); i++ {
arr = append(arr, [2]int{ages[i], scores[i]})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][0] == arr[j][0] {
return arr[i][1] < arr[j][1]
}
return arr[i][0] < arr[j][0]
})
dp := make([]int, len(arr))
res := 0
for i := 0; i < len(arr); i++ {
dp[i] = arr[i][1]
for j := 0; j < i; j++ {
if arr[j][1] <= arr[i][1] {
dp[i] = max(dp[i], dp[j]+arr[i][1])
}
}
res = max(res, dp[i])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1630.等差子数组(1)
如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。
更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。
例如，下面这些都是 等差数列 ：
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
下面的数列 不是等差数列 ：
1, 1, 2, 5, 7
给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，
其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。
返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... ,
nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。
示例 1：输入：nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5] 输出：[true,false,true]
解释：第 0 个查询，对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。
第 1 个查询，对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。
第 2 个查询，对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。
示例 2：输入：nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10],
l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
输出：[false,true,false,false,true,true]
提示：n == nums.length
m == l.length
m == r.length
2 <= n <= 500
1 <= m <= 500
0 <= l[i] < r[i] < n
-105 <= nums[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(n^2*log(n)) |
O(n) |
func checkArithmeticSubarrays(nums []int, l []int, r []int) []bool {
res := make([]bool, 0)
for i := 0; i < len(l); i++ {
flag := true
arr := make([]int, 0)
arr = append(arr, nums[l[i]:r[i]+1]...)
sort.Ints(arr)
for j := 2; j < len(arr); j++ {
if arr[j]-arr[j-1] != arr[1]-arr[0] {
flag = false
break
}
}
res = append(res, flag)
}
return res
}
1631.最小体力消耗路径(4)
你准备参加一场远足活动。给你一个二维rows x columns的地图heights，
其中heights[row][col]表示格子(row, col)的高度。
一开始你在最左上角的格子(0, 0)，且你希望去最右下角的格子(rows-1, columns-1)（注意下标从 0 开始编号）。
你每次可以往 上，下，左，右四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值是路径上相邻格子之间 高度差绝对值的 最大值决定的。
请你返回从左上角走到右下角的最小体力消耗值。
示例 1：输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
示例 2：输入：heights = [[1,2,3],[3,8,4],[5,3,5]] 输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
示例 3：输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出：0
解释：上图所示路径不需要消耗任何体力。
提示：rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找+广度优先搜索 |
O(n^2log(n)) |
O(n^2) |
| 02 |
并查集 |
O(n^2log(n)) |
O(n^2) |
| 03 |
Dijkstra |
O(n^2log(n)) |
O(n^2) |
| 04 |
二分查找+广度优先搜索+内置函数 |
O(n^2log(n)) |
O(n^2) |
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func minimumEffortPath(heights [][]int) int {
n, m := len(heights), len(heights[0])
left, right := 0, 1000000
res := 0
for left <= right {
mid := left + (right-left)/2
queue := make([][2]int, 0)
queue = append(queue, [2]int{0, 0})
visited := make([][]bool, n)
for i := 0; i < n; i++ {
visited[i] = make([]bool, m)
}
for len(queue) > 0 {
a, b := queue[0][0], queue[0][1]
queue = queue[1:]
for i := 0; i < 4; i++ {
x, y := a+dx[i], b+dy[i]
if 0 <= x && x < n && 0 <= y && y < m &&
visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= mid {
queue = append(queue, [2]int{x, y})
visited[x][y] = true
}
}
}
if visited[n-1][m-1] == true {
res = mid
right = mid - 1
} else {
left = mid + 1
}
}
return res
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
# 2
func minimumEffortPath(heights [][]int) int {
n, m := len(heights), len(heights[0])
arr := make([][3]int, 0)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
index := i*m + j
if i > 0 {
value := abs(heights[i][j] - heights[i-1][j])
arr = append(arr, [3]int{index - m, index, value})
}
if j > 0 {
value := abs(heights[i][j] - heights[i][j-1])
arr = append(arr, [3]int{index - 1, index, value})
}
}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][2] < arr[j][2]
})
fa = Init(n * m)
for i := 0; i < len(arr); i++ {
a, b, c := arr[i][0], arr[i][1], arr[i][2]
union(a, b)
if query(0, n*m-1) == true {
return c
}
}
return 0
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
var fa []int
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
func find(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
func union(i, j int) {
fa[find(i)] = find(j)
}
func query(i, j int) bool {
return find(i) == find(j)
}
# 3
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func minimumEffortPath(heights [][]int) int {
n, m := len(heights), len(heights[0])
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, m)
for j := 0; j < m; j++ {
arr[i][j] = math.MaxInt32
}
}
arr[0][0] = 0
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [3]int{0, 0, 0})
for {
node := heap.Pop(&intHeap).([3]int)
a, b, c := node[0], node[1], node[2]
if a == n-1 && b == m-1 {
return c
}
if arr[a][b] < c {
continue
}
for i := 0; i < 4; i++ {
x, y := a+dx[i], b+dy[i]
if 0 <= x && x < n && 0 <= y && y < m {
diff := max(c, abs(heights[x][y]-heights[a][b]))
if diff < arr[x][y] {
arr[x][y] = diff
heap.Push(&intHeap, [3]int{x, y, diff})
}
}
}
}
return 0
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
type IntHeap [][3]int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i][2] < h[j][2]
}
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.([3]int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
# 4
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func minimumEffortPath(heights [][]int) int {
n, m := len(heights), len(heights[0])
return sort.Search(1000000, func(target int) bool {
queue := make([][2]int, 0)
queue = append(queue, [2]int{0, 0})
visited := make([][]bool, n)
for i := 0; i < n; i++ {
visited[i] = make([]bool, m)
}
for len(queue) > 0 {
a, b := queue[0][0], queue[0][1]
queue = queue[1:]
if a == n-1 && b == m-1 {
return true
}
for i := 0; i < 4; i++ {
x, y := a+dx[i], b+dy[i]
if 0 <= x && x < n && 0 <= y && y < m &&
visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= target {
queue = append(queue, [2]int{x, y})
visited[x][y] = true
}
}
}
return false
})
return 0
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
1637.两点之间不包含任何点的最宽垂直面积(1)
给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，
请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
垂直面积 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。
最宽垂直面积 为宽度最大的一个垂直面积。
请注意，垂直区域 边上 的点 不在 区域内。
示例 1：输入：points = [[8,7],[9,9],[7,4],[9,7]] 输出：1
解释：红色区域和蓝色区域都是最优区域。
示例 2：输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]] 输出：3
提示： n == points.length
2 <= n <= 105
points[i].length == 2
0 <= xi, yi <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
func maxWidthOfVerticalArea(points [][]int) int {
sort.Slice(points, func(i, j int) bool {
return points[i][0] < points[j][0]
})
res := 0
for i := 1; i < len(points); i++ {
res = max(res, points[i][0]-points[i-1][0])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1638.统计只差一个字符的子串数目(3)
给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，
是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。
比方说， "computer" 和 "computation" 加粗部分只有一个字符不同：
'e'/'a' ，所以这一对子字符串会给答案加 1 。
请你返回满足上述条件的不同子字符串对数目。
一个 子字符串 是一个字符串中连续的字符。
示例 1：输入：s = "aba", t = "baba" 输出：6
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 2：输入：s = "ab", t = "bb" 输出：3
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 3：输入：s = "a", t = "a" 输出：0
示例 4：输入：s = "abe", t = "bbc" 输出：10
提示：1 <= s.length, t.length <= 100
s 和 t 都只包含小写英文字母。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^3) |
O(1) |
| 02 |
暴力法 |
O(n^4) |
O(n) |
| 03 |
动态规划 |
O(n^2) |
O(n^2) |
func countSubstrings(s string, t string) int {
res := 0
for i := 0; i < len(s); i++ {
for j := 0; j < len(t); j++ {
diff := 0
for k := 0; i+k < len(s) && j+k < len(t); k++ {
if s[i+k] != t[j+k] {
diff++
}
if diff > 1 {
break
}
if diff == 1 {
res++
}
}
}
}
return res
}
# 2
func countSubstrings(s string, t string) int {
res := 0
for i := 0; i < len(s); i++ {
for j := i + 1; j <= len(s); j++ {
length := j - i
newStr := s[i:j]
for k := 0; k <= len(t)-length; k++ {
b := t[k : k+length]
if compare(newStr, b) {
res++
}
}
}
}
return res
}
func compare(a, b string) bool {
count := 0
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
count++
}
if count >= 2 {
return false
}
}
if count == 0 {
return false
}
return true
}
# 3
func countSubstrings(s, t string) int {
res := 0
m, n := len(s), len(t)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
same := make([][]int, m+1)
for i := 0; i <= m; i++ {
same[i] = make([]int, n+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if s[i] == t[j] {
dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j]
same[i+1][j+1] = same[i][j] + 1
} else {
dp[i+1][j+1] = same[i][j] + 1
}
res = res + dp[i+1][j+1]
}
}
return res
}
1641.统计字典序元音字符串的数目(3)
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，
s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例 1：输入：n = 1 输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
示例 2：输入：n = 2 输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
示例 3：输入：n = 33 输出：66045
提示：1 <= n <= 50
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(1) |
| 03 |
数学 |
O(1) |
O(1) |
func countVowelStrings(n int) int {
dp := make([][5]int, n+1)
dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4] = 1, 1, 1, 1, 1
for i := 1; i <= n; i++ {
for j := 0; j < 5; j++ {
for k := 0; k <= j; k++ {
dp[i][j] = dp[i][j] + dp[i-1][k]
}
}
}
res := 0
for i := 0; i < 5; i++ {
res = res + dp[n-1][i]
}
return res
}
# 2
func countVowelStrings(n int) int {
dp := make([]int, 5)
dp[0] = 1
for i := 0; i < n; i++ {
for j := 1; j < 5; j++ {
dp[j] = dp[j] + dp[j-1]
}
}
res := 0
for i := 0; i < 5; i++ {
res = res + dp[i]
}
return res
}
# 3
func countVowelStrings(n int) int {
return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24
}
1642.可以到达的最远建筑(2)
给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
示例 1：输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。
示例 2：输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 输出：7
示例 3：输入：heights = [14,3,19,3], bricks = 17, ladders = 0 输出：3
提示：1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
堆 |
O(nlog(n)) |
O(n) |
| 02 |
二分查找 |
O(nlog(n)^2) |
O(n) |
func furthestBuilding(heights []int, bricks int, ladders int) int {
if len(heights) <= 1 {
return 0
}
intHeap := &IntHeap{}
heap.Init(intHeap)
need := 0
for i := 1; i < len(heights); i++ {
need = heights[i] - heights[i-1]
if need <= 0 {
continue
}
heap.Push(intHeap, need)
if intHeap.Len() > ladders {
need = heap.Pop(intHeap).(int)
if need > bricks {
return i - 1
}
bricks = bricks - need
}
}
return len(heights) - 1
}
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
}
# 2
func furthestBuilding(heights []int, bricks int, ladders int) int {
left, right := 0, len(heights)
res := 0
for left <= right {
mid := left + (right-left)/2
if check(heights[0:mid], bricks, ladders) {
left = mid + 1
res = mid
} else {
right = mid - 1
}
}
return res - 1
}
func check(heights []int, bricks int, ladders int) bool {
arr := make([]int, 0)
for i := 1; i < len(heights); i++ {
need := heights[i] - heights[i-1]
if need > 0 {
arr = append(arr, need)
}
}
sort.Ints(arr)
i := 0
for ; i < len(arr); i++ {
if bricks-arr[i] >= 0 {
bricks = bricks - arr[i]
continue
}
if ladders > 0 {
ladders--
continue
}
break
}
return i == len(arr)
}
1647.字符频次唯一的最小删除次数(1)
如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。
例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。
示例 1：输入：s = "aab" 输出：0
解释：s 已经是优质字符串。
示例 2：输入：s = "aaabbbcc" 输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。
示例 3：输入：s = "ceabaacb" 输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
提示：1 <= s.length <= 10^5 s 仅含小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序+贪心 |
O(n) |
O(1) |
func minDeletions(s string) int {
m := make(map[int]int)
for i := 0; i < len(s); i++ {
m[int(s[i])]++
}
arr := make([]int, 0)
for _, v := range m {
arr = append(arr, v)
}
sort.Ints(arr)
M := make(map[int]bool)
res := 0
for i := len(arr) - 1; i >= 0; i-- {
if M[arr[i]] == false {
M[arr[i]] = true
continue
}
j := arr[i]
for j >= 0 {
if M[j] == false {
M[j] = true
res = res + arr[i] - j
break
}
j--
}
if j == -1 {
res = res + arr[i]
}
}
return res
}
1648.销售价值减少的颜色球(2)
你有一些球的库存inventory，里面包含着不同颜色的球。一个顾客想要任意颜色 总数为orders的球。
这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的同色球的数目。
比方说还剩下6个黄球，那么顾客买第一个黄球的时候该黄球的价值为6。
这笔交易以后，只剩下5个黄球了，所以下一个黄球的价值为5（也就是球的价值随着顾客购买同色球是递减的）
给你整数数组inventory，其中inventory[i]表示第i种颜色球一开始的数目。
同时给你整数orders，表示顾客总共想买的球数目。你可以按照 任意顺序卖球。
请你返回卖了 orders个球以后 最大总价值之和。
由于答案可能会很大，请你返回答案对 109+ 7取余数的结果。
示例 1：输入：inventory = [2,5], orders = 4 输出：14
解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。
最大总和为 2 + 5 + 4 + 3 = 14 。
示例 2：输入：inventory = [3,5], orders = 6 输出：19
解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。
最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。
示例 3：输入：inventory = [2,8,4,10,6], orders = 20 输出：110
示例 4：输入：inventory = [1000000000], orders = 1000000000 输出：21
解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。
500000000500000000 对 109 + 7 取余为 21 。
提示：1 <= inventory.length <= 105
1 <= inventory[i] <= 109
1 <= orders <= min(sum(inventory[i]), 109)
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(nlog(n)) |
O(n) |
| 02 |
二分查找 |
O(nlog(n)) |
O(1) |
func maxProfit(inventory []int, orders int) int {
inventory = append(inventory, 0)
sort.Ints(inventory)
n := len(inventory)
res := 0
for i := n - 1; i >= 1; i-- {
if orders <= 0 {
break
}
total := (n - i) * (inventory[i] - inventory[i-1])
if total <= orders {
sum := (inventory[i-1] + 1 + inventory[i]) * (inventory[i] - inventory[i-1]) / 2 * (n - i)
res = (res + sum) % 1000000007
orders = orders - total
} else {
a, b := orders/(n-i), orders%(n-i)
start := inventory[i] - a + 1
sum := (start+inventory[i])*a/2*(n-i) + b*(start-1)
res = (res + sum) % 1000000007
orders = 0
}
}
return res
}
# 2
func maxProfit(inventory []int, orders int) int {
left, right := 0, math.MaxInt32
target := 0
for left <= right {
target = left + (right-left)/2
sum := 0
count := 0
for i := 0; i < len(inventory); i++ {
if inventory[i] >= target {
count++
sum = sum + (inventory[i] - target)
}
}
if sum > orders {
left = target + 1
} else if sum+count <= orders {
right = target - 1
} else {
break
}
}
res := 0
temp := 0
for i := 0; i < len(inventory); i++ {
if inventory[i] > target {
res = (res + getCount(target+1, inventory[i])) % 1000000007
temp = temp + inventory[i] - target
}
}
return (res + (orders-temp)*target) % 1000000007
}
func getCount(a, b int) int {
return (a + b) * (b - a + 1) / 2
}
1653.使字符串平衡的最少删除次数(4)
给你一个字符串s，它仅包含字符'a' 和'b'。
你可以删除s中任意数目的字符，使得s 平衡。
我们称s平衡的当不存在下标对(i,j)满足i < j 且s[i] = 'b'同时s[j]= 'a'。
请你返回使 s平衡的 最少删除次数。
示例 1：输入：s = "aababbab" 输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
示例 2：输入：s = "bbaaaaabb" 输出：2
解释：唯一的最优解是删除最前面两个字符。
提示：1 <= s.length <= 105
s[i]要么是'a' 要么是'b'。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前缀和+后缀和 |
O(n) |
O(n) |
| 02 |
栈 |
O(n) |
O(n) |
| 03 |
遍历 |
O(n) |
O(1) |
| 04 |
动态规划 |
O(n) |
O(n) |
func minimumDeletions(s string) int {
n := len(s)
dpA := make([]int, n)
dpB := make([]int, n)
if s[0] == 'a' {
dpA[0] = 1
}
for i := 1; i < n; i++ {
if s[i] == 'a' {
dpA[i] = dpA[i-1] + 1
} else {
dpA[i] = dpA[i-1]
}
}
if s[n-1] == 'b' {
dpB[n-1] = 1
}
for i := n - 2; i >= 0; i-- {
if s[i] == 'b' {
dpB[i] = dpB[i+1] + 1
} else {
dpB[i] = dpB[i+1]
}
}
res := 0
for i := 0; i < n; i++ {
res = max(res, dpA[i]+dpB[i])
}
return n - res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func minimumDeletions(s string) int {
res := 0
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
if s[i] == 'b' {
stack = append(stack, 'b')
} else {
if len(stack) > 0 {
res++
stack = stack[:len(stack)-1]
}
}
}
return res
}
# 3
func minimumDeletions(s string) int {
aCount := 0
for i := 0; i < len(s); i++ {
if s[i] == 'a' {
aCount = aCount + 1
}
}
res := aCount
bCount := 0
for i := 0; i < len(s); i++ {
if s[i] == 'a' {
aCount--
} else {
bCount++
}
res = min(res, aCount+bCount)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 4
func minimumDeletions(s string) int {
n := len(s)
dp := make([][2]int, n+1)
for i := 0; i < n; i++ {
if s[i] == 'a' {
dp[i+1][0] = dp[i][0]
dp[i+1][1] = dp[i][1] + 1
} else {
dp[i+1][0] = dp[i][0] + 1
dp[i+1][1] = min(dp[i][0], dp[i][1])
}
}
return min(dp[n][0], dp[n][1])
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1654.到家的最少跳跃次数(2)
有一只跳蚤的家在数轴上的位置x处。请你帮助它从位置0出发，到达它的家。
跳蚤跳跃的规则如下：
它可以 往前 跳恰好 a个位置（即往右跳）。
它可以 往后跳恰好 b个位置（即往左跳）。
它不能 连续 往后跳 2 次。
它不能跳到任何forbidden数组中的位置。
跳蚤可以往前跳 超过它的家的位置，但是它 不能跳到负整数的位置。
给你一个整数数组forbidden，其中forbidden[i]是跳蚤不能跳到的位置，同时给你整数a，b和x，
请你返回跳蚤到家的最少跳跃次数。
如果没有恰好到达 x的可行方案，请你返回 -1 。
示例 1：输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
示例 2：输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11 输出：-1
示例 3：输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7 输出：2
解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
提示：1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden中所有位置互不相同。
位置x不在 forbidden中。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
广度优先搜索 |
O(n) |
O(n) |
| 02 |
深度优先搜索 |
O(n) |
O(n) |
func minimumJumps(forbidden []int, a int, b int, x int) int {
m := make([]bool, 6001)
for i := 0; i < len(forbidden); i++ {
m[forbidden[i]] = true
}
queue := make([][2]int, 0)
queue = append(queue, [2]int{0, 0})
res := -1
for len(queue) > 0 {
length := len(queue)
res++
for i := 0; i < length; i++ {
index, dir := queue[i][0], queue[i][1]
if index == x {
return res
}
if dir == 0 && index-b > 0 && m[index-b] == false {
m[index-b] = true
queue = append(queue, [2]int{index - b, 1})
}
if index+a < len(m) && m[index+a] == false {
m[index+a] = true
queue = append(queue, [2]int{index + a, 0})
}
}
queue = queue[length:]
}
return -1
}
# 2
var m []bool
func minimumJumps(forbidden []int, a int, b int, x int) int {
m = make([]bool, 6001)
for i := 0; i < len(forbidden); i++ {
m[forbidden[i]] = true
}
return dfs(0, 0, a, b, x)
}
func dfs(index int, dir int, a int, b int, x int) int {
if index == x {
return 0
}
res := -1
if index+a < len(m) && m[index+a] == false {
m[index+a] = true
res = dfs(index+a, 0, a, b, x)
if res != -1 {
return res + 1
}
}
if dir == 0 && index-b > 0 && m[index-b] == false {
res = dfs(index-b, 1, a, b, x)
if res != -1 {
return res + 1
}
}
return res
}
1657.确定两个字符串是否接近(1)
如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
操作 1：交换任意两个 现有 字符。
例如，abcde -> aecdb
操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
示例 1：输入：word1 = "abc", word2 = "bca" 输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"
示例 2：输入：word1 = "a", word2 = "aa" 输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
示例 3：输入：word1 = "cabbba", word2 = "abbccc" 输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"
示例 4：输入：word1 = "cabbba", word2 = "aabbss" 输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
提示：1 <= word1.length, word2.length <= 105
word1 和 word2 仅包含小写英文字母
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(n) |
O(1) |
func closeStrings(word1 string, word2 string) bool {
if len(word1) != len(word2) {
return false
}
arr1 := make([]int, 26)
arr2 := make([]int, 26)
m1 := make(map[uint8]bool)
m2 := make(map[uint8]bool)
for i := 0; i < len(word1); i++ {
arr1[word1[i]-'a']++
arr2[word2[i]-'a']++
m1[word1[i]-'a'] = true
m2[word2[i]-'a'] = true
}
for key := range m1 {
if m2[key] != true {
return false
}
}
sort.Ints(arr1)
sort.Ints(arr2)
for i := 0; i < 26; i++ {
if arr1[i] != arr2[i] {
return false
}
}
return true
}
1658.将x减到0的最小操作数(2)
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，
然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x恰好 减到0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：输入：nums = [1,1,4,2,3], x = 5 输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：输入：nums = [5,6,7,8,9], x = 4 输出：-1
示例 3：输入：nums = [3,2,20,1,1,3], x = 10 输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
前后缀和 |
O(n) |
O(n) |
| 02 |
滑动窗口 |
O(n) |
O(1) |
func minOperations(nums []int, x int) int {
n := len(nums)
res := n + 1
sum := 0
for i := 0; i < n; i++ {
sum = sum + nums[i]
}
if sum < x {
return -1
}
if sum == x {
return n
}
left := make([]int, n)
right := make([]int, n)
mLeft := make(map[int]int)
mRight := make(map[int]int)
left[0] = nums[0]
mLeft[nums[0]] = 0
right[n-1] = nums[n-1]
mRight[nums[n-1]] = n - 1
if left[0] == x || right[n-1] == x {
return 1
}
for i := 1; i < n; i++ {
left[i] = left[i-1] + nums[i]
mLeft[left[i]] = i
if left[i] == x {
res = min(res, i+1)
}
}
for i := n - 2; i >= 0; i-- {
right[i] = right[i+1] + nums[i]
mRight[right[i]] = i
if right[i] == x {
res = min(res, n-i)
}
}
for i := 1; i < n; i++ {
left := left[i]
if index, ok := mRight[x-left]; ok && i < index {
target := n - (index - i - 1)
res = min(res, target)
}
}
if res == n+1 {
return -1
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minOperations(nums []int, x int) int {
n := len(nums)
sum := 0
for i := 0; i < n; i++ {
sum = sum + nums[i]
}
target := sum - x
left := 0
right := 0
res := -1
cur := 0
for left < n {
if right < n {
cur = cur + nums[right]
right++
}
for cur > target && left < n {
cur = cur - nums[left]
left++
}
if cur == target {
res = max(res, right-left)
}
if right == n {
left++
}
}
if res == -1 {
return -1
}
return n - res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1663.具有给定数值的最小字符串(2)
小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，
c 的数值为 3 ，以此类推。
字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。
例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
x 是 y 的一个前缀；
如果 i 是x[i] != y[i] 的第一个位置，且 x[i]在字母表中的位置比y[i]靠前。
示例 1：输入：n = 3, k = 27 输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。
示例 2：输入：n = 5, k = 73 输出："aaszz"
提示：1 <= n <= 105
n <= k <= 26 * n
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func getSmallestString(n int, k int) string {
res := ""
k = k - n
a := k / 25
b := k % 25
right := a
var left, middle int
if b == 0 {
left = n - right
middle = 0
} else {
left = n - right - 1
middle = b
}
res = res + strings.Repeat("a", left)
if middle > 0 {
res = res + string('a'+middle)
}
res = res + strings.Repeat("z", right)
return res
}
# 2
func getSmallestString(n int, k int) string {
arr := make([]byte, n)
k = k - n
for i := n - 1; i >= 0; i-- {
if k > 25 {
arr[i] = 'z'
k = k - 25
} else {
arr[i] = byte('a' + k)
k = 0
}
}
return string(arr)
}
1664.生成平衡数组的方案数(2)
给你一个整数数组nums。你需要选择 恰好一个下标（下标从 0开始）并删除对应的元素。
请注意剩下元素的下标可能会因为删除操作而发生改变。
比方说，如果nums = [6,1,7,4,1]，那么：
选择删除下标 1 ，剩下的数组为nums = [6,7,4,1]。
选择删除下标2，剩下的数组为nums = [6,1,4,1]。
选择删除下标4，剩下的数组为nums = [6,1,7,4]。
如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。
请你返回删除操作后，剩下的数组nums是平衡数组 的方案数。
示例 1：输入：nums = [2,1,6,4] 输出：1
解释：删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。
示例 2：输入：nums = [1,1,1] 输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。
示例 3：输入：nums = [1,2,3] 输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
前缀和 |
O(n) |
O(n) |
func waysToMakeFair(nums []int) int {
res := 0
a := 0
b := 0
for i := 0; i < len(nums); i++ {
if i%2 == 0 {
a = a + nums[i]
} else {
b = b + nums[i]
}
}
x, y := 0, 0
for i := 0; i < len(nums); i++ {
if i%2 == 0 {
a = a - nums[i]
} else {
b = b - nums[i]
}
even := x + b
odd := y + a
if even == odd {
res++
}
if i%2 == 0 {
x = x + nums[i]
} else {
y = y + nums[i]
}
}
return res
}
# 2
func waysToMakeFair(nums []int) int {
n := len(nums)
dp := make([]int, n+1)
for i := 0; i < n; i++ {
if i%2 == 0 {
dp[i+1] = dp[i] + nums[i]
} else {
dp[i+1] = dp[i] - nums[i]
}
}
res := 0
for i := 0; i < n; i++ {
if dp[i] == dp[n]-dp[i+1] {
res++
}
}
return res
}
1669.合并两个链表(2)
给你两个链表list1 和list2，它们包含的元素分别为n 个和m 个。
请你将list1中第a个节点到第b个节点删除，并将list2接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 1：输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。
提示：3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
res := &ListNode{}
temp := res
for i := 0; i < a; i++{
temp.Next = list1
temp = temp.Next
list1 = list1.Next
}
for list2 != nil{
temp.Next = list2
temp = temp.Next
list2 = list2.Next
}
for i := a; i <= b; i++{
list1 = list1.Next
}
for list1 != nil{
temp.Next = list1
temp = temp.Next
list1 = list1.Next
}
return res.Next
}
# 2
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
cur := list1
for i := 0; i < a-1; i++ {
cur = cur.Next
}
temp := cur.Next
for i := 0; i < (b - a + 1); i++ {
temp = temp.Next
}
cur.Next = list2
for cur.Next != nil {
cur = cur.Next
}
cur.Next = temp
return list1
}
1670.设计前中后队列(1)
请你设计一个队列，支持在前，中，后三个位置的 push和 pop操作。
请你完成FrontMiddleBack类：
FrontMiddleBack()初始化队列。
void pushFront(int val) 将val添加到队列的 最前面。
void pushMiddle(int val) 将val添加到队列的 正中间。
void pushBack(int val)将val添加到队里的 最后面。
int popFront()将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
int popMiddle() 将 正中间的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
请注意当有两个中间位置的时候，选择靠前面的位置进行操作。比方说：
将 6添加到[1, 2, 3, 4, 5]的中间位置，结果数组为[1, 2, 6, 3, 4, 5]。
从[1, 2, 3, 4, 5, 6]的中间位置弹出元素，返回3，数组变为[1, 2, 4, 5, 6]。
示例 1：输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle",
"pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：[null, null, null, null, null, 1, 3, 4, 2, -1]
解释：FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1); // [1]
q.pushBack(2); // [1, 2]
q.pushMiddle(3); // [1, 3, 2]
q.pushMiddle(4); // [1, 4, 3, 2]
q.popFront(); // 返回 1 -> [4, 3, 2]
q.popMiddle(); // 返回 3 -> [4, 2]
q.popMiddle(); // 返回 4 -> [2]
q.popBack(); // 返回 2 -> []
q.popFront(); // 返回 -1 -> [] （队列为空）
提示：1 <= val <= 109
最多调用1000次pushFront，pushMiddle，pushBack，popFront，popMiddle和popBack 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组 |
O(n^2) |
O(n) |
type FrontMiddleBackQueue struct {
arr []int
}
func Constructor() FrontMiddleBackQueue {
return FrontMiddleBackQueue{}
}
func (this *FrontMiddleBackQueue) PushFront(val int) {
this.arr = append([]int{val}, this.arr...)
}
func (this *FrontMiddleBackQueue) PushMiddle(val int) {
mid := len(this.arr) / 2
this.arr = append(this.arr[:mid], append([]int{val}, this.arr[mid:]...)...)
}
func (this *FrontMiddleBackQueue) PushBack(val int) {
this.arr = append(this.arr, val)
}
func (this *FrontMiddleBackQueue) PopFront() int {
var res int
if len(this.arr) == 0 {
return -1
}
res = this.arr[0]
this.arr = this.arr[1:]
return res
}
func (this *FrontMiddleBackQueue) PopMiddle() int {
var res, mid int
if len(this.arr) == 0 {
return -1
}
if len(this.arr)%2 == 1 {
mid = len(this.arr) / 2
} else {
mid = len(this.arr)/2 - 1
}
res = this.arr[mid]
this.arr = append(this.arr[:mid], this.arr[mid+1:]...)
return res
}
func (this *FrontMiddleBackQueue) PopBack() int {
var res int
if len(this.arr) == 0 {
return -1
}
res = this.arr[len(this.arr)-1]
this.arr = this.arr[:len(this.arr)-1]
return res
}
1673.找出最具竞争力的子序列(1)
给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
在子序列a 和子序列b 第一个不相同的位置上，如果a中的数字小于 b 中对应的数字，
那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。
例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上，4 小于 5 。
示例 1：输入：nums = [3,5,2,6], k = 2 输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，
[2,6] 最具竞争力。
示例 2：输入：nums = [2,4,3,3,5,4,9,6], k = 4 输出：[2,3,3,4]
提示：1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈 |
O(n) |
O(n) |
func mostCompetitive(nums []int, k int) []int {
stack := make([]int, 0)
k = len(nums) - k
for i := 0; i < len(nums); i++ {
value := nums[i]
for len(stack) > 0 && stack[len(stack)-1] > value && k > 0 {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, value)
}
stack = stack[:len(stack)-k]
return stack
}
1674.使数组互补的最少操作次数(1)
给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。
每一次操作，你可以将 nums 中的任何整数替换为1到limit 之间的另一个整数。
如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i]都等于同一个数，
则数组 nums 是 互补的 。
例如，数组 [1,2,3,4] 是互补的，因为对于所有下标i ，nums[i] + nums[n - 1 - i] = 5 。
返回使数组 互补 的 最少操作次数。
示例 1：输入：nums = [1,2,4,3], limit = 4 输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。
示例 2：输入：nums = [1,2,2,1], limit = 2 输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。
示例 3：输入：nums = [1,2,1,2], limit = 2 输出：0
解释：nums 已经是互补的。
提示：n == nums.length
2 <= n<=105
1 <= nums[i]<= limit <=105
n 是偶数。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
差分数组 |
O(n) |
O(n) |
func minMoves(nums []int, limit int) int {
n := len(nums)
arr := make([]int, 2*limit+2)
for i := 0; i < n/2; i++ {
a, b := nums[i], nums[n-1-i]
arr[2] = arr[2] + 2
arr[2*limit+1] = arr[2*limit+1] - 2
arr[1+min(a, b)] = arr[1+min(a, b)] - 1
arr[limit+max(a, b)+1] = arr[limit+max(a, b)+1] + 1
arr[a+b] = arr[a+b] - 1
arr[a+b+1] = arr[a+b+1] + 1
}
res := n
sum := 0
for i := 2; i <= 2*limit; i++ {
sum = sum + arr[i]
if res > sum {
res = sum
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
1679.K和数对的最大数目(3)
给你一个整数数组 nums 和一个整数 k 。
每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
返回你可以对数组执行的最大操作数。
示例 1：输入：nums = [1,2,3,4], k = 5 输出：2
解释：开始时 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。
示例 2：输入：nums = [3,1,3,4,3], k = 6 输出：1
解释：开始时 nums = [3,1,3,4,3]：
- 移出前两个 3 ，之后nums = [1,4,3]
不再有和为 6 的数对，因此最多执行 1 次操作。
提示：1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希 |
O(n) |
O(n) |
| 02 |
排序 |
O(nlog(n)) |
O(1) |
| 03 |
哈希 |
O(n) |
O(n) |
func maxOperations(nums []int, k int) int {
res := 0
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
if m[k-nums[i]] > 0 {
res++
m[k-nums[i]]--
} else {
m[nums[i]]++
}
}
return res
}
# 2
func maxOperations(nums []int, k int) int {
sort.Ints(nums)
res := 0
left := 0
right := len(nums) - 1
for left < right {
sum := nums[left] + nums[right]
if sum == k {
res++
left++
right--
} else if sum > k {
right--
} else {
left++
}
}
return res
}
# 3
func maxOperations(nums []int, k int) int {
res := 0
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
for key := range m {
res = res + min(m[key], m[k-key])
}
return res / 2
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
1680.连接连续二进制数字(2)
给你一个整数n，请你将1到 n的二进制表示连接起来，
并返回连接结果对应的 十进制数字对 109+ 7取余的结果。
示例 1：输入：n = 1 输出：1
解释：二进制的 "1" 对应着十进制的 1 。
示例 2：输入：n = 3 输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。
示例 3：输入：n = 12 输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后，结果为 505379714 。
提示：1 <= n <= 10^5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
package main
import "math/bits"
func main() {
}
func concatenatedBinary(n int) int {
res := 0
for i := 1; i <= n; i++ {
length := bits.Len(uint(i))
res = (res<<length + i) % 1000000007
}
return res
}
# 2
func concatenatedBinary(n int) int {
res := 0
length := 0
for i := 1; i <= n; i++ {
if i&(i-1) == 0 {
length++
}
res = (res<<length + i) % 1000000007
}
return res
}
1685.有序数组中差绝对值之和(2)
给你一个 非递减有序整数数组nums。
请你建立并返回一个整数数组result，它跟nums长度相同，
且result[i]等于nums[i]与数组中所有其他元素差的绝对值之和。
换句话说，result[i]等于sum(|nums[i]-nums[j]|) ，
其中0 <= j < nums.length 且j != i（下标从 0 开始）。
示例 1：输入：nums = [2,3,5] 输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
示例 2：输入：nums = [1,4,6,8,10] 输出：[24,15,13,15,21]
提示：2 <= nums.length <= 105
1 <= nums[i] <= nums[i + 1] <= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
前缀和 |
O(n) |
O(n) |
func getSumAbsoluteDifferences(nums []int) []int {
n := len(nums)
res := make([]int, 0)
right := 0
left := 0
for i := 1; i < n; i++ {
right = right + (nums[i] - nums[0])
}
res = append(res, right)
for i := 1; i < n; i++ {
diff := nums[i] - nums[i-1]
left = left + diff*i
right = right - diff*(n-i)
res = append(res, left+right)
}
return res
}
# 2
func getSumAbsoluteDifferences(nums []int) []int {
n := len(nums)
res := make([]int, 0)
arr := make([]int, 0)
sum := 0
for i := 0; i < n; i++ {
sum = sum + nums[i]
arr = append(arr, sum)
}
res = append(res, sum-n*nums[0])
for i := 1; i < n; i++ {
left := nums[i]*i - arr[i-1]
right := (sum - arr[i]) - nums[i]*(n-1-i)
res = append(res, left+right)
}
return res
}
1686.石子游戏VI(1)
Alice 和Bob 轮流玩一个游戏，Alice 先手。
一堆石子里总共有n个石子，轮到某个玩家时，他可以移出一个石子并得到这个石子的价值。
Alice 和 Bob 对石子价值有不一样的的评判标准。双方都知道对方的评判标准。
给你两个长度为 n的整数数组aliceValues 和bobValues。
aliceValues[i] 和bobValues[i]分别表示 Alice 和 Bob 认为第i个石子的价值。
所有石子都被取完后，得分较高的人为胜者。
如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略进行游戏。
请你推断游戏的结果，用如下的方式表示：
如果 Alice 赢，返回1。
如果 Bob 赢，返回-1。
如果游戏平局，返回0。
示例 1：输入：aliceValues = [1,3], bobValues = [2,1] 输出：1
解释：如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。
示例 2：输入：aliceValues = [1,2], bobValues = [3,1] 输出：0
解释：Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。
示例 3：输入：aliceValues = [2,4,3], bobValues = [1,6,7] 输出：-1
解释：不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。
提示：n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
贪心 |
O(nlog(n)) |
O(n) |
func stoneGameVI(aliceValues []int, bobValues []int) int {
arr := make([][2]int, len(aliceValues))
for i := 0; i < len(arr); i++ {
arr[i] = [2]int{i, aliceValues[i] + bobValues[i]}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][1] > arr[j][1]
})
a, b := 0, 0
for i := 0; i < len(arr); i++ {
if i%2 == 0 {
a = a + aliceValues[arr[i][0]]
} else {
b = b + bobValues[arr[i][0]]
}
}
if a == b {
return 0
} else if a > b {
return 1
}
return -1
}
1689.十-二进制数的最少数目(1)
如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。
例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。
给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。
示例 1：输入：n = "32" 输出：3
解释：10 + 11 + 11 = 32
示例 2：输入：n = "82734" 输出：8
示例 3：输入：n = "27346209830709182346" 输出：9
提示：1 <= n.length <= 105
n 仅由数字组成
n 不含任何前导零并总是表示正整数
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
func minPartitions(n string) int {
res := 0
for i := 0; i < len(n); i++ {
value := int(n[i] - '0')
if value > res {
res = value
}
}
return res
}
1690.石子游戏VII(4)
石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，
并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。
爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，
如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
示例 1：输入：stones = [5,3,1,4,2] 输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2：输入：stones = [7,90,5,1,100,10,10,2] 输出：122
提示：n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
递归 |
O(n^2) |
O(n^2) |
| 03 |
动态规划 |
O(n^2) |
O(n^2) |
| 04 |
动态规划 |
O(n^2) |
O(n) |
func stoneGameVII(stones []int) int {
n := len(stones)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + stones[i]
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
for j := 2; j <= n; j++ {
for i := 0; i+j <= n; i++ {
left := arr[i+j] - arr[i+1] - dp[i+1][i+j-1]
right := arr[i+j-1] - arr[i] - dp[i][i+j-2]
dp[i][i+j-1] = max(left, right)
}
}
return dp[0][n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
var dp [][]int
var arr []int
func stoneGameVII(stones []int) int {
n := len(stones)
arr = make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + stones[i]
}
dp = make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
if i == j {
continue
}
dp[i][j] = -1
}
}
dfs(0, n-1)
return dp[0][n-1]
}
func dfs(i, j int) int {
if dp[i][j] != -1 {
return dp[i][j]
}
left := arr[j+1] - arr[i+1] - dfs(i+1, j)
right := arr[j] - arr[i] - dfs(i, j-1)
dp[i][j] = max(left, right)
return dp[i][j]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func stoneGameVII(stones []int) int {
n := len(stones)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + stones[i]
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
left := arr[j+1] - arr[i+1] - dp[i+1][j]
right := arr[j] - arr[i] - dp[i][j-1]
dp[i][j] = max(left, right)
}
}
return dp[0][n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 4
func stoneGameVII(stones []int) int {
n := len(stones)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
arr[i+1] = arr[i] + stones[i]
}
dp := make([]int, n)
for i := n - 2; i >= 0; i-- {
sum := stones[i]
for j := i + 1; j < n; j++ {
sum = sum + stones[j]
left := sum - stones[i] - dp[j]
right := sum - stones[j] - dp[j-1]
dp[j] = max(left, right)
}
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1695.删除子数组的最大得分(1)
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。
删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是a 的一个子数组。
示例 1：输入：nums = [4,2,4,5,6] 输出：17
解释：最优子数组是 [2,4,5,6]
示例 2：输入：nums = [5,2,1,2,5,2,1,2,5] 输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
提示：1 <= nums.length <= 105
1 <= nums[i] <= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
滑动窗口 |
O(n) |
O(n) |
func maximumUniqueSubarray(nums []int) int {
res := 0
sum := 0
m := make(map[int]int)
left := 0
for i := 0; i < len(nums); i++ {
m[nums[i]]++
sum = sum + nums[i]
for m[nums[i]] > 1 {
m[nums[left]]--
sum = sum - nums[left]
left++
}
if sum > res {
res = sum
}
}
return res
}
1696.跳跃游戏VI(4)
给你一个下标从 0 开始的整数数组 nums和一个整数 k。
一开始你在下标0处。每一步，你最多可以往前跳k步，但你不能跳出数组的边界。
也就是说，你可以从下标i跳到[i + 1， min(n - 1, i + k)]包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1），你的 得分为经过的所有数字之和。
请你返回你能得到的 最大得分。
示例 1：输入：nums = [1,-1,-2,4,-7,3], k = 2 输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：输入：nums = [10,-5,-2,4,0,3], k = 3 输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出：0
提示：1 <= nums.length, k <= 105
-104<= nums[i]<= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
栈辅助 |
O(n) |
O(n) |
| 04 |
堆 |
O(nlog(n)) |
O(n) |
func maxResult(nums []int, k int) int {
n := len(nums)
dp := make([]int, n)
if k > n {
k = n
}
dp[0] = nums[0]
maxValue := nums[0]
for i := 1; i < len(nums); i++ {
if i <= k {
dp[i] = maxValue + nums[i]
maxValue = max(maxValue, dp[i])
} else {
if maxValue == dp[i-1-k] {
maxValue = getMaxValue(dp[i-k : i])
}
dp[i] = maxValue + nums[i]
maxValue = max(maxValue, dp[i])
}
}
return dp[n-1]
}
func getMaxValue(arr []int) int {
maxValue := arr[0]
for i := 0; i < len(arr); i++ {
if arr[i] > maxValue {
maxValue = arr[i]
}
}
return maxValue
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maxResult(nums []int, k int) int {
n := len(nums)
dp := make([]int, n)
if k > n {
k = n
}
dp[0] = nums[0]
maxValue := nums[0]
maxIndex := 0
for i := 1; i < len(nums); i++ {
if i <= k {
dp[i] = maxValue + nums[i]
if dp[i] >= maxValue {
maxValue = dp[i]
maxIndex = i
}
} else {
if i-k > maxIndex {
maxValue = dp[maxIndex+1]
for j := maxIndex + 1; j < i; j++ {
if dp[j] >= maxValue {
maxValue = dp[j]
maxIndex = j
}
}
}
dp[i] = maxValue + nums[i]
if dp[i] >= maxValue {
maxValue = dp[i]
maxIndex = i
}
}
}
return dp[n-1]
}
# 3
func maxResult(nums []int, k int) int {
n := len(nums)
if k > n {
k = n
}
res := nums[0]
stack := make([][2]int, 0)
stack = append(stack, [2]int{0, nums[0]})
for i := 1; i < len(nums); i++ {
if stack[0][0] < i-k {
stack = stack[1:]
}
res = stack[0][1] + nums[i]
for len(stack) > 0 && stack[len(stack)-1][1] < res {
stack = stack[:len(stack)-1]
}
stack = append(stack, [2]int{i, res})
}
return res
}
# 4
func maxResult(nums []int, k int) int {
n := len(nums)
if k > n {
k = n
}
res := nums[0]
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
heap.Push(&intHeap, [2]int{0, nums[0]})
for i := 1; i < len(nums); i++ {
for i-intHeap[0][0] > k {
heap.Pop(&intHeap)
}
res = intHeap[0][1] + nums[i]
heap.Push(&intHeap, [2]int{i, res})
}
return res
}
type IntHeap [][2]int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i][1] > h[j][1]
}
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.([2]int))
}
func (h *IntHeap) Pop() interface{} {
value := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return value
}
1601-1700-Hard
1606.找到处理最多请求的服务器(2)
你有 k个服务器，编号为 0到 k-1，它们可以同时处理多个请求组。
每个服务器有无穷的计算能力但是 不能同时处理超过一个请求。请求分配到服务器的规则如下：
第i（序号从 0 开始）个请求到达。
如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
如果第(i % k)个服务器空闲，那么对应服务器会处理该请求。
否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。
比方说，如果第 i个服务器在忙，那么会查看第 (i+1)个服务器，第 (i+2)个服务器等等。
给你一个 严格递增的正整数数组arrival，表示第i个任务的到达时间，和另一个数组load，
其中load[i]表示第i个请求的工作量（也就是服务器完成它所需要的时间）。
你的任务是找到 最繁忙的服务器。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。
请你返回包含所有最繁忙服务器序号的列表，你可以以任意顺序返回这个列表。
示例 1：输入：k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 输出：[1]
解释：所有服务器一开始都是空闲的。
前 3 个请求分别由前 3 台服务器依次处理。
请求 3 进来的时候，服务器 0 被占据，所以它呗安排到下一台空闲的服务器，也就是服务器 1 。
请求 4 进来的时候，由于所有服务器都被占据，该请求被舍弃。
服务器 0 和 2 分别都处理了一个请求，服务器 1 处理了两个请求。所以服务器 1 是最忙的服务器。
示例 2：输入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2] 输出：[0]
解释：前 3 个请求分别被前 3 个服务器处理。
请求 3 进来，由于服务器 0 空闲，它被服务器 0 处理。
服务器 0 处理了两个请求，服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。
示例 3：输入：k = 3, arrival = [1,2,3], load = [10,12,11] 输出：[0,1,2]
解释：每个服务器分别处理了一个请求，所以它们都是最忙的服务器。
示例 4：输入：k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2] 输出：[1]
示例 5：输入：k = 1, arrival = [1], load = [1] 输出：[0]
提示：1 <= k <= 105
1 <= arrival.length, load.length <= 105
arrival.length == load.length
1 <= arrival[i], load[i] <= 109
arrival保证 严格递增。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双堆 |
O(nlog(n)) |
O(n) |
| 02 |
堆+二分查找 |
O(nlog(n)) |
O(n) |
func busiestServers(k int, arrival []int, load []int) []int {
n := len(arrival)
res := make([]int, 0)
freeHeap := &mixHeap{isBig: false}
busyHeap := &mixHeap{isBig: false}
for i := 0; i < k; i++ {
freeHeap.push([]int{i})
}
arr := make([]int, k)
for i := 0; i < n; i++ {
start := arrival[i]
for busyHeap.Len() > 0 && busyHeap.Top()[0] <= start {
id := busyHeap.pop()[1]
freeHeap.push([]int{i + ((id-i)%k+k)%k})
}
if freeHeap.Len() > 0 {
id := freeHeap.pop()[0] % k
busyHeap.push([]int{start + load[i], id})
arr[id]++
}
}
var maxValue int
for i := 0; i < len(arr); i++ {
if arr[i] > maxValue {
maxValue = arr[i]
res = []int{i}
} else if arr[i] == maxValue {
res = append(res, i)
}
}
return res
}
type mixHeap struct {
arr [][]int
isBig bool
}
func (m *mixHeap) Len() int {
return len(m.arr)
}
func (m *mixHeap) Swap(i, j int) {
m.arr[i], m.arr[j] = m.arr[j], m.arr[i]
}
func (m *mixHeap) Less(i, j int) bool {
if m.isBig {
return m.arr[i][0] > m.arr[j][0]
}
return m.arr[i][0] < m.arr[j][0]
}
func (m *mixHeap) Push(x interface{}) {
m.arr = append(m.arr, x.([]int))
}
func (m *mixHeap) Pop() interface{} {
value := (m.arr)[len(m.arr)-1]
m.arr = (m.arr)[:len(m.arr)-1]
return value
}
func (m *mixHeap) push(x []int) {
heap.Push(m, x)
}
func (m *mixHeap) pop() []int {
return heap.Pop(m).([]int)
}
func (m *mixHeap) Top() []int {
if m.Len() > 0 {
return m.arr[0]
}
return nil
}
# 2
func busiestServers(k int, arrival []int, load []int) []int {
n := len(arrival)
res := make([]int, 0)
arr := make([]int, k)
free := make([]int, k)
for i := 0; i < k; i++ {
free[i] = i
}
busyHeap := make(IntHeap, 0)
heap.Init(&busyHeap)
for i := 0; i < n; i++ {
start := arrival[i]
for busyHeap.Len() > 0 && busyHeap[0][0] <= start {
id := busyHeap[0][1]
index := sort.SearchInts(free, id)
free = append(free[:index], append([]int{id}, free[index:]...)...)
heap.Pop(&busyHeap)
}
if len(free) == 0 {
continue
}
id := sort.SearchInts(free, i%k)
if id == len(free) {
id = 0
}
arr[free[id]]++
heap.Push(&busyHeap, []int{start + load[i], free[id]})
free = append(free[:id], free[id+1:]...)
}
var maxValue int
for i := 0; i < len(arr); i++ {
if arr[i] > maxValue {
maxValue = arr[i]
res = []int{i}
} else if arr[i] == maxValue {
res = append(res, i)
}
}
return res
}
type IntHeap [][]int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
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{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
1611.使整数变为0的最少操作次数(3)
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。
示例 1：输入：n = 0 输出：0
示例 2：输入：n = 3 输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。
示例 3：输入：n = 6 输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。
示例 4：输入：n = 9 输出：14
示例 5：输入：n = 333 输出：393
提示：0 <= n <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
格雷码 |
O(log(n)) |
O(1) |
| 03 |
遍历 |
O(log(n)) |
O(1) |
func minimumOneBitOperations(n int) int {
res := 0
if n == 0 {
return 0
}
for i := 0; (1 << i) <= n; i++ {
if (1<<i)&n > 0 {
total := 1<<(1+i) - 1
res = total - res
}
}
return res
}
# 2
func minimumOneBitOperations(n int) int {
res := 0
for n > 0 {
res = res ^ n
n = n / 2
}
return res
}
# 3
func minimumOneBitOperations(n int) int {
res := 0
if n == 0 {
return 0
}
length := bits.Len(uint(n))
flag := 1
for i := 0; (1 << i) <= n; i++ {
if (1<<(length-1-i))&n > 0 {
total := 1<<(length-i) - 1
res = res + total*flag
flag = -1 * flag
}
}
return res
}
1649.通过指令创建有序数组(2)
给你一个整数数组instructions，你需要根据instructions中的元素创建一个有序数组。
一开始你有一个空的数组nums，你需要从左到右遍历instructions中的元素，将它们依次插入nums数组中。
每一次插入操作的代价是以下两者的 较小值：
nums中 严格小于instructions[i]的数字数目。
nums中 严格大于instructions[i]的数字数目。
比方说，如果要将3 插入到nums = [1,2,3,5]，
那么插入操作的代价为min(2, 1) (元素1和2小于3，元素5大于3），插入后nums 变成[1,2,3,3,5]。
请你返回将instructions中所有元素依次插入nums后的 总最小代价。由于答案会很大，请将它对109 + 7取余后返回。
示例 1：输入：instructions = [1,5,6,2] 输出：1
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。
插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。
插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。
示例 2:输入：instructions = [1,2,3,6,5,4] 输出：3
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。
插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。
插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。
插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。
插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。
示例 3：输入：instructions = [1,3,3,3,2,4,2,1,2] 输出：4
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。
插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。
插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。
插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。
提示：1 <= instructions.length <= 105
1 <= instructions[i] <= 105
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
树状数组 |
O(nlog(n)) |
O(n) |
| 02 |
线段树 |
O(nlog(n)) |
O(n) |
var mod = 1000000007
func createSortedArray(instructions []int) int {
res := 0
c = make([]int, 100002)
length = 100001
for i := 0; i < len(instructions); i++ {
value := instructions[i]
upData(value, 1)
left := getSum(value - 1)
right := getSum(100000) - getSum(value)
res = (res + min(left, right)) % mod
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
var length int
var c []int
func lowBit(x int) int {
return x & (-x)
}
func upData(i, k int) {
for i <= length {
c[i] = c[i] + k
i = i + lowBit(i)
}
}
func getSum(i int) int {
res := 0
for i > 0 {
res = res + c[i]
i = i - lowBit(i)
}
return res
}
# 2
var mod = 1000000007
func createSortedArray(instructions []int) int {
res := 0
n := 100001
arr = make([]int, n*4+1)
for i := 0; i < len(instructions); i++ {
x := instructions[i]
left := query(0, 1, n, 1, x-1)
right := query(0, 1, n, x+1, n)
res = (res + min(left, right)) % mod
update(0, 1, n, x)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
var arr []int
func update(id int, left, right, x int) {
if left > x || right < x {
return
}
arr[id]++
if left == right {
return
}
mid := left + (right-left)/2
update(2*id+1, left, mid, x)
update(2*id+2, mid+1, right, x)
}
func query(id int, left, right, queryLeft, queryRight int) int {
if left > queryRight || right < queryLeft {
return 0
}
if queryLeft <= left && right <= queryRight {
return arr[id]
}
mid := left + (right-left)/2
return query(id*2+1, left, mid, queryLeft, queryRight) +
query(id*2+2, mid+1, right, queryLeft, queryRight)
}
1655.分配重复整数
题目
给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值。
同时你有 m个顾客的订单 quantity，其中，整数quantity[i]是第i位顾客订单的数目。
请你判断是否能将 nums中的整数分配给这些顾客，且满足：
第i位顾客 恰好有quantity[i]个整数。
第i位顾客拿到的整数都是 相同的。
每位顾客都满足上述两个要求。
如果你可以分配 nums中的整数满足上面的要求，那么请返回true，否则返回 false。
示例 1：输入：nums = [1,2,3,4], quantity = [2] 输出：false
解释：第 0 位顾客没办法得到两个相同的整数。
示例 2：输入：nums = [1,2,3,3], quantity = [2] 输出：true
解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3：输入：nums = [1,1,2,2], quantity = [2,2] 输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。
示例 4：输入：nums = [1,1,2,3], quantity = [2,2] 输出：false
解释：尽管第 0 位顾客可以得到 [1,1] ，第 1 位顾客没法得到 2 个一样的整数。
示例 5：输入：nums = [1,1,1,1,1], quantity = [2,3] 输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [1,1,1] 。
提示：n == nums.length
1 <= n <= 105
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 105
nums中至多有50个不同的数字。
解题思路
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(1) |
1665.完成所有任务的最少初始能量(1)
给你一个任务数组tasks ，其中tasks[i] = [actuali, minimumi]：
actuali是完成第 i个任务 需要耗费的实际能量。
minimumi是开始第 i个任务前需要达到的最低能量。
比方说，如果任务为[10, 12]且你当前的能量为11，那么你不能开始这个任务。
如果你当前的能量为13，你可以完成这个任务，且完成它后剩余能量为 3。
你可以按照 任意顺序完成任务。
请你返回完成所有任务的 最少初始能量。
示例 1：输入：tasks = [[1,2],[2,4],[4,8]] 输出：8
解释：一开始有 8 能量，我们按照如下顺序完成任务：
- 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
- 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
- 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。
示例 2：输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]] 输出：32
解释：一开始有 32 能量，我们按照如下顺序完成任务：
- 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
- 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
- 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
- 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
- 完成第 5 个任务，剩余能量为 9 - 8 = 1 。
示例 3：输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]] 输出：27
解释：一开始有 27 能量，我们按照如下顺序完成任务：
- 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
- 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
- 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
- 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
- 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
- 完成第 6 个任务，剩余能量为 12 - 6 = 6 。
提示：1 <= tasks.length <= 105
1 <= actuali<= minimumi<= 104
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(1) |
func minimumEffort(tasks [][]int) int {
sort.Slice(tasks, func(i, j int) bool {
return tasks[i][1]-tasks[i][0] > tasks[j][1]-tasks[j][0]
})
total := 0
res := 0
for i := 0; i < len(tasks); i++ {
res = max(res, total+tasks[i][1])
total = total + tasks[i][0]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1671.得到山形数组的最少删除次数(1)
我们定义arr是 山形数组当且仅当它满足：
arr.length >= 3
存在某个下标i（从 0 开始）满足0 < i < arr.length - 1且：
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给你整数数组nums，请你返回将 nums变成 山形状数组的最少删除次数。
示例 1：输入：nums = [1,3,1] 输出：0
解释：数组本身就是山形数组，所以我们不需要删除任何元素。
示例 2：输入：nums = [2,1,1,5,6,2,3,1]输出：3
解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。
示例 3：输入：nums = [4,3,2,1,1,2,3,1]输出：4
提示：输入：nums = [1,2,3,4,4,3,2,1]输出：1
提示：3 <= nums.length <= 1000
1 <= nums[i] <= 109
题目保证nums 删除一些元素后一定能得到山形数组。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
func minimumMountainRemovals(nums []int) int {
n := len(nums)
res := 0
left := make([]int, n)
right := make([]int, n)
for i := 0; i < n; i++ {
left[i] = 0
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
left[i] = max(left[j]+1, left[i])
}
}
}
for i := n - 1; i >= 0; i-- {
right[i] = 0
for j := n - 1; j > i; j-- {
if nums[j] < nums[i] {
right[i] = max(right[j]+1, right[i])
}
}
}
for i := 1; i < n-1; i++ {
res = max(res, left[i]+right[i]+1)
}
return n - res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1675.数组的最小偏移量(1)
给你一个由 n 个正整数组成的数组 nums 。
你可以对数组的任意元素执行任意次数的两类操作：
如果元素是 偶数 ，除以 2
例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
如果元素是 奇数 ，乘上 2
例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]
数组的 偏移量 是数组中任意两个元素之间的 最大差值 。
返回数组在执行某些操作之后可以拥有的 最小偏移量 。
示例 1：输入：nums = [1,2,3,4] 输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1
示例 2：输入：nums = [4,1,5,20,3] 输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3
示例 3：输入：nums = [2,10,8] 输出：3
提示：n == nums.length
2 <= n <= 105
1 <= nums[i] <= 109
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
堆 |
O(nlog(n)) |
O(n) |
func minimumDeviation(nums []int) int {
intHeap := make(IntHeap, 0)
heap.Init(&intHeap)
minValue := math.MaxInt32
for i := 0; i < len(nums); i++ {
if nums[i]%2 == 1 {
nums[i] = nums[i] * 2
}
heap.Push(&intHeap, nums[i])
minValue = min(minValue, nums[i])
}
res := intHeap[0] - minValue
for intHeap.Len() > 0 && intHeap[0]%2 == 0 {
node := heap.Pop(&intHeap).(int)
minValue = min(minValue, node/2)
heap.Push(&intHeap, node/2)
res = min(res, intHeap[0]-minValue)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
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
}
1691.堆叠长方体的最大高度(1)
给你 n 个长方体 cuboids ，
其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。
请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，
你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体cuboids 可以得到的 最大高度 。
示例 1：输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]] 输出：190
解释：第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。
示例 2：输入：cuboids = [[38,25,45],[76,35,3]] 输出：76
解释：无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。
示例 3：输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出：102
解释：重新排列长方体后，可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下，这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。
提示：n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序+动态规划 |
O(n^2) |
O(n) |
func maxHeight(cuboids [][]int) int {
for i := 0; i < len(cuboids); i++ {
arr := cuboids[i]
sort.Ints(arr)
cuboids[i] = arr
}
sort.Slice(cuboids, func(i, j int) bool {
if cuboids[i][0] == cuboids[j][0] {
if cuboids[i][1] == cuboids[j][1] {
return cuboids[i][2] < cuboids[j][2]
}
return cuboids[i][1] < cuboids[j][1]
}
return cuboids[i][0] < cuboids[j][0]
})
n := len(cuboids)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = cuboids[i][2]
}
res := dp[0]
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if cuboids[i][0] >= cuboids[j][0] &&
cuboids[i][1] >= cuboids[j][1] &&
cuboids[i][2] >= cuboids[j][2] {
dp[i] = max(dp[i], dp[j]+cuboids[i][2])
}
}
res = max(res, dp[i])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}