2024-12-05：构造相同颜色的正方形。用go语言，给定一个3x3的矩阵，每个格子是’B’或’W’。

你需要判断是否可以通过修改最多一个格子的颜色，使得矩阵中存在一个2x2的颜色完全相同的正方形。

如果能得到这样的正方形，返回true；否则返回false。

输入：grid = [[“B”,“W”,“B”],[“B”,“W”,“W”],[“B”,“W”,“B”]]。

输出：true。

解释：

修改 grid[0][2] 的颜色，可以满足要求。

大体步骤如下：

1.创建一个函数 canMakeSquare(grid [][]byte) bool，该函数接受一个 3x3 的二维字节数组作为参数。

2.在 canMakeSquare 函数中，使用两个嵌套的循环遍历所有可能的左上角位置 (i, j)。

3.对于每个左上角位置 (i, j)，调用 check(grid [][]byte, i, j int) bool 函数进行检查。

4.check 函数接受当前左上角位置 (i, j)，遍历这个2x2的小正方形格子，检查是否有超过两个相同颜色 (‘B’) 的格子。

5.如果发现这个小正方形中超过两个相同颜色的格子，返回 false，否则返回 true。

6.如果所有的情况都检查完毕后没有找到符合条件的正方形，最终返回 false。

时间复杂度：

• 遍历所有可能的左上角位置需要 O(1) 的时间复杂度。

• 在每个左上角位置下，检查2x2小正方形格子是否满足条件的过程复杂度是 O(1)。

• 因此，总的时间复杂度为 O(1)。

空间复杂度：

• 除了输入参数之外，额外只使用了常数级别的额外空间。

• 因此，总的额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

func canMakeSquare(grid [][]byte) bool {
    for i := 0; i <= 1; i++ {
        for j := 0; j <= 1; j++ {
            if check(grid, i, j) {
                return true
            }
        }
    }
    return false
}
func check(grid[][]byte, x, y int) bool {
    count := 0
    for i := 0; i <= 1; i++ {
        for j := 0; j <= 1; j++ {
            if grid[x + i][y + j] == 'B' {
                count++
            }
        }
    }
    return count != 2
}


func main() {
	grid := [][]byte{{'B','W','B'},{'B','W','W'},{'B','W','B'}}
	fmt.Println(canMakeSquare(grid))
}

Rust完整代码如下：

fn can_make_square(grid: &Vec<Vec<char>>) -> bool {
    for i in 0..=1 {
        for j in 0..=1 {
            if check(grid, i, j) {
                return true;
            }
        }
    }
    false
}

fn check(grid: &Vec<Vec<char>>, x: usize, y: usize) -> bool {
    let mut count = 0;
    for i in 0..=1 {
        for j in 0..=1 {
            if grid[x + i][y + j] == 'B' {
                count += 1;
            }
        }
    }
    count != 2
}

fn main() {
    let grid = vec![
        vec!['B', 'W', 'B'],
        vec!['B', 'W', 'W'],
        vec!['B', 'W', 'B']
    ];
    println!("{}", can_make_square(&grid));
}