100256. Latest Time You Can Obtain After Replacing Characters
给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 "?" 替换。
12 小时制时间格式为 "HH:MM" ，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 00:00，最晚的时间为 11:59。
你需要将 s 中的 所有 "?" 字符替换为数字，使得结果字符串代表的时间是一个 有效 的 12 小时制时间，并且是可能的 最晚 时间。
返回结果字符串。
测试样例：
输入：s = "1?:?4"
输出："11:54"
解释：通过替换 "?" 字符，可以得到的最晚12小时制时间是 "11:54"。
解答：暴力枚举所有可能，判断最大的时间。
class Solution {
public String findLatestTime(String s) {
String[] tmp = s.split(":");
String leftMax = mark(tmp[0], 11), rightMax = mark(tmp[1], 59);
return leftMax + ":" + rightMax;
}
private String mark(String tmp, int max) {
int best = -1;
for (int i = 0; i <= max; ++i) {
if (isMatch(tmp.charAt(0), i / 10) && isMatch(tmp.charAt(1), i % 10)) {
best = i;
}
}
return best < 10 ? ("0" + best) : String.valueOf(best);
}
private boolean isMatch(char c, int num) {
return c == '?' || c == (num + '0');
}
}100265. Maximum Prime Difference
给你一个整数数组 nums。
返回两个（不一定不同的）素数在 nums 中 下标 的 最大距离。
测试样例：
输入：nums = [4,2,9,5,3]
输出：3
解释：nums[1]、nums[3] 和 nums[4] 是素数。因此答案是 |4 - 1| = 3。
解答：判断素数的位置，然后计算第一个和最后一个的位置。
class Solution {
public int maximumPrimeDifference(int[] nums) {
int left = nums.length, right = -1;
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == 1) continue;
boolean isPrime = true;
for (int j = 2; j * j <= nums[i]; ++j) {
if (nums[i] % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
left = Math.min(i, left);
right = Math.max(i, right);
}
res = Math.max(res, right - left);
}
return res;
}
}100267. Kth Smallest Amount With Single Denomination Combination
给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。
你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。
返回使用这些硬币能制造的 第 kth 小 金额。
测试样例：
输入：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等。
解答：首先可以想到的是利用二分查找可以迅速定位到需要的数字。其次的问题，在于当前数字中有多少满足要求的数字（即能被coins中的数字整除）。总的coins长度小于15，就基本利用暴力算法了，利用暴力枚举所有数字组合的可能，根据容斥原理，计算能被整除的个数了。
class Solution {
public long findKthSmallest(int[] coins, int k) {
int max = 1 << coins.length;
List<long[]> mem = new ArrayList<>();
for (int i = 1; i < max; ++i) {
long count = 0, g = -1;
for (int j = 0; j < coins.length; ++j) {
int tmp = (i >> j) & 1;
if (tmp == 1) {
++count;
if (g == -1) {
g = coins[j];
} else {
g = g / gcd(g, coins[j]) * coins[j];
}
}
}
mem.add(new long[]{g, count});
}
long left = 0, right = 25L * k;
while (left < right) {
long mid = left + (right - left) / 2;
if (count(mid, mem) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private long count(long mid, List<long[]> mem) {
long res = 0;
for (long[] t : mem) {
if (t[1] % 2 == 1) {
res += mid / t[0];
} else {
res -= mid / t[0];
}
}
return res;
}
public long gcd(long x, long y) {
while (y != 0) {
long t = y;
y = x % y;
x = t;
}
return x;
}
}100259. Minimum Sum of Values by Dividing Array
给你两个数组 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 。
测试样例：
输入：nums = [1,4,3,3,2], andValues = [0,3,3,2]
输出：12
解释：唯一可能的划分方法为：
- [1,4] 因为 1 & 4 == 0
- [3] 因为单元素子数组的按位 AND 结果就是该元素本身
- [3] 因为单元素子数组的按位 AND 结果就是该元素本身
- [2] 因为单元素子数组的按位 AND 结果就是该元素本身
这些子数组的值之和为 4 + 3 + 3 + 2 = 12
解答：这题其实难度不到8分，但是代码写起来比较麻烦。我们首先要计算出，当前andValues[i]时，nums[j]为最后一个数字的情况下，什么范围可能满足。这个可以利用前缀和来计算，我们需要记录第一个0出现的位置。因为&的特性，可以比较轻松的确定范围。最后利用SegmentTree来计算区间最小，来更新当前数字。
class Solution {
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = Math.min(tree[i * 2], tree[i * 2 + 1]);
}
public int minRange(int l, int r) {
l += n;
r += n;
int sum = Integer.MAX_VALUE;
while (l <= r) {
if ((l % 2) == 1) {
sum = Math.min(sum, tree[l]);
l++;
}
if ((r % 2) == 0) {
sum = Math.min(sum, tree[r]);
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public int minimumValueSum(int[] nums, int[] andValues) {
int len = nums.length;
int[][] zero = new int[len][17];
int[] lastPos = new int[17];
Arrays.fill(lastPos, len);
for (int i = 0; i < len; ++i) {
for (int j = 0; j <= 16; ++j) {
if (!isMark(nums[i], j)) {
lastPos[j] = i;
}
zero[i][j] = lastPos[j];
}
}
int[] dp = new int[len];
Arrays.fill(dp, Integer.MAX_VALUE);
int tmp = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; ++i) {
tmp &= nums[i];
if (tmp == andValues[0]) {
dp[i] = nums[i];
}
}
for (int ap = 1; ap < andValues.length; ++ap) {
SegmentTree tree = new SegmentTree(dp);
int[] nextDp = new int[len];
for (int i = 0; i < nums.length; ++i) {
nextDp[i] = Integer.MAX_VALUE;
int left = 0, right = i;
for (int offset = 0; offset <= 16; ++offset) {
if (isMark(andValues[ap], offset)) {
left = Math.max(left, zero[i][offset] + 1 > len ? 0 : (zero[i][offset] + 1));
} else {
right = Math.min(right, zero[i][offset] + 1 > len ? -1 : zero[i][offset]);
}
}
left = Math.max(left - 1, 0);
right -= 1;
if (left <= right) {
int bestRange = tree.minRange(left, right);
if (bestRange < Integer.MAX_VALUE) {
nextDp[i] = bestRange + nums[i];
}
}
}
dp = nextDp;
}
return dp[len - 1] == Integer.MAX_VALUE ? -1 : dp[len - 1];
}
private boolean isMark(int num, int offset) {
int tmp = (num >> offset) & 1;
return tmp == 1;
}
}