754.到达终点数字

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

C++

/*
数学。找到第一个使 sum = 1 + 2 + ... + k >= target 且 sum - target 为偶数的 k。

首先，可以将所有 target 为负的情况转化为 target 为正的情况。

我们一直向右走，直到所处的位置超过 target，此时处在 sum = 1 + 2 + ... + k。我们可以算出多走了几个位置：a = sum - target。那么我们就要使前面走的某一步 x 反向，使 sum 变为：sum' = sum - a = target = 1 + 2 + ... - x + ... + k。可以看到，sum' 其实是在 sum 的基础上减了 2 个 x：sum' = sum - 2x。

那么就可以推出 a = 2x = sum - target。所以 sum - target 必须为偶数。

所以我们只需要找到第一个使 sum = 1 + 2 + ... + k >= target 且 sum - target 为偶数的 k 即为答案。
*/
class Solution {
public:
    bool check(int steps, int target) {
        int sum = (1 + steps) * steps >> 1;
        if( sum == target || (sum > target && ((sum - target) % 2 == 0)) ) 
            return true;
        return false;
    }

    int reachNumber(int target) {
        for(int i = 0; i <= 2 * abs(target); i ++) 
            if(check(i, abs(target))) return i;
        return -1;
    }
};







// DFS：数据量太大就不行，这里的时间复杂度为 O(2^2*target)
// class Solution {
// public:
//     int reachNumber(int target) {
//         return dfs(0, 1, target);
//     }

//     int dfs(int npos, int k, int target){
//         if(npos == target) return k - 1;
//         if(k > 2 * abs(target)) return INT_MAX; 
//         return min(dfs(npos + k, k + 1, target), dfs(npos - k, k + 1, target));
//     } 
// };