上岸算法LeetCode Weekly Contest 280解题报告
【 NO.1 得到 0 的操作数】解题思路
签到题，模拟操作即可。
代码展示
class Solution {
public int countOperations(int num1, int num2) {
int res = 0;
for (; num1 * num2 != 0; res++) {
if (num1 > num2) {
num1 -= num2;
} else {
num2 -= num1;
}
}
return res;
}
}
【 NO.2 使数组变成交替数组的最少操作数】
解题思路
统计每种数字在奇数、偶数下标上的数量，然后使用最多的和次多的作为最终数字即可。
代码展示
class Solution {
public int minimumOperations(int[] nums) {
Map<Integer, Integer> cnt0 = new HashMap<>(); // 偶数下标计数
Map<Integer, Integer> cnt1 = new HashMap<>(); // 奇数下标计数
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) {
cnt0.put(nums, cnt0.getOrDefault(nums, 0) + 1);
} else {
cnt1.put(nums, cnt1.getOrDefault(nums, 0) + 1);
}
}
int[] cnt0Max = getMax(cnt0);
int[] cnt1Max = getMax(cnt1);
if (cnt0Max != cnt1Max) {
return nums.length - cnt0.getOrDefault(cnt0Max, 0) - cnt1.getOrDefault(cnt1Max, 0);
}
return nums.length - Math.max(
cnt0.getOrDefault(cnt0Max, 0) + cnt1.getOrDefault(cnt1Max, 0),
cnt0.getOrDefault(cnt0Max, 0) + cnt1.getOrDefault(cnt1Max, 0)
);
}
private int[] getMax(Map<Integer, Integer> cnt) {
int[] res = new int;
for (var c : cnt.keySet()) {
if (cnt.getOrDefault(res, 0) <= cnt.get(c)) {
res = res;
res = c;
} else if (cnt.getOrDefault(res, 0) <= cnt.get(c)) {
res = c;
}
}
return res;
}
}
【 NO.3 拿出最少数目的魔法豆】
解题思路
前缀和。排序后，枚举分界点，分界点之前的全部置零，分界点之后的全部置为与分界点处相同的数目，通过前缀和可以快速计算。
代码展示
class Solution {
public long minimumRemoval(int[] beans) {
Arrays.sort(beans);
var sum = new IntervalSum(beans);
long res = sum.suffix(0) - (long) beans * (long) beans.length;
for (int i = 0; i < beans.length - 1; i++) {
// -> 0;
res = Math.min(res, sum.prefix(i) + sum.suffix(i + 1) - (long) beans * (beans.length - i - 1));
}
return res;
}
}
class IntervalSum {
private final long[] pre;
public IntervalSum(int[] arr) {
pre = new long;
pre = arr;
for (int i = 1; i < arr.length; i++) {
pre = pre + arr;
}
}
// interval
public long prefix(int i) {
return interval(0, i + 1);
}
// == interval [i, length)
public long suffix(int i) {
return interval(i, pre.length);
}
// [start, end)
public long interval(int start, int end) {
end--;
return pre - (start == 0 ? 0 : pre);
}
}
【 NO.4 数组的最大与和】
解题思路
记忆化搜索，令 f 表示 slots 状态为 i 时，还能获取到多少加和
状态转移：枚举当前数字放到哪个 slot 里面
答案：f
其中 i 是一个 18 位的二进制数，每两位表示一个 slot 里已经放入了多少个数字
代码展示
class Solution {
public int maximumANDSum(int[] nums, int numSlots) {
Map<Integer, Integer> mem = new HashMap<>();
return maximumANDSum(0, nums, numSlots, nums.length, mem);
}
private int maximumANDSum(int stat, int[] nums, int numSlots, int numLeft, Map<Integer, Integer> mem) {
if (mem.containsKey(stat)) {
return mem.get(stat);
}
if (numLeft == 0) {
return 0;
}
int curRes = 0;
for (int i = 1; i <= numSlots; i++) {
int slot = getSlot(stat, i);
if (slot == 2) {
continue;
}
int and = i & nums;
int stat2 = setSlot(stat, i, slot + 1);
curRes = Math.max(curRes, and + maximumANDSum(stat2, nums, numSlots, numLeft - 1, mem));
}
mem.put(stat, curRes);
return curRes;
}
// i start from 1
private int getSlot(int bits, int i) {
int offset = (i - 1) * 2;
return (bits >> offset) & 0b11;
}
// num = 0 or 1 or 2
private int setSlot(int bits, int i, int num) {
int offset = (i - 1) * 2;
bits -= bits & (0b11 << offset);
bits += num << offset;
return bits;
}
}
页:
[1]