列表

详情

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

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 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

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int numSteps(string s) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-31 15:40:20 

func numSteps(s string) (res int) {
    index := len(s) - 1
    oneStatus := false
    for index > 0 {
        // 当前位为 1 或者当前为应该从 0 变成 1
        if s[index] == '1' || oneStatus {
            res += 2    // 奇数加 1 除 2，两步
            index--
            for index >= 0 && s[index] == '1' {
                // 连接着的所有 1 都变成 0，偶数情况除 2，只需一步
                res++
                index--
            }
            if index >= 0 {
                // 退出上一个循环时当前 index 对应为 0，需要变成 1，oneStatus 记录
                oneStatus = true
            }
        } else {
            // 为 0 ，偶数
            res++
            index--
        }
    }
    return
}

python3 解法, 执行用时: 52 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-31 15:39:37 

class Solution:
    def numSteps(self, s: str) -> int:

        #特殊情况只是开头有1
        if s[1::].count("0") == len(s)-1: return len(s)-1
        """
        1.一定会进行移位，所以次数为len(s)-1
        2.因为偶数才会直接除，当第一次遇见1时会进行2次操作
        3.在第一个和最后一个1之间的0，会因为进位而进行两次操作，所以统计第一个1和第二个1之间的0的个数 zero
        最后结果 cnt = len(s)-1+2+zero = len(s)+1+zero
        """
        cnt = len(s) + 1
        for i in range(len(s)):
            if "1" not in s[i+1::]: break      
        return cnt + s[:i].count("0")

python3 解法, 执行用时: 52 ms, 内存消耗: 16 MB, 提交时间: 2023-05-31 15:39:23 

class Solution:
    def numSteps(self, s: str) -> int:
        #字符串转为2进制下的十进制
        s = int(s,2)
        cnt = 0
        while s > 1:
            #判断最后一位是否为1，不管结果如何都算一步
            if s&1 == 1:
                s += 1
            elif s&1 == 0:
                s = s>>1
            cnt += 1
        return cnt

python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-05-31 15:39:07 

class Solution:
    def numSteps(self, s: str) -> int:
        carry, res = 0, 0
        for i in range(len(s)-1, 0, -1):
            res = res+2 if carry ^ (s[i] == '1') else res+1
            carry = 1 if carry or (s[i] == '1') else 0
        return res+1 if carry else res

python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-31 15:38:19 

class Solution:
    def numSteps(self, s: str) -> int:
        n, ans = len(s), 0
        # meet1 记录我们有没有遇见过字符 1
        meet1 = False
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                # 如果当前字符为 0，分为两种情况
                # (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
                # (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
                ans += (2 if meet1 else 1)
            else:
                # 如果当前字符为 1，分为两种情况
                # (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
                #     这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作
                # (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
                if not meet1:
                    if i != 0:
                        ans += 2
                    meet1 = True
                else:
                    ans += 1
        return ans

java 解法, 执行用时: 0 ms, 内存消耗: 39.5 MB, 提交时间: 2023-05-31 15:37:56 

class Solution {
    public int numSteps(String s) {
        int i,x,n=s.length();
        for(i=-48,x=48;--n!=0;){
            ++i;
            if (s.charAt(n)==x) continue;
            x=49;++i;
        }
        return i+x;
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 6.2 MB, 提交时间: 2023-05-31 15:37:42 

class Solution {
public:
    int numSteps(string s) {
        int n=s.length(),i=n-49,x=48;
        for(;--n;i+=x^s[n],x|=s[n]);
        return i+x;
    }
};

上一题

© 2024 leetcode.cn