首页 > 其他分享 >【刷力扣】1342. 将数字变成 0 的操作次数

【刷力扣】1342. 将数字变成 0 的操作次数

时间:2024-08-14 15:37:42浏览次数:15  
标签:cnt 二进制 int 1342 次数 builtin num 刷力 复杂度

1342.将数字变成 0 的操作次数
这题是包含在“力扣新手村”里的题,按直接模拟的方法来写很简单。
不过我一点儿都没有想到位运算的写法,看了看别人的题解,学习了一下下~

解法1:直接模拟

直接按题意模拟:
1.判断num是否为0。
2.num不为0,进行一次操作:
(1)奇数:num = num - 1;
(2)偶数:num = num / 2;
3.再次运行1进行判断,2进行操作(cnt++),直到num为0。

class Solution {
public:
    int numberOfSteps(int num) {
        int cnt = 0;
        while (num) {
            if (num % 2 == 0) num /= 2;
            else num -= 1;
            cnt++;
        }
        return cnt;
    }
};

时间复杂度:\(O(log num)\)
空间复杂度:\(O(1)\)

解法2:位运算1

其中:
num & 1:判断num是否为奇数,如果为奇数,则进行一次操作,操作次数cnt加1。
cnt再次加1,num并作右移操作,即num >> 1(num / 2)。
多做了一次右移操作,所以要将cnt - 1。

class Solution {
public:
    int numberOfSteps(int num) {
        int cnt = 0;
        while (num) {
            cnt += (num & 1) + 1;
            num >>= 1;
        }
        return max(cnt - 1, 0);
    }
};

时间复杂度:\(O(log num)\)
空间复杂度:\(O(1)\)

解法3:位运算2

其中:
1.减去1的次数,即二进制位中1的个数。
__bulitin_popcount
这个函数作用是返回输入的二进制表示中1的个数;如果传入0则返回0。
2.除以2的次数,二进制数长度减一,即最高位到最低位的距离。
__builtin_clz
这个函数作用是返回输入数二进制表示从最高位开始(左起)的连续的0的个数。

class Solution {
public:
    int numberOfSteps(int num) {
        if (num == 0) return 0;
        return 32 - __builtin_clz(num) - 1 + __builtin_popcount(num);
    }
};

时间复杂度:\(O(1)\)。\(O(logW)\),其中W为32。
空间复杂度:\(O(1)\)。

函数学习

1.__builtin_ctz

这个函数作用是返回输入数二进制表示从最低位开始(右起)的连续的0的个数。

2.__builtin_clz

这个函数作用是返回输入数二进制表示从最高位开始(左起)的连续的0的个数。

3.__builtin_ffs

这个函数作用是返回输入数二进制表示的最低非0位的下标,下标从1开始计数;如果传入0则返回0。

4.__bulitin_popcount

这个函数作用是返回输入的二进制表示中1的个数;如果传入0则返回0。

5.__bulitin_parity

这个函数作用是返回输入的二进制表示中1的个数的奇偶,也就是输入的二进制中1的个数对2取模的结果。

标签:cnt,二进制,int,1342,次数,builtin,num,刷力,复杂度
From: https://www.cnblogs.com/Henfiu/p/18359117

相关文章

  • 编写一个程序,打开和读取一个文本文件,并统计文件中每个单词出现的次数。用改进的二叉查
    /编写一个程序,打开和读取一个文本文件,并统计文件中每个单词出现的次数。用改进的二叉查找树存储单词及其出现的次数。程序在读入文件后会提供一个有三个选项菜单。第一个选项是列出所有的单词和出现的次数。第二个选项是让用户输入一个单词,程序报告该单词在文件中出现的次数。......
  • 【SQL】参加测试的次数
    目录题目分析代码题目学生表: Students+---------------+---------+|ColumnName|Type|+---------------+---------+|student_id|int||student_name|varchar|+---------------+---------+在SQL中,主键为student_id(学生ID)。该表内的......
  • 【Spring-RabbitMq】设置消费重试次数
    引言在我们实际项目中需要对消息消费的高可用做保证,首先需要做到的就是消息的重试机制,设想一下以下场景:当库存服务处理上游服务发过来的订单消息时,此时服务宕机了,或者网络不可用了,那我这个消息是应该算消费成功还是消费失败呢?显然,我们肯定要对处理不成功的消息进行重试......
  • 008.Vue3入门,最基础的事件处理,点击按钮增加次数,支持传参
    1、代码如下:<template><h3>内联事件处理群</h3><button@click="addCount1">Add</button><p>{{count1}}</p><button@click="addCount2('hello')">按钮</button><p>{{coun......
  • 3224. 使差值相等的最少数组改动次数
    原题链接前情提要,结合原题解区的题解题解先简化问题,对于一对数\(a,b\),其中\(a\leqb\),要使其差为\(X\)的操作数是多少?分类讨论1.如果\(b-a==X\),操作数为\(0\)(不操作)2.如果\(X\ltb-a\),操作数为\(1\)(增加a或者减小b)3.如果\(X\in[b-a+1,k-a]\),操作数为\(1\)(增大b......
  • 3229. 使数组等于目标数组所需的最少操作次数
    原题链接题解原题解区写的很详细,所以这里总结一下自己的语言性质1.如果两个数组相等,那么两个数组的差分数组也相等根据这个性质,原题就转换成了对数组\(a\)的差分数组操作(选取两个点\(i,j\)使\(d[i]+1,d[j]-1\)或者\(d[i]-1,d[j]+1\))性质2:差分数组上,有多少加,就有多少......
  • gRPC 是否能够添加最大调用重试次数?
    我还没有找到任何如何在某些rpc调用上添加重试逻辑的示例。gRPC是否能够添加最大调用重试次数?如果是的话,它是一个内置函数吗?gRPC本身没有内置机制来指定最大重试次数。gRPC使用的常见模式是deadline和cancellation,允许你在请求级别控......
  • 编写一个函数接受这些参数:内含int类型元素的数组名,数组的大小和一个代表选取次数的值
    /编写一个函数接受这些参数:内含int类型元素的数组名,数组的大小和一个代表选取次数的值。该函数从数组中随机指定数量的元素,并打印他们。每个元素只能选择一次(模拟抽奖数字或挑选陪审团成员)。另外,如果你的实现有time()或类似的函数,可以在srand()中使用这个函数的输出来初始化......
  • 一次数据库迁移遇到的一些问题
    简单数据库迁移操作迁移方案迁移方案很简单,首先将旧的库dump下来,然后在新库中导入旧的库dump下来的文件.#旧库dump的指令mysqldump-hhost-Ppost-uuser-pdatabase>database_backup.sql#新库导入的命令mysql-hhost-Ppost-uuser-pdatabase<databas......
  • 英语真题在线解决查词限制次数(仅供学习参考)
    在我学习四级的时候发现了一个在线四六级题库网站,而且还自带翻译功能,实在是太贴心了。网站地址如下:英语真题在线-试卷排版设计|官网(burningvocabulary.cn)但是它每天查词次数有限  所以我想看看能不能让我多查几次,然后我觉着它不可能联网记录我的查询次数,那么肯定在......