LeetCode刷题(149)~将数字变成 0 的操作次数
【摘要】 题目描述
给你一个非负整数 num ,请你返回将它变成 0 所需要的步数。 如果当前数字是偶数,你需要把它除以 2 ;否则,减去 1 。
示例 1:
输入:num = 14
输出:6
解释:
步骤 1) 14 是偶数,除以 2 得到 7 。
步骤 2) 7 是奇数,减 1 得到 6 。
步骤 3) 6 是偶数,除以 2 得到 3 。
步骤 4) 3 是奇数,减 1...
题目描述
给你一个非负整数 num ,请你返回将它变成 0 所需要的步数。 如果当前数字是偶数,你需要把它除以 2 ;否则,减去 1 。
示例 1:
输入:num = 14
输出:6
解释:
步骤 1) 14 是偶数,除以 2 得到 7 。
步骤 2) 7 是奇数,减 1 得到 6 。
步骤 3) 6 是偶数,除以 2 得到 3 。
步骤 4) 3 是奇数,减 1 得到 2 。
步骤 5) 2 是偶数,除以 2 得到 1 。
步骤 6) 1 是奇数,减 1 得到 0 。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
示例 2:
输入:num = 8
输出:4
解释:
步骤 1) 8 是偶数,除以 2 得到 4 。
步骤 2) 4 是偶数,除以 2 得到 2 。
步骤 3) 2 是偶数,除以 2 得到 1 。
步骤 4) 1 是奇数,减 1 得到 0 。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
示例 3:
输入:num = 123
输出:12
- 1
- 2
提示:
- 0 <= num <= 10^6
解答 By 海轰
提交代码
int numberOfSteps (int num) { int count=0; while(num) { if(num%2==0) { num/=2; ++count; } else { num-=1; ++count; } } return count; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
运行结果
提交代码
// 思路:
// 比如 8=1000 有1个1,8有四位,那么答案就是 1+4-1=0
// 14=1110 3个1,一共4位,答案就是 3+4-1=6;
// 规律:数的位数(二进制表示)+其中1的个数 再减去1 【注意0特殊 直接返回0即可】
// 解释:题目中偶数除以2其实就是数右移一位,奇数减1其实就是将二进制表示下的最后一位1变成0,
// 而减去1之后,奇数又变成了偶数 依然会进行除2的操作
// 所以二进制表示中有一个1 就会进行一次的移位 再加上偶数除2的移位
// 那么为什么会减去1呢
// 因为最后变成1时 再减去1就变为0 之后又做了一次除2的操作 故需要减去1
int numberOfSteps (int num) { if(num==0) return 0; int count=0; while(num) { count+= (num&1)==1? 2:1; num>>=1; } return count-1; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
运行结果
题目来源
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero
文章来源: haihong.blog.csdn.net,作者:海轰Pro,版权归原作者所有,如需转载,请联系作者。
原文链接:haihong.blog.csdn.net/article/details/108545469
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)