LeetCode 1611. 使整数变为 0 的最少操作次数
文章目录
- 一、题目
-
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
-
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、本题小知识
- 四、加群须知
一、题目
1、题目描述
给你一个整数 n n n,你需要重复执行多次下述操作将其转换为 0 0 0 :
1)翻转 n n n 的二进制表示中最右侧位(第 0 0 0 位)。
2)如果第 ( i − 1 ) (i-1) (i−1) 位为 1 1 1 且从第 ( i − 2 ) (i-2) (i−2) 位到第 0 0 0 位都为 0 0 0,则翻转 n n n 的二进制表示中的第 i i i 位。
返回将 n n n 转换为 0 0 0 的最小操作次数。
样例输入:n = 3
样例输出:2
2、基础框架
- C语言 版本给出的基础框架代码如下:
int minimumOneBitOperations(int n){}
3、原题链接
LeetCode 1611. 使整数变为 0 的最少操作次数
二、解题报告
1、思路分析
( 1 ) (1) (1) 1 1 1 通过 1 1 1 次 变成 0 0 0;
( 2 ) (2) (2) 10 10 10 通过先变成 11 11 11,再翻转最高位变成 01 01 01,然后变成 0 0 0,总共 3 次;
( 3 ) (3) (3) 100 100 100 通过 3次变成 110 110 110,再翻转最高位变成 010 010 010,再三次变成 0 0 0,总共 7 次;
( 4 ) (4) (4) 根据数学归纳法,我们发现,对于 1 0...0⏟ k 1\underbrace{0...0}_{k} 1k 0...0,变到 0 0 0 的次数为 2k+1 − 1 2^{k+1} - 1 2k+1−1 次;
( 5 ) (5) (5) 然后我们对一个数 n n n 进行二进制分解 n = ( 101011 ) 2 n = (101011)_2 n=(101011)2 ,那么我们必须先想办法把最高位的 1 1 1 变成 0 0 0,于是就转化成了求将 ( 01011 ) 2 (01011)_2 (01011)2 转化为 ( 10000 ) 2 (10000)_2 (10000)2 的最少步数;而对于 ( 01011 ) 2 (01011)_2 (01011)2 要转化成 ( 10000 ) 2 (10000)_2 (10000)2,又可以转化成将 ( 1011 ) 2 (1011)_2 (1011)2 转化成 ( 1000 ) 2 (1000)_2 (1000)2 的最少步数;然后就是 ( 011 ) 2 (011)_2 (011)2 要变成 ( 000 ) 2 (000)_2 (000)2, 也就是 ( 11 ) 2 (11)_2 (11)2 变成 ( 00 ) 2 (00)_2 (00)2;
( 6 ) (6) (6) 于是得出算法:
( 6.1 ) (6.1) (6.1) 首先将 n n n 进行二进制分解;
( 6.2 ) (6.2) (6.2) 一个数如果要变到 1 0...0⏟ k 1\underbrace{0...0}_{k} 1k 0...0 ,则调用递归dfs1(n)
;如果要变到 0 0 0,则调用递归dfs2(n)
,于是递归求解dfs2(n)
就是答案了。
2、时间复杂度
最坏时间复杂度 O ( l o g 2 n ) O(log_2n) O(log2n) 。
3、代码详解
int dfs1(int *bit, int d); // (1)int dfs2(int *bit, int d); // (2)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);}
- ( 1 ) (1) (1)
int dfs1(int *bit, int d)
表示 b i t [ d : 0 ] → 1 0...0 ⏟ d bit[d:0] \to 1\underbrace{0...0}_{d} bit[d:0]→1d 0...0 的最少步数; - ( 2 ) (2) (2)
int dfs2(int *bit, int d)
表示 b i t [ d : 0 ] → 0 0...0 ⏟ d bit[d:0] \to 0\underbrace{0...0}_{d} bit[d:0]→0d 0...0 的最少步数; - ( 3 ) (3) (3) 对于这两个函数,判断
bit[d]
这一位和要求的位是否一致,如果不一致,则需要利用规则二进行翻转;如果一直,则继续计算 b i t [ d − 1 : 0 ] → 0 0...0 ⏟d − 1bit[d-1:0] \to 0\underbrace{0...0}_{d-1} bit[d−1:0]→0d−1 0...0 的最少步数;
三、本题小知识
递归求解某个问题的时候,抽象出中间步骤,会清晰许多;
四、加群须知
相信看我文章的大多数都是「 大学生 」,能上大学的都是「 精英 」,那么我们自然要「 精益求精 」,如果你还是「 大一 」,那么太好了,你拥有大把时间,当然你可以选择「 刷剧 」,然而,「 学好算法 」,三年后的你自然「 不能同日而语 」。
那么这里,我整理了「 几十个基础算法 」 的分类,点击开启:
🌌《算法入门指引》🌌
如果链接被屏蔽,或者有权限问题,可以私聊作者解决。
大致题集一览:
为了让这件事情变得有趣,以及「 照顾初学者 」,目前题目只开放最简单的算法 「 枚举系列 」 (包括:线性枚举、双指针、前缀和、二分枚举、三分枚举),当有 一半成员刷完 「 枚举系列 」 的所有题以后,会开放下个章节,等这套题全部刷完,你还在群里,那么你就会成为「 夜深人静写算法 」专家团 的一员。
不要小看这个专家团,三年之后,你将会是别人 望尘莫及 的存在。如果要加入,可以联系我,考虑到大家都是学生, 没有「 主要经济来源 」,在你成为神的路上,「 不会索取任何 」。
🔥联系作者,或者扫作者主页二维码加群,加入刷题行列吧🔥
🔥让天下没有难学的算法🔥
C语言免费动漫教程,和我一起打卡! 🌞《光天化日学C语言》🌞
让你养成九天持续刷题的习惯 🔥《九日集训》🔥
入门级C语言真题汇总 🧡《C语言入门100例》🧡
组团学习,抱团生长 🌌《算法零基础100讲》🌌
几张动图学会一种数据结构 🌳《画解数据结构》🌳
竞赛选手金典图文教程 💜《夜深人静写算法》💜