反转数位

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

示例 1：

输入: num = 1775(110111011112)
输出: 8
示例 2：

输入: num = 7(01112)
输出: 4
通过次数5,796提交次数13,702

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-bits-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int reverseBits(int num) {
        String s = "";
        if (num > 0) s = "0" + Integer.toBinaryString(num);
        else s = Integer.toBinaryString(num);
        char[] arr = s.toCharArray();
        int len = arr.length;
        int[] dp = new int[arr.length];
        dp[0] = arr[0] == '1' ? 1 : 0;

        boolean flag = false;

        for (int i = 1; i < len; i++) {                     //正向计数
            if (arr[i] == '1') {
                dp[i] = dp[i - 1] + 1;
            } else {
                flag = true;
                dp[i] = 0;
            }
        }

        if (!flag) return arr.length;                       //如果没有0，直接返回二进制的长度

        int max = 0;

        for (int i = len - 2; i >= 0; i--) {                //反向计数
            if (arr[i + 1] == '1' && arr[i] == '1') {
                dp[i] = dp[i + 1];
            }
        }


        for (int i = 0; i < dp.length; i++) {               //碰到一个0，看左边的数量和右边的数量之和
            if (dp[i] == 0) {
                if (i + 1 < len && dp[i + 1] != 0) {        //只有右边
                    max = Math.max(max, dp[i + 1]);
                }
                if (i - 1 >= 0 && dp[i - 1] != 0) {         //只有左边
                    max = Math.max(max, dp[i - 1]);
                }

                if (i > 0 && i + 1 < len && dp[i - 1] != 0 && dp[i + 1] != 0) {
                    max = Math.max(max, dp[i - 1] + dp[i + 1]);
                }
            }
        }
        return max + 1;
    }
}

更优雅的写法

class Solution {
    public int reverseBits(int num) {
        String s = Integer.toBinaryString(num);
        String[] arr = s.split("0");
        if(arr.length<1) {
            return arr.length+1;
        }
        int max = arr[0].length();
        int res = max+1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1].length() + arr[i].length() > max) {
                max = arr[i - 1].length() + arr[i].length();
                res = max + 1;
            }
        }
        return Math.min(res,32);                                //全是1时保证是正确的
    }
}

作者：286029651
链接：https://leetcode-cn.com/problems/reverse-bits-lcci/solution/chao-jian-dan-fang-fa-by-286029651/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信