LeetCode 754. 到达终点数字

题目描述

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

题解

思路

• 由于对称，所以正负不影响。
• 向右走 step 步，直到累加步数 sum 大于等于目标值。

$$1 + 2 + 3 + \dots + step = sum \label{eq1}$$

• 如果 sum == target，返回 step。
• 如果 sum > target ，其中步数差为 sum - target。
• 如果 sum - target 是偶数，那么翻转 (sum - target)/2 的符号即可达成。

例如：sum - target = 4，将 2 符号变为 -2，所以 sum 减少了 4，sum 就与 target 相等。

$$\begin{align} sum - target &= 4 \nonumber \\ (1 + 2 + \dots + step) - (1 - 2 + \dots + step) &= 4 \nonumber \\ 1 + \dots - \frac{sum - target}{2} + \dots + step &= target \label{eq2} \end{align}$$

所以得出公式 $\eqref{eq2}$，走了 step 步并且翻转了 (sum - target)/2 的符号，所以最终返回 step。

• 如果 sum - target 是奇数。sum - target + 1 即 sum - (target - 1) 是偶数，根据公式$\eqref{eq2}$ 可以得出

$$\begin{equation} 1 + \dots - \frac{sum-target+1}{2} + \dots + step = target - 1 \label{eq3} \end{equation}$$

• 如果 step 是偶数，且 step > sum - target + 1。

从公式 $\eqref{eq3}$ 可以得出

$$\begin{align} 1 + \dots - \frac{sum - target + 1}{2} + \dots + step &= target - 1 \nonumber \\ 1+\dots-\frac{sum - target + 1}{2}+\dots+step+(step+1) &= target - 1 + (step + 1) \nonumber \\ &= target + step \nonumber \\ 1 + \dots - \frac{sum - target + 1}{2} + \dots -\frac{step}{2} + \dots + step + (step + 1) &= target \label{eq4} \end{align}$$

公式 $\eqref{eq4}$ 表示走了 step + 1 步并且翻转了 (sum - target + 1)/2 和 step/2 的符号，所以最终步数为 step + 1。

• 如果 step 是奇数。

从公式 $\eqref{eq3}$ 可以得出

$$\begin{align} 1 + \dots - \frac{sum - target + 1}{2} + \dots + step - (step + 1) + (step + 2) &= target \label{eq5} \end{align}$$

公式 $\eqref{eq5}$ 表示走了 step + 2 步，并且翻转了 (sum - target + 1)/2 和 step + 1 的符号，所以最终步数为 step + 2。

代码

C++

int reachNumber(int target) {
    if(target < 0) {
        target = -target;
    }
    int step = 0;
    int sum = 0;
    while(sum < target) {
        ++step;
        sum += step;
    }
    int delta = sum - target;
    if(delta % 2 == 0) {
        return step;
    } else {
        if( step % 2 == 0) {
            return step + 1;
        } else {
            return step + 2;
        }
    }
    return 0;
}

参考链接

• LeetCode 评论, LeetCode.