[LintCode 797.] 到达一个数字

LintCode 797. 到达一个数字

更新

其实第一份错误代码的内存问题不是占用内存过多，而是 heap-use-after-free。问题出在 auto&& p = q.front(); q.pop(); 使用的引用类型，但是对象随后就被释放掉了。改为 auto p = q.front(); q.pop(); 就变成 TLE 的错误了。

问题描述

你站在一个无穷数轴上的 0 位置。在位置目标上有一个目标。
在每一个动作中，你可以向左或向右。在第n次移动中(从1开始)，你行走n步。
返回到达目的地所需的最小步骤数。

样例

样例1

输入: target = 3
输出: 2
解释:
在第一步，我们从0到1。
在第二步，我们从1到3。
样例2

输入: target = 2
输出: 3
解释:
在第一步，我们从0到1。
在第二个步骤中，我们从1到-1。
在第三步，从-1到2。

注意事项

目标将是一个非零的整数范围[-10^9, 10^9]。

解题思路

一开始以为这是个BFS问题，结果提交测试的时候，target=4710915 发生了 Memory Limit Exceeded。
这其实是道数学题，通过手动构造最快方案来解决问题。
首先根据对称性，target<0 和 target>0 需要的步数一样多，走的路径相反。我们只需要把tatget转成正数来解决就好。
下面开始构造方案：

首先尽可能往前走，用最少的步数到达或者超过target；
如果正好到达target，则必是最短路径；
如果相差偶数步，则直接翻转前面某一步即可，必是最短路径；
如果相差奇数步，则需要再走1-2步，转成奇数步，再翻转。

我们注意到把第 k 步翻转，则减少的步数是 2k 步。所以如果相差偶数步，只需要翻转第 (sum - target)/2 步即可。

错误代码

BFS 内存占用过多：

class Solution {
public:
    /**
     * @param target: the destination
     * @return: the minimum number of steps
     */
    int reachNumber(int target) {
        // Write your code here
        if (target == 0) return 0;
        queue<pair<int,int>> q;
        q.push(make_pair(0,0));
        while(!q.empty()) {
            auto&& p = q.front();
            q.pop();
            int step = p.second + 1;
            int addr1 = p.first + step;
            if (-1E9 <= addr1 && addr1 <= 1E9) {
                if (addr1 == target) return step;
                else q.push(make_pair(addr1, step));
            }
            int addr2 = p.first - step;
            if (-1E9 <= addr2 && addr2 <= 1E9) {
                if (addr2 == target) return step;
                else q.push(make_pair(addr2, step));
            }
        }
        return -1;
    }
};

换一种写法的BFS，省一半内存也会TLE：

class Solution {
public:
    int reachNumber(int target) {
        if (target == 0) return 0;
        if (target < 0) target = -target;

        int step = 1;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                int x = q.front();
                q.pop();
                // if (x == target) return step;
                int left = x - step;
                int right = x + step;
                if (left == target || right == target) {
                    return step;
                }
                if (left > -target) q.push(left);
                if (right < target) q.push(right);
            }
            ++step; //
        }
        return -1;
    } // BFS, TLE
};

正确代码

构造法解决：

class Solution {
public:
    /**
     * @param target: the destination
     * @return: the minimum number of steps
     */
    int reachNumber(int target) {
        // Write your code here
        if (target == 0) return 0;
        if (target < 0) target = -target;
        int step = 0;
        int64_t sum = 0;
        while (sum < target) {
            sum += ++step;
        }
        if (sum == target) return step;
        int gap = sum - target;
        if (gap % 2 == 0) return step; // 翻转一个可做到 -2, -4, -6, ...
        if (step % 2 == 0) return step + 1; // 再走一个奇数步，转成偶数差值
        return step + 2; // 走完偶数步才能走奇数步，转成偶数差值
    }
};