判断矩阵是否满足条件。用go语言,给定一个大小为 m x n 的二维矩阵 grid,我们需要判断每个格子 grid[i][j] 是否符合以下两个条件:
1.如果下方的格子存在,则该格子必须与其下方格子相等,即 grid[i][j] 必须等于 grid[i + 1][j]。
2.如果右侧的格子存在,则该格子必须与其右侧格子不相等,即 grid[i][j] 必须不等于 grid[i][j + 1]。
如果矩阵中的所有格子都满足这两个条件,则返回 true;否则返回 false。
1 <= n, m <= 10。
0 <= grid[i][j] <= 9。
输入:grid = [[1,0,2],[1,0,2]]。
输出:true。
解释:
网格图中所有格子都符合条件。
大体步骤如下:
1.初始化变量:
- 定义一个函数
satisfiesConditions
接受一个二维整数数组grid
作为参数,返回一个布尔值。 - 函数内部遍历矩阵元素时,使用两个嵌套的
for
循环,分别遍历行和列。 - 初始化遍历矩阵时的索引变量
i
和j
。
2.遍历矩阵元素:
- 对于每个元素
grid[i][j]
,检查下方的元素是否存在,即判断i+1
是否小于矩阵的行数,如果小于且下方的元素与当前元素不相等,则返回false
。 - 同样,检查右侧的元素是否存在,即判断
j+1
是否小于矩阵的列数,如果小于且右侧的元素与当前元素相等,则返回false
。
3.返回结果:
- 如果遍历完所有元素后都满足上述两个条件,则返回
true
,表示矩阵中的所有元素符合条件。
4.时间复杂度:
- 假设矩阵的维度为 m x n,那么总共需要遍历 m x n 个元素。
- 因此,总的时间复杂度为 O(mn)。
5.额外空间复杂度:
- 除了存储输入二维矩阵
grid
的空间外,没有额外的空间开销。 - 因此,总的额外空间复杂度为 O(1)。
Go完整代码如下:
package main
import (
"fmt"
)
func satisfiesConditions(grid [][]int) bool {
for i := range grid {
for j := range grid[0] {
if i+1 < len(grid) && grid[i][j] != grid[i+1][j] {
return false
}
if j+1 < len(grid[0]) && grid[i][j] == grid[i][j+1] {
return false
}
}
}
return true
}
func main() {
grid := [][]int{{1, 0, 2}, {1, 0, 2}}
fmt.Println(satisfiesConditions(grid))
}
Rust完整代码如下:
fn satisfies_conditions(grid: &Vec<Vec<i32>>) -> bool {
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if i+1 < grid.len() && grid[i][j] != grid[i+1][j] {
return false;
}
if j+1 < grid[0].len() && grid[i][j] == grid[i][j+1] {
return false;
}
}
}
true
}
fn main() {
let grid = vec![vec![1, 0, 2], vec![1, 0, 2]];
println!("{}", satisfies_conditions(&grid));
}