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

标签: 位运算 字符串

难度: Medium

给你一个以二进制形式表示的数字 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'

Submission

运行时间: 17 ms

内存: 16.0 MB

class Solution:
    def numSteps(self, s: str) -> int:
        L=len(s)
        ret=0
        idx=L-1
        while idx>0 and s[idx]=='0':
            ret+=1
            idx-=1
        if idx>0:
            ret+=2

        while idx>0:
            if s[idx]=='0':
                ret+=2
            else:
                ret+=1
            idx-=1
        return ret

Explain

题解的主要思路是模拟题目中描述的操作，直接在二进制字符串上进行操作。首先从字符串的最右侧开始，即从最低位开始处理。首先跳过所有的'0'，这表示连续的除以2的操作，直到遇到第一个'1'。当遇到'1'时，需要执行加1的操作，然后再继续检查之前的位。对于每个'1'，需要加1然后除以2（这可以理解为直接转移到下一个较高位）。对于每个'0'，仅需要除以2。这样，通过一次遍历，即可计算出将字符串减少到'1'所需的总步骤数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numSteps(self, s: str) -> int:
        L = len(s) # 获取二进制数的长度
        ret = 0 # 初始化步骤计数器
        idx = L - 1 # 从字符串的最后一个字符开始处理
        # 跳过末尾的所有'0'，每跳过一个'0'，步数加一
        while idx > 0 and s[idx] == '0':
            ret += 1
            idx -= 1
        # 处理至少还有一个'1'的情况，将第一个'1'转换为'0'后继续处理
        if idx > 0:
            ret += 2 # 这里包括了为最后一个'1'加1然后除以2的步骤
        # 继续处理剩余位
        while idx > 0:
            if s[idx] == '0':
                ret += 2 # 对于'0'，我们需要将其变为'1'（加1），然后除以2（再加1步）
            else:
                ret += 1 # 对于'1'，仅需要除以2（已经是'1'，加1后变为'10'，除以2回到'1'）
            idx -= 1 # 处理下一个更高位
        return ret

Explore

直接在二进制字符串上操作主要涉及字符遍历和条件判断，其时间复杂度为O(n)，其中n为字符串的长度。对于较大长度的字符串，这种方法效率相对较高，因为操作是线性的。然而，对于极大长度的字符串，由于每次操作仅减少一位或几位，可能导致需要多次遍历，这可能会导致效率问题。此外，字符串操作通常比直接数值计算有更高的时间和空间复杂度，尤其是在需要频繁修改字符串长度的场景中。

在代码中，对于'1'的处理是通过模拟二进制加法来实现的。具体来说，遇到'1'后会将其变为'0'，然后将进位加到下一个更高位。如果下一个更高位也是'1'，则继续进位，直到遇到'0'或超出字符串范围。这个过程实际上模拟了二进制中的加1操作。处理完加1后，执行除以2的操作，实际上就是将字符串中的每个字符向右移动一位，即把当前位的值改为下一位的值。

代码中确实对每个'0'都执行了加1操作后再除以2，这可能看起来有些冗余。然而，这是为了确保所有位均正确处理。在实际操作中，对于连续的'0'，每个'0'实际上都被视为需要进行进位的处理（即假设前面有一个'1'进位到当前'0'上），因此每个'0'都需要变成'1'，然后再除以2。虽然这增加了操作的数量，但保证了算法的正确性和简洁性。

在题解中，处理二进制字符串时跳过的'0'指的是二进制数的尾部'0'，即最低位的'0'。对于位于字符串首部的'0'（最高位的'0'），在二进制数中这些'0'实际上是没有任何意义的，因为它们不会影响二进制数的值。因此，在计算时不需要对首部的'0'进行操作，只需要从第一个非零位开始处理。这样做可以减少不必要的步骤，提高算法的效率。