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)$

相关题目

最后更新于