- 難度分: 2006
- 這一題如果沒有條件一,則很簡單,根據奇偶數索引位置,判斷是否要 flip 就可以了。
int minFlips(string s) {
int n = s.size();
int ans1 = 0, ans2 = 0;
for (int i = 0; i < n; i++) {
if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1;
if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2;
}
int ans = min(ans1, ans2);
}
- 但這一題加上條件一,可以用很精巧的手法,把它轉成 sliding window 的問題,將字串重覆兩次,以原字串長度作為 window size,可解這題。
class Solution {
public:
int minFlips(string s) {
int k = s.size();
s += s;
int ans1 = 0, ans2 = 0;
for (int i = 0; i < k; i++) {
if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1;
if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2;
}
int ans = min(ans1, ans2);
for (int i = k; i < s.size(); i++) {
if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1;
if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2;
if (((i - k) % 2 == 0 && s[i - k] != '1') || ((i - k) % 2 == 1 && s[i - k] != '0')) --ans1;
if (((i - k) % 2 == 0 && s[i - k] != '0') || ((i - k) % 2 == 1 && s[i - k] != '1')) --ans2;
ans = min({ans1, ans2, ans});
}
return ans;
}
};