1404.将二进制表示减到 1 的步骤数：模拟+高精度模拟玩玩(运算符重载)

【LetMeFly】1404.将二进制表示减到 1 的步骤数：模拟+高精度模拟玩玩(运算符重载)

力扣题目链接：https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/

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

解题方法：模拟

Python直接转int，C++使用字符串双端队列代替

• 时间复杂度$O(len(s))$
• 空间复杂度$O(\log s)$或$O(len(s))$

AC代码

C++

/*
 * @LastEditTime: 2026-02-27 22:29:56
 */
class LetsNum {
private:
    // 低位->高位
    deque<char> num;
public:
    // From binary string
    LetsNum(string& s) {
        for (char c : s) {
            *this <<= 1;
            *this += c;
        }
    }

    LetsNum& operator++(int) {
        int carry = 1;
        for (deque<char>::iterator it = num.begin(); it != num.end(); it++) {
            carry += *it - '0';
            *it = carry % 10 + '0';
            carry /= 10;
        }
        if (carry) {
            num.push_back(carry + '0');
        }
        return *this;
    }

    // only 0/1 supported
    LetsNum& operator+=(const int& n) {
        if (!n) {
            return *this;
        }
        (*this)++;
        return *this;
    }

    // only 0/1 supported
    LetsNum& operator+=(const char& c) {
        *this += c - '0';
        return *this;
    }

    // only <<1 supported
    LetsNum& operator<<=(const int&) {
        int carry = 0;
        for (deque<char>::iterator it = num.begin(); it != num.end(); it++) {
            carry += (*it - '0') * 2;
            *it = carry % 10 + '0';
            carry /= 10;
        }
        if (carry) {
            num.push_back(carry + '0');
        }
        return *this;
    }

    // only >>1 supported
    LetsNum& operator>>=(const int&) {
        int mod = 0;
        for (deque<char>::reverse_iterator it = num.rbegin(); it != num.rend(); it++) {
            mod = mod * 10 + (*it - '0');
            *it = mod / 2 + '0';
            mod %= 2;
        }
        if (*num.rbegin() == '0') {
            num.pop_back();
        }
        return *this;
    }

    // only 1 supported
    bool operator!=(const int&) {
        return num.size() != 1 || *num.begin() != '1';
    }

    bool isOdd() {
        return (*num.begin() - '0') % 2;
    }

    void print() {
        for (deque<char>::reverse_iterator it = num.rbegin(); it != num.rend(); it++) {
            putchar(*it);
        }
        puts("");
    }
};

class Solution {
public:
    int numSteps(string s) {
        LetsNum num(s);
        int ans = 0;
        while (num != 1) {
            if (num.isOdd()) {
                num += 1;
            } else {
                num >>= 1;
            }
            ans++;
        }
        return ans;
    }
};

#if defined(_WIN32) || defined(__APPLE__)
/*
1101
*/
int main() {
    string s;
    while (cin >> s) {
        Solution sol;
        cout << sol.numSteps(s) << endl;
    }
    return 0;
}
#endif

Python

'''
LastEditTime: 2026-02-26 23:59:25
'''
"""
1101
1110
111
1000
100
10
1
"""
class Solution:
    def numSteps(self, s: str) -> int:
        a = int(s, 2)
        ans = 0
        while a != 1:
            if a % 2:
                a += 1
            else:
                a //= 2
            ans += 1
            # print(a)
        return ans

# print(Solution.numSteps('', '1101'))

C++完胜！(bushi)

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源