2020-03-10 22:00:52
问题描述：
在一根无限长的数轴上，你站在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]范围中的非零整数。
问题求解：
首先看数据规模，时间复杂度大致是O(logn) / O(sqrt(n))左右。
比较容易想到的是不断1 + 2 + ... + k >= target，此时如果sum - target为偶数，那么可以通过翻转前面一个数字就可以达到target，那么整体的步数是k。
主要的难点就是当diff为奇数的时候如何处理。此时如果k是偶数，那么我们再加k + 1，diff就会变成偶数，那么就可以通过翻转一个数字达到target；如果k是奇数，那么我们需要- k + 1 + k + 2来让diff变成偶数，整体k + 2。
public int reachNumber(int target) {
target = target > 0 ? target : -target;
int sum = 0;
int k = 0;
while (sum < target) sum += ++k;
int diff = sum - target;
if (diff % 2 == 0) return k;
else return k + 1 + k % 2;
}