050-二维生物的旅行-754--到达终点数字

第三题 二维生物的旅行

二维生物hip当前处于x轴的0坐标位置，打算去拜访它的老友hop，hop位于坐标轴的target位置。hip有一个很奇怪的能力，其迈出的第n步（从1算起），步长为n。也就是说第一步可以移动的距离为1，第二步可以移动的距离为2，以此类推。每走一步之前，hip都可以决定这一步是向左走还是向右走，但每一步都只能朝一个方向前进。二维生物都很懒，hip希望你能先帮他计算出最少需要走多少步才能到达target位置，他再决定要不要去拜访老友。

输入描述：

每个测试输入包含1个测试用例，即给出目标位置target的值。这里保证-10^{9<=target<=10}9,且为整数

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。

返回到达终点需要的最小移动次数。

示例 1:

输入: target = 3 输出: 2 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 3 。 示例 2:

输入: target = 2 输出: 3 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 -1 。 第三次移动，从 -1 到 2 。 注意:

target是在[-10^9, 10^9]范围中的非零整数。

题解

• 首先注意到对称性，向正向行走和反向行走相同距离使用最小步数是一样的，因此只考虑target>0的情况。
• 注意到，走n步所能达到的最大距离为$n * (n + 1) / 2$。 因此，令$a = math.sqrt(2 * target + 0.25) - 0.5$，若$a == int(a)$则说明此时的target正好是a步所能达到的最远距离。直接返回$int(a)$即可。
• 如果$a != int(a)$，则将a设置为最远距离大于target的最小步数。此时分情况讨论。
• 注意到对于走了步数n：
• 若((n + 1) // 2) % 2 == 1则此时停下来的距离肯定为奇数
• 若((n + 1) // 2) % 2 == 0则此时停下来的距离肯定为偶数
• 若步数a对应的奇偶数情况和target正好相同，则输出a。
• 若步数a对应的奇偶数情况和target不相同，则输出大于a的下一个与target奇偶相同的步数。 直接看代码更清晰

import math
class Solution(object):
    def reachNumber(self, target):
        """
        :type target: int
        :rtype: int
        """
        if target < 0:
            target = 0 - target
        a = math.sqrt(2 * target + 0.25) - 0.5
        # print(a)
        if a == int(a):
            return int(a)
        else:
            a = int(a) + 1
            if ((a + 1) // 2) % 2 == target % 2:
                return a
            elif a % 2 == 1:
                return a + 2
            else:
                return a + 1