目录
一，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;
}
}
