Leetcode 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


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
34
35
36

• 首先，对于target为负的情况取反，因为方向不影响最少步数
• 要求步数最少，最直观的想法是首先一直前进，直到无法前进为止。
• 那么前进的值为$1+2+\mathrm{3...}+n=(n+1)\ast n/2$,当该值sum >= target时，我们停止前进，此时我们可以看出sum值比target大，差值为sum-target,当sum-target为偶数时，那么我们直接让前面某一步值为(sum-targte) / 2改为向后退，那么最后sum值就会减少sum-target。
• 若sum - target为奇数,那么再前进一步或者两步必然会让sum-target变为偶数。
• 若n为偶数，那么n+1为奇数，那么只用前进一步，sum-target为偶数
• 若n为奇数，那么前进两步后，sum-target变为偶数
• 对于n的寻找可以使用二分查找
• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

class Solution {
    public int reachNumber(int target) {
        if (target < 0) target = -target; 
        int l = 1, r = target;
        while (l < r) {
            int mid = (l + r) / 2;  
            if ((1 + (long)mid) * mid / 2 < target) l = mid + 1; // 寻找第一个n使 (1+n) * n / 2 >= target
            else r = mid; 
        } 
        int sum = (1 + r) * r / 2; 
        return (sum - target) % 2 == 0 ? r : r + 1 + r % 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 或者可以使用二元一次方程公式计算出n
• $n+n^2>=2\ast target$ => $n>=(sqrt(8\ast target+1)-1)/2$
• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

class Solution {
    public int reachNumber(int target) {
        if (target < 0) target = -target; 
        int n = (int) Math.ceil((Math.sqrt(8L * target + 1) - 1) / 2);
        int sum = (1 + n) * n / 2; 
        return (sum - target) % 2 == 0 ? n : n + 1 + n % 2;
    }
}
1
2
3
4
5
6
7
8