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)       |

```go
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
}
Copyright © Zhi2014 2023 all right reserved，powered by Gitbook该文件修订时间： 2023-10-23 15:20:51

results matching ""

    No results matching ""