Solutions CS101

Appearance

第 448 场周赛-20250504 ​

https://leetcode.cn/contest/weekly-contest-447/

中国时间：2025-05-04 10:30, 1 小时 30 分

E3536.两个数字的最大乘积 ​

implementation, https://leetcode.cn/problems/maximum-product-of-two-digits/

M3537.填充特殊网格 ​

dfs, https://leetcode.cn/problems/fill-a-special-grid/

T3538.合并得到最小旅行时间 ​

dp, https://leetcode.cn/problems/merge-operations-for-minimum-travel-time/

738 / 997 个通过的测试用例

python
from typing import List
from functools import lru_cache

class Solution:
    def minTravelTime(self, l: int, n: int, k: int, position: List[int], time: List[int]) -> int:
        from copy import deepcopy

        # 计算总时间
        def compute_total(pos, time):
            total = 0
            for i in range(len(pos) - 1):
                distance = pos[i + 1] - pos[i]
                total += distance * time[i]
            return total

        min_time = float('inf')

        def dfs(pos, t, merges_left):
            nonlocal min_time
            if merges_left == 0:
                min_time = min(min_time, compute_total(pos, t))
                return

            for i in range(1, len(pos) - 1):  # only valid merge indices
                # Merge position[i] into position[i+1]
                new_pos = pos[:i] + pos[i+1:]
                new_time = t[:i] + [t[i] + t[i+1]] + t[i+2:]
                dfs(new_pos, new_time, merges_left - 1)

        dfs(position, time, k)
        return min_time

加@lru_cache, 797 / 997 个通过测试用例。

T3539.魔法序列的数组乘积之和 ​

https://leetcode.cn/contest/weekly-contest-448/problems/find-sum-of-array-product-of-magical-sequences/

给你两个整数 M 和 K，和一个整数数组 nums。

一个整数序列 seq 如果满足以下条件，被称为 魔法 序列：

  • seq 的序列长度为 M。
  • 0 <= seq[i] < nums.length
  • 2seq[0] + 2seq[1] + ... + 2seq[M - 1] 的 二进制形式 有 K 个 置位。

这个序列的 数组乘积 定义为 prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[M - 1]])。

返回所有有效 魔法 序列的 数组乘积 的 总和 。

由于答案可能很大，返回结果对 109 + 7 取模。

置位 是指一个数字的二进制表示中值为 1 的位。

示例 1:

输入: M = 5, K = 5, nums = [1,10,100,10000,1000000]

输出: 991600007

解释:

所有 [0, 1, 2, 3, 4] 的排列都是魔法序列，每个序列的数组乘积是 1013。

示例 2:

输入: M = 2, K = 2, nums = [5,4,3,2,1]

输出: 170

解释:

魔法序列有 [0, 1]，[0, 2]，[0, 3]，[0, 4]，[1, 0]，[1, 2]，[1, 3]，[1, 4]，[2, 0]，[2, 1]，[2, 3]，[2, 4]，[3, 0]，[3, 1]，[3, 2]，[3, 4]，[4, 0]，[4, 1]，[4, 2] 和 [4, 3]。

示例 3:

输入: M = 1, K = 1, nums = [28]

输出: 28

解释:

唯一的魔法序列是 [0]。

提示:

  • 1 <= K <= M <= 30
  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 10^8
python