Uber NG OA 真题复盘：最小操作数 + 好子数组 两道算法题完整解析

概述

Uber New Grad OA 包含两道算法题，考察位运算和滑动窗口的综合应用。本文提供完整的解题思路、代码实现和优化技巧。

---

Question 1: 最小操作数归零

题目描述

给定一个正整数 n，你可以在一次操作中对 n 进行以下操作之一：

• 加上 2 的某个幂次（2^i）
• 减去 2 的某个幂次（2^i）

求将 n 归零所需的最小操作数。

示例：

输入: n = 5
输出: 2

解释:
5 → 5 - 2^0 = 4 → 4 - 2^2 = 0
或者: 5 → 5 - 1 = 4 → 4 - 4 = 0

示例 2：

输入: n = 21
输出: 3

解释:
21 的二进制: 10101
需要 3 次操作

约束条件：

• 1 ≤ n < 2^60

---

解题思路

核心观察

这道题的关键在于二进制表示：

• 每个正整数都可以用二进制表示
• 加减 2 的幂次 = 改变某一位的值
• 目标是用最少操作将所有位变为 0

方法一：贪心 + 位运算 ⭐ 最优解

核心思想：

1. 统计二进制中连续 1 的段数
2. 连续的 1 可以通过一次"进位"操作合并
3. 例如：111 (7) = 1000 (8) - 1，只需 2 次操作

算法步骤：

10101 (21)
↓
连续1的段: [1], [1, 1] 
段数 = 2 个独立的1 + 1 个连续段 = 3

优化技巧：

• 连续的 1：可以用"加法进位"优化
• 孤立的 1：直接减去

代码实现

def getMinOperations(n):
    """
    计算将 n 归零的最小操作数
    
    思路：统计二进制中 1 的段数
    - 连续的 1 算作一段
    - 每段需要 1-2 次操作
    """
    if n == 0:
        return 0
    
    operations = 0
    prev_bit = 0
    
    while n > 0:
        current_bit = n & 1  # 获取最低位
        
        # 如果当前位是 1，且前一位是 0（新段开始）
        if current_bit == 1 and prev_bit == 0:
            operations += 1
        
        prev_bit = current_bit
        n >>= 1  # 右移一位
    
    return operations

# 测试用例
print(getMinOperations(5))   # 输出: 2
print(getMinOperations(21))  # 输出: 3
print(getMinOperations(15))  # 输出: 1 (1111 -> 10000 - 1)

时间复杂度：O(log n) - 遍历二进制位数
空间复杂度：O(1)

---

方法二：Brian Kernighan 算法

def getMinOperations_v2(n):
    """
    使用 Brian Kernighan 算法
    每次消除最右边的 1
    """
    # 先将连续的 1 合并
    # n + (n >> 1) 可以检测连续 1
    operations = 0
    
    while n:
        # 检查是否有连续的 1
        if n & (n >> 1):
            # 有连续 1，进位
            n += (n & -(n & (n >> 1)))
        else:
            # 没有连续 1，直接减
            n &= n - 1
        operations += 1
    
    return operations

---

常见陷阱

❌ 错误 1：直接统计 1 的个数

# 错误示例
def wrong_solution(n):
    return bin(n).count('1')  # 对于 111 会返回 3，实际只需 2

❌ 错误 2：没有考虑连续 1 的优化

# 15 = 1111，直接统计是 4，但实际只需 1 次（16 - 1）

✅ 正确做法：统计连续 1 的段数，而不是 1 的个数

---

Question 2: 好子数组的最小长度

题目描述

给定一个包含 n 个正整数的数组 arr[n] 和一个整数 k，如果一个子数组包含至少 k 个不同的整数，则称其为好子数组。

求最短好子数组的长度。如果不存在这样的子数组，返回 -1。

示例：

输入: arr = [2, 2, 1, 1, 3], k = 3
输出: 4

解释:
包含至少 3 个不同整数的子数组:
- [2, 2, 1, 1, 3] (长度 5)
- [2, 1, 1, 3] (长度 4) ✓ 最短

约束条件：

• 1 ≤ n ≤ 10^6
• 1 ≤ arr[i] ≤ 10^6
• 1 ≤ k ≤ n

---

解题思路

核心思想：滑动窗口

这是一道经典的滑动窗口问题：

1. 维护一个窗口，记录窗口内不同整数的个数
2. 当窗口内不同整数 ≥ k 时，尝试缩小窗口
3. 记录满足条件的最小窗口长度

算法步骤

arr = [2, 2, 1, 1, 3], k = 3

步骤 1: [2] - 1 个不同整数
步骤 2: [2, 2] - 1 个不同整数
步骤 3: [2, 2, 1] - 2 个不同整数
步骤 4: [2, 2, 1, 1] - 2 个不同整数
步骤 5: [2, 2, 1, 1, 3] - 3 个不同整数 ✓

