Leetcode - 周赛393

目录

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

二，3115. 素数的最大距离

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

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

---

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

本题是一道模拟题，直接上代码。

代码如下：

class Solution {
    public String findLatestTime(String s) {
        char[] t = s.toCharArray();
        if(t[0] == '?')
            t[0] = t[1]=='?'||t[1]<='1'?'1':'0';
        if(t[1] == '?')
            t[1] = t[0]=='1'?'1':'9';
        if(t[3] == '?')
            t[3] = '5';
        if(t[4] == '?')
            t[4] = '9';
        return new String(t);
    }
}

二，3115. 素数的最大距离

本题主要考察素数的定义，需要注意的是该题的范围包括1，所以需要额外判断一下。

代码如下： 

class Solution {
    public int maximumPrimeDifference(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while(i < n){
            if(is_prime(nums[i])){//找第一个出现的素数
                break;
            }
            i++;
        }
        while(j >= 0){
            if(is_prime(nums[j])){//找最后一个出现的素数
                break;
            }
            j--;
        }
        return j-i;
    }
    boolean is_prime(int x){//校验是否是素数
        for(int i=2; i<=Math.sqrt(x); i++){
            if(x%i == 0)
                return false;
        }
        return x>=2;
    }
}

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

二分 + lcm + 容斥原理

根据题目和它给的数据范围，可以发现直接求第k小是非常困难的，所以直接想到二分答案，想使用二分，还要看题目是否有单调的性质，可以发现，当枚举的数越大，所能创造的金额就越多，就越容易满足条件，所以可以二分。

接下来就是实现check方法，该方法需要统计在【0，二分答案】之间可以产生多少不重复的金额，再具体一点，就是计算在【0，二分答案】之间，coins数组中每个数及其倍数的并集，这里就要使用到容斥原理：

• |A∪B| = |A| + |B| - |A∩B|
• |A∪B∪C| = |A| + |B| - |A∩B| + |C| - |A∩C| - |B∩C| + |A∩B∩C|
• ......

发现当求∩的集合的数量为单数时，它前面的符号是 +，为偶数时，它前面的符号是 -，也就是奇正偶负

搞清楚了符号问题，那么这里A∩..这个集合的大小该如何计算呢？举个例子，coins=[2，3]

求在【0，14】范围内 |2的倍数∩3的倍数| 的大小，2的倍数=[2，4，6，8，10，12，14]，3的倍数=[3，6，9，12]，它们的交集=[6，12]，而这恰好是[2，3]最小公倍数的倍数，所以交集的大小就等于【二分答案（在这里指14） / 最小公倍数（在这里指6）】

而两个数的最小公倍数 = 两个数的乘积 / 两个数的最大公约数，如果最大公约数不会求，可以去网上学习一下辗转相除法，这里就不过多介绍了.

代码如下：

class Solution {
    public long findKthSmallest(int[] coins, int k) {
        Arrays.sort(coins);
        long l = k - 1;
        long r = (long)coins[0] * k;
        while(l <= r){//二分答案
            long mid = (l + r) / 2;
            if(check(mid, coins, k)){
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r + 1;
    }
    boolean check(long m, int[] coins, int k){
        int n = coins.length;
        long cnt = 0;
        for(int i=1; i<(1<<n); i++){//枚举子集
            long res_lcm = 1;
            for(int j=0; j<n; j++){
                if((i>>j&1) == 1){//如果i>>j&1为1,说明子集包括coins[j]
                    res_lcm = lcm(res_lcm, coins[j]);
                }
            }
            cnt += Integer.bitCount(i)%2==1?m/res_lcm:-m/res_lcm;
        }
        return cnt >= k;
    }
 
    long lcm(long a, long b){//最小公倍数
        return a*b/gcd(a,b);
    }
    long gcd(long a, long b){//最大公约数
        return b==0?a:gcd(b,a%b);
    }
}

 

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

划分dp

使用dfs来实现，dfs(i，j，and)的定义：前 i 个数分成 j 段所得到的最小子数组值之和，and是第 j 段的&值

dfs(i，j，and)有两个来源：

• 当前nums[i]不划分，划分段数不变，即 j 不增加，用dfs表示就是 dfs(i+1，j，and)
• 当前nums[i]划分到新的子数组中，划分段数 j 加一，用dfs表示就是 dfs(i+1，j+1，and) + nums[i]，不过还需要注意的是，只有 and == andValue[j]时，才能划分
• 根据上述可以推出 dfs(i，j，and) = Math.min(dfs(i+1，j，and)，dfs(i+1，j+1，and) + nums[i]）

dfs终止条件(n=nums.length，m=andValues.length)：

• 要保证剩下的数 n-i 可以分成 m-j 段，即 if ( n-i < m-j )，返回 Integer.MAX_VALUE/2
• 当数组已经划分成了m段 j == m，如果 i == n，说明刚好划分完，返回 0；如果 i != n，说明还有数没划分，返回Integer.MAX_VALUE/2
• 根据&的数量越多，&值越小这个性质，可以剪枝，if (and < andValue[j])，return Integer.MAX_VALUE/2.

这里使用Integer.MAX_VALUE/2是为了防止溢出

代码如下：

class Solution {
    //划分dp - 前i个数分成j段
    //&越多，&值越小
    Map<String,Integer> map = new HashMap<>();
    int n, m;
    int[] nums, andValues;
    public int minimumValueSum(int[] nums, int[] andValues) {
        n = nums.length;
        m = andValues.length;
        this.nums = nums;
        this.andValues = andValues;
        int ans = dfs(0,0,-1);
        return ans == Integer.MAX_VALUE/2 ? -1 : ans;
    }
    int dfs(int i, int j, int and){
        String key = i + "-" + j + "-" + and;
        if(!map.isEmpty() && map.containsKey(key)) 
            return map.get(key);//记忆化
        if(n-i < m-j) 
            return Integer.MAX_VALUE/2;//剩下的数不足以分成m-j段
        if(j == m) 
            return i==n?0:Integer.MAX_VALUE/2;
        and &= nums[i];
        if(and < andValues[j])//剪枝
            return Integer.MAX_VALUE/2;
        int res = dfs(i+1, j, and);
        if(and == andValues[j])
            res = Math.min(res, dfs(i+1, j+1, -1) + nums[i]);
        map.put(key, res);
        return res;
    }
}