Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間8月前 (2025/03/25 23:42)推噓2(2推 0噓 0→)

https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections 3394. Check if Grid can be Cut into Sections 給你一個數字n表示n*n的二維空間，rectangles[i] = [startx, starty, endx, endy] 表示多個矩形的左下角座標和右上角座標，求出我們是否可以將這個空間切成三塊(橫或縱切)，使每個矩形不橫跨其他區域且每個區域至少有一個矩形。 https://assets.leetcode.com/uploads/2024/10/23/tt1drawio.png

思路: 跟昨天那題類似，我們把每個矩形的橫座標和縱座標看成一個區間，然後把交集的區域兩兩合併，可以得到橫切或縱切的不交合區間，如果最後剩下的區間大於等於3個只要隨變挑兩個縫縫切下去就變成合法的三塊了，比較需要注意的是 [1,2] 和 [2,3] 不算是交合所以要用 <= 判斷。 Java Code: --------------------------------------------------- class Solution { public boolean checkValidCuts(int n, int[][] rectangles) { List<int[]> xInterval = new ArrayList<>(); List<int[]> yInterval = new ArrayList<>(); for (int[] rectangle : rectangles) { xInterval.add(new int[]{rectangle[0], rectangle[2]}); yInterval.add(new int[]{rectangle[1], rectangle[3]}); } xInterval.sort(Comparator.comparingInt(x -> x[0])); yInterval.sort(Comparator.comparingInt(x -> x[0])); List<int[]> mergedInterval = new ArrayList<>(); mergedInterval.add(xInterval.get(0)); for (int[] interval : xInterval) { int[] last = mergedInterval.get(mergedInterval.size() - 1); if (last[1] <= interval[0]) { mergedInterval.add(new int[]{interval[0], interval[1]}); } else { last[1] = Math.max(last[1], interval[1]); } } if (mergedInterval.size() >= 3) { return true; } mergedInterval = new ArrayList<>(); mergedInterval.add(yInterval.get(0)); for (int[] interval : yInterval) { int[] last = mergedInterval.get(mergedInterval.size() - 1); if (last[1] <= interval[0]) { mergedInterval.add(new int[]{interval[0], interval[1]}); } else { last[1] = Math.max(last[1], interval[1]); } } return mergedInterval.size() >= 3; } } --------------------------------------------------- -- https://i.imgur.com/ZfdGodg.jpeg