现在尝试缩小窗口:
步骤 6: [2, 1, 1, 3] - 3 个不同整数 ✓ (长度 4)
步骤 7: [1, 1, 3] - 2 个不同整数 ✗

答案: 4

---

代码实现

def findMinimumLengthSubarray(arr, k):
    """
    使用滑动窗口找到包含至少 k 个不同整数的最短子数组
    
    时间复杂度: O(n)
    空间复杂度: O(k)
    """
    from collections import defaultdict
    
    n = len(arr)
    if k > n:
        return -1
    
    # 窗口内每个数字的出现次数
    window = defaultdict(int)
    left = 0
    min_length = float('inf')
    
    for right in range(n):
        # 扩展窗口
        window[arr[right]] += 1
        
        # 当窗口内不同整数 >= k 时，尝试缩小窗口
        while len(window) >= k:
            min_length = min(min_length, right - left + 1)
            
            # 缩小窗口
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1
    
    return min_length if min_length != float('inf') else -1

# 测试用例
print(findMinimumLengthSubarray([2, 2, 1, 1, 3], 3))  # 输出: 4
print(findMinimumLengthSubarray([1, 2, 3, 4], 2))     # 输出: 2
print(findMinimumLengthSubarray([1, 1, 1, 1], 2))     # 输出: -1

---

优化版本：更简洁的实现

def findMinimumLengthSubarray_v2(arr, k):
    """
    优化版本：使用 Counter
    """
    from collections import Counter
    
    if k > len(set(arr)):
        return -1
    
    window = Counter()
    left = 0
    min_length = float('inf')
    
    for right, num in enumerate(arr):
        window[num] += 1
        
        while len(window) >= k:
            min_length = min(min_length, right - left + 1)
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1
    
    return min_length if min_length != float('inf') else -1

时间复杂度：O(n) - 每个元素最多被访问两次
空间复杂度：O(k) - 哈希表最多存储 k 个不同元素

---

常见陷阱

❌ 错误 1：使用暴力枚举 O(n²)

# 超时！
def brute_force(arr, k):
    min_len = float('inf')
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if len(set(arr[i:j+1])) >= k:
                min_len = min(min_len, j - i + 1)
    return min_len if min_len != float('inf') else -1

❌ 错误 2：没有正确维护窗口

# 忘记删除计数为 0 的元素
window[arr[left]] -= 1
# 应该加上:
if window[arr[left]] == 0:
    del window[arr[left]]

✅ 正确做法：使用滑动窗口 + 哈希表，O(n) 时间复杂度

---

临场应对策略

时间分配建议

题目	难度	建议时间	优先级
Question 1	Medium	20-25 分钟	⭐⭐⭐
Question 2	Medium	25-30 分钟	⭐⭐⭐⭐

总时间：45-55 分钟（留 5-10 分钟检查）

---

调试技巧

Question 1 调试：

def debug_operations(n):
    """打印每一步操作"""
    print(f"n = {n}, binary = {bin(n)}")
    operations = 0
    prev_bit = 0
    
    while n > 0:
        current_bit = n & 1
        if current_bit == 1 and prev_bit == 0:
            operations += 1
            print(f"New segment found at position, operations = {operations}")
        prev_bit = current_bit
        n >>= 1
    
    return operations

Question 2 调试：

def debug_window(arr, k):
    """打印窗口状态"""
    from collections import defaultdict
    
    window = defaultdict(int)
    left = 0
    
    for right in range(len(arr)):
        window[arr[right]] += 1
        print(f"Window [{left}:{right+1}]: {dict(window)}, distinct = {len(window)}")
        
        while len(window) >= k:
            print(f"  → Found valid window, length = {right - left + 1}")
            window[arr[left]] -= 1
            if window[arr[left]] == 0:
                del window[arr[left]]
            left += 1

---

知识点总结

Question 1 考点

• ✅ 位运算基础
• ✅ 二进制表示
• ✅ 贪心算法
• ✅ 数学优化

Question 2 考点

• ✅ 滑动窗口
• ✅ 哈希表应用
• ✅ 双指针技巧
• ✅ 时间复杂度优化

---

相关题目

Question 1 相关

• LeetCode 191: Number of 1 Bits
• LeetCode 338: Counting Bits
• LeetCode 201: Bitwise AND of Numbers Range

Question 2 相关

• LeetCode 340: Longest Substring with At Most K Distinct Characters
• LeetCode 904: Fruit Into Baskets
• LeetCode 3: Longest Substring Without Repeating Characters

---

🚀 需要 OA/VO 辅助？

oavoservice 提供专业的面试辅助服务：

✅ 实时代码支持 - OA/VO 全程辅助
✅ 真题题库 - 1000+ 最新真题
✅ 模拟面试 - 1对1 模拟训练
✅ 简历优化 - 提高面试通过率

👉 立即添加微信：Coding0201
👉 访问官网：oavoservice.com

---

最后更新：2026-03-15
难度评级：⭐⭐⭐ Medium
通过率：约 65%
公司：Uber New Grad OA