分类： leetcode

目标

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

示例 1：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32

示例 2：

输入：n = "82734"
输出：8

示例 3：

输入：n = "27346209830709182346"
输出：9

说明：

• 1 <= n.length <= 10^5
• n 仅由数字组成
• n 不含任何前导零并总是表示正整数

思路

返回整数 n 中的最大数字即可。

代码

/**
 * @date 2026-04-17 16:06
 */
public class MinPartitions1689 {

    public int minPartitions(String n) {
        int res = 0;
        char[] chars = n.toCharArray();
        for (char c : chars) {
            res = Math.max(res, c - '0');
        }
        return res;
    }
}

性能

目标

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 10^9 + 7 取余的结果。

示例 1：

输入：n = 1
输出：1
解释：二进制的 "1" 对应着十进制的 1 。

示例 2：

输入：n = 3
输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。

示例 3：

输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后，结果为 505379714 。

说明：

• 1 <= n <= 10^5

思路

拼接 1 ~ n 的二进制表示，将结果对应的十进制数对 10^9 + 7 取模。

遍历 1 ~ n 模拟拼接过程，将之前拼接的数字左移当前数字的 bitLength 并对 mod 取模。拼接 a b c 可以视为 (a * 2^bitLength(b) + b) * 2^bitLength(c) + c，可以先对括号内的运算取模，即 (a << bitLength(b)) + b ) % mod。

代码

/**
 * @date 2026-02-28 9:18
 */
public class ConcatenatedBinary1680 {

    public int concatenatedBinary(int n) {
        int mod = 1000000007;
        long res = 0L;
        for (int i = 1; i <= n; i++) {
            int bl = 32 - Integer.numberOfLeadingZeros(i);
            res = ((res << bl) + i) % mod;
        }
        return (int) res;
    }

}

性能

目标

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：

如果当前数字为偶数，则将其除以 2 。

如果当前数字为奇数，则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

示例 1：

输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14 
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7  是奇数，加 1 得到 8
Step 4) 8  是偶数，除 2 得到 4  
Step 5) 4  是偶数，除 2 得到 2 
Step 6) 2  是偶数，除 2 得到 1  

示例 2：

输入：s = "10"
输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1 

示例 3：

输入：s = "1"
输出：0

说明：

• 1 <= s.length <= 500
• s 由字符 '0' 或 '1' 组成。
• s[0] == '1'

思路

有一个二进制表示的数字，如果当前是偶数，可以将数字除以 2，即右移；如果当前是奇数，将数字加 1。求将数字变为 1 需要的操作数。

根据题意模拟，使用变量 carry 保存进位，从右向左遍历，判断最后一位数字 d 与 carry 相加后的奇偶性，即 sum = d + carry。如果 sum 是偶数（0 或者 2），右移后这一位消失，只需考虑 carry = sum / 2；如果 sum 是奇数，加一后进位 carry = 1，此时当前数字变为偶数，可以将这两个操作合并。

代码

/**
 * @date 2026-02-26 8:51
 */
public class NumSteps1404 {

    public int numSteps(String s) {
        int res = 0;
        int n = s.length();
        char[] chars = s.toCharArray();
        int carry = 0;
        for (int i = n - 1; i > 0; i--) {
            int d = chars[i] - '0';
            int sum = d + carry;
            if (sum % 2 == 0) {
                carry = sum / 2;
                res++;
            } else {
                carry = 1;
                res += 2;
            }
        }
        return res + carry;
    }

}

性能

目标

给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 3：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

说明：

• 1 <= s.length <= 5 * 10^5
• s[i] 不是 '0' 就是 '1'
• 1 <= k <= 20

思路

检查一个二进制字符串是否包含所有长度为 k 的二进制子串。

长度为 k 的二进制子串的个数有 2^k 个，将子串视为二进制数字，使用长度为 k 的滑动窗口，记录窗口内子串表示的数字，判断是否所有数字都出现过即可。将左边界移出窗口需要将左边第一位置零 num = (num & (1 << (k - 1))) ^ num。先提取左边第一位，其余位均为 0，然后与 num 异或即可。

代码

/**
 * @date 2026-02-24 11:31
 */
public class HasAllCodes1461 {

    public boolean hasAllCodes(String s, int k) {
        if (k > 18) {
            return false;
        }
        int n = 1 << k;
        boolean[] visited = new boolean[n];
        int num = 0;
        char[] chars = s.toCharArray();
        int l = 0;
        for (int r = 0; r < chars.length; r++) {
            num = (num << 1) | (chars[r] - '0');
            if (r - l + 1 == k) {
                visited[num] = true;
                num = (num & (1 << (k - 1))) ^ num;
                l++;
            }
        }
        for (boolean b : visited) {
            if (!b) {
                return false;
            }
        }
        return true;
    }

}

性能