给定一个正整数 n,你可以做如下操作:
n 变为 1 所需的最小替换次数是多少?
示例 1:
输入:
8
输出:
3
解释:
8 -> 4 -> 2 -> 1
示例 2:
输入:
7
输出:
4
解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/integer-replacement 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int integerReplacement(int n) {
if(n == 1)
return 0;
if(n == 2147483647)//防止+1溢出
return 32;
if(n%2 == 0)
return 1+integerReplacement(n>>1);
else
return 1+min(integerReplacement(n+1), integerReplacement(n-1));
}
};
class Solution {
unordered_map<int,int> map;
public:
int integerReplacement(int n) {
if(n == 1)
return 0;
if(n == 2147483647)//防止+1溢出
return 32;
if(map.find(n) != map.end())
return map[n];
int m;
if(n%2 == 0)
m = 1+integerReplacement(n>>1);
else
m = 1+min(integerReplacement(n+1), integerReplacement(n-1));
map[n] = m;
return m;
}
};
偶数的时候没什么选择,直接除以2 奇数的时候,怎么选择?+1,-1 ?(操作后肯定为偶数,2的倍数) 为了让数更快的等于1,更优的操作是,操作后还为4的倍数,就可以连续除以2两次
class Solution {
public:
int integerReplacement(int n) {
int count = 0;
if(n == INT_MAX)
return 32;
while(n != 1)
{
if((n&1) == 0)//偶数
{
++count;
n >>= 1;
}
else//奇数有两种情况0b01, 0b11
{
if(n == 3)//特殊情况
{
count += 2;
break;
}
if((n&3) == 3)
n += 1;//操作后可以多除1次2
else
n -= 1;
++count;
}
}
return count;
}
};