題目來源
給一個(gè)數(shù)附鸽，求經(jīng)過多少次變換變?yōu)?脱拼。
我一開始想著直接用DP，但是想想應(yīng)該會(huì)內(nèi)存溢出拒炎。
class Solution {
public:
int integerReplacement(int n) {
vector<int> dp(n+1, 0);
for (int i=2; i<=n; i++) {
if (i % 2 == 0)
dp[i] = dp[i/2] + 1;
else
dp[i] = min(dp[i-1], dp[(i+1)/2]+1) + 1;
}
return dp[n];
}
};
然后果然就溢出了挪拟。
然后實(shí)際上想想，如果從指數(shù)級(jí)別來看的話击你，int最大也沒多大，所以直接dfs不會(huì)有什么問題谎柄。
代碼如下：
class Solution {
public:
int integerReplacement(int n) {
int cnt = 0;
return dfs(n);
}
int dfs(long long n)
{
if (n == 1)
return 0;
if (n % 2 == 0)
return dfs(n / 2) + 1;
else
return min(dfs(n+1), dfs(n-1)) + 1;
}
};
討論區(qū)里利用了位操作來實(shí)現(xiàn)丁侄，不是很理解，不管它朝巫。
