LeetCode 1404：二进制字符串减至1的最少步骤解析-平芜编程栈

1. 问题背景与理解

今天遇到一道挺有意思的LeetCode题目（编号1404），要求计算将一个二进制字符串表示的数值减到1所需的最少步骤数。题目看似简单，但实际处理起来有不少细节需要注意。我花了些时间研究，最终实现了耗时100ms的解法，这里把解题思路和优化过程记录下来。

这道题的规则是这样的：如果数字是偶数，直接除以2；如果是奇数，则加1。每次操作算一步，直到数字变为1为止。例如二进制"1101"表示13，操作步骤是13→14→7→8→4→2→1，共6步。

2. 基础解法分析

2.1 字符串模拟法

最直观的思路是将二进制字符串转为十进制数，然后按照规则模拟操作过程：

def numSteps(s: str) -> int: num = int(s, 2) steps = 0 while num != 1: if num % 2 == 0: num //= 2 else: num += 1 steps += 1 return steps

但这种方法存在明显问题：当输入字符串很长时（比如长度500位），转换后的十进制数会非常大，导致计算效率低下甚至溢出。

2.2 直接操作二进制字符串

更合理的做法是直接在二进制字符串上进行操作。这需要实现以下功能：

判断奇偶（看最后一位）
除以2（右移一位）
加1（需要考虑进位）

def add_one(bin_str): carry = 1 res = [] for bit in reversed(bin_str): if bit == '1' and carry == 1: res.append('0') carry = 1 elif bit == '0' and carry == 1: res.append('1') carry = 0 else: res.append(bit) if carry: res.append('1') return ''.join(reversed(res)) def numSteps(s: str) -> int: steps = 0 while s != '1': if s[-1] == '0': s = s[:-1] # 相当于除以2 else: s = add_one(s) steps += 1 return steps

3. 优化思路与实现

3.1 观察操作规律

通过分析操作过程，可以发现：

遇到偶数时（末位0），直接右移，步数+1
遇到奇数时（末位1），加1后通常会连续产生多个0，可以一次性处理

例如："1011"（11）→加1→"1100"→可以连续右移2次

3.2 优化后的算法

基于这个观察，可以改进算法：

从右向左扫描字符串
遇到0时计数连续的0
遇到1时处理连续的1并计算进位

def numSteps(s: str) -> int: steps = 0 s = list(s) while len(s) > 1: if s[-1] == '0': s.pop() # 除以2 steps += 1 else: # 处理连续的1 i = len(s) - 1 while i >= 0 and s[i] == '1': s[i] = '0' i -= 1 if i >= 0: s[i] = '1' else: s.insert(0, '1') steps += 1 return steps

3.3 进一步优化

可以合并一些操作，减少不必要的循环：

def numSteps(s: str) -> int: steps = 0 s = list(s) while len(s) > 1: if s[-1] == '0': s.pop() steps += 1 else: # 找到最右边的0 i = len(s) - 1 while i >= 0 and s[i] == '1': i -= 1 if i < 0: s = ['1'] + ['0'] * len(s) steps += len(s) break s[i] = '1' steps += (len(s) - i) s = s[:i+1] return steps

4. 性能分析与实测

4.1 时间复杂度分析

优化后的算法时间复杂度为O(n)，其中n是二进制字符串的长度。每个字符最多被处理两次（一次置0，一次置1）。

4.2 实际测试结果

使用LeetCode的测试用例进行验证：

短字符串（<10位）：<1ms
长字符串（500位）：约100ms
极端情况（全1）：处理最快，因为可以一步到位

5. 常见问题与调试技巧

5.1 边界条件处理

特别注意以下情况：

输入已经是"1"：直接返回0
全1的情况：加1后变成100...0，可以一步处理
中间有连续多个1时的进位处理

5.2 调试建议

打印中间步骤的二进制字符串
使用小例子手动验证（如"1101"）
特别注意进位时的索引处理

6. 其他语言实现思路

6.1 C++实现

可以使用bitset或直接操作字符串：

int numSteps(string s) { int steps = 0; while (s != "1") { if (s.back() == '0') { s.pop_back(); } else { int i = s.size() - 1; while (i >= 0 && s[i] == '1') { s[i] = '0'; i--; } if (i >= 0) { s[i] = '1'; } else { s = "1" + s; } } steps++; } return steps; }

6.2 Java实现

类似思路，注意String的不可变性：

public int numSteps(String s) { int steps = 0; StringBuilder sb = new StringBuilder(s); while (sb.length() > 1) { if (sb.charAt(sb.length()-1) == '0') { sb.deleteCharAt(sb.length()-1); } else { int i = sb.length() - 1; while (i >= 0 && sb.charAt(i) == '1') { sb.setCharAt(i, '0'); i--; } if (i >= 0) { sb.setCharAt(i, '1'); } else { sb.insert(0, '1'); } } steps++; } return steps; }