当前位置: 首页 > news >正文

做企业网站需要提供什么资料百度网站名称及网址

做企业网站需要提供什么资料,百度网站名称及网址,网站如何做竞价,搜索引擎分析论文一、题目 1、题目描述 给你一个下标从 0 开始的二进制数组 nums,其长度为 n ;另给你一个 正整数 k 以及一个 非负整数 maxChanges 。 Alice 在玩一个游戏,游戏的目标是让 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] == 1nums[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(vector<int>& 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, initial=0))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 * 2
cpp
 ​
class Solution {
public:long long minimumMoves(vector<int>& nums, int k, int maxChanges) {int c = 0;std::vector<int> 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::vector<long 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;
};

http://www.ritt.cn/news/19166.html

相关文章:

  • 彩票网站建设平台手机百度高级搜索入口在哪里
  • wordpress数据库重装长沙seo优化首选
  • 免费的网站模板下载百度认证有什么用
  • 做poster的网站百度平台营销收费标准
  • 电大企业网站建设论文范文郑州seo管理
  • 南阳开网站制作google app下载
  • 天津建设网站官网seo站点是什么意思
  • 监管网站建设情况百度搜索引擎的特点
  • 站长工具app下载深圳整合营销
  • 内蒙建设工程信息网站seo搜索引擎优化费用
  • 惠州住房和城乡建设局网站天津百度分公司
  • 政府蒙古文网站建设汇报谷歌seo排名公司
  • 怎样查询自己购房网签成功外贸网站优化公司
  • 广州做网站建设哪家专业html网页制作
  • 湘潭网站优化宁波seo外包快速推广
  • 做网站月薪两万大学生网页设计主题
  • 完整的网站建设郑州网络推广专业公司
  • 国内网站建设流程重庆seo网络推广关键词
  • 广东商城网站建设公司如何找到网络公关公司
  • 做愛偷拍视频网站网络推广营销技巧
  • 不配置iis做网站怎样做好网络推广呀
  • 网站嵌套代码网络推广员工作好做吗
  • 做网站 就上微赞网营销推广软文
  • b2b网站举例商业软文
  • 网站动态banner怎么做如何增加网站的外链
  • 亚马逊网站首页seo推广软件排名
  • xenforo和wordpress企业站seo报价
  • 在线看免费电影网站百度指数 移民
  • 网络销售是做网站推广单页面网站如何优化
  • 网站设计网站开发湖南省人民政府