【数论 排序 滑动窗口】1040. 移动石子直到连续 II

2024-09-03 03:28

本文主要是介绍【数论 排序 滑动窗口】1040. 移动石子直到连续 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文涉及知识点

排序 质数、最大公约数、菲蜀定理
C++算法:滑动窗口总结

LeetCode1040. 移动石子直到连续 II

在一个长度 无限 的数轴上,第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大,那么该石子被称作 端点石子 。
每个回合,你可以将一颗端点石子拿起并移动到一个未占用的位置,使得该石子不再是一颗端点石子。
值得注意的是,如果石子像 stones = [1,2,5] 这样,你将 无法 移动位于位置 5 的端点石子,因为无论将它移动到任何位置(例如 0 或 3),该石子都仍然会是端点石子。
当你无法进行任何移动时,即,这些石子的位置连续时,游戏结束。
要使游戏结束,你可以执行的最小和最大移动次数分别是多少? 以长度为 2 的数组形式返回答案:answer = [minimum_moves, maximum_moves] 。
示例 1:
输入:[7,4,9]
输出:[1,2]
解释:
我们可以移动一次,4 -> 8,游戏结束。
或者,我们可以移动两次 9 -> 5,4 -> 6,游戏结束。
示例 2:
输入:[6,5,4,3,10]
输出:[2,3]
解释:
我们可以移动 3 -> 8,接着是 10 -> 7,游戏结束。
或者,我们可以移动 3 -> 7, 4 -> 8, 5 -> 9,游戏结束。
注意,我们无法进行 10 -> 2 这样的移动来结束游戏,因为这是不合要求的移动。
示例 3:
输入:[100,101,104,102,103]
输出:[0,0]
提示:
3 <= stones.length <= 104
1 <= stones[i] <= 109
stones[i] 的值各不相同。

数量

n = stones.length
对stones按升序排序。如果最石子间没有空隙,则游戏结束。如果有空隙一定不会结束,下面来分情况证明:
一,如果空隙不挨着第一颗个石子,也不挨着最后一颗石子则将第一颗石子或最后一颗石子移到此处。
二,如果空隙同时挨着第一颗石子和最后一颗石子,说明总共只有2颗石子,和n>=3矛盾。
三,如果只挨着第一颗石子,将最后一颗石子移到此处。
四,如果只挨着最后一颗石子,将第一颗石子移到此处。
结论一:如果石子间有空隙则一定能继续,否则只能结束游戏。
本题 ⟺ \iff 如何最快(慢)减少空隙。

最慢减少空隙(最多操作数)

如果最前(后)端,有两个及以上挨着的石子,则将最前端的石子移到从前到后的第一个空隙。可以持续减少一个空隙。我们简称此情况为:理想情况。
如果初始不是理想情况,则将石子移动前端的右边,或后端的左边。便是理想情况。
初始空隙i1 =stone.back()-stone[0]+1 - n
答案是:n - min(stone[1]-stone[0],stone.back()-stone[stone.length()-2]) 第一次可能会浪费空隙。

最快减少空隙(最少操作数)

我们假定游戏结束时,石子为[i2,i2+n-1)
如果i2和i2+n-1 没有石子则移到这两处,如果这两处不是所有石子的前面或后面(假设一),一定能移,下面来证明:
由于有3个石子,且此处没石子,前面或后面至少有一处,有2个石子。不失一般性,假定前面有两个石子。最前面的那个石子移到此处,移动后不会是左端。由于不是所有石子的左边,则此处不会右端点之外。
两个端点有石子后,端点外的石子,一次占一个空隙。即一个空位需要一次移动次数。
如果i2除没有石子则无需枚举,下来用决策包容性来证明:
i21后面没石子,则无法将任何石子移到i2处。
i21后的石子为i22,则[i22,i22+n)的石子一定不会少于[i21,n)。因为[i21,i22)被替换的部分没石子,被替换后石子数不会减少。
只枚举有石子的i2,会违反假设一,此解会被某个[i3,i3+n)包容。i3=i2 ,i3–,直到i3+n-1是石子。如果某个i3有石子,会被枚举。如果所有的i3都没石头,最终的i3也是合法解。

特列

除第(最后)一个石子外,其它石子是连续的,比如:
1,2,3,4,5,6,x 如果x为7,无需移动。
如果x为8,1边7,移动一次。
如果x>8,x1变8,x变7最多两次。

代码

核心代码

class Solution {
public:vector<int> numMovesStonesII(vector<int>& stones) {sort(stones.begin(), stones.end());const int N = stones.size();const int i1 = stones.back() - stones.front() + 1 - N;vector<int> ret(2);ret[1] = i1 - min(stones[1] - stones[0]-1, stones.back() - stones[stones.size() - 2]-1);if (stones[stones.size() - 2] - stones[0] + 1 == N - 1) {ret[0]= min(2, stones.back() - stones[stones.size() - 2]-1);return ret;}if (stones.back() - stones[1] + 1 == N - 1) {ret[0] = min(2, stones[1] - stones[0] - 1);return ret;}int iMaxStone = 0;for (int i = 0, right = 0, sum = 0; i < N; i++) {while ((right < N) && (stones[right] < stones[i] + N)) {sum++;right++;}iMaxStone = max(iMaxStone, sum);sum--;}ret[0] = N - iMaxStone;return ret;}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1,  double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> stones;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){stones = { 7,4,9 };auto res = Solution().numMovesStonesII(stones);AssertEx(vector<int>{1, 2}, res);}TEST_METHOD(TestMethod01){stones = { 6,5,4,3,10 };auto res = Solution().numMovesStonesII(stones);AssertEx(vector<int>{2, 3}, res);}TEST_METHOD(TestMethod02){stones = { 100,101,104,102,103 };auto res = Solution().numMovesStonesII(stones);AssertEx(vector<int>{0, 0}, res);}};
}

扩展阅读

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【数论 排序 滑动窗口】1040. 移动石子直到连续 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131894

相关文章

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Qt把文件夹从A移动到B的实现示例

《Qt把文件夹从A移动到B的实现示例》本文主要介绍了Qt把文件夹从A移动到B的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录如何移动一个文件? 如何移动文件夹(包含里面的全部内容):如何删除文件夹:QT 文件复制,移动(

Python重命名文件并移动到对应文件夹

《Python重命名文件并移动到对应文件夹》在日常的文件管理和处理过程中,我们可能会遇到需要将文件整理到不同文件夹中的需求,下面我们就来看看如何使用Python实现重命名文件并移动到对应文件夹吧... 目录检查并删除空文件夹1. 基本需求2. 实现代码解析3. 代码解释4. 代码执行结果5. 总结方法补充在

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

bat脚本启动git bash窗口,并执行命令方式

《bat脚本启动gitbash窗口,并执行命令方式》本文介绍了如何在Windows服务器上使用cmd启动jar包时出现乱码的问题,并提供了解决方法——使用GitBash窗口启动并设置编码,通过编写s... 目录一、简介二、使用说明2.1 start.BAT脚本2.2 参数说明2.3 效果总结一、简介某些情

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法,它将时间划分为若干个固定大小的窗口,每个窗口内记录了该时间

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig