力扣面试题 05.03. 翻转数位（前、后缀和）

Problem: 面试题 05.03. 翻转数位

题目描述

思路及解法

1.将十进制数转换为二进制数（每次按位与1求与，并且右移）；
2.依次求取二进制数中每一位的前缀1的数量和，和后缀1的数量和（代码实现时，可以先用一个变量记录，当当前位为1时将该变量加一，否则置为0）
3.依次循环查询每一个二进制数的前后缀1的和再加上1，并从中取出最大值

复杂度

时间复杂度:

$O(1)$

空间复杂度:

$O(1)$

Code

class Solution {
   
public:
    /**
     * Prefix and suffix sum
     * 
     * @param num Given array
     * @return int
     */
    int reverseBits(int num) {
   
        if (num == 0) {
   
            return 1;
        }
        vector<int> nums(32);
        for (int i = 0; i < 32; ++i) {
   
            nums[i] = (num & 1);
            num >>= 1;
        }
        vector<int> leftCounts(32);
        int count = 0;
        for (int i = 0; i < 32; ++i) {
   
            leftCounts[i] = count;
            if (nums[i] == 1) {
   
                count++;
            } else {
   
                count = 0;
            }
        }
        count = 0;
        vector<int> rightCount(32);
        for (int i = 31; i >= 0; --i) {
   
            rightCount[i] = count;
            if (nums[i] == 1) {
   
                count++;
            } else {
   
                count = 0;
            }
        }
        int maxOne = leftCounts[0] + rightCount[0] + 1;
        for (int i = 1; i < 32; ++i) {
   
            if ((leftCounts[i] + rightCount[i] + 1) > maxOne) {
   
                maxOne = leftCounts[i] + rightCount[i] + 1;
            }
        }
        return maxOne;
    }
};