【LetMeFly】1033.移动石子直到连续
力扣题目链接:https://leetcode.cn/problems/moving-stones-until-consecutive/
三枚石子放置在数轴上,位置分别为 a
,b
,c
。
每一回合,你可以从两端之一拿起一枚石子(位置最大或最小),并将其放入两端之间的任一空闲位置。形式上,假设这三枚石子当前分别位于位置 x, y, z
且 x < y < z
。那么就可以从位置 x
或者是位置 z
拿起一枚石子,并将该石子移动到某一整数位置 k
处,其中 x < k < z
且 k != y
。
当你无法进行任何移动时,即,这些石子的位置连续时,游戏结束。
要使游戏结束,你可以执行的最小和最大移动次数分别是多少? 以长度为 2 的数组形式返回答案:answer = [minimum_moves, maximum_moves]
示例 1:
输入:a = 1, b = 2, c = 5 输出:[1, 2] 解释:将石子从 5 移动到 4 再移动到 3,或者我们可以直接将石子移动到 3。
示例 2:
输入:a = 4, b = 3, c = 2 输出:[0, 0] 解释:我们无法进行任何移动。
提示:
1 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a
方法一:思维
不失一般性,我们先对a、b、c排个序,使得 a < b < c a<b<c a<b<c
接着,我们判断最小距离:
- 如果a、b、c相邻,那么移动所需最小距离就为0
- 否则如果a、b相邻或b、c相邻,我们只需要将不相邻的那一个移动过来即可;如果a、b间隔为1或b、c间隔为1,我们只需要将另外一个移动到这两个中间的间隔处。总之,移动最小距离为1。
- 否则,我们移动两次,可以使a、b、c相邻
接着,我们计算最大距离:
在a、b、c不全部相邻时:
- 若a、b不相邻,那么我们就把a往右移动一步
- 否则,就把b往左移动一步
总之,在没有把a、b、c移动到一起时,我们有办法每次只移动一步。因此最大总移动步数为 c − a + 2 c-a+2 c−a+2
- 时间复杂度 O ( 1 ) O(1) O(1)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
public:vector<int> numMovesStones(int a, int b, int c) {// sort(a, b, c)if (a > b) {swap(a, b);}if (b > c) {swap(b, c);}if (a > b) {swap(a, b);}// calculateif (a + 1 == b && b + 1 == c) { // 直接相连return {0, 0};}if (a + 1 == b || b + 1 == c || a + 2 == b || b + 2 == c) { // 有两个相连 或 有两个间隔为2return {1, c - a - 2};}else { // 三个各不相连return {2, c - a - 2};}}
};
Python
# from typing import Listclass Solution:def numMovesStones(self, a: int, b: int, c: int) -> List[int]:a, b, c = sorted([a, b, c])if a + 1 == b and b + 1 == c:return [0, 0]elif a + 1 == b or b + 1 == c or a + 2 == b or b + 2 == c:return [1, c - a - 2]else:return [2, c - a - 2]
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/130446773