leetcode biweekly contest 486

leetcode contest 486

本周的题目确实没啥太大难度，前 $3$ 题基本都是简单题目。

3818. 移除前缀使数组严格递增

给你一个整数数组 nums。

你需要从 nums 中 恰好 移除一个前缀（可以为空）。

返回一个整数，表示被移除的前缀的 最小 长度，使得剩余的数组 严格递增 。

数组的 前缀 是从数组的起始位置开始，一直延伸到任意位置的子数组。

如果一个数组的每个元素都严格大于它的前一个元素（若存在），则称该数组 严格递增 。

示例 1：

输入： nums = [1,-1,2,3,3,4,5]

输出： 4

解释：

移除前缀 prefix = [1, -1, 2, 3] 后，剩余数组为 [3, 4, 5]，严格递增。

示例 2：

输入： nums = [4,3,-2,-5]

输出： 3

解释：

移除前缀 prefix = [4, 3, -2] 后，剩余数组为 [-5]，严格递增。

示例 3：

输入： nums = [1,2,3,4]

输出： 0

解释：

数组 nums = [1, 2, 3, 4] 已经是严格递增的，因此移除空前缀即可。

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

地址

https://leetcode.cn/problems/minimum-prefix-removal-to-make-array-strictly-increasing/

题意

模拟

思路

  1. 倒序遍历找到第一个前一个元素大于等于后一个元素的位置。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int minimumPrefixLength(vector<int>& nums) {
        int n = nums.size();
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[i + 1]) {
                return i + 1;
            }
        }

        return 0;
    }
};

3819. 非负元素轮替

给你一个整数数组 nums 和一个整数 k。

将数组中 非负 元素以循环的方式 向左 轮替 k 个位置。

所有 负数 元素必须保持在它们原来的位置，不进行移动。

轮替后，将 非负 元素按照新的顺序放回数组中，仅填充原先包含 非负 值的位置，并 跳过所有负数 的位置。

返回处理后的数组。

示例 1：

输入： nums = [1,-2,3,-4], k = 3

输出： [3,-2,1,-4]

解释：

  • 非负元素按顺序为 [1, 3]。
  • 以 k = 3 进行向左轮替，结果为：
    • [1, 3] -> [3, 1] -> [1, 3] -> [3, 1]
  • 将它们放回非负值对应的位置，结果为 [3, -2, 1, -4]。

示例 2：

输入： nums = [-3,-2,7], k = 1

输出： [-3,-2,7]

解释：

  • 非负元素按顺序为 [7]。
  • 以 k = 1 进行向左轮替，结果为 [7]。
  • 将它们放回非负值对应的位置，结果为 [-3, -2, 7]。

示例 3：

输入： nums = [5,4,-9,6], k = 2

输出： [6,5,-9,4]

解释：

  • 非负元素按顺序为 [5, 4, 6]。
  • 以 k = 2 进行向左轮替，结果为 [6, 5, 4]。
  • 将它们放回非负值对应的位置，结果为 [6, 5, -9, 4]。

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

地址

https://leetcode.cn/problems/rotate-non-negative-elements/

题意

模拟

思路

  1. 将所有非负数筛选出来然后进行原地循环位移，然后再填充回去即可。

  2. 复杂度分析：

  • 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度
  • 空间复杂度：$O(1)$；

代码

