LeetCode 754. Reach a Number

754.Reach a Number（到达终点数字）

链接

https://leetcode-cn.com/problems/reach-a-number/

题目

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

思路

emmmmmm这是一道数学题，需要找规律（一看这个数就知道不能暴力破解）。

设定目标坐标为target，已经走了n步，坐标为F（n）=（n+1）*n/2，F（n-1）<sum<=F（n）找规律：

如果每一步都往同方向走，最后的坐标是1+2+3+…+n=（n+1）*n/2。这样成立的话，所需步数就是n步，target=sum；
目标值与sum存在差，（sum-target）为偶数 t 。那么，我们只需要在步长为 t/2 的那步反向走就行了，所需要的步数是 n；
如果二者差距为奇数，（sum-target）为奇数k，这时候就有两种可能：
1. n为奇数，将n拆为（n-1）和1，（n-1）为偶数，按照第一类进行，1就多走两步，一正一反就得到差值1，所需步数为n+2
2. n为偶数，这时候多走一步n+1，差距就为n+1+sum-target（偶数），也按照第一类进行，只需要n+1步。

代码

public static int reachNumber(int target) {
  target = Math.abs(target); //处理负值的情况
  int count = 0;
  int sum = 0;
  while (sum < target) {
    count++;
    sum = sum + count;
  }
  if ((sum - target) % 2 != 0) {
    if (count % 2 == 0) {
      count = count + 1;
    } else {
      count = count + 2;
    }
  }
  return count;
}