题目描述
在一根无限长的数轴上,你站在 0
的位置。终点在 target
的位置。
每次你可以选择向左或向右移动。第 n
次移动(从 1 开始),可以走 n
步。
返回到达终点需要的最小移动次数。
样例
输入:target = 3
输出:2
解释:
第一次移动,从 0 到 1。
第二次移动,从 1 到 3。
输入:target = 2
输出:3
解释:
第一次移动,从 0 到 1。
第二次移动,从 1 到 -1。
第三次移动,从 -1 到 2。
限制
target
是在[-10^9, 10^9]
范围中的非零整数。
算法
(数学) $O(1)$
- 负位置与正位置是对应的,统一按照正位置考虑。
- 假设每次都是向右移动,当位置大于等于
target
的时候停止。 - 此时如果位置与
target
的差距为偶数,则显然可以将某一步改为向左走,即可到达target
。 - 如果差距为奇数,则需要再向后走,直到出现位置为偶数的情况(不会超过 4 次)。
时间复杂度
- 仅需要常数的时间求解。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int s = sqrt(2 * target);
while (s * (s + 1) / 2 < target || (s * (s + 1) / 2 - target) % 2 == 1)
s++;
return s;
}
};