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

lc1040-移动石子直到连续II

题目描述

  • 在 X 轴上有 n 个不同位置的石子
  • 两端的石子往中间放,放完后,位置不能是两端
  • 放到石子连续为止,求最少次数与最多次数

示例

输入:[7,4,9]
输出:[1,2]
解释:
我们可以移动一次,4 -> 8,游戏结束。
或者,我们可以移动两次 9 -> 5,4 -> 6,游戏结束。
输入:[6,5,4,3,10]
输出:[2,3]
解释:
我们可以移动 3 -> 8,接着是 10 -> 7,游戏结束。
或者,我们可以移动 3 -> 7, 4 -> 8, 5 -> 9,游戏结束。
注意,我们无法进行 10 -> 2 这样的移动来结束游戏,因为这是不合要求的移动。

题解

  • 思路:需要分类讨论
    • 找一段长度为 n 的路径,使得石子最多,记为 m 个
    • m == n 时
    • m == n-1 时
      • 有空隙
      • 无空隙
    • m <= n-2 时
class Solution {
public:vector<int> numMovesStonesII(vector<int>& stones) {vector<int> res(2);int n = stones.size();sort(stones.begin(), stones.end());int m = stones.back() - stones[0] - (n - 1);res[1] = m - min(stones[1] - stones[0] - 1, stones[n - 1] - stones[n - 2] - 1);res[0] = n;for (int i = 0, j = 0; i < n; i ++ ) {while (stones[i] - stones[j] + 1 > n) j ++ ;m = i - j + 1;int r;if (m == n - 1 && stones[i] - stones[j] == i - j) r = 2;else r = n - m;res[0] = min(res[0], r);}return res;}
};
http://www.hskmm.com/?act=detail&tid=21127

相关文章:

  • 2025年9月29日
  • c++算法学习笔记
  • test5
  • 最高人民法院新劳动争议司法解释一 理解与适用
  • PyPI维护者遭遇钓鱼攻击:假冒登录网站威胁开源供应链安全
  • Tomcat 相关漏洞扫描器(一) - 指南
  • 题解:CF2125E Sets of Complementary Sums
  • 929
  • ManySpeech —— 使用 C# 开发人工智能语音应用
  • 20250929
  • 驱动基础知识速览(迅为RK3568文档)
  • 学习笔记-析合树
  • CSPJ2025模拟赛
  • java代码审计-Shiro认证授权
  • CF868F题解
  • ThinkPHP反序列化分析
  • AT_iroha2019_day4_l 题解
  • AT_abc290_f 题解
  • 一张图读懂绿电直连系统架构 - 智慧园区
  • P5469 [NOI2019] 机器人 题解
  • 题解:P14080 [GESP202509 八级] 最小生成树
  • 实用指南:Spring Cloud Gateway 实战:全局过滤器日志统计与 Prometheus + Grafana 接口耗时监控
  • GTSAM 中自定义因子(Custom Factor)的详解和实战示例 - 指南
  • AtCoder AGC073 A 题解
  • CF506C Mr. Kitayuta vs. Bamboos 51nod1457 小K vs. 竹子 题目分析
  • 北京 意大利 硕士学签/D签 vfs代办 材料清单
  • temp
  • 我有园子了
  • 使用 Jenkins 的流水线方案实施 CI/CD
  • 加密的病例单