X

LEETCODE 1404. Number of Steps to Reduce a Number in Binary Representation to One 解题思路分析

题目大意:

将二进制表示减到 1 的步骤数

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数:

  • 如果当前数字为偶数,则将其除以 2 。
  • 如果当前数字为奇数,则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

示例 1:

输入:s = "1101"
输出:6
解释:"1101" 表示十进制数 13 。
Step 1) 13 是奇数,加 1 得到 14 
Step 2) 14 是偶数,除 2 得到 7
Step 3) 7 是奇数,加 1 得到 8
Step 4) 8 是偶数,除 2 得到 4 
Step 5) 4 是偶数,除 2 得到 2 
Step 6) 2 是偶数,除 2 得到 1 

示例 2:

输入:s = "10"
输出:1
解释:"10" 表示十进制数 2 。
Step 1) 2 是偶数,除 2 得到 1 

示例 3:

输入:s = "1"
输出:0

提示:

  • 1 <= s.length <= 500
  • s 由字符 '0''1' 组成。
  • s[0] == '1'

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1404

解题思路分析:

本题的数据规模不大,最简单的思路即是模拟一遍题目的流程即可。

  1. 判断当前二进制是否是偶数,只需看其最后一位是0还是1,即可。0为偶数,1为奇数。
  2. 当为偶数时,进行除二操作,实际上就是抹掉二进制数的最低位。
  3. 当为奇数时,进行加一操作,这也不难,利用一个进位符,不断做加1进位操作即可。

实现代码:

public int numSteps(String s) {
    int res=0; // 返回结果
    while(s.length()>1){ // 当s不等于1时,循环操作
        // 为了方便计算,将当前字符串变为字符数组
        char[] arr = s.toCharArray();
        // 构建二进制操作后的字符串 
        StringBuilder sb=new StringBuilder();
        // 当前二进制是偶数时,进行除2操作。
        if(arr[s.length()-1]=='0'){
            // 截取s的最后一位
            for(int i=0;i<s.length()-1;i++){
                sb.append(arr[i]);
            }
        }else{ // 当前二进制是奇数时,进行加一操作
            int carry=1;
            for(int i=s.length()-1;i>=0;i--){
                int sum= (s.charAt(i)-'0')+carry;
                carry=sum/2;
                int n=sum%2;
                sb.append(n);
            }
            if(carry==1) sb.append(carry);
            sb.reverse();
        }
        s=sb.toString();
        res++;
    }
    return res;
}

本题解法执行时间为27ms。

Runtime: 27 ms, faster than 13.11% of Java online submissions for Number of Steps to Reduce a Number in Binary Representation to One.

Memory Usage: 39.8 MB, less than 100.00% of Java online submissions for Number of Steps to Reduce a Number in Binary Representation to One.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1404-number-of-steps-to-reduce-a-number-in-binary-representation-to-one-解题思路分析/
Categories: leetcode
kwantong: