3127.构造相同颜色的正方形

https://leetcode.cn/problems/make-a-square-with-the-same-color/description/?envType=daily-question&envId=2024-08-31

题目描述

给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 ‘B’ ，要么是 ‘W’ 。字符 ‘W’ 表示白色，字符 ‘B’ 表示黑色。

你的任务是改变 至多一个 格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。

如果可以得到一个相同颜色的 2 x 2 正方形，那么返回 true ，否则返回 false 。

示例 1：

 

 

 

 

 

 

 

 

 

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

输出：true

解释：

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

示例 2：

 

 

 

 

 

 

 

 

 

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

输出：false

解释：

只改变一个格子颜色无法满足要求。

示例 3：

 

 

 

 

 

 

 

 

 

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

输出：true

解释：

grid 已经包含一个 2 x 2 颜色相同的正方形了。

提示：

grid.length == 3
grid[i].length == 3
grid[i][j] 要么是 ‘W’ ，要么是 ‘B’ 。

解题思路

通过遍历0,0 0,1 1,0 1,1 这些索引，以这些索引为顶点找到2x2的正方形是否有>=3个黑色 或者>=3个白色 有就return true
下图红色表示要遍历的顶点索引

 

 

 

 

 

 

 

 

 

代码编写

public boolean canMakeSquare(char[][] grid) {
    // System.out.println(Arrays.deepToString(grid));
    for (int i = 0; i < grid.length - 1; i++) {
        char[] chars = grid[i];
        for (int j = 0; j < chars.length - 1; j++) {
            int bCount = 0;
            int wCount = 0;
            // System.out.println(i + "," + j + ":" + grid[i][j]);
            // 判断2x2
            if (grid[i][j] == 'B') {
                bCount++;
            } else if (grid[i][j] == 'W') {
                wCount++;
            }
            if (grid[i + 1][j] == 'B') {
                bCount++;
            } else if (grid[i + 1][j] == 'W') {
                wCount++;
            }
            if (grid[i][j + 1] == 'B') {
                bCount++;
            } else if (grid[i][j + 1] == 'W') {
                wCount++;
            }
            if (grid[i + 1][j + 1] == 'B') {
                bCount++;
            } else if (grid[i + 1][j + 1] == 'W') {
                wCount++;
            }
            if (bCount >= 3 || wCount >= 3) {
                return true;
            }
        }
    }
    return false;
}

单元测试

System.out.println(new Solution3127().canMakeSquare(TransformUtils.charTwoDimensionalArrays(
    "[[\"B\",\"W\",\"B\"],[\"B\",\"W\",\"W\"],[\"B\",\"W\",\"B\"]]")));// true
System.out.println(new Solution3127().canMakeSquare(TransformUtils.charTwoDimensionalArrays(
    "[[\"B\",\"W\",\"B\"],[\"W\",\"B\",\"W\"],[\"B\",\"W\",\"B\"]]")));// false
System.out.println(new Solution3127().canMakeSquare(TransformUtils.charTwoDimensionalArrays(
    "[[\"B\",\"W\",\"B\"],[\"B\",\"W\",\"W\"],[\"B\",\"W\",\"W\"]]")));// true

额外补充

将字符串转换为二维数组

public static char[][] charTwoDimensionalArrays(String str) {
    List<List<Character>> collect = JSONUtil.parseArray(str)
        .stream()
        .map(obj -> ((JSONArray) obj).toList(Character.class))
        .collect(Collectors.toList());
    char[][] result = new char[collect.size()][0];
    for (int i = 0; i < collect.size(); i++) {
        result[i] = collect.get(i).stream().map(String::valueOf).collect(Collectors.joining()).toCharArray();
    }
    return result;
}