題目描述:
給定一個只包含 '0' 和 '1' 的二進位字串 s,你可以翻轉任意數量的字元('0' 變 '1' 或 '1' 變 '0')。求最少翻轉次數使字串變成單調遞增(所有 '0' 在所有 '1' 的左邊)。
解題思路: 前綴 1 計數法:
想像一條分界線,左邊全是 '0',右邊全是 '1'。我們需要:
'1' 翻成 '0''0' 翻成 '1'用一個變數 ones 追蹤目前為止遇到的 '1' 的數量,用 flips 記錄最小翻轉次數:
遍歷字串,對每個字元:
'1':ones++(可能需要未來翻轉)'0':要麼翻這個 '0' 為 '1'(flips + 1),要麼把之前所有 '1' 翻為 '0'(ones)。取較小值:flips = min(flips + 1, ones)。時間複雜度:O(n) — 一次遍歷字串。
空間複雜度:O(1) — 只使用兩個變數。
1. Initialize ones = 0, flips = 0. 2. For each character c in s: a. If c == '1': increment ones. b. If c == '0': flips = min(flips + 1, ones). 3. Return flips.
前綴和 + 枚舉分割點:O(n) 時間、O(n) 空間。先計算前綴 1 的數量和後綴 0 的數量,枚舉每個分割點取最小值。邏輯清晰但需要額外空間。
DP 雙狀態:O(n) 時間、O(1) 空間。定義 dp0 = 到目前為止以 '0' 結尾的最小翻轉數,dp1 = 以 '1' 結尾的最小翻轉數。轉移:dp0' = dp0 + (c == '1'),dp1' = min(dp0, dp1) + (c == '0')。最終答案 min(dp0, dp1)。
flips = min(flips + 1, ones) 背後的直覺是什麼?為什麼只需要這兩個選項?