【LeetCode刷题记录】35.翻转数位

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

题目来源：LeetCode-翻转数位

给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。

示例 1：

输入: num = 1775(110111011112)

输出: 8

示例 2：

输入: num = 7(01112)

输出: 4

二、思路分析：

思路一：

1. 使用动态规划思想
2. 新建两个动态规划数组 current[]、reverse[]
3. current[i] 表示包含第i位的从num二进制低位至第i位连续1的最长长度
4. reverse[i] 表示包含第i位的从低位到第i位最多翻转1个0->1 的连续1的最长长度
5. 用num[i]表示整数num第i位的值
6. 当num[i]=1时，current[i] = current[i-1]+1,因为current[i-1]一定包含i-1位，也就是和第i位连续，所以前i-1的最大长度连上第i位的长度就等于current[i],同理reverse[i] = reverse[i-1]+1
7. num[i]=0时，连续中断，current[i]=0,而reverse[i]允许翻转1次，但是reverse[i]又必须包含第i位，也就是说只能翻转第i位，所以前面不能出现翻转，必须全是1，这个长度恰好就是current[i-1]，所以reverse[i] = current[i-1]+1
8. 遍历num所有位数，也就是32位后，reverse数组中的最大值就是答案。

状态方程：
current[i] = num[i]==1?current[i-1]+1:0
reverse[i] = num[i]==1?reverse[i-1]+1:current[i-1]+1

观察状态方程，我们发现current和reverse第i位只和第i-1位有关，所以可以把动态数组优化成两个变量current和reverse，同时更新最大值max并作为结果返回。

思路二：

1. 将数字转为二进制
2. 使用字符串的split方法以0进行分割，存储到字符串数组中
3. 相加两个相邻的元素的长度，最长的长度+1即可

三、AC 代码：

思路一：

    class Solution {
        public int reverseBits(int num) {
            int max = 0;
            int reverse = 0;
            int current = 0;
            for (int i = 0; i < 32; i++) {
                if ((num & 1) == 1) {
                    current++;
                    reverse++;
                } else {
                    reverse = current + 1;
                    current = 0;
                }
                if (reverse > max) {
                    max = reverse;
                }
                num >>= 1;
            }
            return max;
        }
    }
复制代码

思路二：

    class Solution {
        public int reverseBits(int num) {
            String split = "0";
            String binaryString = Integer.toBinaryString(num);
            String[] stingArray = binaryString.split(split);
            if (stingArray.length < 1) return stingArray.length + 1;
            int max = stingArray[0].length();
            int result = max + 1;
            for (int i = 1; i < stingArray.length; i++) {
                if (stingArray[i - 1].length() + stingArray[i].length() > max) {
                    max = stingArray[i - 1].length() + stingArray[i].length();
                    result = max + 1;
                }
            }
            return result;
        }
    }
复制代码