Leetcode 第 393 场周赛题解

题目1：3114. 替换字符可以得到的最晚时间

思路

模拟。

代码

/*
 * @lc app=leetcode.cn id=3114 lang=cpp
 *
 * [3114] 替换字符可以得到的最晚时间
 */

// @lc code=start
class Solution
{
public:
    string findLatestTime(string s)
    {
        int i = 0;
        if (s[0] == '?' && s[1] == '?')
        {
            s[0] = s[1] = '1';
            i += 3;
        }
        for (; i < 5; i++)
            if (s[i] == '?')
            {
                if (i == 0)
                {
                    if (s[1] < '2')
                        s[i] = '1';
                    else
                        s[i] = '0';
                }
                else if (i == 1)
                {
                    if (s[0] == '1')
                        s[i] = '1';
                    else
                        s[i] = '9';
                }
                else if (i == 3)
                    s[i] = '5';
                else if (i == 4)
                    s[i] = '9';
            }
        return s;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(1)。

题目2：3115. 质数的最大距离

思路

双指针。

左指针下标初始化为 0，从左往右找到第一个素数；

右指针下标初始化为 nums.size()-1，从右往左找到第一个素数。

素数的最大距离=右指针下标-左指针下标。

代码

/*
 * @lc app=leetcode.cn id=3115 lang=cpp
 *
 * [3115] 素数的最大距离
 */

// @lc code=start
class Solution
{
private:
    bool isPrime(int x)
    {
        for (int i = 2; i * i <= x; i++)
            if (x % i == 0)
                return false;
        return x != 1;
    }

public:
    int maximumPrimeDifference(vector<int> &nums)
    {
        int n = nums.size();
        int leftPrimeIdx = 0, rightPrimeIdx = n - 1;
        while (leftPrimeIdx < n && !isPrime(nums[leftPrimeIdx]))
            leftPrimeIdx++;
        while (rightPrimeIdx >= 0 && !isPrime(nums[rightPrimeIdx]))
            rightPrimeIdx--;
        return leftPrimeIdx == rightPrimeIdx ? 0 : rightPrimeIdx - leftPrimeIdx;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的元素个数。

空间复杂度：O(1)。

题目3：3116. 单面值组合的第 K 小金额

思路

容斥原理 + 二分答案。

题解：二分答案+容斥原理+预处理（Python/Java/C++/Go）

代码

/*
 * @lc app=leetcode.cn id=3116 lang=cpp
 *
 * [3116] 单面值组合的第 K 小金额
 */

// @lc code=start
class Solution
{
public:
    long long findKthSmallest(vector<int> &coins, int k)
    {
        auto check = [&](long long m) -> bool
        {
            long long cnt = 0;
            // 枚举所有非空子集
            for (int i = 1; i < (1 << coins.size()); i++)
            {
                long long lcm_res = 1; // 计算子集 LCM
                for (int j = 0; j < coins.size(); j++)
                {
                    if ((i >> j) & 0x1)
                    {
                        lcm_res = lcm(lcm_res, coins[j]);
                        if (lcm_res > m)
                        { // 太大了
                            break;
                        }
                    }
                }
                cnt += __builtin_popcount(i) % 2 ? m / lcm_res : -m / lcm_res;
            }
            return cnt >= k;
        };

        long long left = k - 1, right = (long long)ranges::min(coins) * k;
        while (left + 1 < right)
        {
            long long mid = (left + right) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};
// @lc code=end

复杂度分析

题目4：3117. 划分数组得到最小的值之和

思路

划分型 DP。

题解：记忆化搜索+选或不选（划分/不划分）Python/Java/C++/Go

代码

#
# @lc app=leetcode.cn id=3117 lang=python3
#
# [3117] 划分数组得到最小的值之和
#

# @lc code=start

# 划分型 DP

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        n = len(nums)
        m = len(andValues)

        @cache
        def dfs(i: int, j: int, and_: int) -> int:
            if m - j > n - i:  # 剩余元素不足
                return inf
            if j == m:  # 分了 m 段
                return 0 if i == n else inf
            and_ &= nums[i]
            if and_ < andValues[j]:  # 剪枝：无法等于 andValues[j]
                return inf
            res = dfs(i + 1, j, and_)  # 不划分
            if and_ == andValues[j]:  # 划分，nums[i] 是这一段的最后一个数
                res = min(res, dfs(i + 1, j + 1, -1) + nums[i])
            return res
        ans = dfs(0, 0, -1)
        return ans if ans < inf else -1
# @lc code=end

复杂度分析