游酷盛世筆試

小紅的01串-AI自測

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 檢查字符串是否為好串（不含"010"或"101"）
bool isGood(string s) {
    for(int i = 0; i < s.length() - 2; i++) {
        if((s[i] == '0' && s[i+1] == '1' && s[i+2] == '0') || 
          (s[i] == '1' && s[i+1] == '0' && s[i+2] == '1')) {
            return false;
        }
    }
    return true;
}

// 計算翻轉次數(shù)
int test(string s) {
    int n = s.length();
    string s1 = s;  // 原始字符串的副本
    int flips1 = 0; // 第一種情況的翻轉次數(shù)
    
    // 情況1：從原始字符串開始修改
    for(int i = 0; i < n-2; i++) {
        if((s1[i] == '0' && s1[i+1] == '1' && s1[i+2] == '0') ||
          (s1[i] == '1' && s1[i+1] == '0' && s1[i+2] == '1')) {
            s1[i+2] = (s1[i+2] == '0' ? '1' : '0'); // 翻轉第i+2位
            flips1++;
            i = max(-1, i-2); // 回退檢查
        }
    }
    
    // 情況2：從相反的修改開始
    string s2 = s;
    int flips2 = 0;
    for(int i = n-1; i >= 2; i--) {
        if((s2[i-2] == '0' && s2[i-1] == '1' && s2[i] == '0') ||
          (s2[i-2] == '1' && s2[i-1] == '0' && s2[i] == '1')) {
            s2[i-2] = (s2[i-2] == '0' ? '1' : '0'); // 翻轉第i-2位
            flips2++;
            i = min(n, i+2); // 前進檢查
        }
    }
    
    // 檢查兩種情況的結果并返回最小值
    int result1 = isGood(s1) ? flips1 : n + 1;
    int result2 = isGood(s2) ? flips2 : n + 1;
    cout << min(result1, result2) <<endl;
}
// #include <vector>
// #include <climits>
// #include <algorithm>
// #include <string>
// #include <iostream>
// #include <cstring> 
// using namespace std;

// int test(string s) {
//     int n = s.size();
//     if (n < 3) return 0; // 無需修改

//     // 初始化動態(tài)規(guī)劃數(shù)組，prev_dp[a][b]表示前兩個字符為a和b的最小翻轉次數(shù)
//     int prev_dp[2][2];
//     for (int a = 0; a < 2; a++) {
//         for (int b = 0; b < 2; b++) {
//             prev_dp[a][b] = (a != (s[0] - '0')) + (b != (s[1] - '0'));
//         }
//     }

//     // 從第三個字符開始處理
//     for (int i = 2; i < n; i++) {
//         int current_dp[2][2];
//         fill(¤t_dp[0][0], ¤t_dp[0][0] + 4, INT_MAX); // 初始化為極大值
//         int orig = s[i] - '0';

//         // 遍歷所有可能的前兩個字符組合
//         for (int a = 0; a < 2; a++) {
//             for (int b = 0; b < 2; b++) {
//                 if (prev_dp[a][b] == INT_MAX) continue; // 無效狀態(tài)跳過

//                 // 嘗試當前字符變?yōu)?或1
//                 for (int c = 0; c < 2; c++) {
//                     // 檢查是否形成壞模式 "010" 或 "101"
//                     if ((a == 0 && b == 1 && c == 0) || (a == 1 && b == 0 && c == 1)) {
//                         continue; // 非法組合，跳過
//                     }

//                     // 計算總翻轉次數(shù)
//                     int cost = prev_dp[a][b] + (c != orig ? 1 : 0);
//                     // 更新當前狀態(tài)的最小值
//                     if (cost < current_dp[b][c]) {
//                         current_dp[b][c] = cost;
//                     }
//                 }
//             }
//         }

//         // 將當前狀態(tài)轉移到prev_dp
//         memcpy(prev_dp, current_dp, sizeof(prev_dp));
//     }

//     // 找到最終所有可能狀態(tài)的最小值
//     int result = INT_MAX;
//     for (int a = 0; a < 2; a++) {
//         for (int b = 0; b < 2; b++) {
//             result = min(result, prev_dp[a][b]);
//         }
//     }
//     cout << result << endl;
//     return result;
// }
int main() {
    test("010101"); // 預期: 2
    test("010");    // 預期: 1
    test("111");    // 預期: 0
    test("0000");   // 預期: 0
    test("1010");   // 預期: 1 
    test("100100"); // 1
    test("01010");  // 1

    return 0;
}