当前位置：首页 > news >正文

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

news 2026/3/27 4:29:09

【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 ( l e n ( s ) ) O(len(s))O(len(s))
空间复杂度O ( log ⁡ s ) O(\log s)O(logs)或O ( l e n ( s ) ) O(len(s))O(len(s))

AC代码

C++

/* * @LastEditTime: 2026-02-27 22:29:56 */classLetsNum{private:// 低位->高位deque<char>num;public:// From binary stringLetsNum(string&s){for(charc:s){*this<<=1;*this+=c;}}LetsNum&operator++(int){intcarry=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 supportedLetsNum&operator+=(constint&n){if(!n){return*this;}(*this)++;return*this;}// only 0/1 supportedLetsNum&operator+=(constchar&c){*this+=c-'0';return*this;}// only <<1 supportedLetsNum&operator<<=(constint&){intcarry=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 supportedLetsNum&operator>>=(constint&){intmod=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 supportedbooloperator!=(constint&){returnnum.size()!=1||*num.begin()!='1';}boolisOdd(){return(*num.begin()-'0')%2;}voidprint(){for(deque<char>::reverse_iterator it=num.rbegin();it!=num.rend();it++){putchar(*it);}puts("");}};classSolution{public:intnumSteps(string s){LetsNumnum(s);intans=0;while(num!=1){if(num.isOdd()){num+=1;}else{num>>=1;}ans++;}returnans;}};#ifdefined(_WIN32)||defined(__APPLE__)/* 1101 */intmain(){string s;while(cin>>s){Solution sol;cout<<sol.numSteps(s)<<endl;}return0;}#endif

Python

''' LastEditTime: 2026-02-26 23:59:25 '''""" 1101 1110 111 1000 100 10 1 """classSolution:defnumSteps(self,s:str)->int:a=int(s,2)ans=0whilea!=1:ifa%2:a+=1else:a//=2ans+=1# print(a)returnans# print(Solution.numSteps('', '1101'))