移动石子直到连续（1033）

今天为大家分享一个脑筋急转弯类型的算法题。leetcode这个脑筋急转弯的tag打的我措手不及…

PNG

01、题目示例

分享这道题目的原因，是因为有很多同学，在拿到题目的一瞬间，如果发现题目很长，然后自己就慌了。其实，对于这种题目，如果认真的分析下去，非常简单。

第1033题：移动石子直到连续
三枚石子放置在数轴上，位置分别为 a，b，c。每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。要使游戏结束，你可以执行的最小和最大移动次数分别是多少？以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

示例1：

  1. 输入：a = 1, b = 2, c = 5
  2. 输出：[1, 2]
  3. 解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。

示例 2：

  1. 输入：a = 4, b = 3, c = 2
  2. 输出：[0, 0]
  3. 解释：我们无法进行任何移动。

提示：

  1. 1 <= a <= 100
  2. 1 <= b <= 100
  3. 1 <= c <= 100
  4. a != b, b != c, c != a

02、题目分析

这种题，基本上不慌，就赢了一半。

通过分析题中的样例，就算再笨，画一画应该都能理解题意。


比如：a = 1, b = 2, c = 5

PNG

比如：a = 4, b = 3, c = 2

PNG

（无法移动）

读懂了题意，开始进行分析。首先可以明确，每一次我们其实是从边上来挑选石子，然后往中间进行移动。所以，我们首先得找到min（左），max（右）以及mid（中）三个值。我们设，min和mid中的距离为x，max和min中的距离为y。大概就是下面这样：

PNG

然后只需要计算x和y的和，就是我们要找的最大值。而最小值，就很容易了，只有0,1,2三种可能性。


根据分析，得到代码：

  1. func numMovesStones(a int, b int, c int) []int {
  2.     arr := []int{a, b, c}
  3.     sort.Ints(arr)
  4.     x := arr[1] - arr[0] - 1
  5.     y := arr[2] - arr[1] - 1
  6.     max := x + y
  7.     min := 0
  8.     if x != 0 || y != 0 {
  9.         if x > 1 && y > 1 {
  10.             min = 2
  11.         } else {
  12.             min = 1
  13.         }
  14.     }
  15.     return []int{min, max}
  16. }

03、C 代码

当然，也可以不用排序，把代码写漂亮一点。像是下面这样…

代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> numMovesStones(int a, int b, int c) {
  4.         int max = a > b ? (a > c ? a : c) : (c > b ? c : b);
  5.         int min = a < b ? (a < c ? a : c) : (b < c ? b : c);
  6.         int med = a + b + c - max - min;
  7.         int maxMove = max - min - 2;
  8.         int minMove = 2;
  9.         if (max - med == 1 && med - min == 1) {
  10.             minMove = 0;
  11.         } else if (max - med == 1 || med - min == 1) {
  12.             minMove = 1;
  13.         }else if (max - med == 2 || med - min == 2) {
  14.             minMove = 1;
  15.         }
  16.         return vector{minMove,maxMove};
  17.     }
  18. };

执行结果：

PNG