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
    """
    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