Leetcode754. 到达终点数字 --数论+思维

754. 到达终点数字
     中等
     313
     相关企业
     在一根无限长的数轴上，你站在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 。

提示:

-1e9 <= target <= 1e9
target != 0

题解

很有趣的题目，一开始看到往动态规划想了半天，但后来思考了下好像不是，我们来思考下，因为每一步都是+i或者-i，因此target不论正负，我们都可以看成是target为正的情况，相当于原来的路径方向取反。

我们思考一种最极端的情况，要到达target的位置，我们至少要向前移动n次，n满足n*(n+1)/2 >= target，这个不难理解。但是不能保证向前移动n次后一定准确到target的位置，所以需要回退，因此我们可以理解在第1次或第2次，或第x次的时候向后移动了，所以最终的位置是n*(n+1)/2 - 2*(x1 + x2 + x3 + …)，这里x1 < x2 < x3 < n。

也就是 n*(n+1)/2 - 2*(x1 + x2 + x3 + …) = target，现在求解出符合我们条件的最小的n就是答案。从这个计算公式可以看到一个规律，就是，需要满足n*(n+1)/2 - target为偶数，因为n*(n+1)/2 - target = 2*(x1 + x2 + x3 + …)肯定为偶数，现在来考虑x1、x2、x3的取值，因为x1 < x2 < x3 < n。取值为1、2、3、4、5、6.、…、n-1，所以为了让n尽可能小，只需要取值为1就行，于是相当于，找到最小的n，使得n*(n+1)/2=target或者n*(n+1)/2 - 2 = target。

我们先用二分快速搜索，然后判断就行。

class Solution {
public:
    typedef long long ll;
    ll binary_search(int target)
    {
        ll l = 1, r=1e6;
        ll fin = -1;
        while(l<=r)
        {
            ll mid = (l+r)/2;
            if(mid*(mid+1)/2 >=target)
            {
                fin = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return fin;
    }
    int reachNumber(int target) 
    {
        if(target <0)
        target = -target;
        ll fin = binary_search(target);
        for(ll i=fin;i<=1e6;i++)
        {
            ll res = i * (i+1)/2;
            if(res==target)return i;
            if((res - target)%2==0)return i;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

写完后我才反应过来，写啥二分啊，可以直接计算的啊，人傻了我。。。。。

class Solution {
public:
    typedef long long ll;
    
    int reachNumber(int target) 
    {
        if(target <0)
        target = -target;
        ll fin = sqrt((ll)target * 2);
        if(fin *(fin+1)/2 <target)
        fin += 1;
        for(ll i=fin;i<=1e6;i++)
        {
            ll res = i * (i+1)/2;
            if(res==target)return i;
            if((res - target)%2==0)return i;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20