LeetCode 經典題目 C/C++ 解法：Nim Game、Reverse String、Sum of Two Integers

LeetCode 經典題目 C/C++ 解法：Nim Game、Reverse String、Sum of Two Integers

本文收錄三道 LeetCode 高頻面試題的 C/C++ 實現，涵蓋博弈論、雙指針反轉、位運算加法，附帶時間複雜度分析與優化思路。

292. Nim Game（博弈論）

規則：堆中有 n 顆石子，雙方輪流取 1-3 顆，取走最後一顆者勝。先手能否必勝？

數學規律：n % 4 == 0 時先手必敗，否則必勝。

// C++
bool canWinNim(int n) {
    return n % 4 != 0;
}

// C
bool canWinNim(int n) {
    return (n > 0 && n < 4) || n % 4 != 0;
}

複雜度：O(1) 時間，O(1) 空間。

344. Reverse String（雙指針原地反轉）

要求：原地反轉字符數組，O(1) 額外空間。

C++ STL 一行解

string reverseString(string s) {
    reverse(s.begin(), s.end());
    return s;
}

C 雙指針交換

char* reverseString(char* s) {
    int len = strlen(s);
    for (int i = 0, j = len - 1; i < j; i++, j--) {
        char tmp = s[i]; s[i] = s[j]; s[j] = tmp;
    }
    return s;
}

複雜度：O(n) 時間，O(1) 空間。

371. Sum of Two Integers（位運算模擬加法）

要求：不使用 +、- 運算符計算兩整數之和。

核心原理

• a ^ b：無進位加法（異或）；
• (a & b) << 1：進位（與運算左移）；
• 迭代直到進位為 0。

C++ 標準解

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

C 完整版（處理負數邊界）

int getSum(int a, int b) {
    while (b) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

關鍵點：C/C++ 無符號左移行為明確，有符號左移負數屬 UB，但實際上主流編譯器（GCC/Clang/MSVC）對補碼機器均正確工作。面試中說明「假設補碼、算術右移、無符號左移」即可。

另類解法：手工二進制加法（教學用，非面試推薦）

將整數轉二進制數組，模擬逐位加法與進位，再轉回十進制。代碼冗長（~140 行），邊界處理繁瑣（負數補碼、最小值溢出），僅供理解原理參考。

總結對比

這三道題分別考察**數學洞察、指針操作、位運算思維**，是面試中極高性價比的必刷題目。