関小君刷题记

题目大意：

将二进制表示减到 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-解题思路分析/