leetcode contest 393

t3,t4 都是比较难得题目。

3114. 替换字符可以得到的最晚时间

给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 "?" 替换。

12 小时制时间格式为 "HH:MM" ，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 00:00，最晚的时间为 11:59。

你需要将 s 中的 所有 "?" 字符替换为数字，使得结果字符串代表的时间是一个 有效 的 12 小时制时间，并且是可能的 最晚 时间。

返回结果字符串。

示例 1：

输入： s = “1?:?4”

输出： “11:54”

解释： 通过替换 "?" 字符，可以得到的最晚12小时制时间是 "11:54"。

示例 2：

输入： s = “0?:5?”

输出： “09:59”

解释： 通过替换 "?" 字符，可以得到的最晚12小时制时间是 "09:59"。

提示：

• s.length == 5
• s[2] 是字符 ":"
• 除 s[2] 外，其他字符都是数字或 "?"
• 输入保证在替换 "?" 字符后至少存在一个介于 "00:00" 和 "11:59" 之间的时间。

地址

https://leetcode.cn/contest/weekly-contest-393/problems/latest-time-you-can-obtain-after-replacing-characters/

题意

直接模拟，贪心

思路

1. 题目比较简单，直接模拟贪心即可，依次尝试即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def findLatestTime(self, s: str) -> str:
        s = list(s)
        if s[0] == '?':
            if s[1] == '?':
                s[0], s[1] = '1', '1'
            elif s[1] > '1':
                s[0] = '0'
            else:
                s[0] = '1'
        else:
            if s[1] == '?':
                if s[0] == '0':
                    s[1] = '9'
                else:
                    s[1] = '1'
        
        if s[3] == '?':
            s[3] = '5'
        if s[4] == '?':
            s[4] = '9'
        
        return ''.join(s)

3115. 素数的最大距离

给你一个整数数组 nums。

返回两个（不一定不同的）素数在 nums 中 下标 的 最大距离。

示例 1：

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

输出： 3

解释： nums[1]、nums[3] 和 nums[4] 是素数。因此答案是 |4 - 1| = 3。

示例 2：

输入： nums = [4,8,2,8]

输出： 0

解释： nums[2] 是素数。因为只有一个素数，所以答案是 |2 - 2| = 0。

提示：

• 1 <= nums.length <= 3 * 105
• 1 <= nums[i] <= 100
• 输入保证 nums 中至少有一个素数。

地址

https://leetcode.cn/contest/weekly-contest-393/problems/maximum-prime-difference/

题意

模拟

思路

1. 直接计算数组中所有的素数，并计算最大的索引与最小的索引的差值即可。
2. 复杂度分析：

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

代码

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        primer = []
        for i, x in enumerate(nums):
            if x == 1:
                continue
            isPrimer = True
            j = 2
            while j * j <= x:
                if x % j == 0:
                    isPrimer = False
                    break
                j += 1
            if isPrimer:
                primer.append(i)
        return primer[-1] - primer[0]

impl Solution {
    pub fn maximum_prime_difference(nums: Vec<i32>) -> i32 {
        let mut primer = Vec::new();
        for i in 0..nums.len() {
            let x = nums[i];
            if x == 1 {
                continue;
            }
            let mut j = 2;
            let mut isPrimer = true;
            while j * j <= x {
                if x % j == 0 {
                    isPrimer = false;
                    break;
                }
                j += 1;
            }
            if isPrimer {
                primer.push(i)
            }
        }
        
        return (primer[primer.len() - 1] - primer[0]) as i32;
    }
}

3116. 单面值组合的第 K 小金额

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。

你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。

返回使用这些硬币能制造的 第 kth 小 金额。

示例 1：

输入： coins = [3,6,9], k = 3

输出： 9

解释：给定的硬币可以制造以下金额：
3元硬币产生3的倍数：3, 6, 9, 12, 15等。
6元硬币产生6的倍数：6, 12, 18, 24等。
9元硬币产生9的倍数：9, 18, 27, 36等。
所有硬币合起来可以产生：3, 6, 9, 12, 15等。

示例 2：

输入：coins = [5,2], k = 7

输出：12

解释：给定的硬币可以制造以下金额：
5元硬币产生5的倍数：5, 10, 15, 20等。
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。

提示：

• 1 <= coins.length <= 15
• 1 <= coins[i] <= 25
• 1 <= k <= 2 * 109
• coins 包含两两不同的整数。

地址

https://leetcode.cn/contest/weekly-contest-393/problems/kth-smallest-amount-with-single-denomination-combination/

题意

二分查找 + 容斥原理

思路

