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