526互联

[LeetCode] 1033. Moving Stones Until Consecutive

发布时间 2023-04-30 03:47:52作者: CNoodle

There are three stones in different positions on the X-axis. You are given three integers a, b, and c, the positions of the stones.

In one move, you pick up a stone at an endpoint (i.e., either the lowest or highest position stone), and move it to an unoccupied position between those endpoints. Formally, let's say the stones are currently at positions x, y, and z with x < y < z. You pick up the stone at either position x or position z, and move that stone to an integer position k, with x < k < z and k != y.

The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions).

Return an integer array answer of length 2 where:

  • answer[0] is the minimum number of moves you can play, and
  • answer[1] is the maximum number of moves you can play.

Example 1:

Input: a = 1, b = 2, c = 5
Output: [1,2]
Explanation: Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.

Example 2:

Input: a = 4, b = 3, c = 2
Output: [0,0]
Explanation: We cannot make any moves.

Example 3:

Input: a = 3, b = 5, c = 1
Output: [1,2]
Explanation: Move the stone from 1 to 4; or move the stone from 1 to 2 to 4.

Constraints:

  • 1 <= a, b, c <= 100
  • a, b, and c have different values.

移动石子直到连续。

三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/moving-stones-until-consecutive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道数学题。首先我们把 a, b, c 放入一个数组然后对其排序。按照题目的要求，最后需要把三个石子放在数组中相邻的三个 index 上，所以很自然的想法就是中间的那个石子不动，把其他两个石子往中间移动。

一个需要处理的 corner case 是如果三个石子一开始就是相邻的，那么我们无需移动，直接返回 [0, 0] 即可。对于一般的 case，最小的移动次数就是各自直接一步将 a 和 c 移动到 b 旁边的两个 index 上，最大的移动次数就是一步一步移动。

时间O(1) - sort 函数几乎可以忽略不计

空间O(1) - 返回的数组是固定空间

Java实现

 1 class Solution {
 2     public int[] numMovesStones(int a, int b, int c) {
 3         int[] s = {a, b, c};
 4         Arrays.sort(s);
 5         // corner case
 6         if (s[2] - s[0] == 2) {
 7             return new int[] {0, 0};
 8         }
 9 
10         // normal case
11         return new int[] { Math.min(s[1] - s[0], s[2] - s[1]) <= 2 ? 1 : 2, s[2] - s[0] - 2 };
12     }
13 }

 

LeetCode 题目总结