面試必備：字符串專題十五大高頻算法總結（C/C++ 實現）

一、字符串與數值互轉：atoi / itoa 手寫核心邏輯

字符串轉整數 (myatoi) 關鍵點

• 跳過前導空格
• 識別正負號
• 逐字符驗證 isdigit
• 溢出檢查：result > INT_MAX/10 || (result==INT_MAX/10 && digit > INT_MAX%10)
• 非法輸入處理（可選 endptr 輸出解析終止位置）

int myatoi(const char* str) {
    while (*str == ' ' || *str == '\t') str++;
    int sign = 1;
    if (*str == '-') { sign = -1; str++; }
    else if (*str == '+') str++;
    long long result = 0;  // 用長長整型暫存防溢出
    while (*str >= '0' && *str <= '9') {
        result = result * 10 + (*str - '0');
        if (sign == 1 && result > INT_MAX) return INT_MAX;
        if (sign == -1 && -result < INT_MIN) return INT_MIN;
        str++;
    }
    return (int)(sign * result);
}

整數轉字符串 (itoa) 核心邏輯

• 處理 INT_MIN 絕對值溢出（用 unsigned 或特判）
• 取模 10 得低位，/=10 縮減，字符逆序存入臨時數組
• 負數補 '-'，最後整體逆序輸出到目標緩衝區

二、最長相同字符子串

單次掃描，維護 curChar, curLen, maxChar, maxLen，字符變化時比較更新最大值。O(n) 時間，O(1) 空間。

三、最長公共子串（Longest Common Substring）

動態規劃 dp[i][j] 表示以 s1[i-1]、s2[j-1] 結尾的最長公共後綴長度。
if (s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=0;
記錄最大值位置回溯提取子串。O(mn) 時間，可優化至 O(min(m,n)) 空間。

四、字符串查找：strstr 實現與 KMP

朴素雙指針 (strstr 參考實現)

char* strstr(char* haystack, char* needle) {
    if (!*needle) return haystack;
    for (; *haystack; haystack++) {
        char *h = haystack, *n = needle;
        while (*h && *n && *h == *n) { h++; n++; }
        if (!*n) return haystack;
    }
    return NULL;
}

KMP 核心：前綴函數 (next/LPS 數組)

next[i] = 模式串 [0..i] 的最長真前綴同時為後綴的長度。匹配失敗時 j = next[j-1] 避免主串回溯。O(n+m)。

五、去除重復字符（保留首次出現）

利用 bool seen[256] = {false}（ASCII）或 unordered_set，遍歷原串，未見過則加入結果並標記。O(n) 時間，O(字符集) 空間。

六、字符串全排列（字典序）

C++ next_permutation 算法：
1. 從右向左找第一個 a[i] < a[i+1]
2. 從右向左找第一個 a[j] > a[i]
3. swap(i,j)，reverse(i+1, end)
下一個排列生成器模式，避免遞歸棧溢出。

七、字符串翻轉

雙指針 left=0, right=len-1，swap(s[left++], s[right--]) 直到相遇。原地 O(n)。

八、第一個不重復字符

兩遍掃描：第一遍統計頻次 cnt[256]，第二遍找第一個 cnt[c]==1 的字符。O(n)。

九、去除相鄰重復字符

棧思想：遍歷字符，棧頂相同則彈出（抵消），不同則壓入。最終棧內即為結果。O(n) 時間，O(n) 空間。

十、判斷是否含回文子串

中心擴展法：枚舉 2n-1 個中心（字符中心、字符間隙），向兩側擴展判斷。發現任意長度≥2 的回文即返回 true。O(n²) 最壞，平均較快。

十一、最長回文子串

Manacher 算法 O(n)：預處理插入 # 統一奇偶長度，維護 RL[i]（以 i 為中心的回文半徑）與 MaxRight, pos。
或 DP O(n²)：dp[i][j] = (s[i]==s[j]) && (j-i<2 || dp[i+1][j-1])。

十二、字符串循環移位包含判斷

s2 是否為 s1 循環移位的子串 ⇔ s2 是 s1+s1 的子串。直接 strstr(s1+s1, s2)。O(n)。

十三、strcpy 實現與重疊內存處理

char* strcpy(char* dest, const char* src) {
    char* ret = dest;
    while ((*dest++ = *src++)) ;  // 賦值同時檢查 '\0'
    return ret;
}
// 注意：src 與 dest 重疊時行為未定義，需用 memmove

十四、去除中文中的英文字符

UTF-8 中文佔 3 字節（首字節高位 1110xxxx 即 ≥0xE0），ASCII 英文字符佔 1 字節（高位 0）。遍歷字節流，根據首字節高位判斷字符寬度，只複製中文字節。O(n)。

十五、連續出現次數最多的子串

同「二」，但統計任意長度子串需後綴數組/後綴自動機，O(n) 構建後綴自動機 可解決廣義最長重復子串問題。

面試加分點總結