題目描述:
給定一個二進位字串 s,可以執行兩種操作:
求使字串變成交替字串("010101..." 或 "101010...")的最少操作 2 次數(操作 1 可以用任意次)。
解題思路:
s + s,長度為 2n。這樣所有循環左移的結果都是 s+s 的長度為 n 的子串。s+s 的每個位置 i,計算它與兩種交替模式("0101..." 和 "1010...")不匹配的情況。s+s 上滑動,維護窗口內兩種模式各需要多少次翻轉(type-2 操作),取最小值。時間複雜度:O(n) — 在長度 2n 的字串上進行一次滑動窗口遍歷。
空間複雜度:O(n) — 建立了 doubled 字串。可以用取模優化到 O(1)。
1. Create doubled = s + s 2. Initialize count0 = 0, count1 = 0 (mismatches for two alternating patterns) 3. Initialize ans = n 4. For each index i in doubled: a. Check if doubled[i] mismatches pattern "010101..." at position i → update count0 b. Check if doubled[i] mismatches pattern "101010..." at position i → update count1 c. If i >= n, remove the contribution of index (i - n) from count0 and count1 d. If i >= n - 1 (window is full): ans = min(ans, min(count0, count1)) 5. Return ans
枚舉所有旋轉 O(n²):對每種循環左移,逐一計算翻轉次數。簡單但 n 大時超時。
O(1) 空間滑動窗口:不建立 doubled 字串,用 i % n 取模存取原字串。省去 O(n) 空間但程式碼可讀性略降。