> 文档中心 > LeetCode 1611. 使整数变为 0 的最少操作次数

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) (i1) 位为 1 1 1 且从第 ( i − 2 ) (i-2) (i2) 位到第 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+11 次;
   ( 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[d1:0]0d1 0...0 的最少步数;

三、本题小知识

  递归求解某个问题的时候,抽象出中间步骤,会清晰许多;


四、加群须知

  相信看我文章的大多数都是「 大学生 」,能上大学的都是「 精英 」,那么我们自然要「 精益求精 」,如果你还是「 大一 」,那么太好了,你拥有大把时间,当然你可以选择「 刷剧 」,然而,「 学好算法 」,三年后的你自然「 不能同日而语 」
  那么这里,我整理了「 几十个基础算法 」 的分类,点击开启:

🌌《算法入门指引》🌌
  如果链接被屏蔽,或者有权限问题,可以私聊作者解决。

  大致题集一览:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述



在这里插入图片描述


  为了让这件事情变得有趣,以及「 照顾初学者 」,目前题目只开放最简单的算法 「 枚举系列 」 (包括:线性枚举、双指针、前缀和、二分枚举、三分枚举),当有 一半成员刷完 「 枚举系列 」 的所有题以后,会开放下个章节,等这套题全部刷完,你还在群里,那么你就会成为「 夜深人静写算法 」专家团 的一员。
  不要小看这个专家团,三年之后,你将会是别人 望尘莫及 的存在。如果要加入,可以联系我,考虑到大家都是学生, 没有「 主要经济来源 」,在你成为神的路上,「 不会索取任何 」
  🔥联系作者,或者扫作者主页二维码加群,加入刷题行列吧🔥


🔥让天下没有难学的算法🔥
C语言免费动漫教程,和我一起打卡! 🌞《光天化日学C语言》🌞
让你养成九天持续刷题的习惯 🔥《九日集训》🔥
入门级C语言真题汇总 🧡《C语言入门100例》🧡
组团学习,抱团生长 🌌《算法零基础100讲》🌌
几张动图学会一种数据结构 🌳《画解数据结构》🌳
竞赛选手金典图文教程 💜《夜深人静写算法》💜