[数据结构与算法]LeetCode每日一题：754. 到达终点数字

题目：754. 到达终点数字

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

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

每次你可以选择向左或向右移动。
第 i?次移动（从 ?i == 1?开始，到?i == numMoves ），在选择的方向上走 i?步。
给定整数?target ，返回 到达目标所需的 最小?移动次数(即最小 numMoves )?。

示例 1:

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
示例 2:

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
?

提示:

-109?<= target <= 109
target != 0

起初我想到的是先一个个加上，直到刚好等于target那就结束，结果差1那就多两次（比如-3+4 两次刚好能补上差的1），差2那就多四次，以此类推 结果发现好像很蠢

看了题解才明白，

一个个加上，sum直到大于或者等于target，等于那就结束，sum大于target则需要看他们之间的差值奇偶

差值为偶数a = sum-target：则前面加上的数中必定存在一个a/2 ，只要把a/2的加变成减，那么刚好sum等于target 则次数与相等时一样

差值为奇数 a = sum-target：则我们需要把差值变为偶数情况然后按照偶数情况来计算。如何变呢？ 当差值为奇数时会有两种情况：a = 奇数-偶数? ?a = 偶数-奇数 两种情况中，如果sum加上一个偶数，那么结果差值a还是为奇数，如果sum加上一个奇数，那么结果差值a就能变成偶数了，所以我们先加上 ans+1，如果ans+1是奇数那么计算结束，如果ans+1是偶数，那么ans+2必定为奇数，a = ( sum+ans+1+ans+2 )?- target? ，a为偶数，可得出答案为ans+2?

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int ans = 0;
        int sum = 0 ;
        while( sum < target ){
            sum += ++ans; 
        }
        return (sum-target)%2==0 ? ans :( (ans+1)%2 ? ans +1 : ans+2 );
    }
};