|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
令f(n)表示从0经过(a)和(b)两种操作到达n的最少步骤,则由题意我们可以得出:
(1)如果n是奇数,则显然有f(n) = f(n-1)+1,即最后一步必须是操作(b),这是因为如果最后一步是操作(a),乘2,我们不可能得到一个奇数
(2)如果n是偶数,则有f(n) = min(f(n/2), f(n-1))+1,由于n-1是奇数,由(1)知f(n-1) = f(n-2)+1,所以
f(n) = min(f(n/2), f(n-2)+1)+1
到底是先减2好呢,还是先除以2好呢,贪心的知觉告诉我们先除好,因为除了之后得到的数更小,通过数学归纳法,我们可以证明知觉是对的:
考虑base的情况,我们有
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 3
可以看到f(4) = min(f(2), f(2)+1)+1 = f(2)+1,所以对于4,最后一步是操作(a)更优,也即f(4) = f(4/2)+1
假设对于n=2k,满足f(n) = f(n/2)+1,即f(2k) = f(k)+1,对于n = 2k+2的情况,通过上面的讨论(2)有
f(2k+2) = min(f(k+1), f(2k)+1)+1
将f(2k) = f(k)+1带入,则有
f(2k+2) = min(f(k+1), f(k)+2)+1,
又因为k+1可由k通过操作(b)达到,所以f(k+1) <= f(k)+1 < f(k)+2,从而
f(2k+2) = f(k+1) + 1
所以对于n为偶数的情况,有f(n) = f(n/2)+1,结合上面的讨论(1)就可以写代码了:
- class Solution {
- public:
- int countOperations(int n) {
- int step = 0;
- for(; n; ++step){
- if(n & 1) --n;
- else n >>= 1;
- }
- return step;
- }
- };
复制代码
|
|