记忆化搜索
如果替换成vector，vector需要n的空间，不行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int integerReplacement(int n) {
if(n == 1)
return 0;
if(memo[n])
return memo[n];
int tmp;
if(n & 1)
tmp = min(integerReplacement(n / 2), integerReplacement(n / 2 + 1)) + 2;
else
tmp = integerReplacement(n / 2) + 1;
memo[n] = tmp;
return tmp;
}
private:
unordered_map<int, int> memo;
};
|
时间复杂度：O(logn) 空间复杂度: O(logn)
原因在于这里每一步都会将原数/2
上述重点语句。对于n为奇数来说，n-1和n+1都必然会带来一个偶数，如果是偶数就不是1而且只能除以2，所以把这个操作合并为一次完成就是(n-1)/2或(n+1)/2。
但是考虑到溢出的问题，由于(n-1)/2就是n/2向下取整，而(n+1)/2就是n/2向上取整，因此他们可以表示为n/2和n/2+1。
dp超内存，空间复杂度是O(N)