前言
不管别人怎么说，现在的我，都是世界上最幸福的女孩。
整体评价
该周赛的t3 很像 第314场周赛的t3，堪称姊妹版。t4是经典的折半搜索的应用。
推荐该周赛。
更多解题报告详见：珂朵莉MM的解题报告汇总
1. 检查数组是否经排序和轮转得到
就是找第一个相邻逆序对，然后把该点作为起点，进行验证。
这样的话，寻找为, 验证为，整体为。
Java
class Solution {
public boolean check(int[] nums) {
// 找到第一个相邻逆序对
int pos = -1;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
pos = i;
break;
}
}
if (pos == -1) return true;
// 旋转验证
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
int next = (pos + 1 + i) % n;
if (nums[next] > nums[(next + 1) % n]) return false;
}
return true;
}
}2. 移除石子的最大得分
属于分类讨论题吧
假设a,b,c已排序，a最小，c最大
Java
class Solution {
public int maximumScore(int a, int b, int c) {
int[] arr = new int[] {a, b, c};
Arrays.sort(arr);
a = arr[0];
b = arr[1];
c = arr[2];
if (c >= a + b) return a + b;
return (a + b + c) / 2;
}
}3. 构造字典序最大的合并字符串
属于贪心的范畴，不过在模拟构造的过程中，复杂度相对较高。
双指针处理两个串，如果两字符首字母不相等的情况下，选择最大的。
如果相等，就比较两个剩下的字符串，谁更有潜力，则选哪个。
因为两字符串的长度(),所以这边时间复杂度最坏情况下为, 在可接受的范围内。
Java
class Solution {
int compare(char[] str1, char[] str2, int t0, int t1) {
while (t0 < str1.length && t1 < str2.length) {
if (str1[t0] == str2[t1]) {
t0++; t1++;
} else {
if (str1[t0] > str2[t1]) return -1;
else return 1;
}
}
if (t0 < str1.length) return -1;
return 1;
}
public String largestMerge(String word1, String word2) {
char[] buf1 = word1.toCharArray();
char[] buf2 = word2.toCharArray();
int i = 0, j = 0;
StringBuilder sb = new StringBuilder();
while (i < buf1.length && j < buf2.length) {
if (buf1[i] != buf2[j]) {
if (buf1[i] > buf2[j]) {
sb.append(buf1[i]);
i++;
} else {
sb.append(buf2[j]);
j++;
}
} else {
int res = compare(buf1, buf2, i, j);
if (res == -1) {
sb.append(buf1[i]);
i++;
} else {
sb.append(buf2[j]);
j++;
}
}
}
while (i < buf1.length) {
sb.append(buf1[i++]);
}
while (j < buf2.length) {
sb.append(buf2[j++]);
}
return sb.toString();
}
}4. 最接近目标值的子序列和
方法一： 折半搜索
这种只能Brute Force解法，不过适用的范围有效，一般对于可行，往上就够呛。
不过这题的范围刚好是, 所以这边的一个思路是如何把40拆成两个20来解。
而本题的思路，就是基于这个朴素的想法，引入的折半搜索的解法。
把40大小的数组，拆分两个数组，每个数组，分别构建自己的子序列和集合
以集合为基准，寻找最接近goal，在的另一个部分，借助二分即可。
这边使用java的TreeSet来实现了。
时间复杂度分两个阶段：
- 计算子序列和的集合，
- 查找最接近goal的遍历过程，
Java
class Solution {
TreeSet<Long> compute(int[] nums, int s, int e) {
TreeSet<Long> sets = new TreeSet<>();
int n = e - s;
int range = 1 << n;
for (int i = 0; i < range; i++) {
long tsum = 0l;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
tsum += nums[s + j];
}
}
sets.add(tsum);
}
return sets;
}
public int minAbsDifference(int[] nums, int goal) {
// 折半搜索
int n = nums.length;
long ans = Math.abs(goal);
if (n <= 8) {
int range = 1 << n;
for (int i = 0; i < range; i++) {
long tsum = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
tsum += nums[j];
}
}
ans = Math.min(ans, Math.abs(tsum - goal));
}
return (int)ans;
} else {
// 折半搜索
TreeSet<Long> ts1 = compute(nums, 0, n / 2);
TreeSet<Long> ts2 = compute(nums, n / 2, n);
for (Long tv: ts1) {
Long k1 = ts2.floor(goal - tv);
if (k1 != null) {
ans = Math.min(ans, Math.abs(tv + k1 - goal));
}
Long k2 = ts2.ceiling(goal - tv);
if (k2 != null) {
ans = Math.min(ans, Math.abs(tv + k2 - goal));
}
if (ans == 0) return 0;
}
return (int)ans;
}
}
}方法二：分治
这个分治法，挺有趣的，最后的双指针，需要细细体会下。
Java
import java.util.Optional;
class Solution {
TreeSet<Long> divide(int[] nums, int s, int e) {
TreeSet<Long> sets = new TreeSet();
int n = e - s;
int range = 1 << n;
for (int i = 0; i < range; i++) {
long t = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
t += nums[s + j];
}
}
sets.add(t);
}
return sets;
}
public int minAbsDifference(int[] nums, int goal) {
if (nums.length == 1) {
return Math.min(Math.abs(nums[0] - goal), Math.abs(goal));
}
// 分治的思想
TreeSet<Long> left = divide(nums, 0, nums.length / 2);
TreeSet<Long> right = divide(nums, nums.length / 2, nums.length);
long lGoal = goal;
long ans = Math.abs(goal);
ans = Math.min(
ans,
Math.min(
Math.abs(Optional.ofNullable(left.floor(lGoal)).orElse(0l) - lGoal),
Math.abs(Optional.ofNullable(left.ceiling(lGoal)).orElse(0l) - lGoal)
)
);
ans = Math.min(
ans,
Math.min(
Math.abs(Optional.ofNullable(right.floor(lGoal)).orElse(0l) - lGoal),
Math.abs(Optional.ofNullable(right.ceiling(lGoal)).orElse(0l) - lGoal)
)
);
// *) 考虑合并
long[] arr1 = left.stream().mapToLong(Long::valueOf).toArray();
long[] arr2 = right.stream().mapToLong(Long::valueOf).toArray();
// 双指针
int r = arr2.length;
for (int i = 0; i < arr1.length; i++) {
long t1 = arr1[i];
while (r - 1 >= 0 && t1 + arr2[r - 1] >= goal) {
ans = Math.min(ans, t1 + arr2[r - 1] - goal);
r--;
}
if (ans == 0) return 0;
// 这个特别要注意(因为是绝对值)
if (r - 1 >= 0) {
ans = Math.min(ans, Math.abs(t1 + arr2[r - 1] - goal));
}
}
return (int)ans;
}
}写在最后
评论 (1)
