当前位置：首页 > news >正文

DeepSeek LeetCode 3821. 二进制中恰好K个1的第N小整数 Python3实现

news 2026/8/6 10:56:52

看到你给出的函数签名 def nthSmallest(self, n: int, k: int) -> int，这是 LeetCode 3821 的标准接口。我来提供完整的、可直接提交的解法：

解法一：组合计数法（推荐）

```python
class Solution:
def nthSmallest(self, n: int, k: int) -> int:
"""
返回二进制表示中恰好有 k 个 1 的第 n 小的正整数
"""
# 计算组合数 C(a, b)
def comb(a: int, b: int) -> int:
if b < 0 or b > a:
return 0
if b > a - b:
b = a - b
res = 1
for i in range(1, b + 1):
res = res * (a - b + i) // i
return res

# 第 1 步：确定答案的二进制长度
length = k # 最短长度就是 k（全为1）
while True:
# 长度为 length 时，首位必须是1，从剩余 length-1 位中选 k-1 个位置放1
cnt = comb(length - 1, k - 1)
if n > cnt:
n -= cnt
length += 1
else:
break

# 第 2 步：在长度为 length 的数中找第 n 个
ans = 1 << (length - 1) # 最高位固定为1
remaining_ones = k - 1 # 还需要放的1的个数
pos = length - 2 # 从次高位开始（索引从0开始）

while remaining_ones > 0 and pos >= 0:
# 如果当前位置放0，后面 pos 个位置能组成的方案数
cnt = comb(pos, remaining_ones)

if n > cnt:
# 跳过所有当前位置为0的情况，当前位置放1
n -= cnt
ans |= (1 << pos)
remaining_ones -= 1

pos -= 1

return ans
```

解法二：位运算生成法

```python
class Solution:
def nthSmallest(self, n: int, k: int) -> int:
"""
使用位运算生成恰好 k 个 1 的二进制数
"""
# 最小的数：最低的 k 位为 1
num = (1 << k) - 1

# 生成第 n 个数（从第1个开始）
for _ in range(n - 1):
# 找到最右边的非拖尾 1（即最右边的 "01" 模式）
# 例如：011100 -> 100011
smallest = num & -num # 最低位的1
ripple = num + smallest # 将连续的1进位
ones = ((num ^ ripple) >> 2) // smallest # 计算需要补的1的个数
num = ripple | ones

return num
```

解法三：递归法（更直观）

```python
class Solution:
def nthSmallest(self, n: int, k: int) -> int:
"""
递归构造：固定首位，递归处理剩余位
"""
def comb(a: int, b: int) -> int:
if b < 0 or b > a:
return 0
if b > a - b:
b = a - b
res = 1
for i in range(1, b + 1):
res = res * (a - b + i) // i
return res

def build(length: int, k: int, n: int) -> int:
"""在长度为 length 的数中找第 n 个（首位已经固定为1）"""
if length == k: # 所有位都是1
return (1 << length) - 1
if k == 0: # 没有1了
return 0

# 次高位放0，后面 length-1 位中选 k 个
cnt_with_zero = comb(length - 1, k)

if n <= cnt_with_zero:
# 第 n 个在次高位为0的分支中
return build(length - 1, k, n)
else:
# 第 n 个在次高位为1的分支中
return (1 << (length - 1)) + build(length - 1, k - 1, n - cnt_with_zero)

# 确定长度
length = k
while True:
cnt = comb(length - 1, k - 1)
if n > cnt:
n -= cnt
length += 1
else:
break

return build(length, k, n)
```

测试验证

```python
if __name__ == "__main__":
sol = Solution()

# 测试用例
test_cases = [
(1, 2), # 3 (11)
(2, 2), # 5 (101)
(3, 2), # 6 (110)
(4, 2), # 9 (1001)
(5, 2), # 10 (1010)
(1, 1), # 1 (1)
(2, 1), # 2 (10)
(3, 1), # 4 (100)
(1, 3), # 7 (111)
(2, 3), # 11 (1011)
]

for n, k in test_cases:
result = sol.nthSmallest(n, k)
print(f"n={n}, k={k} -> {result} (binary: {bin(result)})")
```