LeetCode.1033-移动石头直到连续(Moving Stones Until Consecutive)-

七彩网络

昔年博客
首页>> 游戏开发 >>LeetCode.1033-移动石头直到连续(Moving Stones Until Consecutive)

今天介绍的是LeetCode算法题中Easy级别的第247题(顺位题号是1033)。在abc位置的数字线上有三块石头。每次,你在一个终点(即最低或最高位置的石头)上拾取一块石头,然后将它移动到这些终点之间的空置位置。

形式上,假设石头当前位于xyz位置,x <y <z。你在x位置或z位置拾取石头,然后将石头移动到整数位置kx <k <zk!= y

当你不能做任何移动时,游戏结束。例如,当石头处于连续的位置时。

当游戏结束时,你可以做出的最小和最大移动次数是多少?将答案作为长度为2的数组返回:answer = [minimum_moves,maximum_moves]

例如:

输入:a = 1,b = 2,c = 5
输出:[1,2]
说明:将石头从5移动到3,或将石头从5移动到4到3。

输入:a = 4,b = 3,c = 2
输出:[0,0]
说明:不能做任何移动。

输入:a = 3,b = 5,c = 1
输出:[1,2]
说明:将石头从1移动到4;或将石头从1移动到2到4。

注意

  • 1 <= a <= 100
  • 1 <= b <= 100
  • 1 <= c <= 100
  • a != b,b != c,c != a

 解题

先将三个数排序,找出最小值min,中间值mid,最大值max

最小移动步数:既然要移动的步数最少,那就跳着移动,向中间值mid靠拢。

如果三个数都相邻,那么就不需要跳。

如果其中有两个数相邻,即最小值和中间值相邻,或者中间值和最大值相邻,那么就只需要跳一步即可。

如果三个数不相邻,分两种情况:

  • 第一,如果最大值与中间值相差2,那么只需要跳一步,将最小值跳到最大值与中间值之间即可;如果中间值与最小值相差2,那么只需要跳一步,将最大值跳到中间值与最小值之间即可。
  • 第二,任意两数的差值大于2,那就往中间数左右两边相邻的数字上跳,左右两边各跳一次即可。

最多移动步数:既然要移动的步数最多,那就一次只移动一次,向中间值mid靠拢。

最大值max向左移动,移动到mid+1的位置,一共移动了max-mid-1步。

最小值min向右移动,移动到mid-1的位置,一共移动了mid-min-1步。

因此,最多移动步数为(max-mid-1)+(mid-min-1) = max - min - 2

public int[] numMovesStones(int a, int b, int c) {
    int max = Math.max(a, Math.max(b, c));
    int min = Math.min(a, Math.min(b, c));
    int mid = a + b + c - max - min;
    int min_moves = Math.min(1, mid-min-1) + 
            Math.min(1, max-mid-1);
    if (mid-min == 2 || max-mid == 2) {
        min_moves = 1;
    }
    int max_moves = max - min - 2;
    return new int[]{min_moves, max_moves};
}


×

感谢您的支持,我们会一直保持!

扫码支持
请土豪扫码随意打赏

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在

打赏作者
版权所有,转载注意明处:昔年博客 » LeetCode.1033-移动石头直到连续(Moving Stones Until Consecutive)
分享本文至:
点击评论 您阅读这篇文章共花了: 

发表评论

路人甲 表情
Ctrl+Enter快速提交

网友评论(0)