[Leetcode] Rectangle Area 矩形面積

Cheng_Gang 發布于2019-08-14 12:26 / 1557人閱讀

摘要：數學法復雜度時間空間思路基本的數學題，考察的是我們能否全面的考慮到所有可能。如果兩個矩形沒有重疊部分，則直接計算兩個矩形面積之和就行了。因為兩個矩形的坐標都可能比對方小，所以我們一共有四種可能情況是不重疊的。

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Rectangle Area Assume that the total area is never beyond the maximum possible value of int.

數學法 復雜度

時間 O(N) 空間 O(1)

思路

基本的數學題，考察的是我們能否全面的考慮到所有可能。如果兩個矩形沒有重疊部分，則直接計算兩個矩形面積之和就行了。如果兩個矩形有重疊部分，則要將重疊部分減去。如何判斷兩個矩形沒有重疊部分呢，如果一個矩形右上角的橫坐標比另一個矩形左下角的橫坐標要小，或者一個矩形右上角的縱坐標比另一個矩形左下角的縱坐標要小，則兩個矩形是不重疊的。因為兩個矩形的坐標都可能比對方小，所以我們一共有四種可能情況是不重疊的。如果重疊的話，計算重疊部分面積就是四個橫坐標中中間那兩個和四個縱坐標中間那兩個。

代碼

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int dup = 0;
        if(C < E || G < A || D < F || H < B){
            dup = 0;
        } else {
            int[] x = {A, C, E, G};
            int[] y = {B, D, F, H};
            Arrays.sort(x);
            Arrays.sort(y);
            dup = (x[2] - x[1]) * (y[2] - y[1]);
        }
        return (C - A) * (D - B) + (G - E)*(H - F) - dup;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64477.html

leetcode363. Max Sum of Rectangle No Larger Than K

摘要：思路一暴力循環如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于的最大值即可。題目要求 Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. E...

nemo 2019-08-16 17:57 評論0 收藏0
Largest Rectangle in Histogram

摘要：而最大的矩形一定滿足兩個邊界的高度小于該矩形的高度這個條件如果不滿足的話，邊界也可以被添加進來計算而不破壞矩形的形狀，此時不為最大，因此找出所有這樣的矩形就一定可以在其中找出面積最大的矩形。 Problem Given n non-negative integers representing the histograms bar height where the width of e...

vvpvvp 2019-07-24 17:33 評論0 收藏0
[Leetcode] Largest Rectangle (in Histogram) 最大矩形

摘要：以此類推，如果一直到棧為空時，說明剛出來的豎條之前的所有豎條都比它自己高，不然不可能棧為空，那我們以左邊全部的寬度作為長方形的寬度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...

鄒強 2019-08-14 12:24 評論0 收藏0
leetcode84. Largest Rectangle in Histogram

摘要：題目要求即找到圖中可以組合而成的面積最大的矩形。從而我們可以知道該矩形在水平方向上的最大擴展程度。也就是說，棧中數據記錄了最遠左側下標，而當前的矩形則是最遠右側下標。當我們不采用數據結構時，尋找和計算的過程需要的時間復雜度。題目要求 Given n non-negative integers representing the histograms bar height where t...

Harpsichord1207 2019-08-15 10:55 評論0 收藏0
leetcode85. Maximal Rectangle

摘要：題目要求輸入一個二維數組，其中代表一個小正方形，求找到數組中最大的矩形面積。思路一用二維數組存儲臨時值的一個思路就是通過存儲換效率。從而省去了許多重復遍歷，提高效率。這里我使用兩個二維數組來分別記錄到為止的最大長度和最大高度。題目要求 Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle ...

jhhfft 2019-08-15 11:04 評論0 收藏0