leetcode 754

问题

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

1
2
3
4
5
Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

1
2
3
4
5
6
Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Note:

target will be a non-zero integer in the range [-10^9, 10^9].

分析

这道题是一道数学问题，和算法问题仿佛关系不大。最初使用广度优先搜索和迭代深搜进行求解，但都超时了。回过头来在数据规模可以看出，这道题的时间复杂度应该是小于O(n)的，所以从O(logn)，O(sqrt(n))，O(1)三种时间复杂度中进行考虑。

分析可知 target 和 -target 的具有相同的答案，因此我们只考虑 target 为正数的时候。使用贪心策略，从 0 走到target最快的方案当然是沿着正方向一直走，假设沿着正方向最少走k次才能超过或者等于target，则有
$$
1+2+…+k = target +d \;\;( 0 \leq d < k)
$$

  1. 若 d == 0，则 k就是最终的答案。
  2. 若 d 是偶数，那么说明我们沿着正方向走k次已经超过了 target ，因此需要调整往回走。为了保证答案的最小化，最佳策略就是在 1，2，…，k 中找到其中一步 i 使其往负方向走，则总体向正方向前进的距离就会减少 2i，此时 i == d/2。最终答案依然是k。
  3. 若d是奇数。这种情况下在 “1，2，…，k 中找到其中一步 i 使其往负方向走” 的方案就行不通了。因为无论选择那个 i，总体前进的距离的减少值总会是偶数。下面还要将 k 分奇偶进行讨论。
    1. 当 k 偶数时。再向正方向前进一步，则有 $ 1+2+..+k+(k+1) = target+d+(k+1) \;(0\leq d<k)$ 此时 d+k+1 便士偶数，于是可以 “1，2，…，k，k+1 中找到其中一步 i 使其往负方向走”，此时 i == (d+k+1)/2。答案k+1。
    2. 当k为奇数时。则向正方向前进一步也无法满足条件，因此我们，在走了k次的基础上先回推一步再向前一步，则有 $ 1+2+..+k-(k+1)+(k+2) = target+d+1) \;(0\leq d<k)$ ，此时再在 “1，2，…，k 中找到其中一步 i 使其往负方向走”，此时 i == (d+1)/2。答案k+2。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// O(sqrt(n))
class Solution {
public:
    int reachNumber(int target) {
        int sum = 0;
        int k = 0;
        int t = abs(target);
        while (sum < t) {
            sum += ++k;
        }
        int d = sum - t;
        if ((d%2) == 0) return k;
        return k + 1 + (k%2);
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// O(1)
class Solution {
public:
    int reachNumber(int target) {
        int sum = 0;
        int t = abs(target);
        int k = sqrt(t*2);   // k^2 + k = 2t -> k < sqrt(2t)
        sum = (1+k)*k/2;
        while (sum < t) { sum += ++k; }
        int d = sum - t;
        if ((d%2) == 0) return k;
        return k + 1 + (k%2);
    }
    
};