leetcode 2026-02-26 每日一练 - 将二进制表示减到 1 的步骤数

题目描述

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

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

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

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

解题思路

核心观察

对于二进制字符串：

  • 偶数：最低位是 0，除以 2 相当于去掉最后一位
  • 奇数：最低位是 1，加 1 会产生进位，需要找到第一个 0 并将其变为 1，之前的所有 1 都变为 0

方法一：直接模拟

从后往前遍历二进制字符串：

  1. 如果最低位是 0，直接去掉（相当于除以 2）
  2. 如果最低位是 1，执行加 1 操作：
    • 从后往前找到第一个 0
    • 将这个 0 变为 1
    • 将这个 0 之后的所有 1 都变为 0
    • 如果没有找到 0（全是 1），则在最前面添加一个 1

代码实现

方法一：直接模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func numSteps(s string) int {
    steps := 0
    bits := []byte(s)

    for len(bits) > 1 {
        lastBit := bits[len(bits) - 1]

        if lastBit == '0' {
            // 偶数：除以2，去掉最后一位
            bits = bits[:len(bits)-1]
            steps++
        } else {
            // 奇数：加1
            steps++
            i := len(bits) - 1
            // 找到第一个0，将其变为1，之前的1都变为0
            for i >= 0 && bits[i] == '1' {
                bits[i] = '0'
                i--
            }
            
            if i >= 0 {
                bits[i] = '1'
            } else {
                // 全是1，需要在最前面添加1
                bits = append([]byte{'1'}, bits...)
            }
        }
    }
    return steps
}

方法二：进位优化（推荐）

通过观察可以发现：

  • 基础步骤：长度为 n 的二进制数，至少需要 n-1 次「除以 2」操作
  • 额外步骤：当某一位是 1（且有进位）时，需要额外执行「加 1」操作
1
2
3
4
5
6
7
8
9
10
11
func numSteps(s string) int {
	ans := len(s) - 1 // 除了最高位，其余每一位都要执行一次「除以 2」
	carry := 0
	for i := len(s) - 1; i > 0; i-- {
		sum := int(s[i]-'0') + carry
		ans += sum % 2 // 如果 s[i] 变成 1，需要执行「加上 1」
		carry = (sum + sum%2) / 2
	}
	// 如果在最高位还有进位，由于 1 + 1 = 10，需要再执行一次「除以 2」
	return ans + carry
}

核心细节

方法一

  1. 切片操作：bits[:len(bits)-1] 去掉最后一位
  2. 进位处理：从后往前遍历，将连续的 1 都变为 0
  3. 边界情况：全是 1 时需要在最前面添加 1

方法二

  1. 基础步骤：len(s) - 1 表示除了最高位，每一位都要除以 2
  2. 额外步骤：sum % 2 表示当前位变成 1 后需要加 1
  3. 进位计算：(sum + sum%2) / 2 计算下一位的进位

复杂度分析

方法一

  • 时间复杂度：O(n²)，最坏情况下每次加 1 都需要遍历整个字符串
  • 空间复杂度：O(n)，需要存储字节数组

方法二

  • 时间复杂度：O(n)，只需遍历一次字符串
  • 空间复杂度：O(1)，只使用常数额外空间

总结

这道题有两种解法：

  • 方法一：直接模拟，思路清晰但效率较低
  • 方法二：进位优化，通过数学推导简化计算，效率更高

关键理解：

  • 偶数除以 2 = 去掉最低位 0

  • 奇数加 1 = 产生进位，影响后续计算

  • 总步骤 = 基础步骤 + 额外步骤 + 最高位进位处理

  • 同样的，灵神给的模拟代码，思路一样，但是代码更简洁。

  • 基础步骤：一个长度为n的二进制数（高位在前），要把除最高位外的所有位 “消掉”，至少需要n-1次「除以 2」操作（比如1101（4 位），基础步骤是 3 次，对应把最后 3 位依次除 2）；

  • 额外步骤：当某一位是1（且有进位）时，需要额外执行「加 1」操作，而「加 1」会产生新的进位，影响前一位的计算；

  • 最终总步骤 = 基础步骤 + 额外步骤 + 最高位进位的额外处理。

1
2
3
4
5
6
7
8
9
10
11
func numSteps(s string) int {
	ans := len(s) - 1 // 除了最高位，其余每一位都要执行一次「除以 2」
	carry := 0
	for i := len(s) - 1; i > 0; i-- {
		sum := int(s[i]-'0') + carry
		ans += sum % 2 // 如果 s[i] 变成 1，需要执行「加上 1」
		carry = (sum + sum%2) / 2
	}
	// 如果在最高位还有进位，由于 1 + 1 = 10，需要再执行一次「除以 2」
	return ans + carry
}