class Solution:
    def rotateElements(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        arr = []
        for i in range(n):
            if nums[i] >= 0:
                arr.append(nums[i])
        
        if not arr:
            return nums
        
        m = len(arr)
        k = k % m
        j = k  # 从旋转后的起始位置开始
        for i in range(n):
            if nums[i] >= 0:
                nums[i] = arr[j % m]
                j += 1
        
        return nums

3271. 哈希分割字符串

给你一个长度为 n 的字符串 s 和一个整数 k ，n 是 k 的 倍数 。你的任务是将字符串 s 哈希为一个长度为 n / k 的新字符串 result 。

首先，将 s 分割成 n / k 个 子字符串 ，每个子字符串的长度都为 k 。然后，将 result 初始化为一个 空 字符串。

我们依次从前往后处理每一个 子字符串 ：

  • 一个字符的 哈希值 是它在 字母表 中的下标（也就是 'a' → 0 ，'b' → 1 ，… ，'z' → 25）。
  • 将子字符串中字幕的 哈希值 求和。
  • 将和对 26 取余，将结果记为 hashedChar 。
  • 找到小写字母表中 hashedChar 对应的字符。
  • 将该字符添加到 result 的末尾。

返回 result 。

示例 1：

输入：s = “abcd”, k = 2

输出：“bf”

解释：

第一个字符串为 "ab" ，0 + 1 = 1 ，1 % 26 = 1 ，result[0] = 'b' 。

第二个字符串为： "cd" ，2 + 3 = 5 ，5 % 26 = 5 ，result[1] = 'f' 。

示例 2：

输入：s = “mxz”, k = 3

输出：“i”

解释：

唯一的子字符串为 "mxz" ，12 + 23 + 25 = 60 ，60 % 26 = 8 ，result[0] = 'i' 。

提示：

  • 1 <= k <= 100
  • k <= s.length <= 1000
  • s.length 能被 k 整除。
  • s 只含有小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-138/problems/hash-divided-string/

题意

贪心，模拟，组合数学

思路

  1. 首先我们找到所有数位为 $n$ 的回文数，这一步我们可以用 $\sqrt{n}$ 的时间复杂度求出，接下来就是排列组合的问题，给定重复的 $n$ 种球，每种球一共有 $c_i$ 个，求可能的排列组合数，可以利用排列组合公式：
    $$
    \dfrac{(\sum_{i=0}^{n-1}c_i)!}{c_0!\times c_1! \cdots\times c_{n-1}}
    $$
    就是一个非常简单的排列组合问题了，当然难点在于求出所有的回文数。当然还有前导 $0$ 的问题，我们抽取一个非 $0$ 的元素放在数字的首位，然后后面则按照排列组合依次排放

    $2后端前端用户后端前端用户提交请求发送API调用返回数据显示结果 $2

    Animal

    +String name

    +eat()

    Dog

    +bark()

  2. 复杂度分析：

  • 时间复杂度：$𝑂(\sqrt{n})$，其中 𝑛 表示给定的数字 。
  • 空间复杂度：$𝑂(𝑛)$；

代码

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        fact = [factorial(i) for i in range(n + 1)]
        base = 10**((n - 1) // 2)
        vis = set()
        for i in range(base, base * 10):
            s = str(i)
            s = s + s[::-1][n % 2:]
            if int(s) % k:
                continue
            sorted_s = ''.join(sorted(s))
            vis.add(sorted_s)

        ans = 0
        for s in vis:
            cnt = Counter(s)
            cur = (n - cnt['0']) * fact[n - 1]
            for c in cnt.values():
                cur //= fact[c]
            ans += cur
        return ans

3273. 对 Bob 造成的最少伤害

给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。

Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。

每一秒中，在敌人对 Bob 造成伤害 之后 ，Bob 会选择 一个 还活着的敌人进行攻击，该敌人的健康值减少 power 。

请你返回 Bob 将 所有 n 个敌人都消灭之前，最少 会收到多少伤害。

示例 1：

输入：power = 4, damage = [1,2,3,4], health = [4,5,6,8]

输出：39

解释：

  • 最开始 2 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间内对 Bob 的总伤害是 10 + 10 = 20 点。
  • 接下来 2 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间内对 Bob 的总伤害是 6 + 6 = 12 点。
  • 接下来 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间内对 Bob 的总伤害是 3 点。
  • 接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间内对 Bob 的总伤害是 2 + 2 = 4 点。

示例 2：

输入：power = 1, damage = [1,1,1,1], health = [1,2,3,4]

输出：20

解释：

  • 最开始 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间对 Bob 的总伤害是 4 点。
  • 接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间对 Bob 的总伤害是 3 + 3 = 6 点。
  • 接下来 3 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间对 Bob 的总伤害是 2 + 2 + 2 = 6 点。
  • 接下来 4 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间对 Bob 的总伤害是 1 + 1 + 1 + 1 = 4 点。

示例 3：

输入：power = 8, damage = [40], health = [59]

输出：320

提示：

  • 1 <= power <= 104
  • 1 <= n == damage.length == health.length <= 105
  • 1 <= damage[i], health[i] <= 104

地址

https://leetcode.cn/contest/biweekly-contest-138/problems/minimum-amount-of-damage-dealt-to-bob/

题意

贪心，排序，前缀和

思路

  1. 题目比较简单，主要是先攻击与后攻击的问题，假设给定的两个敌人的伤害和健康值分别 $(x_1,y_1),(x_2,y_2)$，此时我们到底应该是先攻击哪个敌人，受到的伤害最小。
    • 假设我们先攻击第一个敌人，再攻击第二个敌人，此时收到的伤害为 $\lceil\dfrac{y_1}{power}\rceil \times(x_1 + x_2) + \lceil\dfrac{y_2}{power}\rceil \times x_2$;
    • 假设我们先攻击第二个敌人，再攻击第一个敌人，此时收到的伤害为 $\lceil\dfrac{y_2}{power}\rceil \times(x_1 + x_2) + \lceil\dfrac{y_1}{power}\rceil \times x_2$;
    • 此时我们可以直到如果满足 $\lceil\dfrac{y_1}{power}\rceil \times x_2 < \lceil\dfrac{y_2}{power}\rceil \times x_1$ ，则此时应该先攻击第一个敌人，否则应该攻击第二个敌人，我们按照上述比较从小到达进行排序即可，然后依次进行攻击即可；
    • 此时我们还需要求出所有的前缀和，提前知道每次攻击时的前缀和，每次攻击次数乘以伤害总值的前缀和即可。
  2. 复杂度分析：
  • 时间复杂度：$𝑂(𝑛log⁡ 𝑛)$，其中 𝑛 表示给定数组的长度 。
  • 空间复杂度：$𝑂(𝑛)$；

代码

class Solution:
    def minDamage(self, power: int, damage: List[int], health: List[int]) -> int:
        n = len(damage)
        arr = [(damage[i], health[i]) for i in range(n)]
        
        # 自定义比较函数
        def compare(a: Tuple[int, int], b: Tuple[int, int]) -> int:
            c1 = (a[1] + power - 1) // power
            c2 = (b[1] + power - 1) // power
            if c1 * b[0] < c2 * a[0]:
                return -1
            elif c1 * b[0] > c2 * a[0]:
                return 1
            else:
                return 0
            
        # 使用自定义比较函数进行排序
        arr.sort(key=cmp_to_key(compare))
        res, cnt = 0, 0
        for d, h in arr:
            cnt += (h + power - 1) // power
            res += cnt * d
        return res

欢迎关注和打赏，感谢支持！

力扣周赛
#力扣周赛赛 #题解
leetcode biweekly contest 486
http://example.com/1970/01/01/力扣周赛题解/224/
Author
Mike Meng
Posted on
January 1, 1970
Updated on
January 26, 2026
Licensed under