游酷盛世笔试

小红的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;
}

// 计算翻转次数
int test(string s) {
    int n = s.length();
    string s1 = s;  // 原始字符串的副本
    int flips1 = 0; // 第一种情况的翻转次数
    
    // 情况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; // 无需修改

//     // 初始化动态规划数组，prev_dp[a][b]表示前两个字符为a和b的最小翻转次数
//     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; // 无效状态跳过

//                 // 尝试当前字符变为0或1
//                 for (int c = 0; c < 2; c++) {
//                     // 检查是否形成坏模式 "010" 或 "101"
//                     if ((a == 0 && b == 1 && c == 0) || (a == 1 && b == 0 && c == 1)) {
//                         continue; // 非法组合，跳过
//                     }

//                     // 计算总翻转次数
//                     int cost = prev_dp[a][b] + (c != orig ? 1 : 0);
//                     // 更新当前状态的最小值
//                     if (cost < current_dp[b][c]) {
//                         current_dp[b][c] = cost;
//                     }
//                 }
//             }
//         }

//         // 将当前状态转移到prev_dp
//         memcpy(prev_dp, current_dp, sizeof(prev_dp));
//     }

//     // 找到最终所有可能状态的最小值
//     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;
}