Reach a Number
You are standing at position 0 on an infinite number line. There is a destination at position target.
You can make some number of moves numMoves so that:
On each move, you can either go left or right.
During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.
Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.
Example 1:
Input: target = 2
Output: 3
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to -1 (2 steps).
On the 3rd move, we step from -1 to 2 (3 steps).
Example 2:
Input: target = 3
Output: 2
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to 3 (2 steps).
Constraints:
-109 <= target <= 109
target != 0
思路一：对所以数字进行求和，有下面的结果
x => y
1 => 1
2 => 3
3 => 6
4 => 10
5 => 15
要到达坐标轴某个点，可以相应的看成是某种形式的求和，对到达坐标轴的点和序列求和完全分类，只可能出现以下两种情况
- 所求坐标点刚好等于序列和
- 序列和大于所求坐标点
因为我们最少也要到达所求的坐标点，所以序列和一定要大于坐标点，对第一种情况，直接返回序列求和的次数，对于第二种情况，由于序列和超越了坐标点，我们要反向减去序列和，而反向的减去的值只可能是 2,4,6,8,10 这样的偶数，判断序列和减去 target 后的值是否是偶数就能判断序列和是否满足坐标点。
举个例子
x => y
1 => 1
2 => 3
3 => 6
4 => 10
5 => 15
__-1__0__1__2__3__4__5__6
要想到达坐标点 5，我们看 y 列的 6， 6 - 5 = 1，无法减去奇数
继续看 10， 10 - 5 = 5，还是奇数
继续看 15， 15 - 5 = 10，10 可以分解成 2 和 8，所以第 1 步和第 4 步反向，其他步正向就是结果 (-1 + 2 + 3 -4 + 5 = 5)
public int reachNumber(int target) {
int result = 0;
target = Math.abs(target);
for (int i = 1; i <= Integer.MAX_VALUE - 1; i++) {
result += i;
if (result == target) return i;
else if (result > target) {
if ((result - target) % 2 == 0)
return i;
}
}
throw new RuntimeException();
}