LeetCode刷题(149)~将数字变成 0 的操作次数

举报
海轰Pro 发表于 2021/08/05 23:03:13 2021/08/05
【摘要】 题目描述 给你一个非负整数 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 。
步骤 27 是奇数,减 1 得到 6 。
步骤 36 是偶数,除以 2 得到 3 。
步骤 43 是奇数,减 1 得到 2 。
步骤 52 是偶数,除以 2 得到 1 。
步骤 61 是奇数,减 1 得到 0
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

示例 2:

输入:num = 8
输出:4
解释:
步骤 18 是偶数,除以 2 得到 4 。
步骤 24 是偶数,除以 2 得到 2 。
步骤 32 是偶数,除以 2 得到 1 。
步骤 41 是奇数,减 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=1000118有四位,那么答案就是 1+4-1=0
// 14=1110 31,一共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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。