通过翻转行或列来去除所有的 1

2128. 通过翻转行或列来去除所有的 1

给你一个大小为 m x n 的二进制矩阵 grid。

每次操作，你可以选择任意一行或者一列，然后将其中的所有值翻转（0 变成 1， 1变成 0）。

如果经过 任意次 操作，你能将矩阵中所有的 1 去除，那么返回 true；否则返回 false。

示例 1:

输入: grid = [[0,1,0],[1,0,1],[0,1,0]]
输出: true
解释: 一种去除所有 1 的可行方法是:
- 翻转矩阵的中间的行
- 翻转矩阵的中间的列

示例 2:

输入: grid = [[1,1,0],[0,0,0],[0,0,0]]
输出: false
解释: 不可能去除矩阵中所有的 1。

示例 3:

输入: grid = [[0]]
输出: true
解释: 矩阵中不存在 1，已经符合要求。

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 是 0 或者 1.

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool removeOnes(vector<vector<int>>& grid) { } };

golang 解法, 执行用时: 48 ms, 内存消耗: 6.8 MB, 提交时间: 2023-10-17 11:25:49

func removeOnes(grid [][]int) bool {
	n := len(grid)
	m := len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[0][j] != grid[i][j] ^ grid[i][0] ^ grid[0][0] {
				return false
			}
		}
	}
	return true
}

java 解法, 执行用时: 3 ms, 内存消耗: 55.4 MB, 提交时间: 2023-10-17 11:25:03

class Solution {
    public boolean removeOnes(int[][] grid) {
        for(int i = 1; i < grid.length; ++i) {
            for(int j = 1; j < grid[0].length; ++j) {
                if ( (grid[i][j] + grid[0][j]) % 2 != (grid[i][0] + grid[0][0]) % 2 ) return false;
            }
        }
        return true;
    }
}

cpp 解法, 执行用时: 40 ms, 内存消耗: 24.4 MB, 提交时间: 2023-10-17 11:24:19

class Solution {
public:
    bool removeOnes(vector<vector<int>>& grid) {
        for(int i = 1; i < grid.size(); ++i){
            for(int j = 1; j < grid[0].size(); ++j){
                if((grid[i][j] + grid[0][j]) % 2 != (grid[i][0] + grid[0][0]) % 2) return false;
            }
        }
        return true;
    }
};

python3 解法, 执行用时: 52 ms, 内存消耗: 19.2 MB, 提交时间: 2023-10-17 11:23:31

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> bool:
        xor = [x ^ 1 for x in grid[0]]
        return all(row in (grid[0], xor) for row in grid)

python3 解法, 执行用时: 96 ms, 内存消耗: 19.4 MB, 提交时间: 2023-10-17 11:23:00

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> bool:
        states = set()  # 与行首异或, 记录每行的状态
        for row in grid:
            cur = []
            for num in row:
                cur.append(str(num ^ row[0])) # 每个数与行首异或
            states.add(''.join(cur))
        return len(states) == 1 # 如果每行的状态都一样，则可变

上一题

下一题

详情