让人做网站需要准备什么条件,网站开发报价单模板,做贵网站多少钱,网站建设论文中期总结一、题目
1、题目描述 给你一个下标从 0 开始的二进制数组 nums#xff0c;其长度为 n #xff1b;另给你一个 正整数 k 以及一个 非负整数 maxChanges 。 Alice 在玩一个游戏#xff0c;游戏的目标是让 Alice 使用 最少 数量的 行动 次数从 nums 中拾起 k 个 1 。游戏开始…一、题目
1、题目描述 给你一个下标从 0 开始的二进制数组 nums其长度为 n 另给你一个 正整数 k 以及一个 非负整数 maxChanges 。 Alice 在玩一个游戏游戏的目标是让 Alice 使用 最少 数量的 行动 次数从 nums 中拾起 k 个 1 。游戏开始时Alice 可以选择数组 [0, n - 1] 范围内的任何索引 aliceIndex 站立。如果 nums[aliceIndex] 1 Alice 会拾起一个 1 并且 nums[aliceIndex] 变成0这 不算 作一次行动。之后Alice 可以执行 任意数量 的 行动包括零次在每次行动中 Alice 必须 恰好 执行以下动作之一 选择任意一个下标 j ! aliceIndex 且满足 nums[j] 0 然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。选择任意两个相邻的下标 x 和 y|x - y| 1且满足 nums[x] 1, nums[y] 0 然后交换它们的值将 nums[y] 1 和 nums[x] 0。如果 y aliceIndex在这次行动后 Alice 拾起一个 1 并且 nums[y] 变成 0 。 返回 Alice 拾起 恰好 k 个 1 所需的 最少 行动次数。 2、接口描述
python3
class Solution:def minimumMoves(self, nums: List[int], k: int, maxChanges: int) - int:
cpp
class Solution {
public:long long minimumMoves(vectorint nums, int k, int maxChanges) {}
};
js
/*** param {number[]} nums* param {number} k* param {number} maxChanges* return {number}*/
var minimumMoves function(nums, k, maxChanges) {}; 3、原题链接
3086. 拾起 K 个 1 需要的最少行动次数 二、解题报告
1、思路分析
操作1其实就是提供了一种两步得到1的方案
我们考虑两步一个1一定是最优的吗
如果1、2、3个连续个1我们发现此时分别需要0、1、2步
所以这道题是有corner case的
我们这样考虑
3个以内的连续1的最大连续长度记为c如果拿掉c个剩下的1可以都通过2步得到
我们的答案就是c - 1 (k - c) * 2
否则问题就变成了一个很简单的中位数贪心问题
扫描一遍k - maxChanges的窗口O(1)计算其中位数贪心下的解维护最优解即可
2、复杂度 时间复杂度 O(N)空间复杂度O(N) 3、代码详解
python3
fmax lambda x, y: x if x y else y
fmin lambda x, y: x if x y else y
class Solution:def minimumMoves(self, nums: List[int], k: int, maxChanges: int) - int:pos []c 0for i, x in enumerate(nums):if x 0:continuepos.append(i)c fmax(c, 1)if i 0 and nums[i - 1]:if i 1 and nums[i - 2]:c 3c fmax(c, 2)c fmin(c, k)if maxChanges k - c:return fmax(c - 1, 0) (k - c) * 2n len(pos)acc list(accumulate(pos, initial0))res infsz k - maxChangesfor r in range(sz, n 1):l r - szmid l sz // 2s1 pos[mid] * (mid - l) - (acc[mid] - acc[l])s2 acc[r] - acc[mid] - pos[mid] * (r - mid)res fmin(res, s1 s2)return res maxChanges * 2cpp
class Solution {
public:long long minimumMoves(vectorint nums, int k, int maxChanges) {int c 0;std::vectorint pos;for (int i 0, n nums.size(); i n; i ) {if (!nums[i]) continue;pos.push_back(i);c max(c, 1);if (i nums[i - 1]) {if (i 1 nums[i - 2])c 3;c max(c, 2);}}c min(c, k);if (maxChanges k - c)return max(c - 1, 0) (k - c) * 2;int n pos.size(), sz k - maxChanges;std::vectorlong long acc(n 1);for (int i 0; i n; i ) acc[i 1] acc[i] pos[i];long long res 1e10;for (int r sz; r n; r ) {int l r - sz, mid l sz / 2;long long s1 1LL * pos[mid] * (mid - l) - (acc[mid] - acc[l]);long long s2 acc[r] - acc[mid] - 1LL * pos[mid] * (r - mid);res min(res, s1 s2);\}return res maxChanges * 2LL;}
};
js
/*** param {number[]} nums* param {number} k* param {number} maxChanges* return {number}*/
var minimumMoves function(nums, k, maxChanges) {let c 0;let pos [];for (let i 0; i nums.length; i ) {if (nums[i] 0) continue;pos.push(i);c Math.max(c, 1);if (i nums[i - 1]) {if (i 1 nums[i - 2])c 3;c Math.max(c, 2);}}c Math.min(c, k);if (maxChanges k - c)return Math.max(c - 1, 0) (k - c) * 2;let n pos.length;let acc new Array(n 1).fill(0);for (let i 0; i n; i )acc[i 1] pos[i] acc[i];let res Infinity, sz k - maxChanges;for (let r sz; r n; r ) {let l r - sz, mid l parseInt(sz / 2);let s1 pos[mid] * (mid - l) - (acc[mid] - acc[l]);let s2 acc[r] - acc[mid] - pos[mid] * (r - mid);res Math.min(res, s1 s2);}return res maxChanges * 2;
};
