LeetCode 每日一题笔记

0. 前言

• 日期：2025.10.29
• 题目：3370. 仅含置位位的最小整数
• 难度：简单
• 标签：二进制、位运算

1. 题目理解

问题描述：
找到大于等于给定整数 n 的最小整数，要求该整数的二进制表示中所有位均为置位位（即二进制全为 1，如 3 是 11，7 是 111）。

示例：

• 输入：n = 4 → 输出：7（二进制 111，是大于4的最小全1数）
• 输入：n = 7 → 输出：7（本身就是全1数）
• 输入：n = 1 → 输出：1（二进制 1）

2. 解题思路

核心观察

• 「仅含置位位的数」本质是 2^k - 1（k 为正整数），例如：
  • k=1 → 2^1 - 1 = 1（二进制 1）
  • k=2 → 2^2 - 1 = 3（二进制 11）
  • k=3 → 2^3 - 1 = 7（二进制 111）
• 目标是找到 最小的 2^k - 1 且满足 2^k - 1 ≥ n。

算法步骤

1. 预计算或动态生成 2^k - 1 形式的数（全1数）。
2. 遍历这些数，找到第一个大于等于 n 的值并返回。

3. 代码实现

class lc3370.Solution {
    public int smallestNumber(int n) {
        // 特殊情况：n=0时，最小全1数是0（2^0 - 1 = 0）
        if (n == 0) {
            return 0;
        }
        
        // 动态计算全1数：2^1-1, 2^2-1, ... 直到找到满足条件的数
        int k = 1;
        while (true) {
            int fullOne = (1 << k) - 1; // 等价于 2^k - 1（位运算更高效）
            if (fullOne >= n) {
                return fullOne;
            }
            k++;
        }
    }
}

4. 代码优化说明

• 简化计算：用位运算 (1 << k) - 1 替代循环乘法，直接生成 2^k - 1，效率更高。
• 边界处理：补充 n=0 的特殊情况（原代码会返回1，不符合预期）。
• 动态扩展：去掉固定长度数组，通过循环动态计算，可支持更大的 n（如 n=10^9 时仍能正确返回 2^30 - 1）。

5. 复杂度分析

• 时间复杂度：O(log n)
  因为 2^k 增长极快，找到满足条件的 k 最多需要 log2(n) 次循环。
• 空间复杂度：O(1)
  仅使用常数个变量，无额外空间消耗。

6. 总结

• 本题的核心是理解「全1数」的数学规律（2^k - 1），位运算在此类问题中能大幅简化计算。
• 遇到二进制相关题目时，可优先考虑 2的幂、位与/或/异或 等特性，往往能找到简洁解法。