Проверка идеального прямоугольника

При отправке этого вопроса я обнаружил, что кто-то уже сформулировал этот вопрос на python, вот моя реализация java для Совершенный прямоугольник-вызов

вызов:

Учитывая массив прямоугольников, где прямоугольники[i] знак равно [xi, yi, ai, bi] представляет собой прямоугольник с выравниванием по оси. Левая нижняя точка прямоугольника — это (xi, yi), а верхняя правая точка — (ai, bi).

Верните true, если все прямоугольники вместе образуют точное покрытие прямоугольной области.

(подробнее по ссылке выше)

Примечание: моя реализация требует как минимум Java 11

Решение начального класса (из leetcode):

/**
 * https://leetcode.com/problems/perfect-rectangle/
 */
public class Solution {

    //Assesment: given method within given class from leetcode - this interface may not be modified
    public boolean isRectangleCover(int[][] input) {
        InputProvider inputProvider = new InputProvider();
        inputProvider.handle(input);
        ArrayDeque<Rectangle> rectangles = inputProvider.getRectangles();
        PerfectRectangleChecker perfectRectangleChecker = new PerfectRectangleChecker(inputProvider.getBounds());
        return perfectRectangleChecker.check(rectangles);
    }

класс Point

public class Point {

    public final int x;
    public final int y;

    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

класс Rectangle

public class Rectangle {

    public final Point[] points;
    public final int area;

    public Rectangle(int x0, int y0, int x1, int y1) {
        points = new Point[4];
        points[0] = new Point(x0,y0);
        points[1] = new Point(x1,y0);
        points[2] = new Point(x0,y1);
        points[3] = new Point(x1,y1);
        area = (x1-x0)*(y1-y0);
    }
    public Rectangle(int[] input) {
        this(input[0],input[1],input[2],input[3]);
    }

}

класс InputProvider

public class InputProvider {

    private final ArrayDeque<Rectangle> rectangles = new ArrayDeque<>();
    private int boundsX0 = Integer.MAX_VALUE;
    private int boundsY0 = Integer.MAX_VALUE;
    private int boundsX1 = Integer.MIN_VALUE;
    private int boundsY1 = Integer.MIN_VALUE;

    public void handle(int[][] input) {
        Arrays.stream(input).forEach(this::processInput);
    }

    public void processInput(int[] input){
        rectangles.add(new Rectangle(input));
        updateBounds(input);
    }

    public ArrayDeque<Rectangle> getRectangles() {
        return rectangles;
    }

    public Rectangle getBounds() {
        return new Rectangle(boundsX0, boundsY0, boundsX1, boundsY1);
    }

    private void updateBounds(int[] input) {
        boundsX0 = Math.min(input[0], boundsX0);
        boundsY0 = Math.min(input[1], boundsY0);
        boundsX1 = Math.max(input[2], boundsX1);
        boundsY1 = Math.max(input[3], boundsY1);
    }

}

класс PerfectRectangleChecker

public class PerfectRectangleChecker {

    private final HashSet<Point> disjunctiveCorners = new HashSet<>();
    private final Rectangle bounds;
    private int area;

    public PerfectRectangleChecker(Rectangle bounds) {
        this.bounds = bounds;
    }

    public boolean check(ArrayDeque<Rectangle> rectangles) {
        for (Rectangle r : rectangles) {
            processRectangles(r);
        }

        if (isAreaMismatching()){
            return false;
        }

        if (boundsMismatchDisjunctivePoints()){
            return false;
        }

        if(disjunctiveCornersMismatchAmount()){
            return false;
        }

        //not simplified return statement to emphasize the three checks performed
        return true;


    }

    private boolean disjunctiveCornersMismatchAmount() {
        return disjunctiveCorners.size() != 4;
    }

    private boolean boundsMismatchDisjunctivePoints() {
        return Arrays.stream(bounds.points).anyMatch(Predicate.not(disjunctiveCorners::contains));
    }

    private boolean isAreaMismatching() {
        return area != bounds.area;
    }

    private void processRectangles(Rectangle r) {
        area = area + r.area;
        Arrays.stream(r.points).forEach(this::processDisjunctiveCorners);
    }

    private void processDisjunctiveCorners(Point p) {
        if (disjunctiveCorners.contains(p)) {
            disjunctiveCorners.remove(p);
        } else {
            disjunctiveCorners.add(p);
        }
    }
}

Тесты:

public class SolutionTest {

    final static int[][] VALID_DATA = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
    final static int[][] INVAILD_DATA = {{0,0,1,1},{0,0,2,1},{1,0,2,1},{0,2,2,3}};

    @Test
    public void testValidInput() {
        Solution solution = new Solution();
        Assert.assertTrue( solution.isRectangleCover(VALID_DATA) );
    }

    @Test
    public void testInvalidInput() {
        Solution solution = new Solution();
        Assert.assertFalse(solution.isRectangleCover(INVAILD_DATA) );
    }

    //more test after more data is provided
}

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *