力扣每日一题 20260226

215 words

1 minute

力扣每日一题 20260226

2026-02-26

leetcode

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

观察可知，一旦发生进位，高位的 $1$ 都会变成 $0$ ，而 $0$ 都会变成 $1$ ，且二进制的位数也会因进位加一，导致多出一步除以 $2$ 的操作，所以设字符串中的 $1$ 的位置为 $pos$ ，字符串长度为 $n$ 。

如果 $pos=0$ 说明没有发生进位，则答案就是 $n-1$ ，如果 $pos>0$ 说明发生了进位，那么答案就是 $n-1$ 加上 $1$ 到 $pos$ 之间 $0$ 的个数，再加两步（ $pos$ 这步的加一操作和高位除以 $2$ 的操作）。

代码：

1
class Solution {
2
public:
3
    int numSteps(string s) {
4
        int pos = 0, ans = s.size() - 1;
5
        for (int i = ans; i >= 0; i--) {
6
            if (s[i] == '1') {
7
                pos = i;
8
                break;
9
            }
10
        }
11
        if (pos > 0) {
12
            ans += count(s.begin() + 1, s.begin() + pos, '0') + 2;
13
        }
14
        return ans;
15
    }
16
};