0754. 到达终点数字

题目地址(754. 到达终点数字)

https://leetcode-cn.com/problems/reach-a-number/

题目描述

在一根无限长的数轴上，你站在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]范围中的非零整数。

前置知识

• 数学

公司

思路

不难看出， 问题的本质就是一个有限序列， 1，2，3，4... 。我们的目标是给这个序列的元素添加正负号，是的其和为 target。这和 494.target-sum 的思路是一样的。

拿题目的 target = 3 来说， 就是 1 + 2 = 3。

拿题目的 target = 2 来说， 就是 1 - 2 + 3 = 2。

为什么是有限序列？

因为我们始终可以在 target 次以内走到 target。严格来说， 最少在根号 target 左右就可以走到 target。

和 494.target-sum 不同的是， 这道题数组是无限的，看起来似乎更难，实际上更简单， 因为数组是有规律的，每次都递增 1。

由于 target 正负是对称的， 因此 target 最少走多少布，-target 也是多少步。因此我们只考虑一种情况即可， 不妨只考虑正数的情况。

其实，只要找出第一个满足 1 + 2 + 3 + .... + steps > target 的 steps 即可。

令 1 + 2 + 3 + .... + steps 为 T。接下来，我们来对不同情况进行分析。

• 如果 T 等于 target，那么 steps 就是我们想求的值，直接返回即可。

• 否则，我们尝试从 [1, steps] 这 steps 个数中找出几个数改成其符号，不难知道找的这几个数的和是 (T - target) / 2。

  1. 如果 T 是偶数， 那么我们总可以找出若干数字使其变为符号，满足 1 + 2 + 3 + .... + steps == target，因此直接返回 steps 即可。

  2. 如果 T 是奇数，(T - target) / 2 是个小数，肯定无法选取的，因此我们还需要在多选数，比如 steps + 1，steps + 2。 由于 T + steps + 1 和 T + steps + 1 + steps + 2 中有且仅有一个是偶数。我们仍然可以套用上面的方法，找出若干数字使其变为负号，满足 1 + 2 + 3 + .... + steps + steps + 1 == target 或者 1 + 2 + 3 + .... + steps + steps + 1 + steps + 2 == target。也就是说在这种情况下答案就是 steps + 1 或者 steps + 2，具体是哪个取决于 T + steps + 1 是偶数还是 T + steps + 1 + steps + 2 是偶数

关键点解析

• 对元素进行分组，分组的依据是符号， 是+ 或者 -

• 通过数学公式推导可以简化我们的求解过程，这需要一点数学知识和数学意识

代码(Python)

Python Code:

class Solution(object):
    def reachNumber(self, target):
        target = abs(target)
        steps = 0
        while target > 0:
            steps += 1
            target -= steps
        if target & 1 == 0: return steps
        steps += 1
        if (target - steps) & 1 == 0: return steps
        return steps + 1

复杂度分析

• 时间复杂度：$O(\sqrt target)$

• 空间复杂度：$O(1)$

相关题目

• 494.target-sum