22 篇博文 含有标签「矩阵」

1、题干​

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。

从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。

请你找出 arr 中第一个使得 mat 的某一行或某一列都被涂色的元素，并返回其下标 i 。

示例 1：

输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2：

输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提示：

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= arr[i], mat[r][c] <= m * n
• arr 中的所有整数 互不相同
• mat 中的所有整数 互不相同

2、思路​

模拟题，对行列涂色计数即可

3、代码​

function firstCompleteIndex(arr: number[], mat: number[][]): number {
    const map = new Array(arr.length + 1);
    for (let i = 0; i < mat.length; i++) {
        for (let j = 0; j < mat[i].length; j++) {
            map[mat[i][j]] = [i, j];
        }
    }

    const rows = new Array(mat.length).fill(0), cols = new Array(mat[0].length).fill(0);
    for (let i = 0; i < arr.length; i++) {
        const [r, c] = map[arr[i]];
        rows[r]++, cols[c]++;
        if (rows[r] === mat[0].length || cols[c] === mat.length) return i;
    }

    return -1;
};

1、题干​

骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

示例 1：

输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出：true
解释：grid 如上图所示，可以证明这是一个有效的巡视方案。

示例 2：

输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
输出：false
解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 7
• 0 <= grid[row][col] < n * n
• grid 中的所有整数 互不相同

2、思路​

从左上角开始 DFS 遍历，如果能完成遍历则说明巡视方案有效

3、代码​

function checkValidGrid(grid: number[][]): boolean {
    let vis = 0;
    const dirs = [[-2, -1], [2, 1], [-2, 1], [2, -1], [-1, -2], [1, 2], [-1, 2], [1, -2]];
    const t = grid.length * grid[0].length;

    function dfs(r: number, c: number) {
        vis++;
        if (grid[r][c] === t - 1) return;

        for (const [dr, dc] of dirs) {
            if (grid[r + dr]?.at(c + dc) === grid[r][c] + 1) {
                dfs(r + dr, c + dc);
                break;
            }
        }
    }

    dfs(0, 0);

    return vis === t;
};

4、复杂度​

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(n^2)$

5、执行结果​

1、题干​

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，且该矩阵满足 rowSum 和 colSum 的要求。

请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。

示例 1：

输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
      [1,7]]
解释：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
                  [3,5]]

示例 2：

输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
      [6,1,0],
      [2,0,8]]

示例 3：

输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
      [6,0,3]]

示例 4：

输入：rowSum = [1,0], colSum = [1]
输出：[[1],
      [0]]

示例 5：

输入：rowSum = [0], colSum = [0]
输出：[[0]]

提示：

• 1 <= rowSum.length, colSum.length <= 500
• 0 <= rowSum[i], colSum[i] <= 108
• sum(rowSum) == sum(colSum)

以为是个回溯，没想到是个贪心，磨蹭半天才想到，还不是最优的思路

2、思路1​

• 生成元素全为 0 的矩阵 grid，grid[0] 初始化为 colSum
• 遍历所有行的元素（最后一行除外），通过 rowSum[i] 的约束将超出的数转移到下一行

3、代码​

function restoreMatrix(rowSum: number[], colSum: number[]): number[][] {
    const grid = rowSum.map(() => colSum.map(() => 0));
    grid[0] = colSum;

    for (let i = 0; i < rowSum.length - 1; i++) {
        let sum = grid[i].reduce((a, c) => a + c, 0);
        for (let j = 0; j < colSum.length && sum > rowSum[i]; j++) {
            grid[i + 1][j] = Math.min(sum - rowSum[i], grid[i][j]);
            grid[i][j] -= grid[i + 1][j];
            sum -= grid[i + 1][j];
        }
    }

    return grid;
};

4、复杂度​

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(1)$

5、执行结果​

6、思路2​

更直接的贪心，通过 rowSum[i] 与 colSum[j] 直接约束 grid[i][j]

7、代码​

function restoreMatrix(rowSum: number[], colSum: number[]): number[][] {
    const grid = rowSum.map(() => colSum.map(() => 0));

    for (let i = 0; i < rowSum.length; i++) {
        for (let j = 0; j < colSum.length; j++) {
            grid[i][j] = Math.min(rowSum[i], colSum[j]);
            rowSum[i] -= grid[i][j];
            colSum[j] -= grid[i][j];
        }
    }

    return grid;
};

8、复杂度​

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(1)$

9、执行结果​

1、题干​

给你一个大小为 n x n 的整数矩阵 grid 。

