这题的核心是不能在检查阶段遍历矩阵，而是要利用你已经实现的init和flip函数，在预处理和修改阶段维护额外的状态，让检查操作能O(1)完成。我给你一个非常直观的解决方案：

思路概述 #

我们需要维护两个额外的状态变量/数组，用来追踪矩阵中全1行的状态：

• row_one_counts：一个大小为n的数组，row_one_counts[i]记录第i行中'1'的数量。
• full_row_count：一个整数，记录当前矩阵中全为'1'的行的总数。

这样，检查函数只需要判断full_row_count > 0即可，完全是O(1)时间。

具体实现步骤 #

1. 初始化阶段（配合init函数）

当你调用init(n, A)初始化全1矩阵时，同时完成状态初始化：

// 你可以把这些状态封装到结构体里，避免全局变量（示例用全局变量简化说明）
int *row_one_counts;
int full_row_count;

void init(int n, char A[n][n]) {
    // 原有的初始化逻辑：填满'1'
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] = '1';
        }
    }
    // 初始化状态变量
    row_one_counts = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        row_one_counts[i] = n; // 每行初始有n个'1'
    }
    full_row_count = n; // 所有行都是全1
}

这里的时间复杂度还是O(n²)，完全符合题目对init的要求。

2. 翻转操作阶段（配合flip函数）

修改flip函数，在翻转元素的同时更新我们维护的状态：

void flip(char A[n][n], int i, int j) {
    if (A[i][j] == '1') {
        // 从'1'翻转为'0'
        A[i][j] = '0';
        row_one_counts[i]--;
        // 如果这一行之前是全1，现在不再是了
        if (row_one_counts[i] == n - 1) {
            full_row_count--;
        }
    } else {
        // 从'0'翻转为'1'
        A[i][j] = '1';
        row_one_counts[i]++;
        // 如果这一行现在变成全1了
        if (row_one_counts[i] == n) {
            full_row_count++;
        }
    }
}

这个修改完全不影响flip的O(1)时间复杂度，所有操作都是常数时间。

3. 检查函数实现

现在检查函数就超级简单了，直接返回full_row_count > 0的结果：

int has_all_one_row(char A[n][n], int n) {
    // O(1)时间判断
    return full_row_count > 0 ? 1 : 0;
}

验证示例 #

拿你给的例子测试：

• 第一个例子：3阶矩阵[[1,1,0],[1,1,1],[0,0,1]]
  初始化后full_row_count=3，经过三次翻转（(0,2)、(2,0)、(2,1)）后，full_row_count最终为1，检查函数返回1，符合预期。
• 第二个例子：[[1,1,0],[1,0,1],[1,0,0]]
  经过对应翻转后，full_row_count会降到0，检查函数返回0，符合预期。

小提示 #

• 如果你不想用全局变量，可以把row_one_counts、full_row_count和矩阵A一起封装到一个结构体里，这样更符合C语言的模块化设计。
• 记得在不需要矩阵的时候，释放row_one_counts的内存，避免内存泄漏。

内容的提问来源于stack exchange，提问作者Adir Mantsur