分类： leetcode

目标

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：

输入：s = "00110011"
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

说明：

• 1 <= s.length <= 10^5
• s[i] 为 '0' 或 '1'

思路

统计二进制字符串 s 中满足条件的子串个数。子串需满足 0 与 1 的个数相等，且子串中所有 0 都是相邻且连续的（由于数量相同，子串中所有的 1 也是相邻且连续的），即 0 与 1 都是成组连续的。

00011 满足条件的子串个数为 min(3, 2)，可以分组循环字符串，记录前一组的个数，累加二者最小值即可。

代码

/**
 * @date 2026-02-24 16:14
 */
public class CountBinarySubstrings696 {

    public int countBinarySubstrings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int preCnt = 0;
        int i = 0;
        int res = 0;
        while (i < n) {
            int start = i;
            while (i < n && chars[start] == chars[i]) {
                i++;
            }
            int cnt = i - start;
            res += Math.min(preCnt, cnt);
            preCnt = cnt;
        }
        return res;
    }

}

性能

目标

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111.

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011.

说明：

• 1 <= n <= 2^31 - 1

思路

判断给定 num 的二进制表示是否是 0、1 交替出现的。

将 num 右移 1 位得到 mask，如果是 0、1 交替出现，那么 (mask & num) == 0 && (mask | num) == (1L << l) - 1，其中 l 是 num 的二进制长度。判断 x 是否全是 1，也可以使用 ((x + 1) & x) == 0。

代码

/**
 * @date 2026-02-24 16:40
 */
public class HasAlternatingBits693 {

    public boolean hasAlternatingBits_v1(int n) {
        int mask = n >> 1;
        int or = mask | n;
        return (mask & n) == 0 && ((or + 1) & or) == 0;
    }

}

性能

目标

颠倒给定的 32 位有符号整数的二进制位。

示例 1：

输入：n = 43261596
输出：964176192
解释：
整数       二进制
43261596  00000010100101000001111010011100
964176192 00111001011110000010100101000000

示例 2：

输入：n = 2147483644
输出：1073741822
解释：
整数        二进制
2147483644 01111111111111111111111111111100
1073741822 00111111111111111111111111111110

说明：

• 0 <= n <= 2^31 - 2
• n 为偶数

进阶: 如果多次调用这个函数，你将如何优化你的算法？

思路

颠倒 32 位有符号整数的二进制表示，返回其表示的数字。

题目限定 n 是正偶数，颠倒之后的最高位为 0，仍是非负数。模拟颠倒的过程，提前记录前导零的个数 lz，最后将结果左移 lz。

代码

/**
 * @date 2024-06-08 22:28
 */
public class ReverseBits190 {

    public int reverseBits_new(int n) {
        int res = 0;
        int lz = Integer.numberOfLeadingZeros(n);
        while (n > 0) {
            int b = n & 1;
            res = (res << 1) | b;
            n >>= 1;
        }
        return res << lz;
    }

}

性能

目标

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

说明：

• 1 <= a.length, b.length <= 10^4
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

思路

对二进制字符串求和，将结果以二进制字符串的形式返回。

代码

/**
 * @date 2024-05-25 21:50
 */
public class AddBinary67 {

    public String addBinary_new(String a, String b) {
        int al = a.length();
        int bl = b.length();
        int n = Math.max(a.length(), b.length());
        int i = 1;
        StringBuilder sb = new StringBuilder();
        // 进位
        int j = 0;
        while (i <= n) {
            int av = 0;
            // 计算从右侧起第 i 个位置的下标
            int ai = al - i;
            if (ai >= 0) {
                av = a.charAt(ai) - '0';
            }
            int bv = 0;
            int bi = bl - i;
            if (bi >= 0) {
                bv = b.charAt(bi) - '0';
            }
            int sum = av + bv + j;
            if (sum > 1) {
                sb.append(sum - 2);
                j = 1;
            } else {
                sb.append(sum);
                j = 0;
            }
            i++;
        }
        if (j == 1) {
            sb.append(j);
        }
        return sb.reverse().toString();
    }

}

性能