这是悦乐书的第 224 次更新, 第 237 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 91 题(顺位题号是 427). 我们想使用四叉树来存储 N*N 布尔网格. 网格中的每个单元格只能是 true 或 false. 根节点表示整个网格. 对于每个节点, 它将被细分为四个子节点, 直到它所代表的区域中的值都相同.
每个节点都有另外两个布尔属性: isLeaf 和 val. 当且仅当节点是叶节点时, isLeaf 才为真. 叶节点的 val 属性包含它所代表的区域的值. 您的任务是使用四叉树来表示给定的网格. 例如:
给定下面的 8 x 8 网格, 我们想构建相应的四叉树:
image
它可以根据上面的定义进行划分:
image
相应的四叉树应如下, 其中每个节点表示为 (isLeaf,val) 对.
对于非叶节点, val 可以是任意的, 因此它表示为 *.
image
注意:
N 小于 1000 并保证为 2 的幂.
如果您想了解有关四叉树的更多信息, 可以参考其维基.
02 理解题意
题目中所说的叶节点, 是指值相同的一片区域, 如上图被分成 64 个小格子的第三张图, 左上, 左下和右下都表示了一片值相等的区域, 左上左下都表示了 16 个 1, 右下表示了 16 个 0, 而右上中的 16 个格子, 其中有 8 个 0 和 8 个 1, 只能再进行四等分, 才能分别表示四个值相同的区域, 所以右上区域不是叶节点, 它的 isLeaf 属性就为 false. 可以看到最后这张图, 根节点不是叶节点, 所以其 isLeaf 也为 false, 而其他叶节点的 isLeaf 都为 true.
03 第一种解法
题目给的参数是一个二维数组, 可以将其想象为一个 N*N 的格子, 其索引就是对应位置的坐标, 只要从根节点开始, 遇到和根节点值不一样的坐标, 就需要进行等分操作, 也就是从一个新的 N/2*N/2 格子开始, 再从根节点开始判断. 因此可以借助递归的方法, 只需要两个从 0 开始的索引, 以及二维数组的长度即可(此参数做再分用).
- /*
- // Definition for a QuadTree node.
- class Node {
- public boolean val;
- public boolean isLeaf;
- public Node topLeft;
- public Node topRight;
- public Node bottomLeft;
- public Node bottomRight;
- public Node() {}
- public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
- val = _val;
- isLeaf = _isLeaf;
- topLeft = _topLeft;
- topRight = _topRight;
- bottomLeft = _bottomLeft;
- bottomRight = _bottomRight;
- }
- };
- */
- class Solution {
- public Node construct(int[][] grid) {
- return build(0, 0, grid.length, grid);
- }
- Node build(int x, int y, int len, int[][] grid){
- if (len <0) {
- return null;
- }
- for (int i = x; i < x+len; ++i) {
- for (int j = y; j < y+len; ++j) {
- if (grid[i][j] != grid[x][y]) {
- return new Node(true, false,
- build(x, y, len/2, grid),
- build(x, y + len/2, len/2, grid),
- build(x + len/2, y, len/2, grid),
- build(x + len/2, y + len/2, len/2, grid));
- }
- }
- }
- return new Node(grid[x][y] == 1, true, null, null, null, null);
- }
- }
04 第二种解法
第一种解法是只用两个点来定位区间, 此解法利用四个点来定位区间, 但是思路都是一样的.
- /*
- // Definition for a QuadTree node.
- class Node {
- public boolean val;
- public boolean isLeaf;
- public Node topLeft;
- public Node topRight;
- public Node bottomLeft;
- public Node bottomRight;
- public Node() {}
- public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
- val = _val;
- isLeaf = _isLeaf;
- topLeft = _topLeft;
- topRight = _topRight;
- bottomLeft = _bottomLeft;
- bottomRight = _bottomRight;
- }
- };
- */
- class Solution {
- public Node construct2(int[][] g) {
- return build(0, 0, g.length - 1, g.length - 1, g);
- }
- Node build(int r1, int c1, int r2, int c2, int[][] g) {
- if (r1> r2 || c1> c2) {
- return null;
- }
- boolean isLeaf = true;
- int val = g[r1][c1];
- for (int i = r1; i <= r2; i++)
- for (int j = c1; j <= c2; j++)
- if (g[i][j] != val) {
- isLeaf = false;
- break;
- }
- if (isLeaf) {
- return new Node(val == 1, true, null, null, null, null);
- }
- int rowMid = (r1 + r2)/2;
- int colMid = (c1 + c2)/2;
- return new Node(false, false,
- build(r1, c1, rowMid, colMid, g),
- build(r1, colMid + 1, rowMid, c2, g),
- build(rowMid + 1, c1, r2, colMid, g),
- build(rowMid + 1, colMid + 1, r2, c2, g)
- );
- }
- }
05 小结
算法专题目前已连续日更超过两个月, 算法题文章 91 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/5a3131e0bcb9