《程序员面试金典（第6版）》面试题 05.03. 翻转数位（不断更新...还有双指针付法，与动态规划）
创始人
2025-05-31 15:51:04
题目描述
给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
示例 1：
- 输入: num = 1775(110111011112)
输出: 8
示例 2：
- 输入: num = 7(01112)
输出: 4
解题思路与代码
这道题的解法涉及到位运算，如果对位运算不太了解的话，请看我这篇文章扫除盲点：教你理解位运算符。
暴力破解
暴力破解是指我们使用双层for循环去解题。
我们第一层for循环去判断num的每一位是否为1,1有1的逻辑，0有0的逻辑。
第二层for循环就是去记录从1开始的，连续为1的数量。
这种方式的缺点在于，中间的逻辑很有可能会写错，反复检查会很麻烦。
具体实现看代码：
class Solution {
public:int reverseBits(int num) {bool flag = true; //标准位，类似与开关，第一次出现0，变成false，第二次出现0，变成trueint maxLength = 0; //记录最大长度int count = 0;//记录1的数量for(int i = 0; i < 32; ++i){bool bit = num & (1<//为1的逻辑flag = true;count = 0;for(int j = i; j < 32; ++j){bool bit_2 = num & (1<count+=1;if(count > maxLength) maxLength = count;}else if(bit_2 == 0 && flag){count += 1;if(count > maxLength) maxLength = count;flag = false;}else if(bit_2 == 1 && !flag){count += 1;if(count > maxLength) maxLength = count;}else break;}}if(bit == 0){num |= (1<bool bit_2 = num & (1<count += 1;if(count > maxLength) maxLength = count;}else if(bit_2 == 0){num &= ~(1< 
复杂度分析
时间复杂度：O(n!) ，n第一开始是32，然后会随着i的增大而减小。
空间复杂度：O(1),我们没有申请额外的数据结构去存储数据。
总结
这道题对我来说，确实也不算是一道难题，但也没那么简单。如果我对动态规划与双指针掌握的更好了话，这道题或许会更加的简单。后序，我会更新双指针与动态规划的做法。
相关内容
热门资讯
实测分享.“[新二号]究竟有挂...
您好：【新二号】这款游戏可以开挂，确实是有挂的，需要了解加客服微信【4579337】很多玩家在这款游...
推荐一款.“[无极大厅]怎么开...
您好：【无极大厅】这款游戏可以开挂，确实是有挂的，需要了解加客服微信【4579337】很多玩家在这款...
重大发现.,728土豪版.辅助...
您好：,728土豪版这款游戏可以开挂，确实是有挂的，需要了解加客服微信【8435338】很多玩家在这...
玩家实测“七千游戏透视挂辅助器...
您好：七千游戏这款游戏可以开挂，确实是有挂的，需要软件加微信【4770480】，很多玩家在七千游戏这...
[第一财经]“功夫川麻究竟是不...
亲:功夫川麻这款游戏是可以开挂的，确实是有挂的,添加客服【8487422】很多玩家在这款游戏中怀疑是...