T1: 对数组执行操作
思路：模拟
public int[] applyOperations(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == nums[i + 1]) {
nums[i] = 2 * nums[i];
nums[i + 1] = 0;
}
}
int[] res = new int[n];
int index = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
res[index++] = nums[i];
}
}
return res;
}
T2: 长度为 K 子数组中的最大和
思路：滑动窗口
public long maximumSubarraySum(int[] nums, int k) {
int n = nums.length;
if (k > n) {
return 0;
}
// 哈希存储当前窗口内的数组元素
Map<Integer, Integer> map = new HashMap<>();
long res = 0;
long sum = 0;
int left = 0, right = 0;
while (right < n) {
sum += nums[right];
map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
if (right - left + 1 == k) {
if (map.size() == k) {
res = Math.max(res, sum);
}
sum -= nums[left];
map.put(nums[left], map.get(nums[left]) - 1);
if (map.get(nums[left]) == 0) {
map.remove(nums[left]);
}
left += 1;
}
right += 1;
}
return res;
}
T3: 雇佣 K 位工人的总代价
思路：小顶堆模拟
左堆堆顶元素 \(\le\) 右堆堆顶元素：弹出左堆值
左堆堆顶元素 \(\gt\) 右堆堆顶元素：弹出右堆值
public long totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
long res = 0;
// 考虑特殊情况，快速返回结果
if (k == n) {
for (int cost : costs) {
res += cost;
}
return res;
}
if (candidates * 2 >= n) {
Queue<Integer> heap = new PriorityQueue<>();
for (int cost : costs) {
heap.offer(cost);
}
while (k > 0) {
res += heap.poll();
k -= 1;
}
return res;
}
// 小顶堆模拟
Queue<int[]> leftMin = new PriorityQueue<>((o1, o2) -> {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
else {
return o1[0] - o2[0];
}
});
Queue<int[]> rightMin = new PriorityQueue<>((o1, o2) -> {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
else {
return o1[0] - o2[0];
}
});
int curLen = n;
for (int i = 0; i < candidates; ++i) {
leftMin.offer(new int[]{costs[i], i});
rightMin.offer(new int[]{costs[n - 1 - i], n - 1 - i});
}
int leftIndex = candidates;
int rightIndex = n - candidates - 1;
while (curLen > 2 * candidates && k > 0) {
if (leftMin.peek()[0] <= rightMin.peek()[0]) {
res += leftMin.poll()[0];
leftMin.offer(new int[]{costs[leftIndex], leftIndex});
leftIndex += 1;
curLen -= 1;
}
else {
res += rightMin.poll()[0];
rightMin.offer(new int[]{costs[rightIndex], rightIndex});
rightIndex -= 1;
curLen -= 1;
}
k -= 1;
}
while (k > 0) {
if (leftMin.isEmpty()) {
res += rightMin.poll()[0];
}
else if (rightMin.isEmpty()) {
res += leftMin.poll()[0];
}
else {
res += (leftMin.peek()[0] <= rightMin.peek()[0] ? leftMin.poll()[0] : rightMin.poll()[0]);
}
k -= 1;
}
return res;
}
T4: 最小移动总距离
本题解答参考学习 灵茶山艾府 大佬的题解。
思路：动态规划
动态规划的使用前提条件
对于机器人 x 和 y ，且位置 x < y
对于修理工厂 f1 和 f2 ，且位置 f1 < f2
则移动距离最小的做法为 x-->f1, y-->f2
所以，将机器人和工厂均按位置排序后，有如下结论：
每个修理工厂维修的机器人是一个连续的序列
动态规划定义
dp[i][j]：前 i 个工厂修理前 j 个机器人的最小移动距离
枚举第 i 个工厂修理的机器人个数 k
\[dp[i][j] = Math.min(dp[i-1][j-k] + cost, dp[i][j]) \qquad (0 \le k \le min(j, factory[i][1]))
\]
public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
int[] robotArr = new int[robot.size()];
robotArr = robot.stream().mapToInt(i -> i).toArray();
Arrays.sort(robotArr);
Arrays.sort(factory, (o1, o2)->{
return o1[0] - o2[0];
});
int m = robotArr.length;
int n = factory.length;
long[][] dp = new long[n + 1][m + 1];
/**
* 初始化
* dp[i][0] = 0
* dp[i][1] = inf
*/
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = (long) 1e18;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// k = 0 的情况
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
// 枚举第 i 个工厂修理了 k 个机器人
// 则前 i - 1 个工厂修理 j - k 个机器人
long cost = 0;
for (int k = 1; k <= Math.min(j, factory[i - 1][1]); k++) {
cost += Math.abs(factory[i - 1][0] - robotArr[j - k]);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k] + cost);
}
}
}
return dp[n][m];
}
由于第i层的状态 dp[i] 的状态只和上一层 dp[i-1]的状态有关，所有该 dp 数组可以状态压缩
注意：状态压缩时，需要倒序遍历 robot ，保证状态覆盖的顺序是正确的
public long minimumTotalDistanceCompressDP(List<Integer> robot, int[][] factory) {
int[] robotArr = new int[robot.size()];
robotArr = robot.stream().mapToInt(i -> i).toArray();
Arrays.sort(robotArr);
Arrays.sort(factory, (o1, o2)->{
return o1[0] - o2[0];
});
// DP
int m = robotArr.length;
long[] dp = new long[m + 1];
for (int i = 1; i < dp.length; i++) {
dp[i] = (long) 1e18;
}
dp[0] = 0;
for (int[] fa : factory) {
for (int j = m; j >= 1; j--) {
long cost = 0;
for (int k = 1; k <= Math.min(j, fa[1]); k++) {
cost += Math.abs(fa[0] - robotArr[j - k]);
dp[j] = Math.min(dp[j], dp[j - k] + cost);
}
}
}
return dp[m];
}
