【leetcode】1033. Moving Stones Until Consecutive

题目如下：

Three stones are on a number line at positions a, b, and c.

Each turn, you pick up a stone at an endpoint (ie., 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, 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, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

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.
Note:

1 <= a <= 100

1 <= b <= 100

1 <= c <= 100

a != b, b != c, c != a

解题思路：首先对a,b,c进行排序，使得a最小，b其次，c最大。最大的移动次数很好求，就是a与c分别往b移动，每次移动一步，很容易得到最大移动次数是abs(c-b-1) + abs(b-a-1)。最小移动次数似乎很直接，就是a与c直接一步移动到b的两侧，这种情况下值应该是2，但是有几种特殊场景：第一是a,b,c都相邻，那么值是0；第二种是a与b相邻或者b与c相邻，那么值为1；第三种是a与b的差值为2或者b与c的差值位2，这时可以直接那剩余那个元素一步移动到a与b或者b与c的直接的空位中。

代码如下：

class Solution(object):

    def numMovesStones(self, a, b, c):

        """

        :type a: int

        :type b: int

        :type c: int

        :rtype: List[int]

        """

        l = sorted([a,b,c])

        a,b,c = l[0],l[1],l[2]

        maxv = abs(c-b-1) + abs(b-a-1)

        minv = 0

        left = (b-a-1)

        right = (c-b-1)

        if left == 0 and right == 0:

            minv = 0

        elif left == 0 or right == 0:

            minv = 1

        elif left == 1 or right == 1:

            minv = 1

        else:

            minv = 2

        return [minv,maxv]

巴特西

【leetcode】1033. Moving Stones Until Consecutive

最新文章

热门文章