1. 本题与1201 基本上一样的思路，但是这个多个组合数的容斥原理确实第一次见到，当时确实应该多查一些资料就晓得这个题目怎么计算了，可以关键时刻给放弃了，容斥原理，相关证明过程很棒，值得学习和回味。当然如果有三个数的话，就非常简单了，关键是有多个集合，怎么利用容斥原理，对于一个子集，如何求该子集的交集。

   

   

2. 复杂度：

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

代码

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        n = len(coins)
        res = 0
        lo, hi = 1, 10**20
        while lo <= hi:
            mid = (lo + hi) // 2
            tot = 0
            for i in range(1, 1 << n):
                lcm = 1
                cnt = 0
                for j in range(len(coins)):
                    if i & (1 << j):
                        cnt += 1
                        lcm = coins[j] * lcm // math.gcd(lcm, coins[j])
                cur = mid // lcm
                tot += cur if cnt % 2 == 1 else -cur
         
            if tot >= k:
                res = mid
                hi = mid - 1
            else:
                lo = mid + 1
        return res

impl Solution {
    fn bit_count(mut n: i64) -> i64 {
        let mut count = 0;
        while n > 0 {
            count += n & 1;
            n >>= 1;
        }
        count
    }

    fn gcd(mut a: i64, mut b: i64) -> i64 {
        while b != 0 {
            let temp = b;
            b = a % b;
            a = temp;
        }
        a.abs()
    }