生成一个大小为 (n - 2) x (n - 2) 的整数矩阵  maxLocal ，并满足：

• maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值 。

换句话说，我们希望找出 grid 中每个 3 x 3 矩阵中的最大值。

返回生成的矩阵。

示例 1：

输入：grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
输出：[[9,9],[8,6]]
解释：原矩阵和生成的矩阵如上图所示。
注意，生成的矩阵中，每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。

示例 2：

输入：grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
输出：[[2,2,2],[2,2,2],[2,2,2]]
解释：注意，2 包含在 grid 中每个 3 x 3 的矩阵中。

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 100
• 1 <= grid[i][j] <= 100

2、思路​

遍历矩阵 [1,n-2] 行列范围内的元素，该元素所在九宫格的最大整数作为最大值存入结果矩阵

3、代码​

function largestLocal(grid: number[][]): number[][] {
    const n = grid.length;
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, -1], [-1, -1], [-1, 1], [1, 1]];
    const ans = Array.from({ length: n - 2 }, () => Array.from({ length: n - 2 }, () => 0));

    for (let i = 1; i < n - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            ans[i - 1][j - 1] = grid[i][j];
            
            for (let k = 0; k < dirs.length; k++) {
                ans[i - 1][j - 1] = Math.max(ans[i - 1][j - 1], grid[i + dirs[k][0]][j + dirs[k][1]]);
            }
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] 为 0 或 1

2、思路​

纯模拟，毫无技巧，全是感情🤡

遍历网格，以当前网格单元作为正方形左上顶点，先求出左上两条边长的最大可能值，再验证右下两条边是否满足要求。

优化代码又折腾了一番，速度得到一些提升，从最快 88ms 达到最快 68ms。

主要优化在于检查边长的时候，由于是正方形可以同时检查两条边。做法是固定起始位置，然后改变边长，两条边同时满足要求时才往下遍历。

3、代码​

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let len = 1;
            while (grid[i][j + len] && grid[i + len]?.at(j)) len++;

            for (; len > maxLen; len--) {
                let step = 1, ei = i + len - 1, ej = j + len - 1;
                while (step < len && grid[i + step][ej] && grid[ei][j + step]) step++;

                if (step === len) maxLen = len;
            }
        }
    }

    return maxLen ** 2;
};

下面是最开始的代码，可以对照看看

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let si = i + 1, sj = j + 1;
            while (si < m && grid[si]?.at(j)) si++;
            while (sj < n && grid[i][sj]) sj++;

            let len = Math.min(si - i, sj - j);
            for (; len > maxLen; len--) {
                let ei = i + len - 1, ej = j + len - 1;
                while (ei > i && grid[ei][j + len - 1]) ei--;
                while (ej > j && grid[i + len - 1][ej]) ej--;

                if (ei === i && ej === j) maxLen = Math.max(maxLen, len);
            }
        }
    }

    return maxLen ** 2;
};

4、复杂度​

• 时间复杂度：最差$O(n^4)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

你还记得那条风靡全球的贪吃蛇吗？

我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。

每次移动，蛇可以这样走：

• 如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
• 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
• 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
  
• 如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。
  

返回蛇抵达目的地所需的最少移动次数。

如果无法到达目的地，请返回 -1。

示例 1：

输入：grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
输出：11
解释：
一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。

示例 2：

输入：grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
输出：9

提示：

• 2 <= n <= 100
• 0 <= grid[i][j] <= 1
• 蛇保证从空单元格开始出发。

2、思路​

使用 BFS 模拟，模拟过程使用二维矩阵存储访问状态，访问状态使用二进制表示：0未访问，1水平访问，2垂直访问，3水平访问+垂直访问

3、代码​

