hiho一下第209周《Powers of Two》题目分析

1
0

《Powers of Two》题目分析

首先在表示n的时候,对于一个确定的k,使用2个(+2^k)或者2个(-2^k)或者一个(+2^k)和一个(-2^k)都是不合理的。所以最多只可能用1个(+2^k)或者1个(-2^k)

如果n是偶数,表示n的时候显然不应该用2^0。因为如果用就至少用2个,不合理。

如果n是奇数,表示n的时候可能用1个+2^0或者1个-2^0

所以我们可以用递归+记忆化搜索来求解答案。

map<int, int> f;
int calc(int n) {
    if (f.find(n) == f.end()) {
        int s;
        if (n % 2 == 0) s = calc(n / 2);
        else if (n == 1) s = 1;
        else s = min(calc(n - 1), calc(n + 1)) + 1;
        f[n] = s;
    }
    return f[n];
}

2 answer(s)

0

fff

1

可以直接构造答案的

int mycal(int n) { int ans,k; ans=k=0; do { k+=n%2; n/=2; if(n%2==0) { if(n/2%2==1) { ans+=k>0?1:0; k=k>1?1:0; }else { ans+=k>1?2:k; k=0; } } }while(n>0); return ans; }

write answer 切换为英文 切换为中文


转发分享