94 lines
3.1 KiB
JavaScript
94 lines
3.1 KiB
JavaScript
/* eslint-disable max-len */
|
||
// eslint-disable-next-line no-underscore-dangle
|
||
function _Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight) {
|
||
this.val = val;
|
||
this.isLeaf = isLeaf;
|
||
this.topLeft = topLeft;
|
||
this.topRight = topRight;
|
||
this.bottomLeft = bottomLeft;
|
||
this.bottomRight = bottomRight;
|
||
}
|
||
|
||
/**
|
||
* @param {number[][]} grid
|
||
* @return {_Node}
|
||
*/
|
||
const construct = function (grid) {
|
||
|
||
};
|
||
|
||
/*
|
||
利用分治算法，我们很容易发现当啊n=1时grid一定可以构建成一个叶子节点，val=当前这个位置表示的值，当n=2时也即是由四个n=1的grid组成的，
|
||
我们把它们划分好，然后查看这左上，有伤，左下，右下的这四个四叉树节点的值是否都是叶子节点，如果都是再判断它们的值是否相等，如果是叶子节点
|
||
并且它们的值也相等，就把他们合成一个更大的叶子节点，否则返回这个有叶子节点的四叉树
|
||
*/
|
||
function f1(grid) {
|
||
const n = grid.length;
|
||
return buildNode(grid, 0, n - 1, 0, n - 1);
|
||
}
|
||
|
||
/**
|
||
*
|
||
* @param {*} grid
|
||
* @param {*} start
|
||
* @param {*} end
|
||
*/
|
||
function buildNode(grid, rStart, rEnd, cStart, cEnd) {
|
||
// 如果划分的grid只有一个值，那么这个值就是四叉树的叶子节点
|
||
if (rStart === rEnd) {
|
||
return new _Node(grid[rStart][cStart], 1);
|
||
}
|
||
|
||
// 划分四个区域构建子节点
|
||
const topLeft = buildNode(grid, rStart, rStart + Math.floor((rEnd - rStart) / 2), cStart, cStart + Math.floor((cEnd - cStart) / 2));
|
||
const topRight = buildNode(grid, rStart, rStart + Math.floor((rEnd - rStart) / 2), cStart + Math.floor((cEnd - cStart) / 2) + 1, cEnd);
|
||
const bottomLeft = buildNode(grid, rStart + Math.floor((rEnd - rStart) / 2) + 1, rEnd, cStart, cStart + Math.floor((cEnd - cStart) / 2));
|
||
const bottomRight = buildNode(grid, rStart + Math.floor((rEnd - rStart) / 2) + 1, rEnd, cStart + Math.floor((cEnd - cStart) / 2) + 1, cEnd);
|
||
|
||
// 如果四个节点都是叶子节点，并且值相同将它们合并成一个更大的叶子节点
|
||
if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf && topLeft.val === topRight.val && topRight.val === bottomLeft.val && bottomLeft.val === bottomRight.val) {
|
||
return new _Node(topLeft.val, 1);
|
||
}
|
||
|
||
// 构建一个包含四个节点的非叶子节点
|
||
return new _Node(1, 0, topLeft, topRight, bottomLeft, bottomRight);
|
||
}
|
||
|
||
/*
|
||
优化分治思路
|
||
*/
|
||
function buildNodeBest(grid) {
|
||
const n = grid.length;
|
||
|
||
function dfs(r0, c0, size) {
|
||
// 判断是否整个区域都是同一个值
|
||
const val = grid[r0][c0];
|
||
let same = true;
|
||
for (let i = r0; i < r0 + size; i++) {
|
||
for (let j = c0; j < c0 + size; j++) {
|
||
if (grid[i][j] !== val) {
|
||
same = false;
|
||
break;
|
||
}
|
||
}
|
||
if (!same) break;
|
||
}
|
||
|
||
if (same) {
|
||
return new Node(val === 1, true, null, null, null, null);
|
||
}
|
||
|
||
const half = size / 2;
|
||
return new Node(
|
||
true,
|
||
false,
|
||
dfs(r0, c0, half), // topLeft
|
||
dfs(r0, c0 + half, half), // topRight
|
||
dfs(r0 + half, c0, half), // bottomLeft
|
||
dfs(r0 + half, c0 + half, half), // bottomRight
|
||
);
|
||
}
|
||
|
||
return dfs(0, 0, n);
|
||
}
|