function minimumMoves(grid: number[][]): number {
    const n = grid.length;
    const dirs = [[0, 0], [0, 1], [1, 0], [1, 1]];
    const visited = grid.map(g => g.map(() => 0));

    function validate([r1, c1, r2, c2]: number[]) {
        const s = r1 === r2 ? 1 : 2;
        return grid[r1]?.at(c1) === 0 && grid[r2]?.at(c2) === 0 && (visited[r1][c1] | s) !== visited[r1][c1];
    }

    for (let step = 0, queue = [[0, 0, 0, 1]]; queue.length; step++) {
        const nextQueue = [];
        for (const [r1, c1, r2, c2] of queue) {
            if (r1 === n - 1 && r2 === n - 1 && c1 === n - 2 && c2 === n - 1) return step;

            const s = r1 === r2 ? 1 : 2;
            if ((visited[r1][c1] | s) === visited[r1][c1]) continue;

            visited[r1][c1] = visited[r1][c1] | s;

            // 水平：向右直走、向下平移
            // 垂直：向下直走、向右平移
            const p1 = [r1, c1 + 1, r2, c2 + 1], p2 = [r1 + 1, c1, r2 + 1, c2];
            if (validate(p1)) nextQueue.push(p1);
            if (validate(p2)) nextQueue.push(p2);

            // 旋转：必须满足4宫格为0
            if (!dirs.every(([dr, dc]) => grid[r1 + dr]?.at(c1 + dc) === 0)) continue;

            // 水平：顺时针旋转
            const p3 = [r1, c1, r2 + 1, c2 - 1];
            if (r1 === r2 && validate(p3)) nextQueue.push(p3);

            // 垂直：逆时针旋转
            const p4 = [r1, c1, r2 - 1, c2 + 1];
            if (c1 === c2 && validate(p4)) nextQueue.push(p4);
        }

        queue = nextQueue;
    }

    return -1;
};

4、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

5、执行结果​

1、题干​

如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：

1. 矩阵对角线上的所有元素都 不是 0
2. 矩阵中所有其他元素都是 0

给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。

示例 1：

输入：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
输出：true
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 是一个 X 矩阵。

示例 2：

输入：grid = [[5,7,0],[0,3,1],[0,5,0]]
输出：false
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 不是一个 X 矩阵。

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 100
• 0 <= grid[i][j] <= 105

2、思路​

遍历矩阵，对于矩阵中任意元素存在两个布尔状态 是否对角线 与 是否非0，二者不一致时返回 false，全部一致返回 true

3、代码​

function checkXMatrix(grid: number[][]): boolean {
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if ((i === j || i + j === grid.length - 1) !== !!grid[i][j]) return false;
        }
    }

    return true;
};

4、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Problem: 1277. 统计全为 1 的正方形子矩阵

2、方法1​

前缀和+暴力枚举

3、Code​

function countSquares(matrix: number[][]): number {
    const preSum = matrix.map(m => m.map(() => 0));

    for (let i = 0; i < matrix.length; i++) {
        let sumRow = 0;
        for (let j = 0; j < matrix[0].length; j++) {
            sumRow += matrix[i][j];
            preSum[i][j] = sumRow + (i ? preSum[i - 1][j] : 0);
        }
    }

    let ans = 0;

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            for (let k = 1; k <= j + 1; k++) {
                const sr = i - k > -1 ? preSum[i - k][j] : 0;
                const sc = preSum[i][j - k] || 0;
                const src = i - k > -1 && j - k > -1 ? preSum[i - k][j - k] : 0;
                const s = preSum[i][j] - sr - sc + src;
                if (s !== k ** 2) break;
                ans++;
            }
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

5、执行结果​

6、方法2​

动态规划

7、Code​

function countSquares(matrix: number[][]): number {
    let ans = 0;

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (i && j && matrix[i][j]) matrix[i][j] = Math.min(matrix[i][j - 1], matrix[i - 1][j], matrix[i - 1][j - 1]) + 1;
            ans += matrix[i][j];
        }
    }

    return ans;
};

8、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

9、执行结果​

1、题干​

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间
• '#' 代表一堵墙
• '@' 是起点
• 小写字母代表钥匙
• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

