QR 特色高频
🔖 #470 · Implement Rand10 Using Rand7 ★
难度: Medium | 标签: Probability, Rejection Sampling | 链接: https://leetcode.com/problems/implement-rand10-using-rand7/
题目描述
给定
rand7()，实现 rand10()。解题思路
拒绝采样 (Rejection Sampling)：
- 调用两次 rand7，构造均匀分布 [1,49]
- 保留 [1,40] 范围（是 10 的倍数），拒绝 41-49
答案代码
def rand10(): while True: row = rand7() col = rand7() idx = (row - 1) * 7 + col # [1, 49] if idx <= 40: return 1 + (idx - 1) % 10
扩展总结
- QR 必考，考察概率理解和拒绝采样思想
- 可优化：用拒绝的剩余构造第三次 rand7 调用以减少期望调用次数
- 通用思路：用 randM 实现 randN，确保覆盖并均匀
🔖 #398 · Random Pick Index ★
难度: Medium | 标签: Reservoir Sampling | 链接: https://leetcode.com/problems/random-pick-index/
题目描述
给定一个可能包含重复元素的整数数组，对给定的 target，随机返回 target 的一个下标。
解题思路
水库抽样 (Reservoir Sampling)：每遇到第 k 个目标，以 1/k 的概率替换结果。
答案代码
import random class Solution: def __init__(self, nums): self.nums = nums def pick(self, target): res = count = 0 for i, n in enumerate(self.nums): if n == target: count += 1 if random.randint(1, count) == 1: res = i return res
扩展总结
- 水库抽样适合汁数据流写常数空间
- 数学证明：第 k 个目标被选择的概率 = 1/k × k/(k+1) × ... = 1/n
- 相关：#382 Linked List Random Node
🔖 #50 · Pow(x, n) ★
难度: Medium | 标签: Math, Recursion | 链接: https://leetcode.com/problems/powx-n/
题目描述
实现 pow(x, n)。
解题思路
快速幂：奇偶分治。奇数：
x * pow(x, n-1)，偶数：pow(x, n//2)^2。注意 n < 0 的情况。答案代码
def myPow(x, n): if n < 0: x, n = 1/x, -n res = 1 while n: if n % 2: res *= x x *= x n //= 2 return res
扩展总结
- 快速幂是 O(log n) 算法，应用在矩阵幂、模幂等地方
- Python 整除 -n 时需注意
INT_MIN边界（Python 无岂，但 Java 要小心）
🔖 #136 · Single Number
难度: Easy | 标签: Bit, XOR | 链接: https://leetcode.com/problems/single-number/
题目描述
数组中除了一个元素出现一次，其他元素均出现两次。
解题思路
XOR 性质：
a ^ a = 0，a ^ 0 = a。全部异或后仅剩独身元素。答案代码
def singleNumber(nums): return reduce(lambda a, b: a ^ b, nums)
扩展总结
- #137 Single Number II：其他元素出现三次，用位计数器解决
- #260 Single Number III：两个元素各出现一次
🔖 #191 · Number of 1 Bits
难度: Easy | 标签: Bit | 链接: https://leetcode.com/problems/number-of-1-bits/
答案代码
def hammingWeight(n): count = 0 while n: n &= n - 1 # 消去最低位 1 count += 1 return count
扩展总结
n & (n-1)消掉最低位 1，是位运算经典技巧
- 应用：#231 判断是否 2 的幂次，#338 Counting Bits