三道經典 LeetCode 面試題深度解析：旋轉矩陣、2 的冪次與主元素

在備戰演算法面試的過程中，刷題時常會遇到乍看簡單、實則暗藏玄機的「陷阱題」。這三道 LeetCode 經典題目——旋轉圖像、2 的冪次判斷、尋找主元素——正是典型代表。它們考驗的不是死記硬背的模板，而是對資料結構特性的洞察與位運算、投票演算法等巧思的靈活運用。下面我們逐一拆解，看看如何用最優雅的姿勢破解它們。

一、旋轉圖像：原地旋轉 90° 的幾何美學

題目要求

給定一個 n × n 的二維矩陣代表圖像，將其 順時針旋轉 90 度。關鍵限制：必須原地修改，不得申請額外的 O(n²) 空間。

核心洞察：兩次鏡像 = 一次旋轉

通用的線性代數做法是乘以旋轉變換矩陣，但那需要額外空間。觀察 90° 旋轉後的矩陣，會發現一個驚人的規律：

1. 先沿 水平中線 鏡像翻轉（上下翻轉）
2. 再沿 主對角線 鏡像翻轉（轉置）

這兩步操作均可在原矩陣上完成，空間複雜度 O(1)，時間複雜度 O(n²)，完美符合要求。

範例演示

原矩陣:        水平鏡像後:      主對角線鏡像後(結果):
11 12 13 14    23 24 25 26    23 19 15 11
15 16 17 18    19 20 21 22    24 20 16 12
19 20 21 22 →  15 16 17 18 →  25 21 17 13
23 24 25 26    11 12 13 14    26 22 18 14

參考代碼

class Solution {
public:
    void rotate(vector>& matrix) {
        if (matrix.empty()) return;
        int n = matrix.size();
        
        // 步驟 1：水平鏡像（上下翻轉）
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - 1 - i][j]);
            }
        }
        
        // 步驟 2：主對角線鏡像（轉置）
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

二、2 的冪次判斷：位運算的極致優雅

題目要求

判斷一個整數 n 是否為 2 的冪次（即 2^k，k ≥ 0）。

二進制視角的洞察

觀察 2 的冪次在二進制中的表示：

1  = 1
2  = 10
4  = 100
8  = 1000
16 = 10000
...

特徵：有且僅有一個 1，且位於最高位。

經典位運算技巧

若 n 是 2 的冪次，則 n - 1 的二進制表示會將那個唯一的 1 變為 0，而低位全變為 1。例如：

n     = 1000 (8)
n - 1 = 0111 (7)
n & (n - 1) = 0000

因此，n & (n - 1) == 0 即為判斷條件（需配合 n > 0 排除 0 和負數）。

一行代碼解決

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0) && ((n & (n - 1)) == 0);
    }
};

三、主元素問題：Boyer-Moore 投票演算法的神奇邏輯

題目要求

給定一個大小為 n 的陣列，找出出現次數 超過 ⌊n/2⌋ 的元素（主元素）。假設主元素必定存在。

從哈希表到 O(1) 空間

最直觀的做法是用哈希表計數，時間 O(n)、空間 O(n)。但能否做到 線性時間、常數空間？

Boyer-Moore 多數投票演算法

這個演算法的核心思想是「抵消」：

• 維護一個 candidate（候選元素）和 count（計數器）
• 遍歷陣列：
  • 若 count == 0，將當前元素設為新 candidate，count = 1
  • 若當前元素 == candidate，count++
  • 否則 count--
• 遍歷結束時，candidate 即為主元素

為什麼這能行？

主元素出現次數 > n/2，意味著它比所有其他元素總和還多。每次「不同元素抵消」都會消耗一個非主元素和一個主元素（或兩個非主元素），但主元素的「餘額」永遠為正，最終倖存下來的必是主元素。

演示過程

陣列: A A A C C B B C C C B C C
步驟:
A:1 → A:2 → A:3 → A:2 → A:1 → ?:0 → B:1 → ... → 最終候選為 C

參考代碼

class Solution {
public:
    int majorityElement(vector& nums) {
        int candidate = 0, count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                ++count;
            } else {
                --count;
            }
        }
        return candidate; // 題目保證主元素存在
    }
};

總結與思考

這三道題目各有千秋：

• 旋轉圖像：將幾何變換轉化為兩次簡單的鏡像操作，體現「換個角度思考」的智慧。
• 2 的冪次：利用二進制特性，用 n & (n-1) 一行代碼解決，展現位運算的威力。
• 主元素：Boyer-Moore 投票演算法以「抵消」思想達到時空雙優，是演算法設計中「以簡馭繁」的經典案例。

面試中遇到這類題目，切忌急著寫代碼。先問自己：「這個問題的核心約束是什麼？有沒有隱藏的數學/結構特性可利用？」 往往一個關鍵洞察，就能將複雜度從 O(n²) 降到 O(n)，從 O(n) 空間降到 O(1)。

Enjoy Coding! :)