输入：grid = ["@.a..","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。

示例 2：

输入：grid = ["@..aA","..B#.","....b"]
输出：6

示例 3:

输入: grid = ["@Aa"]
输出: -1

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'
• 钥匙的数目范围是 [1, 6] 
• 每个钥匙都对应一个 不同 的字母
• 每个钥匙正好打开一个对应的锁

Problem: 864. 获取所有钥匙的最短路径

2、思路​

写过最长的代码，心态崩了

思路：

• 回溯，对所有钥匙进行排列组合，得到所有路径（不校验路径是否连通）
• 遍历所有路径，累计从起点经过所有钥匙需要的步数，结果取最小步数
• 广搜计算两把钥匙之间的最短路径（需要校验路径是否连通）

3、Code​

function shortestPathAllKeys(grid: string[]): number {
    const m = grid.length, n = grid[0].length;

    const M = 10007;
    const encode = (i: number, j: number) => i * M + j;
    const decode = (d: number) => [(d / M) >> 0, d % M];

    let start = 0;
    const keys: number[] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === "@") start = encode(i, j);
            if (grid[i][j] >= "a" && grid[i][j] <= "f") keys.push(encode(i, j));
        }
    }

    // 寻找两把钥匙之间的最短路径
    function bfs(source: number, target: number, visited: Set<number>, foundKeys: Set<string>): number {
        let queue = [source];
        const [ti, tj] = decode(target);

        let step = 1;
        while (queue.length) {
            const nextQueue = new Set<number>();

            for (const q of queue) {
                if (visited.has(q)) continue;
                visited.add(q);

                const [qi, qj] = decode(q);
                const dirs = [[qi, qj + 1], [qi, qj - 1], [qi + 1, qj], [qi - 1, qj],];

                for (const [i, j] of dirs) {
                    if (!grid[i] || !grid[i][j] || grid[i][j] === "#") continue;
                    if (grid[i][j] >= "A" && grid[i][j] <= "F" && !foundKeys.has(grid[i][j].toLowerCase())) continue;
                    if (i === ti && j === tj) return step;

                    nextQueue.add(encode(i, j));
                }
            }

            step++;
            queue = [...nextQueue];
        }

        return 0;
    }

    // 遍历所有路径，累计从起点经过所有钥匙需要的步数，结果取最小步数
    let res = Infinity;
    function calcSteps(path: Set<number>) {
        let step = 0, source = start, foundKeys = new Set<string>();

        for (const p of path) {
            const st = bfs(source, p, new Set(), foundKeys);
            step += st;
            if (!st || step >= res) return;

            const [pi, pj] = decode(p);
            foundKeys.add(grid[pi][pj]);
            source = p;
        }

        if (step < res) res = step;
    }

    // 对钥匙进行排列组合
    function dfs(path: Set<number>) {
        for (const k of keys) {
            if (path.has(k)) continue;
            path.add(k);
            dfs(path);
            if (path.size === keys.length) calcSteps(path);
            path.delete(k);
        }
    }

    dfs(new Set());

    return res === Infinity ? -1 : res;
}

4、复杂度​

• 时间复杂度：$O(k!*mn)$
• 空间复杂度：$O(mn)$

5、执行结果​

1、题干​

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的 四叉树 的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

• val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
• isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
3. 使用适当的子网格递归每个子节点。

如果你想了解更多关于四叉树的内容，可以参考 wiki 。

四叉树格式：

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。

示例 2：

输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：

提示：

1. n == grid.length == grid[i].length
2. n == 2x 其中 0 <= x <= 6

2、解题思路​

日常吐槽翻译，题目看了老半天

题目意思是要把 $n * n$ 矩阵分割成 $4$ 等份（左上、右上、左下、右下）；分割之后返回一个 Node，Node 初始化要确定 $3$ 个值：val、isLeaf、children（$4$ 个子节点）；如果 Node 不是叶子节点就接着递归分割它的 $4$ 个子节点对应的子矩阵。

• children：可以先递归求出 $4$ 个子节点，当前节点是否有子节点由 isLeaf 决定
• val：所有子节点的 val 之和除以 $4$ 并向上取整（也可以向下取整）
• isLeaf：所有子节点的 val 之和是 $4$ 或 $0$，且所有子节点都是叶子节点

矩阵大小是$n * n(n = 2 ^ x, 0 <= x <= 6)$，矩阵最小是 $1*1$ 最大是 $64*64$，因此除最小矩阵外所有矩阵都可以被 $4$ 等分，没有其他特殊情况需要处理

3、代码​

var construct = function (grid) {
    const n = grid.length;

    function dfs(i0, i1, j0, j1) {
        if (i0 === i1 && j0 === j1) return new Node(grid[i0][j0], true);

        // 递归求出4个子节点
        const mi = Math.floor(i1 / 2 + i0 / 2), mj = Math.floor(j1 / 2 + j0 / 2);
        const tl = dfs(i0, mi, j0, mj);
        const tr = dfs(i0, mi, mj + 1, j1);
        const bl = dfs(mi + 1, i1, j0, mj);
        const br = dfs(mi + 1, i1, mj + 1, j1);

        const children = [tl, tr, bl, br];
        // 求出所有子节点的 val 之和
        const val = children.reduce((a, c) => a + c.val, 0);
        // isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点 
        const isLeaf = (val % 4 === 0) && children.every((n) => n.isLeaf);

        // node.val：所有子节点的 val 之和除以 4 并向上取整
        // node.isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点
        // 4个子节点：当前节点是否有子节点由 isLeaf 决定
        return new Node(Math.ceil(val / 4), isLeaf, ...(isLeaf ? [] : children));
    }

    return dfs(0, n - 1, 0, n - 1);
};

4、执行结果​