给定一些矩形2 求覆盖面积矩形不超过200个

1#

算法1 朴素思想虽然朴素但是代码却有意思

利用容斥原理

复杂度高达 N*2^N

class Solution:

    def intersect(rec1,rec2):

        return [max(rec1[1],rec2[1]),

                    max(rec1[2],rec2[2]),

                    min(rec1[3],rec2[3]),

                    min(rec1[4],rec2[4]

                    ]

#这里是两个矩形的两点式求 矩形的相交子矩形 *非常值得思考

    def area(rec):

        dx=max(0,rec[2]-rec[0])

        dy=max(0,rec[3]-rec[1])

        return dx*dy

    ans=0

    for size in range(1,len(rectangles)+1):

        for group in itertools.combinations(rectangles,size):

            ans = ans +(-1)** (size+1) * area(reduce(intersect,group))

    return ans%mod

2#

点位压缩，压缩后进行暴力循环

同时压缩x和y

最后返回

class Solution(object):

    def rectangleArea(self, rectangles):

        N = len(rectangles)

        Xvals, Yvals = set(), set()

        for x1, y1, x2, y2 in rectangles:

            Xvals.add(x1); Xvals.add(x2)

            Yvals.add(y1); Yvals.add(y2)

        imapx = sorted(Xvals)

        imapy = sorted(Yvals)

        mapx = {x: i for i, x in enumerate(imapx)}

        mapy = {y: i for i, y in enumerate(imapy)}

        grid = [[0] * len(imapy) for _ in imapx]

        for x1, y1, x2, y2 in rectangles:

            for x in xrange(mapx[x1], mapx[x2]):

                for y in xrange(mapy[y1], mapy[y2]):

                    grid[x][y] = 1

        ans = 0

        for x, row in enumerate(grid):

            for y, val in enumerate(row):

                if val:

                    ans += (imapx[x+1] - imapx[x]) * (imapy[y+1] - imapy[y])

        return ans % (10**9 + 7)

N^3

3#

算法3 扫描线算法

将每一个矩形看作一个 "事件" 这样的事件

class Solution(object):

    def rectangleArea(self, rectangles):

        # Populate events

        OPEN, CLOSE = 0, 1

        events = []

        for x1, y1, x2, y2 in rectangles:

            events.append((y1, OPEN, x1, x2))

            events.append((y2, CLOSE, x1, x2))

        events.sort()

        def query():

            ans = 0

            cur = -1

            for x1, x2 in active:

                cur = max(cur, x1)

                ans += max(0, x2 - cur)

                cur = max(cur, x2)

            return ans

        active = []

        cur_y = events[0][0]

        ans = 0

        for y, typ, x1, x2 in events:

            # For all vertical ground covered, update answer

            ans += query() * (y - cur_y)

            # Update active intervals

            if typ is OPEN:

                active.append((x1, x2))

                active.sort()

            else:

                active.remove((x1, x2))

            cur_y = y

        return ans % (10**9 + 7)

4#

注意到刚才的3算法中使用了区间维护的算法这里使用线段树维护这个区间

使得达到 NlogN

下面是py 实现线段树

class Node:

    def __init__(self,start,end):

        self.start=start

        self.end=end

        self.mid=(start+end)//2

        self.active_count=0

        self.totle =0

        self._left=None

        self._right=None

    @property

    def right(self):

        self._right= self._right or Node(self.mid,self.end)

        return self._right

    @property

    def left(self):

        self._left=self._left or Node(self.start,self.mid)

        return self._left

    #更新 i j 合适的区域 + val

    #同时返回 i j 之间的x大小

    def update(self,i,j,val):

        print(str(i)+" "+str(j))

        if(i>=j):

            return 0

        if(i==self.start and j==self.end):

            self.active_count = self.active_count + val

        else:

            self.left .update( i,  min( self.mid ,j )  , val )

            self.right.update( max(self.mid,i)       ,j, val ) 

        #当前区域有 至少一个覆盖

        if(self.active_count>0):

            self.totle= X[self.end]-X[self.start]

        else:

            self.totle= self.left.totle + self.right.totle 

        return self.totle 

class Solution:

    def rectangleArea(self, rectangles):

        """

        :type rectangles: List[List[int]]

        :rtype: int

        """

        ACTIVE = 1

        DEACTIVE = -1

        global X

        X=set()

        events=[]

        for rect in rectangles:

            X.add(rect[0])

            X.add(rect[2])

            events.append([rect[1],rect[0],rect[2],ACTIVE])

            events.append([rect[3],rect[0],rect[2],DEACTIVE])

        X=sorted(X)

        events=sorted(events)

        pos2idx={ x:i for i,x in enumerate(X) }        

        sum_area=0

        y_cur=0

        y_cur_next=0

        x_cur=0

        SegNode = Node(0,len(pos2idx))

        print(pos2idx)

        for event in events:

            y_cur_next=event[0]

            sum_area=sum_area+(y_cur_next-y_cur)*x_cur

            x_cur=SegNode.update(pos2idx[event[1]],pos2idx[event[2]],event[3])

            print(event)

            print(x_cur)

            y_cur=y_cur_next

        return sum_area%(1000000000 + 7)

注意这里的下标实际意义不是容器而是标志

所以会有

start mid

mid end

这样的划分方法应该注意

另外利用python 的 property 很方便的写出了懒申请策略

(python 做点集压缩真的方便

付：

leetcode 56. Merge Intervals On 求overlap

巴特西

leetcode 850. Rectangle Area II

1#

2#

3#

4#

最新文章

热门文章