Medium

题目描述

给定一个整数的二进制表示字符串 s，返回按照以下规则将其减少到 1 所需的步数：

  • 如果当前数字是偶数，你必须将其除以 2。
  • 如果当前数字是奇数，你必须给它加 1。

保证对于所有测试用例都能达到 1。

示例 1：

输入：s = "1101"
输出：6
解释："1101" 对应十进制数字 13。
步骤 1) 13 是奇数，加 1 得到 14。
步骤 2) 14 是偶数，除以 2 得到 7。
步骤 3) 7 是奇数，加 1 得到 8。
步骤 4) 8 是偶数，除以 2 得到 4。
步骤 5) 4 是偶数，除以 2 得到 2。
步骤 6) 2 是偶数，除以 2 得到 1。

示例 2：

输入：s = "10"
输出：1
解释："10" 对应十进制数字 2。
步骤 1) 2 是偶数，除以 2 得到 1。

示例 3：

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

约束条件：

  • 1 <= s.length <= 500
  • s 仅由字符 ‘0’ 或 ‘1’ 组成
  • s[0] == ‘1’

解题思路

这道题有两种主要解法：模拟法和优化计数法。

模拟法：直接按照题目描述的规则进行操作。如果最后一位是 ‘0’，说明是偶数，相当于右移一位（去掉最后的 ‘0’）；如果最后一位是 ‘1’，说明是奇数，需要加 1。二进制加 1 的操作相当于从右到左找到第一个 ‘0’，将其变为 ‘1’，并将其右边所有的 ‘1’ 变为 ‘0’。

优化计数法（推荐）：我们可以观察到规律，从右到左扫描二进制串：

  • 遇到 ‘0’：只需要一步除以2操作（右移）
  • 遇到连续的 ‘1’：第一个 ‘1’ 需要加1操作，后续的 ‘1’ 都会因为进位而变成 ‘0’，每个都需要一步除以2操作，最后进位产生的 ‘1’ 又需要一步加1操作

具体来说，遇到连续的k个 ‘1’ 时，总共需要 k+1 步：1步加1操作 + k步除以2操作。

这种方法避免了实际的字符串操作，只需要计数即可，效率更高。

代码实现

class Solution {
public:
    int numSteps(string s) {
        int steps = 0;
        int carry = 0;
        
        // 从右到左遍历，跳过最后一位（因为目标是到达"1"）
        for (int i = s.length() - 1; i > 0; i--) {
            int digit = (s[i] - '0') + carry;
            
            if (digit % 2 == 1) {
                // 奇数：需要加1操作，然后除以2
                steps += 2;
                carry = 1;
            } else {
                // 偶数：只需要除以2操作
                steps += 1;
                carry = 0;
            }
        }
        
        // 如果最后还有进位，需要额外的步骤
        return steps + carry;
    }
};

class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        carry = 0
        
        # 从右到左遍历，跳过最后一位
        for i in range(len(s) - 1, 0, -1):
            digit = int(s[i]) + carry
            
            if digit % 2 == 1:
                # 奇数：需要加1操作，然后除以2
                steps += 2
                carry = 1
            else:
                # 偶数：只需要除以2操作
                steps += 1
                carry = 0
        
        # 如果最后还有进位，需要额外的步骤
        return steps + carry

public class Solution {
    public int NumSteps(string s) {
        int steps = 0;
        int carry = 0;
        
        // 从右到左遍历，跳过最后一位
        for (int i = s.Length - 1; i > 0; i--) {
            int digit = (s[i] - '0') + carry;
            
            if (digit % 2 == 1) {
                // 奇数：需要加1操作，然后除以2
                steps += 2;
                carry = 1;
            } else {
                // 偶数：只需要除以2操作
                steps += 1;
                carry = 0;
            }
        }
        
        // 如果最后还有进位，需要额外的步骤
        return steps + carry;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numSteps = function(s) {
    let steps = 0;
    let carry = 0;
    
    for (let i = s.length - 1; i > 0; i--) {
        let bit = parseInt(s[i]) + carry;
        
        if (bit % 2 === 1) {
            steps += 2;
            carry = 1;
        } else {
            steps += 1;
        }
    }
    
    return steps + carry;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，n为字符串长度
空间复杂度O(1)只使用了常数个额外变量

相关题目