思维

754.到达终点的数字

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

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

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

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

其中 \(-10^9 \le target \le 10^9\)

方法一思维

对于 \(\textit{target} < 0\) 的情况，都可以全部取反对应到 \(\textit{target} > 0\) 的情况。

假设走了 \(k\) 步，每次都向右走，那么最终会走到 \(\textit{sum} = \sum_{i=1}^k\) 的地方。我们找到满足 \(\textit{sum} \ge \textit{target}\) 的最小 \(k\)，如果 \(\textit{sum} = \textit{target}\)，那么答案就是 \(k\)，否则需要调整一些数字的符号来使得 \(\textit{sum}\) 变小。

现在我们需要使得总和减小 \(\textit{sum} - \textit{target}\)，由于 \(k\) 是最小的满足 \(\textit{sum} \ge \textit{target}\) 的数字，所以 \(k \gt \textit{sum} - \textit{target}\)

设 \(\textit{delta} = \textit{sum} - \textit{target}\)，如果 \(\textit{delta}\) 是偶数，那么只需将 \(1\sim k\) 中的某个数字 \({delta \over 2}\) 置为负数即可。

但如果是奇数，那么是没有办法这样做的，因为置为负数，\(\textit{delta}\) 变化量永远都是偶数。因此我们需要使用最小的代价使得 \(\textit{delta}\) 变为偶数。

如何变？只需要增加 \(k + 1\)，或者 \((k + 1) + (k + 2)\)，具体由 \(k\) 的奇偶性决定。

C++Python

class Solution {
public:
    using ll = long long;
    int reachNumber(int target) {
        if (target < 0) {
            return reachNumber(-target);
        }
        int l = 0, r = 1E9;
        while (l < r) {
            int mid = l + r >> 1;
            if ((ll) mid * (1 + mid) / 2 >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (((ll) l * (l + 1) / 2 - target) % 2 == 0) {
            return l;
        } else {
            if (l % 2 == 0) {
                return l + 1;
            } else {
                return l + 2;
            }
        }
    }
};

class Solution:
    def reachNumber(self, target: int) -> int:
        if target < 0:
            return self.reachNumber(-target)
        l, r = 0, 10**9
        while l < r:
            m = (l + r) // 2
            if m * (m + 1) // 2 >= target:
                r = m
            else:
                l = m + 1

        if (l * (l + 1) // 2 - target) % 2 == 0:
            return l
        else:
            return l + 1 if l % 2 == 0 else l + 2

本文访问次

思维

754.到达终点的数字

方法一 思维

方法一思维