且听疯吟

leetcode biweekly contest 138

2024-09-03

leetcode biweekly contest 138

t3 确实没有想到很好的解法，最近题目质量确实越来越高了，非常喜欢最近的题目。

3270. 求出数字答案

给你三个 正 整数 num1 ，num2 和 num3 。

数字 num1 ，num2 和 num3 的数字答案 key 是一个四位数，定义如下：

  • 一开始，如果有数字 少于 四位数，给它补 前导 0 。
  • 答案 key 的第 i 个数位（1 <= i <= 4）为 num1 ，num2 和 num3 第 i 个数位中的 最小 值。

请你返回三个数字 没有 前导 0 的数字答案。

示例 1：

输入：num1 = 1, num2 = 10, num3 = 1000

输出：0

解释：

补前导 0 后，num1 变为 "0001" ，num2 变为 "0010" ，num3 保持不变，为 "1000" 。

  • 数字答案 key 的第 1 个数位为 min(0, 0, 1) 。
  • 数字答案 key 的第 2 个数位为 min(0, 0, 0) 。
  • 数字答案 key 的第 3 个数位为 min(0, 1, 0) 。
  • 数字答案 key 的第 4 个数位为 min(1, 0, 0) 。

所以数字答案为 "0000" ，也就是 0 。

示例 2：

输入： num1 = 987, num2 = 879, num3 = 798

输出：777

示例 3：

输入：num1 = 1, num2 = 2, num3 = 3

输出：1

提示：

  • 1 <= num1, num2, num3 <= 9999

地址

https://leetcode.cn/contest/biweekly-contest-138/problems/find-the-key-of-the-numbers/

题意

模拟

思路

  1. 直接模拟即可，我们每次找到每一位上的最小数字即可。
  2. 复杂度分析：
  • 时间复杂度：$O(1)$。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def generateKey(self, num1: int, num2: int, num3: int) -> int:
        arr = [num1, num2, num3]
        res = 0
        for i in range(4):
            res = min(x // (10**i) % 10 for x in arr) * (10**i) + res
        return res

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. 题目比较简单，我们依次模拟即可，找到连续的 $k$ 个字符串依次计算相应的值即可。

  2. 复杂度分析：

  • 时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度 。
  • 空间复杂度：$O(n)$；

代码

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        n = len(s)
        res = []
        for i in range(n // k):
            x = sum(ord(s[i * k + j]) - ord('a') for j in range(k)) % 26
            res.append(chr(ord('a') + x))
        return "".join(res)

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. 复杂度分析：

  • 时间复杂度：$𝑂(\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

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

Tags: 题解 力扣周赛赛
← leetcode weekly contest 412 leetcode weekly contest 413 →

扫描二维码，分享此文章