2301-2400-Easy¶
2303.计算应缴税款总额(2)¶
题目
给你一个下标从 0 开始的二维整数数组 brackets ，其中 brackets[i] = [upperi, percenti] ，
表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。
税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。
税款计算方式如下：
不超过 upper0 的收入按税率 percent0 缴纳
接着 upper1 - upper0 的部分按税率 percent1 缴纳
然后 upper2 - upper1 的部分按税率 percent2 缴纳
以此类推
给你一个整数 income 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10-5 的结果将被视作正确答案。
示例 1：输入：brackets = [[3,50],[7,10],[12,25]], income = 10 输出：2.65000
解释：前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。
接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。
最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。
需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。
示例 2：输入：brackets = [[1,0],[4,25],[5,50]], income = 2 输出：0.25000
解释：前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。
剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。
需要支付的税款总计 $0 + $0.25 = $0.25 。
示例 3：输入：brackets = [[2,50]], income = 0 输出：0.00000
解释：没有收入，无需纳税，需要支付的税款总计 $0 。
提示：1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi 按递增顺序排列
upperi 中的所有值 互不相同
最后一个税级的上限大于等于 income
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func calculateTax(brackets [][]int, income int) float64 {
res := 0
prev := 0
for i := 0; i < len(brackets); i++ {
a, b := brackets[i][0], brackets[i][1]
if income <= a {
res = res + (income-prev)*b
break
}
res = res + (a-prev)*b
prev = a
}
return float64(res) / 100
}
# 2
func calculateTax(brackets [][]int, income int) float64 {
res := 0
prev := 0
for i := 0; i < len(brackets); i++ {
a, b := brackets[i][0], brackets[i][1]
if income < prev {
break
}
res = res + (min(income, a)-prev)*b
prev = a
}
return float64(res) / 100
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2309.兼具大小写的最好英文字母(1)¶
题目
给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。
如果不存在满足条件的字母，则返回一个空字符串。
最好 英文字母的大写和小写形式必须 都 在 s 中出现。
英文字母 b 比另一个英文字母a更好 的前提是：英文字母表中，b 在 a 之 后 出现。
示例 1：输入：s = "lEeTcOdE" 输出："E"
解释：字母 'E' 是唯一一个大写和小写形式都出现的字母。
示例 2：输入：s = "arRAzFif" 输出："R"
解释：字母 'R' 是大写和小写形式都出现的最好英文字母。
注意 'A' 和 'F' 的大写和小写形式也都出现了，但是 'R' 比 'F' 和 'A' 更好。
示例 3：输入：s = "AbCdEfGhIjK" 输出：""
解释：不存在大写和小写形式都出现的字母。
提示：1 <= s.length <= 1000
s 由小写和大写英文字母组成
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
func greatestLetter(s string) string {
m := make(map[byte]bool)
for i := 0; i < len(s); i++ {
m[s[i]] = true
}
for i := 25; i >= 0; i-- {
x := byte('a' + i)
y := byte('A' + i)
if m[x] == true && m[y] == true {
return string(y)
}
}
return ""
}
2315.统计星号(2)¶
题目
给你一个字符串s，每两个连续竖线'|'为 一对。换言之，第一个和第二个'|'为一对，第三个和第四个'|'为一对，以此类推。
请你返回 不在 竖线对之间，s中'*'的数目。
注意，每个竖线'|'都会 恰好属于一个对。
示例 1：输入：s = "l|*e*et|c**o|*de|" 输出：2
解释：不在竖线对之间的字符加粗加斜体后，得到字符串："l|*e*et|c**o|*de|" 。
第一和第二条竖线 '|' 之间的字符不计入答案。
同时，第三条和第四条竖线 '|' 之间的字符也不计入答案。
不在竖线对之间总共有 2 个星号，所以我们返回 2 。
示例 2：输入：s = "iamprogrammer" 输出：0
解释：在这个例子中，s 中没有星号。所以返回 0 。
示例 3：输入：s = "yo|uar|e**|b|e***au|tifu|l" 输出：5
解释：需要考虑的字符加粗加斜体后："yo|uar|e**|b|e***au|tifu|l" 。不在竖线对之间总共有 5 个星号。所以我们返回 5 。
提示：1 <= s.length <= 1000
s只包含小写英文字母，竖线'|'和星号'*'。
s包含 偶数个竖线'|' 。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 内置函数 | O(n) | O(n) |
| 02 | 遍历 | O(n) | O(1) |
func countAsterisks(s string) int {
res := 0
arr := strings.Split(s, "|")
for i := 0; i < len(arr); i = i + 2 {
res = res + strings.Count(arr[i], "*")
}
return res
}
# 2
func countAsterisks(s string) int {
res := 0
count := 0
for i := 0; i < len(s); i++ {
if s[i] == '|' {
count++
}
if s[i] == '*' && count%2 == 0 {
res++
}
}
return res
}
2319.判断矩阵是否是一个X矩阵(1)¶
题目
如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：
矩阵对角线上的所有元素都 不是 0
矩阵中所有其他元素都是 0
给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。
示例 1：输入：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]] 输出：true
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 是一个 X 矩阵。
示例 2：输入：grid = [[5,7,0],[0,3,1],[0,5,0]] 输出：false
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 不是一个 X 矩阵。
提示：n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 105
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(1) |
func checkXMatrix(grid [][]int) bool {
n := len(grid)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i == j || (i+j == n-1) {
if grid[i][j] == 0 {
return false
}
} else {
if grid[i][j] != 0 {
return false
}
}
}
}
return true
}
2325.解密消息(1)¶
题目
给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：
使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
将替换表与普通英文字母表对齐，形成对照表。
按照对照表 替换 message 中的每个字母。
空格 ' ' 保持不变。
例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），
据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。
返回解密后的消息。
示例 1：输入：key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
输出："this is a secret"
解释：对照表如上图所示。
提取 "the quick brown fox jumps over the lazy dog" 中每个字母的首次出现可以得到替换表。
示例 2：输入：key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
输出："the five boxing wizards jump quickly"
解释：对照表如上图所示。
提取 "eljuxhpwnyrdgtqkviszcfmabo" 中每个字母的首次出现可以得到替换表。
提示：26 <= key.length <= 2000
key 由小写英文字母及 ' ' 组成
key 包含英文字母表中每个字符（'a' 到 'z'）至少一次
1 <= message.length <= 2000
message 由小写英文字母和 ' ' 组成
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(n) |
func decodeMessage(key string, message string) string {
m := make(map[byte]byte)
cur := byte('a')
for i := 0; i < len(key); i++ {
if key[i] != ' ' && m[key[i]] == 0 {
m[key[i]] = cur
cur++
}
}
arr := []byte(message)
for i := 0; i < len(message); i++ {
if message[i] != ' ' {
arr[i] = m[message[i]]
}
}
return string(arr)
}
2331.计算布尔二叉树的值(1)¶
题目
给你一棵 完整二叉树的根，这棵树有以下特征：
叶子节点要么值为0要么值为1，其中0 表示False，1 表示True。
非叶子节点 要么值为 2要么值为 3，其中2表示逻辑或OR ，3表示逻辑与AND。
计算一个节点的值方式如下：
如果节点是个叶子节点，那么节点的 值为它本身，即True或者False。
否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算。
返回根节点root的布尔运算值。
完整二叉树是每个节点有 0个或者 2个孩子的二叉树。
叶子节点是没有孩子的节点。
示例 1：输入：root = [2,1,3,null,null,0,1] 输出：true
解释：上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ，所以我们返回 true 。
示例 2：输入：root = [0] 输出：false
解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
提示：树中节点数目在[1, 1000]之间。
0 <= Node.val <= 3
每个节点的孩子数为0 或2。
叶子节点的值为0或1。
非叶子节点的值为2或3 。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 递归 | O(n) | O(log(n)) |
func evaluateTree(root *TreeNode) bool {
if root.Left == nil || root.Right == nil { // 叶子节点
return root.Val == 1 //
}
if root.Val == 2 {
return evaluateTree(root.Left) || evaluateTree(root.Right)
}
if root.Val == 3 {
return evaluateTree(root.Left) && evaluateTree(root.Right)
}
return true
}
2335.装满杯子需要的最短总时长(2)¶
题目
现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，
其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。
返回装满所有杯子所需的 最少 秒数。
示例 1：输入：amount = [1,4,2]输出：4
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。
示例 2：输入：amount = [5,4,4] 输出：7
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。
示例 3：输入：amount = [5,0,0] 输出：5
解释：每秒装满一杯冷水。
提示：amount.length == 3
0 <= amount[i] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 模拟 | O(n) | O(1) |
| 02 | 数学 | O(1) | O(1) |
func fillCups(amount []int) int {
res := 0
for {
sort.Ints(amount)
if amount[1] == 0 {
break
}
res++
amount[1]--
amount[2]--
}
return res + amount[2]
}
# 2
func fillCups(amount []int) int {
sort.Ints(amount)
if amount[0]+amount[1] <= amount[2] {
return amount[2]
}
// a+b>c
// 超出部分：a+b-c
return (amount[0]+amount[1]-amount[2]+1)/2 + amount[2]
}
2341.数组能形成多少数对(2)¶
题目
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：
从 nums 选出 两个 相等的 整数
从 nums 中移除这两个整数，形成一个 数对
请你在 nums 上多次执行此操作直到无法继续执行。
返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，
其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。
示例 1：输入：nums = [1,3,2,1,3,2,2] 输出：[3,1]
解释：nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。
示例 2：输入：nums = [1,1] 输出：[1,0]
解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。
示例 3：输入：nums = [0] 输出：[0,1]
解释：无法形成数对，nums 中剩下 1 个数字。
提示：1 <= nums.length <= 100
0 <= nums[i] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(n) |
| 02 | 哈希 | O(n) | O(n) |
func numberOfPairs(nums []int) []int {
a, b := 0, 0
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
for _, v := range m {
a = a + v/2
b = b + v%2
}
return []int{a, b}
}
# 2
func numberOfPairs(nums []int) []int {
a := 0
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
if m[nums[i]]%2 == 0 {
a++
}
}
return []int{a, len(nums) - 2*a}
}
2347.最好的扑克手牌(1)¶
题目
给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌，第 i 张牌大小为 ranks[i] ，花色为 suits[i] 。
下述是从好到坏你可能持有的 手牌类型 ：
"Flush"：同花，五张相同花色的扑克牌。
"Three of a Kind"：三条，有 3 张大小相同的扑克牌。
"Pair"：对子，两张大小一样的扑克牌。
"High Card"：高牌，五张大小互不相同的扑克牌。
请你返回一个字符串，表示给定的 5 张牌中，你能组成的 最好手牌类型 。
注意：返回的字符串 大小写 需与题目描述相同。
示例 1：输入：ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"] 输出："Flush"
解释：5 张扑克牌的花色相同，所以返回 "Flush" 。
示例 2：输入：ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"] 输出："Three of a Kind"
解释：第一、二和四张牌组成三张相同大小的扑克牌，所以得到 "Three of a Kind" 。
注意我们也可以得到 "Pair" ，但是 "Three of a Kind" 是更好的手牌类型。
有其他的 3 张牌也可以组成 "Three of a Kind" 手牌类型。
示例 3：输入：ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"] 输出："Pair"
解释：第一和第二张牌大小相同，所以得到 "Pair" 。
我们无法得到 "Flush" 或者 "Three of a Kind" 。
提示：ranks.length == suits.length == 5
1 <= ranks[i] <= 13
'a' <= suits[i] <= 'd'
任意两张扑克牌不会同时有相同的大小和花色。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(1) |
func bestHand(ranks []int, suits []byte) string {
if strings.Count(string(suits), string(suits[0])) == 5 {
return "Flush"
}
m := make(map[int]int)
for _, v := range ranks {
m[v]++
if m[v] == 3 {
return "Three of a Kind"
}
}
for _, v := range m {
if v >= 2 {
return "Pair"
}
}
return "High Card"
}
2351.第一个出现两次的字母(2)¶
题目
给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。
注意：如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
s 包含至少一个出现两次的字母。
示例 1：输入：s = "abccbaacz" 输出："c"
解释：字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。
示例 2：输入：s = "abcdd" 输出："d"
解释：只有字母 'd' 出现两次，所以返回 'd' 。
提示：2 <= s.length <= 100
s 由小写英文字母组成
s 包含至少一个重复字母
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(1) |
| 02 | 位运算 | O(n) | O(1) |
func repeatedCharacter(s string) byte {
m := make(map[byte]bool)
for _, v := range s {
if m[byte(v)] == true {
return byte(v)
}
m[byte(v)] = true
}
return 0
}
# 2
func repeatedCharacter(s string) byte {
mask := 0
for _, v := range s {
target := 1 << (v - 'a')
if mask&target != 0 {
return byte(v)
}
mask = mask | target
}
return 0
}
2357.使数组中所有元素都等于零(1)¶
题目
给你一个非负整数数组 nums 。在一步操作中，你必须：
选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
nums 中的每个正整数都减去 x。
返回使 nums 中所有元素都等于 0 需要的 最少 操作数。
示例 1：输入：nums = [1,5,0,3,5] 输出：3
解释：第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。
示例 2：输入：nums = [0] 输出：0
解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。
提示：1 <= nums.length <= 100
0 <= nums[i] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(1) |
func minimumOperations(nums []int) int {
m := make(map[int]bool)
for i := 0; i < len(nums); i++ {
if nums[i] > 0 {
m[nums[i]] = true // 统计不为0的数字去重个数
}
}
return len(m)
}
2363. 合并相似的物品(1)¶
题目
给你两个二维整数数组items1 和items2，表示两个物品集合。每个数组items有以下特质：
items[i] = [valuei, weighti] 其中valuei表示第i件物品的价值，weighti表示第 i件物品的 重量。
items中每件物品的价值都是 唯一的。
请你返回一个二维数组ret，其中ret[i] = [valuei, weighti]，weighti是所有价值为valuei物品的重量之和。
注意：ret应该按价值 升序排序后返回。
示例 1：输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]] 输出：[[1,6],[3,9],[4,5]]
解释：value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 5 ，总重量为 5 。
所以，我们返回 [[1,6],[3,9],[4,5]] 。
示例 2：输入：items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]] 输出：[[1,4],[2,4],[3,4]]
解释：value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
所以，我们返回 [[1,4],[2,4],[3,4]] 。
示例 3：输入：items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]] 输出：[[1,7],[2,4],[7,1]]
解释：value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。
所以，我们返回 [[1,7],[2,4],[7,1]] 。
提示：1 <= items1.length, items2.length <= 1000
items1[i].length == items2[i].length == 2
1 <= valuei, weighti <= 1000
items1中每个 valuei都是 唯一的。
items2中每个 valuei都是 唯一的。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希+拍下 | O(nlog(n)) | O(n) |
func mergeSimilarItems(items1 [][]int, items2 [][]int) [][]int {
m := make(map[int]int)
for i := 0; i < len(items1); i++ {
a, b := items1[i][0], items1[i][1]
m[a] += b
}
for i := 0; i < len(items2); i++ {
a, b := items2[i][0], items2[i][1]
m[a] += b
}
res := make([][]int, 0)
for k, v := range m {
res = append(res, []int{k, v})
}
sort.Slice(res, func(i, j int) bool {
return res[i][0] < res[j][0]
})
return res
}
2367.算术三元组的数目(1)¶
题目
给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个 算术三元组 ：
i < j < k ，
nums[j] - nums[i] == diff 且
nums[k] - nums[j] == diff
返回不同 算术三元组 的数目。
示例 1：输入：nums = [0,1,4,6,7,10], diff = 3 输出：2
解释：(1, 2, 4) 是算术三元组：7 - 4 == 3 且 4 - 1 == 3 。
(2, 4, 5) 是算术三元组：10 - 7 == 3 且 7 - 4 == 3 。
示例 2：输入：nums = [4,5,6,7,8,9], diff = 2 输出：2
解释：(0, 2, 4) 是算术三元组：8 - 6 == 2 且 6 - 4 == 2 。
(1, 3, 5) 是算术三元组：9 - 7 == 2 且 7 - 5 == 2 。
提示：3 <= nums.length <= 200
0 <= nums[i] <= 200
1 <= diff <= 50
nums 严格 递增
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(n) |
func arithmeticTriplets(nums []int, diff int) int {
res := 0
m := make(map[int]bool)
for i := 0; i < len(nums); i++ {
m[nums[i]] = true
}
for i := 0; i < len(nums); i++ {
if m[nums[i]-diff] && m[nums[i]+diff] {
res++
}
}
return res
}
2373. 矩阵中的局部最大值(1)¶
题目
给你一个大小为 n x n 的整数矩阵 grid 。
生成一个大小为(n - 2) x (n - 2) 的整数矩阵 maxLocal ，并满足：
maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值 。
换句话说，我们希望找出 grid 中每个3 x 3 矩阵中的最大值。
返回生成的矩阵。
示例 1：输入：grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]] 输出：[[9,9],[8,6]]
解释：原矩阵和生成的矩阵如上图所示。
注意，生成的矩阵中，每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。
示例 2：输入：grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
输出：[[2,2,2],[2,2,2],[2,2,2]]
解释：注意，2 包含在 grid 中每个 3 x 3 的矩阵中。
提示：n == grid.length == grid[i].length
3 <= n <= 100
1 <= grid[i][j] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^2) | O(n^2) |
func largestLocal(grid [][]int) [][]int {
n := len(grid)
res := make([][]int, n-2)
for i := 0; i < n-2; i++ {
res[i] = make([]int, n-2)
}
for i := 1; i < n-1; i++ {
for j := 1; j < n-1; j++ {
maxValue := grid[i][j]
for a := i - 1; a <= i+1; a++ {
for b := j - 1; b <= j+1; b++ {
maxValue = max(maxValue, grid[a][b])
}
}
res[i-1][j-1] = maxValue
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2379.得到K个黑块的最少涂色次数¶
题目¶
给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，
表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。
给你一个整数 k ，表示想要 连续 黑色块的数目。
每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。
示例 1：输入：blocks = "WBBWWBBWBW", k = 7 输出：3
解释：一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。
示例 2：输入：blocks = "WBWBBBW", k = 2 输出：0
解释：不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。
提示：n == blocks.length
1 <= n <= 100
blocks[i] 要么是 'W' ，要么是 'B' 。
1 <= k <= n
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 暴力法 | O(n^2) | O(n^2) |
2301-2400-Medium¶
2304.网格中的最小路径代价(2)¶
题目
给你一个下标从 0 开始的整数矩阵grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。
你可以在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，
且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格。
注意：在最后一行中的单元格不能触发移动。
每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，
其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从grid 最后一行的单元格移动的代价可以忽略。
grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。
从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
示例 1：输入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]] 输出：17
解释：最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。
示例 2：输入：grid = [[5,1,2],[4,0,3]],
moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]] 输出：6
解释：最小代价的路径是 2 -> 3 。
- 路径途经单元格值之和 2 + 3 = 5 。
- 从 2 移动到 3 的代价为 1 。
路径总代价为 5 + 1 = 6 。
提示：m == grid.length
n == grid[i].length
2 <= m, n <= 50
grid 由从 0 到 m * n - 1 的不同整数组成
moveCost.length == m * n
moveCost[i].length == n
1 <= moveCost[i][j] <= 100
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划-二维 | O(n^3) | O(n^2) |
| 02 | 动态规划-一维 | O(n^3) | O(n) |
func minPathCost(grid [][]int, moveCost [][]int) int {
n, m := len(grid), len(grid[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
for j := 0; j < m; j++ {
dp[0][j] = grid[0][j] // 第一行的代价
}
for i := 1; i < n; i++ {
for j := 0; j < m; j++ {
value := math.MaxInt32
for k := 0; k < m; k++ {
// 上一行的代价+当前的单元值+移动的代价
prev := grid[i-1][k] // 上一层的值
value = min(value, dp[i-1][k]+grid[i][j]+moveCost[prev][j])
}
dp[i][j] = value
}
}
res := math.MaxInt32
for j := 0; j < m; j++ {
res = min(res, dp[n-1][j])
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func minPathCost(grid [][]int, moveCost [][]int) int {
n, m := len(grid), len(grid[0])
dp := make([]int, m)
copy(dp, grid[0])
for i := 1; i < n; i++ {
temp := make([]int, m)
for j := 0; j < m; j++ {
value := math.MaxInt32
for k := 0; k < m; k++ {
// 上一行的代价+当前的单元值+移动的代价
prev := grid[i-1][k] // 上一层的值
value = min(value, dp[k]+grid[i][j]+moveCost[prev][j])
}
temp[j] = value
}
copy(dp, temp)
}
res := math.MaxInt32
for j := 0; j < m; j++ {
res = min(res, dp[j])
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
2305.公平分发饼干(3)¶
题目
给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。
另给你一个整数 k 表示等待分发零食包的孩子数量，所有 零食包都需要分发。
在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。
分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。
返回所有分发的最小不公平程度。
示例 1：输入：cookies = [8,15,10,20,8], k = 2 输出：31
解释：一种最优方案是 [8,15,8] 和 [10,20] 。
- 第 1 个孩子分到 [8,15,8] ，总计 8 + 15 + 8 = 31 块饼干。
- 第 2 个孩子分到 [10,20] ，总计 10 + 20 = 30 块饼干。
分发的不公平程度为 max(31,30) = 31 。
可以证明不存在不公平程度小于 31 的分发方案。
示例 2：输入：cookies = [6,1,3,2,2,4,1,2], k = 3 输出：7
解释：一种最优方案是 [6,1]、[3,2,2] 和 [4,1,2] 。
- 第 1 个孩子分到 [6,1] ，总计 6 + 1 = 7 块饼干。
- 第 2 个孩子分到 [3,2,2] ，总计 3 + 2 + 2 = 7 块饼干。
- 第 3 个孩子分到 [4,1,2] ，总计 4 + 1 + 2 = 7 块饼干。
分发的不公平程度为 max(7,7,7) = 7 。
可以证明不存在不公平程度小于 7 的分发方案。
提示：2 <= cookies.length <= 8
1 <= cookies[i] <= 105
2 <= k <= cookies.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划-状态压缩-二维 | O(n*3^n) | O(n*2^n) |
| 02 | 动态规划-状态压缩-一维 | O(n*3^n) | O(2^n) |
| 03 | 回溯 | O(n^n) | O(n) |
# 题目同leetcode 1723.完成所有工作的最短时间
func distributeCookies(cookies []int, k int) int {
n := len(cookies)
total := 1 << n
sum := make([]int, total)
for i := 0; i < n; i++ { // 预处理：饼干分配的状态和，分配给某一个人的和
count := 1 << i
for j := 0; j < count; j++ {
sum[count|j] = sum[j] + cookies[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
}
}
dp := make([][]int, k) // f[i][j]=>给前i个人分配工作，饼干的分配情况为j时，最小不公平程度
for i := 0; i < k; i++ {
dp[i] = make([]int, total)
}
for i := 0; i < total; i++ { // 第0个人的时候
dp[0][i] = sum[i]
}
for i := 1; i < k; i++ {
for j := 0; j < total; j++ {
minValue := math.MaxInt32 // dp[i][j]未赋值，为0
for a := j; a > 0; a = (a - 1) & j { // 遍历得到比较小的子集：数字j二进制为1位置上的非0子集
// 取子集的补集：j-a 或者 使用异或j^a
// minValue = min(minValue, max(dp[i-1][j-a], sum[a]))
minValue = min(minValue, max(dp[i-1][j^a], sum[a]))
}
dp[i][j] = minValue
}
}
return dp[k-1][total-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
var res int
func distributeCookies(cookies []int, k int) int {
res = math.MaxInt32
dfs(cookies, make([]int, k), 0, 0, 0)
return res
}
// index => cookies的下标；count => 已经分配的个数
func dfs(cookies []int, arr []int, index int, maxValue int, count int) {
if maxValue > res { // 剪枝
return
}
if index == len(cookies) {
res = maxValue
return
}
if count < len(arr) {
arr[count] = cookies[index]
dfs(cookies, arr, index+1, max(maxValue, arr[count]), count+1)
arr[count] = 0
}
for i := 0; i < count; i++ {
arr[i] = arr[i] + cookies[index]
dfs(cookies, arr, index+1, max(maxValue, arr[i]), count)
arr[i] = arr[i] - cookies[index]
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2310.个位数字为K的整数之和(2)¶
题目
给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：
每个整数个位数字都是 k 。
所有整数之和是 num 。
返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。
注意：多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
个位数字 是数字最右边的数位。
示例 1：输入：num = 58, k = 9 输出：2
解释：多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。
另一个满足条件的多重集是 [19,39] 。
可以证明 2 是满足题目条件的多重集的最小长度。
示例 2：输入：num = 37, k = 2 输出：-1
解释：个位数字为 2 的整数无法相加得到 37 。
示例 3：输入：num = 0, k = 7 输出：0
解释：空多重集的和为 0 。
提示：0 <= num <= 3000
0 <= k <= 9
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 枚举 | O(n) | O(1) |
| 02 | 枚举 | O(1) | O(1) |
func minimumNumbers(num int, k int) int {
if num == 0 {
return 0
}
if k == 0 {
if num%10 == 0 {
return 1
}
return -1
}
if num%2 == 1 && k%2 == 0 {
return -1
}
for i := 1; i <= num; i++ {
sum := i * k
left := num - sum
if left%10 == 0 {
return i
}
if left < 0 {
return -1
}
}
return -1
}
# 2
func minimumNumbers(num int, k int) int {
if num == 0 {
return 0
}
for i := 1; i <= 10; i++ {
// 只考虑个位数
if i*k <= num && (i*k)%10 == num%10 {
return i
}
}
return -1
}
2311.小于等于K的最长二进制子序列(2)¶
题目
给你一个二进制字符串s和一个正整数k。
请你返回 s的 最长子序列，且该子序列对应的 二进制数字小于等于 k。
注意：子序列可以有 前导 0。 空字符串视为0。
子序列是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。
示例 1：输入：s = "1001010", k = 5 输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。
示例 2：输入：s = "00101001", k = 1 输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。
提示：1 <= s.length <= 1000
s[i] 要么是'0'，要么是'1' 。
1 <= k <= 109
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 贪心 | O(n) | O(1) |
| 02 | 贪心 | O(n) | O(1) |
func longestSubsequence(s string, k int) int {
res := 0
sum, bitValue := int64(0), int64(1)
target := int64(k)
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '0' { // 0全部加上
res++
} else if sum <= target {
sum = sum + bitValue
if sum <= target { // 小于<=k加上
res++
}
}
if sum <= target && bitValue <= target {
bitValue = bitValue * 2
}
}
return res
}
# 2
func longestSubsequence(s string, k int) int {
res := 0
sum, bitValue := 0, 1
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '0' { // 0全部加上
res++
} else {
if sum+bitValue <= k {
res++
sum = sum + bitValue
}
}
if bitValue <= k {
bitValue = bitValue * 2
}
}
return res
}
2316.统计无向图中无法互相到达点对数(2)¶
题目
给你一个整数n，表示一张无向图中有 n个节点，编号为0到n - 1。
同时给你一个二维整数数组edges，其中edges[i] = [ai, bi]表示节点ai 和bi之间有一条无向边。
请你返回 无法互相到达的不同 点对数目。
示例 1：输入：n = 3, edges = [[0,1],[0,2],[1,2]] 输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
示例 2：输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]] 输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。
提示：1 <= n <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不会有重复边。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 并查集 | O(nlog(n)) | O(n) |
| 02 | 深度优先搜索 | O(n) | O(n) |
func countPairs(n int, edges [][]int) int64 {
res := int64(0)
fa = Init(n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
union(a, b)
}
m := make(map[int]int)
for i := 0; i < n; i++ {
m[find(i)]++ // 统计每组个数
}
for _, v := range m {
res = res + int64(v)*int64(n-v)
}
return res / 2
}
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)
}
# 2
var arr [][]int
var visited []bool
var count int
func countPairs(n int, edges [][]int) int64 {
res := int64(0)
arr = make([][]int, n)
visited = make([]bool, n)
for i := 0; i < len(edges); i++ {
a, b := edges[i][0], edges[i][1]
arr[a] = append(arr[a], b)
arr[b] = append(arr[b], a)
}
for i := 0; i < n; i++ {
if visited[i] == false {
count = 0
dfs(i)
res = res + int64(count)*int64(n-count)
}
}
return res / 2
}
func dfs(start int) {
visited[start] = true
count++
for i := 0; i < len(arr[start]); i++ {
next := arr[start][i]
if visited[next] == false {
dfs(next)
}
}
}
2317.操作后的最大异或和(1)¶
题目
给你一个下标从 0开始的整数数组nums。一次操作中，选择 任意非负整数x和一个下标i，
更新nums[i]为nums[i] AND (nums[i] XOR x)。
注意，AND是逐位与运算，XOR是逐位异或运算。
请你执行 任意次更新操作，并返回nums中所有元素最大逐位异或和。
示例 1：输入：nums = [3,2,4,6] 输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。
示例 2：输入：nums = [1,2,3,9,2] 输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。
提示：1 <= nums.length <= 105
0 <= nums[i] <= 108
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 位运算 | O(n) | O(1) |
func maximumXOR(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
// 最大逐位异或和：在某位上有奇数个1，能达到最大
// 更新操作：and操作能把部分位从1置为0，但是不能把0修改为1
// 求解方案：使用更新操作把相同位置保留1个1，其它置为0 => 转为求位或
// => 有多少位存在1
res = res | nums[i] // XOR位或，只要该位为1，结果就是1
}
return res
}
2320.统计放置房子的方式数(3)¶
题目
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：输入：n = 1 输出：4
解释：可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。
示例 2：输入：n = 2 输出：9
解释：如上图所示，共有 9 种可能的放置方式。
提示：1 <= n <= 104
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划-二维 | O(n) | O(n) |
| 02 | 动态规划-一维 | O(n) | O(n) |
| 03 | 动态规划 | O(n) | O(1) |
var mod = 1000000007
func countHousePlacements(n int) int {
dp := make([][4]int, n+1)
dp[1][0] = 1 // 2侧没有房子
dp[1][1] = 1 // 1侧有房子：上
dp[1][2] = 1 // 1侧有房子：下
dp[1][3] = 1 // 2侧都有房子
for i := 2; i <= n; i++ {
dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % mod
dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % mod
dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % mod
dp[i][3] = (dp[i-1][0]) % mod
}
sum := 0
for i := 0; i < 4; i++ {
sum = (sum + dp[n][i]) % mod
}
return sum
}
# 2
var mod = 1000000007
func countHousePlacements(n int) int {
dp := make([]int, n+3) // 只考虑单侧的方案
dp[0] = 1
dp[1] = 2
for i := 2; i <= n; i++ {
// 不放；dp[i] = dp[i-1]
// 放: i-1不能放，dp[i] = dp[i-2]
dp[i] = (dp[i-1] + dp[i-2]) % mod
}
return dp[n] * dp[n] % mod // 考虑2侧情况
}
# 3
var mod = 1000000007
func countHousePlacements(n int) int {
var a, b, c, d int
a = 1 // 2侧没有房子
b = 1 // 1侧有房子：上
c = 1 // 1侧有房子：下
d = 1 // 2侧都有房子
for i := 2; i <= n; i++ {
a, b, c, d = (a+b+c+d)%mod, (a+c)%mod, (a+b)%mod, a%mod
}
return (a + b + c + d) % mod
}
2326.螺旋矩阵IV(1)¶
题目
给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。
链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。
返回生成的矩阵。
示例 1：输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释：上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。
示例 2：输入：m = 1, n = 4, head = [0,1,2] 输出：[[0,1,2,-1]]
解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。
注意，矩阵中剩下的空格用 -1 填充。
提示：1 <= m, n <= 105
1 <= m * n <= 105
链表中节点数目在范围 [1, m * n] 内
0 <= Node.val <= 1000
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n^2) | O(n^2) |
// 顺时针：上右下左
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
func spiralMatrix(m int, n int, head *ListNode) [][]int {
res := make([][]int, m)
for i := 0; i < m; i++ {
res[i] = make([]int, n)
for j := 0; j < n; j++ {
res[i][j] = -1
}
}
x, y, dir := 0, 0, 0
for ; head != nil; head = head.Next {
res[x][y] = head.Val
newX, newY := x+dx[dir], y+dy[dir]
if 0 > newX || newX >= m || 0 > newY || newY >= n || res[newX][newY] != -1 {
dir = (dir + 1) % 4 // 换方向
}
x = x + dx[dir]
y = y + dy[dir]
}
return res
}
2327.知道秘密的人数¶
题目¶
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 |
2332.坐上公交的最晚时间¶
题目¶
给你一个下标从 0开始长度为 n的整数数组buses，其中buses[i]表示第 i辆公交车的出发时间。
同时给你一个下标从 0开始长度为 m的整数数组passengers，其中passengers[j]表示第j位乘客的到达时间。
所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。
给你一个整数capacity，表示每辆公交车最多能容纳的乘客数目。
每位乘客都会搭乘下一辆有座位的公交车。如果你在 y时刻到达，公交在x时刻出发，
满足y <= x且公交没有满，那么你可以搭乘这一辆公交。
最早到达的乘客优先上车。
返回你可以搭乘公交车的最晚到达公交站时间。你 不能跟别的乘客同时刻到达。
注意：数组buses 和passengers不一定是有序的。
示例 1：输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2 输出：16
解释：第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
示例 2：输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2 输出：20
解释：第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。
提示：n == buses.length
m == passengers.length
1 <= n, m, capacity <= 105
2 <= buses[i], passengers[i] <= 109
buses中的元素 互不相同。
passengers中的元素 互不相同。
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口-双指针 | O(n) | O(1) |
2336.无限集中的最小数字(2)¶
题目
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类：
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
int popSmallest() 移除 并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中。
示例：输入["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest",
"popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出 [null, null, 1, 2, 3, null, 1, 4, 5]
解释 SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
// 且 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。
提示：1 <= num <= 1000
最多调用 popSmallest 和 addBack 方法 共计 1000 次
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n^2) | O(n) |
| 02 | 数组 | O(n^2) | O(n) |
type SmallestInfiniteSet struct {
m map[int]bool
}
func Constructor() SmallestInfiniteSet {
return SmallestInfiniteSet{m: make(map[int]bool)}
}
func (this *SmallestInfiniteSet) PopSmallest() int {
for i := 1; i <= 1000; i++ {
if this.m[i] == false {
this.m[i] = true
return i
}
}
return 0
}
func (this *SmallestInfiniteSet) AddBack(num int) {
delete(this.m, num)
}
# 2
type SmallestInfiniteSet struct {
arr []bool
}
func Constructor() SmallestInfiniteSet {
return SmallestInfiniteSet{arr: make([]bool, 1001)}
}
func (this *SmallestInfiniteSet) PopSmallest() int {
for i := 1; i <= 1000; i++ {
if this.arr[i] == false {
this.arr[i] = true
return i
}
}
return 0
}
func (this *SmallestInfiniteSet) AddBack(num int) {
this.arr[num] = false
}
2337.移动片段得到字符串¶
题目¶
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，
而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
示例 1：输入：start = "_L__R__R_", target = "L______RR" 输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
- 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。
可以从字符串 start 得到 target ，所以返回 true 。
示例 2：输入：start = "R_L_", target = "__LR" 输出：false
解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
示例 3：输入：start = "_R", target = "R_" 输出：false
解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。
提示：n == start.length == target.length
1 <= n <= 105
start 和 target 由字符 'L'、'R' 和 '_' 组成
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n^2) | O(n) |
2342.数位和相等数对的最大和(1)¶
题目
给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），
且 nums[i] 的数位和 与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值 。
示例 1：输入：nums = [18,43,36,13,7] 输出：54
解释：满足条件的数对 (i, j) 为：
- (0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。
- (1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。
所以可以获得的最大和是 54 。
示例 2：输入：nums = [10,12,19,14] 输出：-1
解释：不存在满足条件的数对，返回 -1 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 109
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(n) |
func maximumSum(nums []int) int {
res := -1
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
v := calculate(nums[i])
if m[v] > 0 { // 存在值
res = max(res, m[v]+nums[i]) // 更新最大值
}
m[v] = max(m[v], nums[i])
}
return res
}
func calculate(a int) int {
res := 0
for a > 0 {
res = res + a%10
a = a / 10
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2348.全0子数组的数目(2)¶
题目
给你一个整数数组nums，返回全部为0的子数组数目。
子数组是一个数组中一段连续非空元素组成的序列。
示例 1：输入：nums = [1,3,0,0,2,0,0,4] 输出：6
解释：子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。
示例 2：输入：nums = [0,0,0,2,0,0] 输出：9
解释：子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。
示例 3：输入：nums = [2,10,2019] 输出：0
解释：没有全 0 子数组，所以我们返回 0 。
提示：1 <= nums.length <= 105
-109 <= nums[i] <= 109
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(1) |
| 02 | 遍历 | O(n) | O(1) |
func zeroFilledSubarray(nums []int) int64 {
res := int64(0)
count := int64(0)
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
count++
res = res + count
} else {
count = 0
}
}
return res
}
# 2
func zeroFilledSubarray(nums []int) int64 {
res := int64(0)
count := int64(0)
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
count++
} else {
res = res + count*(count+1)/2
count = 0
}
}
res = res + count*(count+1)/2
return res
}
2352.相等行列对(1)¶
题目
给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。
示例 1：输入：grid = [[3,2,1],[1,7,6],[2,7,7]] 输出：1
解释：存在一对相等行列对：- (第 2 行，第 1 列)：[2,7,7]
示例 2：输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]] 输出：3
解释：存在三对相等行列对：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行, 第 2 列)：[2,4,2,2]
- (第 3 行, 第 2 列)：[2,4,2,2]
提示：n == grid.length == grid[i].length
1 <= n <= 200
1 <= grid[i][j] <= 105
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n^2) | O(n) |
func equalPairs(grid [][]int) int {
res := 0
n := len(grid)
countMap := make(map[[200]int]int)
for i := 0; i < n; i++ {
arr := [200]int{}
for j := 0; j < n; j++ {
arr[j] = grid[i][j]
}
countMap[arr]++
}
for j := 0; j < n; j++ {
arr := [200]int{}
for i := 0; i < n; i++ {
arr[i] = grid[i][j]
}
res = res + countMap[arr]
}
return res
}
2358.分组的最大数量(3)¶
题目
给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：
第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。
返回可以形成的 最大 组数。
示例 1：输入：grades = [10,6,12,7,3,5] 输出：3
解释：下面是形成 3 个分组的一种可行方法：
- 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1
- 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2
- 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3
可以证明无法形成超过 3 个分组。
示例 2：输入：grades = [8,8] 输出：1
解释：只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。
提示：1 <= grades.length <= 105
1 <= grades[i] <= 105
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口-双指针 | O(log(n)) | O(1) |
| 02 | 数学 | O(1) | O(1) |
| 03 | 模拟 | O(log(n)) | O(1) |
func maximumGroups(grades []int) int {
n := len(grades)
res := 1 // 至少可以分为1组
left, right := 1, n
for left <= right {
mid := left + (right-left)/2 // 分为mid组:1+2+3+...+mid（多余的分在最后一组）
total := (1 + mid) * mid / 2 // 分为mid组至少需要的人数
if total > n {
right = mid - 1
} else {
res = mid
left = mid + 1
}
}
return res
}
# 2
func maximumGroups(grades []int) int {
n := len(grades)
// k*(k+1)/2 <= n
// k^2 + k - 2*n <= 0
ans := math.Sqrt(0.25+2*float64(n)) - 0.5
// 求根公式
// ans = (math.Sqrt(1+8*float64(n)) - 1) / 2
return int(math.Floor(ans)) // 向下取整
}
# 3
func maximumGroups(grades []int) int {
n := len(grades)
res := 0
start := 1
for start <= n {
res++
n = n - start
start++
}
return res
}
2364.统计坏数对的数目(1)¶
题目
给你一个下标从0开始的整数数组nums。如果 i < j且j - i != nums[j] - nums[i]，那么我们称(i, j)是一个 坏数对。
请你返回 nums中 坏数对的总数目。
示例 1：输入：nums = [4,1,3,3] 输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。
示例 2：输入：nums = [1,2,3,4,5] 输出：0
解释：没有坏数对。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 109
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 哈希 | O(n) | O(n) |
func countBadPairs(nums []int) int64 {
res := int64(0)
n := int64(len(nums))
m := make(map[int]int64)
for i := 0; i < len(nums); i++ {
diff := nums[i] - i
res = res + m[diff] // 累计相等
m[diff]++
}
return n*(n-1)/2 - res // 总数-不满足条件的数量
}
2365.任务调度器II(1)¶
题目
给你一个下标从 0开始的正整数数组tasks，表示需要 按顺序完成的任务，其中tasks[i]表示第i件任务的 类型。
同时给你一个正整数space，表示一个任务完成后，另一个相同类型任务完成前需要间隔的最少天数。
在所有任务完成前的每一天，你都必须进行以下两种操作中的一种：
完成tasks中的下一个任务
休息一天
请你返回完成所有任务所需的 最少天数。
示例 1：输入：tasks = [1,2,1,2,3,1], space = 3 输出：9
解释：9 天完成所有任务的一种方法是：
第 1 天：完成任务 0 。
第 2 天：完成任务 1 。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2 。
第 6 天：完成任务 3 。
第 7 天：休息。
第 8 天：完成任务 4 。
第 9 天：完成任务 5 。
可以证明无法少于 9 天完成所有任务。
示例 2：输入：tasks = [5,8,8,5], space = 2 输出：6
解释：6 天完成所有任务的一种方法是：
第 1 天：完成任务 0 。
第 2 天：完成任务 1 。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2 。
第 6 天：完成任务 3 。
可以证明无法少于 6 天完成所有任务。
提示：1 <= tasks.length <= 105
1 <= tasks[i] <= 109
1 <= space <= tasks.length
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 模拟 | O(n) | O(n) |
func taskSchedulerII(tasks []int, space int) int64 {
res := int64(0)
m := make(map[int]int64)
for i := 0; i < len(tasks); i++ {
if m[tasks[i]] == 0 {
res = res + 1 // 没出现+1
} else {
prev := m[tasks[i]]
res = max(res+1, prev+int64(space)+1) // 出现：取较大
}
m[tasks[i]] = res
}
return res
}
func max(a, b int64) int64 {
if a < b {
return b
}
return a
}
2369.检查数组是否存在有效划分(1)¶
题目
给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。
如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：
子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。
例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。
示例 1：输入：nums = [4,4,4,5,6] 输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。
示例 2：输入：nums = [1,1,1,2] 输出：false
解释：该数组不存在有效划分。
提示：2 <= nums.length <= 105
1 <= nums[i] <= 106
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n) | O(n) |
func validPartition(nums []int) bool {
n := len(nums)
dp := make([]bool, n+1) // dp[i]表示长度为i的数组nums[:i]能否划分成功
dp[0] = true
for i := 0; i < n; i++ {
// 3种有效划分方式
if i > 0 && dp[i-1] == true && nums[i] == nums[i-1] {
dp[i+1] = true
}
if i > 1 && dp[i-2] == true && nums[i] == nums[i-1] && nums[i] == nums[i-2] {
dp[i+1] = true
}
if i > 1 && dp[i-2] == true && nums[i] == nums[i-1]+1 && nums[i] == nums[i-2]+2 {
dp[i+1] = true
}
}
return dp[n]
}
2374.边积分最高的节点(1)¶
题目
给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
示例 1：输入：edges = [1,0,0,0,0,7,7,5] 输出：7
解释：- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。
节点 7 的边积分最高，所以返回 7 。
示例 2：输入：edges = [2,0,0,2] 输出：0
解释：- 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。
- 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。
节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。
提示：n == edges.length
2 <= n <= 105
0 <= edges[i] < n
edges[i] != i
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 遍历 | O(n) | O(n) |
func edgeScore(edges []int) int {
res := 0
m := make(map[int]int)
for i := 0; i < len(edges); i++ {
v := edges[i]
m[v] = m[v] + i
if m[v] > m[res] || m[v] == m[res] && v < res {
res = v
}
}
return res
}
2375.根据模式串构造最小数字¶
题目¶
给你下标从 0 开始、长度为 n的字符串pattern，它包含两种字符，'I'表示 上升，'D'表示 下降。
你需要构造一个下标从 0开始长度为n + 1的字符串，且它要满足以下条件：
num包含数字'1'到'9'，其中每个数字至多使用一次。
如果pattern[i] == 'I'，那么num[i] < num[i + 1]。
如果pattern[i] == 'D'，那么num[i] > num[i + 1]。
请你返回满足上述条件字典序 最小的字符串num。
示例 1：输入：pattern = "IIIDIDDD" 输出："123549876"
解释：下标 0 ，1 ，2 和 4 处，我们需要使 num[i] < num[i+1] 。
下标 3 ，5 ，6 和 7 处，我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 "245639871" ，"135749862" 和 "123849765" 。
"123549876" 是满足条件最小的数字。
注意，"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。
示例 2：输入：pattern = "DDD" 输出："4321"
解释：一些可能的 num 的值为 "9876" ，"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。
提示：1 <= pattern.length <= 8
pattern只包含字符'I' 和'D' 。
解题思路¶
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口-双指针 | O(n) | O(1) |
2301-2400-Hard¶
2302.统计得分小于K的子数组数目(2)¶
题目
一个数字的 分数定义为数组之和 乘以数组的长度。
比方说，[1, 2, 3, 4, 5]的分数为(1 + 2 + 3 + 4 + 5) * 5 = 75。
给你一个正整数数组nums和一个整数k，请你返回nums中分数严格小于k的非空整数子数组数目。
子数组 是数组中的一个连续元素序列。
示例 1：输入：nums = [2,1,4,3,5], k = 10 输出：6
解释：有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。
示例 2：输入：nums = [1,1,1], k = 5 输出：5
解释：除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 滑动窗口-双指针 | O(n) | O(1) |
| 02 | 滑动窗口-双指针 | O(n) | O(1) |
func countSubarrays(nums []int, k int64) int64 {
var res, sum, count int64
n := len(nums)
left := -1
for right := 0; right < n; right++ {
sum = sum + int64(nums[right])
count++
for left < n && sum*count >= k {
left++
sum = sum - int64(nums[left])
count--
}
res = res + count
}
return res
}
# 2
func countSubarrays(nums []int, k int64) int64 {
var res, sum int64
var left int
for right := 0; right < len(nums); right++ {
sum = sum + int64(nums[right])
for sum*int64(right-left+1) >= k {
sum = sum - int64(nums[left])
left++
}
res = res + int64(right-left+1)
}
return res
}
2312.卖木头块(3)¶
题目
给你两个整数m 和n，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组prices，
其中prices[i] = [hi, wi, pricei]表示你可以以pricei元的价格卖一块高为hi宽为wi的矩形木块。
每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：
沿垂直方向按高度 完全 切割木块，或
沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后，你可以根据 prices卖木块。你可以卖多块同样尺寸的木块。
你不需要将所有小木块都卖出去。你 不能旋转切好后木块的高和宽。
请你返回切割一块大小为m x n 的木块后，能得到的最多钱数。
注意你可以切割木块任意次。
示例 1：输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]] 输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。
示例 2：输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]] 输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。
提示：1 <= m, n <= 200
1 <= prices.length <= 2 * 104
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 106
所有(hi, wi) 互不相同。
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 动态规划 | O(n^3) | O(n^2) |
| 02 | 动态规划 | O(n^3) | O(n^2) |
| 03 | 递归 | O(n^3) | O(n^2) |
func sellingWood(m int, n int, prices [][]int) int64 {
dp := make([][]int64, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int64, n+1)
}
temp := make(map[[2]int]int) // 转为map方便查找
for i := 0; i < len(prices); i++ {
a, b, c := prices[i][0], prices[i][1], prices[i][2]
temp[[2]int{a, b}] = c // [a,b] => c
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
dp[i][j] = int64(temp[[2]int{i, j}])
// 2个方向进行切割
for k := 1; k < i; k++ {
dp[i][j] = max(dp[i][j], dp[k][j]+dp[i-k][j])
}
for k := 1; k < j; k++ {
dp[i][j] = max(dp[i][j], dp[i][k]+dp[i][j-k])
}
}
}
return dp[m][n]
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
# 2
func sellingWood(m int, n int, prices [][]int) int64 {
dp := make([][]int64, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int64, n+1)
}
for i := 0; i < len(prices); i++ {
a, b, c := prices[i][0], prices[i][1], prices[i][2]
dp[a][b] = int64(c) // [a,b] => c
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
// 2个方向进行切割
for k := 1; k <= i/2; k++ {
dp[i][j] = max(dp[i][j], dp[k][j]+dp[i-k][j])
}
for k := 1; k <= j/2; k++ {
dp[i][j] = max(dp[i][j], dp[i][k]+dp[i][j-k])
}
}
}
return dp[m][n]
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
# 3
var temp map[[2]int]int
var dp [][]int64
func sellingWood(m int, n int, prices [][]int) int64 {
dp = make([][]int64, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int64, n+1)
for j := 0; j <= n; j++ {
dp[i][j] = -1
}
}
temp = make(map[[2]int]int) // 转为map方便查找
for i := 0; i < len(prices); i++ {
a, b, c := prices[i][0], prices[i][1], prices[i][2]
temp[[2]int{a, b}] = c // [a,b] => c
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
dp[i][j] = int64(temp[[2]int{i, j}])
// 2个方向进行切割
for k := 1; k < i; k++ {
dp[i][j] = max(dp[i][j], dp[k][j]+dp[i-k][j])
}
for k := 1; k < j; k++ {
dp[i][j] = max(dp[i][j], dp[i][k]+dp[i][j-k])
}
}
}
return dfs(m, n)
}
func dfs(m int, n int) int64 {
if dp[m][n] != -1 {
return dp[m][n]
}
res := int64(temp[[2]int{m, n}])
// 2个方向进行切割
for k := 1; k < m; k++ {
res = max(res, dfs(k, n)+dfs(m-k, n))
}
for k := 1; k < n; k++ {
res = max(res, dfs(m, k)+dfs(m, n-k))
}
dp[m][n] = res
return res
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
2321.拼接数组的最大分数(1)¶
题目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。
你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，
接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。
例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，
整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。
你可以选择执行上述操作 一次 或不执行任何操作。
数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。
返回 可能的最大分数 。
子数组 是数组中连续的一个元素序列。arr[left...right]
表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。
示例 1：输入：nums1 = [60,60,60], nums2 = [10,90,10] 输出：210
解释：选择 left = 1 和 right = 1 ，得到 nums1 = [60,90,60] 和 nums2 = [10,60,10] 。
分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210 。
示例 2：输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20] 输出：220
解释：选择 left = 3 和 right = 4 ，得到 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30] 。
分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220 。
示例 3：输入：nums1 = [7,11,13], nums2 = [1,1,1] 输出：31
解释：选择不交换任何子数组。
分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31 。
提示：n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 104
解题思路
| No. | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 01 | 前缀和 | O(n) | O(1) |
func maximumsSplicedArray(nums1 []int, nums2 []int) int {
return max(solve(nums1, nums2), solve(nums2, nums1)) // 取2种情况最大值
}
func solve(nums1 []int, nums2 []int) int {
maxDiff := 0
sum1 := 0
sum := 0
// nums1 + maxDiff(num2[left:right]-sum1[left:right])
// 求maxDiff最大
// 使用最大子序和来计算maxDiff
for i := 0; i < len(nums1); i++ {
sum1 = sum1 + nums1[i]
// leetcode 53.最大子序和
sum = max(0, sum+nums2[i]-nums1[i])
maxDiff = max(maxDiff, sum)
}
return sum1 + maxDiff
}
func max(a, b int) int {
if a > b {
return a
}
return b
}