EasyRating 1189
3461. Check If Digits Are Equal in String After Operations I
mathstringsimulationcombinatoricsnumber-theory
解題說明
Check If Digits Are Equal in String After Operations I
題目描述:給定一個由數字組成的字串 s。反覆執行以下操作直到字串長度變為 2:對每對相鄰數字取和再模 10,產生一個新的、長度減 1 的字串。判斷最終剩下的兩個數字是否相等。
解題思路:由於 Easy 版本字串長度較小,可以直接模擬整個過程。每一輪將字串從長度 n 縮減為 n-1,直到長度為 2。每輪中,新字串的第 i 個字元為 (s[i] + s[i+1]) % 10。最終比較兩個剩餘數字是否相等。
C++ 解法
複雜度分析
時間複雜度:O(n²) — 共 n-2 輪,第 i 輪處理長度 n-i 的字串,總計 O(n²)。
空間複雜度:O(n) — 每輪產生的新字串最長為 n。
虛擬碼
1. While s.length > 2: a. Create new string: for each i, new[i] = (s[i] + s[i+1]) % 10 b. Replace s with new string 2. Return s[0] == s[1]
其他解法
組合數學 O(n):最終的兩個數字是原始數字的加權和(權重為 Pascal 三角形的二項式係數,模 10)。可以直接計算 sum(C(n-2, i) * s[i]) mod 10 和 sum(C(n-2, i) * s[i+1]) mod 10 來判斷,但需要處理模 10 下的二項式係數(使用 Lucas 定理)。
原地模擬 O(n²):不產生新字串,直接在原始陣列上覆寫。節省空間但邏輯相同。
延伸思考
- 如果字串長度達到 10⁵,模擬法的 O(n²) 會超時,如何用 Lucas 定理在 O(n) 內求解?
- 如果取模的數不是 10 而是任意質數 p,問題會更簡單還是更難?
- 如果要判斷最終所有剩餘數字是否都相等(不限於長度 2),如何推廣?