754. 到达终点数字

题目描述

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

你可以做一些数量的移动 numMoves :

每次你可以选择向左或向右移动。
第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的最小移动次数(即最小 numMoves ) 。

示例 1:

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

示例 2:

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

提示:

-10⁹ <= target <= 10⁹
target != 0

解法

方法一：数学分析

思考

第 \(i\) 步必须走 \(i\)，方向自选，求到达 \(\textit{target}\) 的最少步数。目标可达 \(10^9\)，搜索步数序列不可行。

方向关于原点对称，可先取绝对值。连续向右走 \(k\) 步到达三角数 \(s\)；若 \(s-\textit{target}\) 为偶数，把其中 \(\frac{s-\textit{target}}{2}\) 这一步反向即可，步数不变。

增大 \(k\) 直到 \(s\ge \textit{target}\) 且差为偶数。\(k\) 为 \(O(\sqrt{|\textit{target}|})\)。

由于对称性，每次可以选择向左或向右移动，因此，我们可以将 \(\textit{target}\) 统一取绝对值。

定义 \(s\) 表示当前所处的位置，用变量 \(k\) 记录移动的次数。初始时 \(s\) 和 \(k\) 均为 \(0\)。

我们将 \(s\) 一直循环累加，直到满足 \(s\ge \textit{target}\) 并且 \((s-\textit{target}) \bmod 2 = 0\)，此时的移动次数 \(k\) 就是答案，直接返回。

为什么？因为如果 \(s\ge \textit{target}\) 且 \((s-\textit{target})\mod 2 = 0\)，我们只需要把前面 \(\frac{s-\textit{target}}{2}\) 这个正整数变为负数，就能使得 \(s\) 与 \(\textit{target}\) 相等。正整数变负数的过程，实际上是将移动的方向改变，但实际移动次数仍然不变。

时间复杂度 \(O(\sqrt{\left | \textit{target} \right | })\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoJavaScript

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s = k = 0
        while 1:
            if s >= target and (s - target) % 2 == 0:
                return k
            k += 1
            s += k

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int s = 0, k = 0;
        while (true) {
            if (s >= target && (s - target) % 2 == 0) {
                return k;
            }
            ++k;
            s += k;
        }
    }
}

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int s = 0, k = 0;
        while (1) {
            if (s >= target && (s - target) % 2 == 0) return k;
            ++k;
            s += k;
        }
    }
};

func reachNumber(target int) int {
    if target < 0 {
        target = -target
    }
    var s, k int
    for {
        if s >= target && (s-target)%2 == 0 {
            return k
        }
        k++
        s += k
    }
}

/**
 * @param {number} target
 * @return {number}
 */
var reachNumber = function (target) {
    target = Math.abs(target);
    let [s, k] = [0, 0];
    while (1) {
        if (s >= target && (s - target) % 2 == 0) {
            return k;
        }
        ++k;
        s += k;
    }
};

754. 到达终点数字

题目描述

解法

方法一：数学分析

评论