为什么同样是记忆化搜索，我就用了将近100倍的时间？

Question

class Solution {
public:
    unordered_map<int, int> memo;
    int integerReplacement(int n) {
        if (n == 1) return 0;
        if (n == INT_MAX) return 32;


        if (memo.count(n)) return memo[n];
        int res = 0;
        if (n & 1) {
            res = 1 + min(integerReplacement(n - 1), integerReplacement(n + 1));
        } else {
            res = 1 + integerReplacement(n >> 1);
        }
        memo[n] = res;
        return res;
    }
    /////   以上是题解（只用了4ms）     ///////////////

    vector<int> cache;
    int integerReplacement(int n) {
        if(n==INT_MAX) return 32;
        int i=0;
        while(n%2==0){
            n=n/2;
            i++;
        }
        cache = vector<int>(n+2,-1);
        return dfs(n)+i;
    }
    int dfs(int n) {
        if(n==1) return 0;
        if(cache[n]!=-1) return cache[n];

        if(n%2==0) cache[n] = dfs(n/2)+1;
        else cache[n] = min(dfs(n+1),dfs(n-1))+1;

        return cache[n];
    }
    ////   上面是我自己写的感觉思路一样但我用了400ms！！   //////
};

Answer 1

需要注意到n的范围比较大，最高能到达int的最大值，2e9左右
你的vector是根据n进行开空间的，虽然前面对n进行了处理（一直除2到奇数），但是在数据构造为奇数的情况下仍然得开大空间
以下测试为测试代码，功能为测试vector开空间以及赋值需要多少时间
这里测试情况在0.26s（260ms）的时候就会断言失败了

double st = clock();
cache = vector<int>(n+2,-1);
double ed = clock();
if (ed - st <= CLOCKS_PER_SEC*0.26) {
    printf("%d", n);
}
assert(ed - st <= CLOCKS_PER_SEC*0.26);

数据为 111111111，这里刚好是9个1，大数据的时候，明显会存在问题

但是如果用unordered_map就不一样了，这个底层为哈希表，而且是动态开空间，查询复杂度和插入复杂度理论都是O(1)