题目描述

这题是要求我们找到最小的步数使得能到目标位置。
我们可以发现每一步能到的步数有一个范围并且所有的值奇偶性与最大值相同

样例

step 1 : 我们能到 -1 1 最大 1 
step 2 : 我们能到 -3 -1 1 3 最大 3
step 3 :  -6 -4 -2 0 2 4 6 
以此类推我们可以发现每次能到的位置 是个公差为2的等差数列 因此我们只要找到最大值能够包含我们的目标值并且和我们目标值奇偶性相同就可以。 

算法1

(二分搜索) $O(logn)$

blablabla

时间复杂度

参考文献

C++ 代码

int reachNumber(int target) {
        target = abs(target);
        long long l = 1 , r = target ;
        while(l<r){
            long long mid = (l+r)>>1; 
            if(mid*(mid+1)<2*target){
                l = mid+1; 
            }else{
                r = mid; 
            }
        }
        while(l*(l+1)/2%2!=target%2){
            l++; 
        }
        return l; 
    }

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla