《程序员面试金典（第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),我们没有申请额外的数据结构去存储数据。
总结
这道题对我来说，确实也不算是一道难题，但也没那么简单。如果我对动态规划与双指针掌握的更好了话，这道题或许会更加的简单。后序，我会更新双指针与动态规划的做法。
相关内容
热门资讯
8个月暴涨10倍，最火AI巨头...
光模块/CPO，又创历史新高了。再创新高，“易中天”大爆发今年以来，AI板块缔造了太多大牛股，而AI...
“祥源系”掌舵人俞发祥被刑拘！...
富豪沦为阶下囚，谁该为百亿兑付“埋单”？作者 | 于婞编辑丨高岩来源 | 野马财经一场涉及上百亿资金...
【视频】超级行动派：如何保卫财...
文 ｜ 清和 智本社社长社长，这种经济环境，该怎么降低风险？怎么配置资产？这几年，经常有社友问我这两...
持续亏损、第三次增资，深蓝汽车...
从成立至今，深蓝汽车经历了销量快速增长的喜悦，也面临着持续亏损的困境，其发展历程折射出传统车企向新能...
“00后”体育生用AI做外贸，...
当下入局做外贸，要想赚到第一桶金，靠的是一个无所不能的“超级个体”，还是分工明确的“系统战队”？两年...