LeetCode刷题实战397：整数替换
Given a positive integer n, you can apply one of the following operations:
If n is even, replace n with n / 2.
If n is odd, replace n with either n + 1 or n - 1.
Return the minimum number of operations needed for n to become 1.
示例
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
n 变为 1 所需的最小替换次数是多少？
解题
class Solution {
public:
int integerReplacement(long long n) {
if(n==1) return 0;
else if(n%2==0) return 1+integerReplacement(n/2);
else
{
long long m=n+1;
return 2+min(integerReplacement(m/2),integerReplacement((n-1)/2));
}
}
};
LeetCode刷题实战381：O(1) 时间插入、删除和获取随机元素
赞 (0)