754. 到达终点数字

Posted on In , Views: Disqus: Reading time ≈ 1 mins.

在一根无限长的数轴上，你站在 0 的位置。终点在 target 的位置。
你可以做一些数量的移动 numMoves :

  • 每次你可以选择向左或向右移动。
  • 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的 最小 移动次数 (即最小 numMoves) 。

数学分析

1
2
3
4
5
6
7
8
9
class Solution {
    public int reachNumber(int target) {
        if (target < 0) target = -target;
        int k = (int) Math.ceil((Math.sqrt(1 + 8 * (double) target) - 1) / 2);
        int d = (1 + k) * k / 2 - target;
        if ((d & 1) == 0) return k;
        return ((k + 1) & 1) == 1 ? k + 1 : k + 2;
    }
}

二分查找

image.png

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int reachNumber(int target) {
        queue<pair<int,int> > pos;
        pos.push(make_pair(0,0));
        while(!pos.empty()){
            if(target==pos.front().first)
                return pos.front().second;
            else{
                int nowPos=pos.front().first;
                int step=pos.front().second;
                pos.push(make_pair(nowPos+step+1,step+1));
                pos.push(make_pair(nowPos-step-1,step+1));
                pos.pop();
            }
        }
        return -1;
    }
};

DP（0-1 背包）

image.png