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