成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Rectangle Area 矩形面積

Cheng_Gang / 1562人閱讀

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

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.
數(shù)學(xué)法 復(fù)雜度

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

思路

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

代碼 
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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64477.html

相關(guān)文章

  • leetcode363. Max Sum of Rectangle No Larger Than K

    摘要：思路一暴力循環(huán)如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于的最大值即可。 題目要求 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 評論0 收藏0

  • Largest Rectangle in Histogram

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

    vvpvvp 評論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...

    鄒強(qiáng) 評論0 收藏0

  • leetcode84. Largest Rectangle in Histogram

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

    Harpsichord1207 評論0 收藏0

  • leetcode85. Maximal Rectangle

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

    jhhfft 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<