题目:
给你一个整数 n nn，你需要重复执行多次下述操作将其转换为 0 00 ：
1）翻转 n nn 的二进制表示中最右侧位（第 0 00 位）。
2）如果第 ( i − 1 ) (i-1)(i−1) 位为 1 11 且从第 ( i − 2 ) (i-2)(i−2) 位到第 0 00 位都为 0 00，则翻转 n nn 的二进制表示中的第 i ii 位。
返回将 n nn 转换为 0 00 的最小操作次数。
样例输入： n = 3
样例输出： 2
思路分析:
(1)1 通过1次变成0;
(2)10通过先变成11,再翻转最高位变成01.然后变成0.总共3次;
(3)100通过3次变成110.在翻转最高位变成010.再三次变成0.总共7次.
通过数学归纳法可以得出算法
首先将n进行二进制分解,在调用递归就可以求解了.
int dfs1(int *bit, int d); // (1)表示bit的最小步数
int dfs2(int *bit, int d); // (2)表示bit的最小步数
int dfs1(int *bit, int d) {
if(d == 0) {
return bit[0] ^ 1;
}
if(!bit[d]) {
return dfs1(bit, d-1) 1 ( (1<<d) - 1 );
}
return dfs2(bit, d-1);
}
int dfs2(int *bit, int d) {
if(d == 0) {
return bit[0];
}
if(bit[d]) {
return dfs1(bit, d-1) 1 ( (1<<d) - 1 );
}
return dfs2(bit, d-1);
}
int minimumOneBitOperations(int n){
if(n == 0) {
return 0;
}
int stk[100], top = 0;
while(n) {
stk[top ] = n & 1;
n >>= 1;
}
return dfs2(stk, top-1);
}