    pub fn find_kth_smallest(coins: Vec<i32>, k: i32) -> i64 {
        let n = coins.len() as i32;
        let mut lcm: Vec<i64> = vec![1; 1 << n];
        let mut res = 0;
        let mut lo = 1 as i64;
        let mut hi = 10i64.pow(20);

        for i in 1..(1 << n as u32) {
            for (j, &coin) in coins.iter().enumerate() {
                if (i >> j) & 1 != 0 {
                    lcm [i] = lcm[i] * (coin as i64) / Self::gcd(lcm[i], coin as i64);
                }
            }
        }

        while lo <= hi {
            let mid = (lo + hi) / 2;
            let mut tot = 0;

            for i in 1..(1 << n as usize) {
                let m = Self::bit_count(i);
                if m % 2 == 1 {
                    tot += mid / lcm[i as usize];
                } else {
                    tot -= mid / lcm[i as usize];
                }
            }         
           
            if tot >= k as i64 {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        res
    }
}

3117. 划分数组得到最小的值之和

给你两个数组 nums 和 andValues，长度分别为 n 和 m。

数组的 值 等于该数组的 最后一个 元素。

你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 [li, ri]，子数组元素的按位AND运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，其中 & 表示按位AND运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。

示例 1：

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

输出： 12

解释：

唯一可能的划分方法为：

1. [1,4] 因为 1 & 4 == 0
2. [3] 因为单元素子数组的按位 AND 结果就是该元素本身
3. [3] 因为单元素子数组的按位 AND 结果就是该元素本身
4. [2] 因为单元素子数组的按位 AND 结果就是该元素本身

这些子数组的值之和为 4 + 3 + 3 + 2 = 12

示例 2：

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

1. [[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17
2. [[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19
3. [[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

子数组值之和的最小可能值为 17

示例 3：

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

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回 -1。

提示：

• 1 <= n == nums.length <= 104
• 1 <= m == andValues.length <= min(n, 10)
• 1 <= nums[i] < 105
• 0 <= andValues[j] < 105

地址

https://leetcode.cn/contest/weekly-contest-393/problems/minimum-sum-of-values-by-dividing-array/

题意

线段树

思路

1. 拿到这个题目时，关键在于给定的数组的长度范围为 $[1,10]$，此时自然而然想到了动态规划，此时假设 $dp[i][j]$ 表示 $nums$ 的前 $i$ 个元素被划分为 $j$ 个不相交的数组时最小值，此时我们可以很容易得写出 $O(mn^2)$ 复杂度的解法，比较容易但是会超时，此时我们知道:

$$dp[i][j] = \min(dp[k-1][j-1]) + nums[i], k-1 \in [0,i-1], if \quad nums[k] \And nums[k+1] \cdots \And nums[i] = andValues[j]$$

上述的递推关系在 $O(mn^2)$ 复杂度下很容易写出来，但是肯定会超时，这样就使得我们需要进行优化， $f(k,i) = nums[k] \And nums[k+1] \cdots \And nums[i]$，当满足$f(k,j) = andValues[j]$ 时，我们可以观察到我们知道 $k$ 一定是属于 $[0,i]$ 的某个子区间，即当满足 $k \in [a,b]$，此时 $0 \le a \le b \le i$，不属于 $[a,b]$ 区间以外的值我们不需要再计算，此时题目的关键有两点：

• 如果找到区间 $[a,b]$，满足 $k \in[a,b]$，使得 $f(k,i) = andValues[j]$，此时我们可以利用二分查找最大的 $b$，刚好使得 $f(b,i) = andValues[j]$，然后再次利用二分查找找到最大的 $a$​，满足即可。
• 在给定的区间 $k \in [a,b]$ 满足区间 $[0,k-1]$ 被分隔为 $j-1$ 个子数组构成的值之和的最小值，因为这样才可以地推到 $dp[i][j]$, 此时求区间的最小值，我们可以使用线段树即可，本身线段树倒不是特别难，但是细节处理不太好处理，线段树区间返回当前区间 $[l,r]$ 被分割为 $1,\cdots,10$ 个子树的最小值。

2. 复杂度分析:

• 时间复杂度：$O(mn\log n)$，其中 $n$ 表示数组 $nums$ 的长度, $m$ 表示 $andvalues$ 数组的长度;
• 空间复杂度：$O(mn)$，其中 $n$ 表示数组 $nums$ 的长度, $m$ 表示 $andvalues$ 数组的长度;

代码

#define CHL(x) (x * 2)
#define CHR(x) (x * 2 + 1)
const int MAXN = 4e5 + 7;

struct SegTreeNode {
    int l, r;
    vector<int> minVal;
};

SegTreeNode tree[MAXN];

void pushUpTree(int idx) {
    for (int i = 0; i < 10; i++) {
        tree[idx].minVal[i] = min(tree[CHL(idx)].minVal[i], tree[CHR(idx)].minVal[i]);
    }
}

void buildTree(int idx, int l, int r) {
    if (l > r) {
        return;
    }
    if (l == r) {
        tree[idx].l = tree[idx].r = l;
        tree[idx].minVal = vector<int>(10, INT_MAX);
        return;
    }
    tree[idx].l = l;
    tree[idx].r = r;
    tree[idx].minVal = vector<int>(10, INT_MAX);
    
    int mid = (l + r) / 2;
    buildTree(CHL(idx), l, mid);
    buildTree(CHR(idx), mid + 1, r);
    pushUpTree(idx);
}

void updateTree(int x, int i, int val, int idx) {
    if (x < tree[idx].l || x > tree[idx].r) {
        return;
    }
    if (x == tree[idx].l && x == tree[idx].r) {
        tree[idx].minVal[i] = val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (x <= mid) {
        updateTree(x, i, val, CHL(idx));
    } else {
        updateTree(x, i, val, CHR(idx));
    }
    pushUpTree(idx);
}

int queryTree(int l, int r, int i, int idx) {
    if (r < tree[idx].l || l > tree[idx].r) {
        return INT_MAX;
    }
    if (l <= tree[idx].l && r >= tree[idx].r) {
        return tree[idx].minVal[i];
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (r <= mid) {
        return queryTree(l, r, i, CHL(idx));
    } else if (l > mid) {
        return queryTree(l, r, i, CHR(idx));
    } else {
        return min(queryTree(l, mid, i, CHL(idx)), queryTree(mid + 1, r, i, CHR(idx)));
    }
}

class Solution {
public:
    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
        int n = nums.size(), m = andValues.size();
        vector<int> cnt(21, -1);
        vector<vector<int>> f(n, vector<int>(m, -1));
        vector<vector<int>> g(n, vector<int>(m, -1));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 20; j++) {
                if (((nums[i] >> j) & 1) == 0) {
                    cnt[j] = i;
                }
            }
            for (int j = 0; j < m; j++) {
                int val = andValues[j];
                int left = 0, right = i;
                for (int k = 0; k <= 20; k++) {
                    if ((val >> k) & 1) {
                        left = max(left, cnt[k] + 1);
                    } else {
                        right = min(right, cnt[k]);
                    }
                }
                if (left <= right) {
                    f[i][j] = left;
                    g[i][j] = right;
                }
            }
        }

        buildTree(1, 0, n - 1);
        int prefix = nums[0];
        for (int i = 0; i < n; i++) {
            prefix &= nums[i];
            if (prefix == andValues[0]) {
                updateTree(i, 0, nums[i], 1);
            }
            for (int j = 1; j < m; j++) {
                int left = f[i][j], right = g[i][j];
                if (left == -1 || right == -1) {
                    continue;
                }
                if (right > 0) {
                    int cur = queryTree(max(left - 1, 0), right - 1, j - 1, 1);
                    if (cur != INT_MAX) {
                        updateTree(i, j, cur + nums[i], 1);
                    }
                }
            }
        }
        
        int ans = queryTree(n - 1, n - 1, m - 1, 1);
        return ans == INT_MAX ? -1 : ans;
    }
};

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者