Untitled
unknown
java
9 months ago
2.4 kB
5
Indexable
class Solution { public static Node construct(int[][] grid) { int n = grid.length; return construct(grid, 0, 0, n - 1, n - 1); } private static Node construct(int[][] grid, int x1, int y1, int x2, int y2) { if (x1 < 0 || x1 >= grid.length || x2 < 0 || x2 >= grid.length || y1 < 0 || y1 >= grid.length || y2 < 0 || y2 >= grid.length || x1 > x2 || y1 > y2) { return null; } if (x1 == x2 && y1 == y2) { System.out.println("Match at " + x1 + " - " + y1 + " - value " + grid[x1][y1]); return new Node(grid[x1][y1] == 1, true); } int newX2 = x1 + (x2 - x1)/2; int newY2 = y1 + (y2 - y1)/2; Node topLeft = construct(grid, x1, y1, newX2 , newY2); int newY1 = y1 + (y2 - y1)/2 + 1; newX2 = x1 + (x2 - x1)/2; Node topRight = construct(grid, x1, newY1, newX2, y2); int newX1 = x1 + (x2 - x1)/2 + 1; newY2 = y1 + (y2 - y1)/2; Node bottomLeft = construct(grid, newX1, y1, x2, newY2); newX1 = x1 + (x2 - x1)/2 + 1; newY1 = y1 + (y2 - y1)/2 + 1; Node bottomRight = construct(grid, newX1, newY1, x2, y2); if (topLeft == null && topRight == null && bottomLeft == null && bottomRight == null) { return new Node(grid[x1][y1] == 1, true); } if (topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) { return new Node(topLeft.val, true, topLeft, topRight, bottomLeft, bottomRight); } return new Node(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight); } public static void main(String[] args) { int grid[][] = {{1,1,0,0},{1,1,0,0},{0,0,1,1},{0,0,1,1}}; Node node = construct(grid); System.out.println(node.isLeaf + " - " + node.val); System.out.println("Top Left " + node.topLeft.isLeaf + " - " + node.topLeft.val); System.out.println("Top Right " + node.topRight.isLeaf + " - " + node.topRight.val); System.out.println("Bottom Left " + node.bottomLeft.isLeaf + " - " + node.bottomLeft.val); System.out.println("Bottom Right " + node.bottomRight.isLeaf + " - " + node.bottomRight.val); System.out.println("Top Left " + node.topLeft.topLeft.isLeaf + " - " + node.topLeft.topLeft.val); } }
Editor is loading...
Leave a Comment