leetcode - LCP 42. 玩具套圈 -二分 -坐标映射 -区间查找 - 坐标范围快速查找

LCP 42. 玩具套圈

「力扣挑战赛」场地外，小力组织了一个套玩具的游戏。所有的玩具摆在平地上，toys[i] 以 [xi,yi,ri] 的形式记录了第 i 个玩具的坐标 (xi,yi) 和半径 ri。小扣试玩了一下，他扔了若干个半径均为 r 的圈，circles[j] 记录了第 j 个圈的坐标 (xj,yj)。套圈的规则如下：

若一个玩具被某个圈完整覆盖了（即玩具的任意部分均在圈内或者圈上），则该玩具被套中。
若一个玩具被多个圈同时套中，最终仅计算为套中一个玩具
请帮助小扣计算，他成功套中了多少玩具。

注意：

输入数据保证任意两个玩具的圆心不会重合，但玩具之间可能存在重叠。
示例 1：

输入：toys = [[3,3,1],[3,2,1]], circles = [[4,3]], r = 2

输出：1

解释： 如图所示，仅套中一个玩具

示例 2：

输入：toys = [[1,3,2],[4,3,1],[7,1,2]], circles = [[1,0],[3,3]], r = 4

输出：2

解释： 如图所示，套中两个玩具

提示：

1 <= toys.length <= 10^4
0 <= toys[i][0], toys[i][1] <= 10^9
1 <= circles.length <= 10^4
0 <= circles[i][0], circles[i][1] <= 10^9
1 <= toys[i][2], r <= 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/vFjcfV

解法1 - 给定圈，找套中的玩具 - 超时

tips

• 将玩具按照左边界从小到大排序
• 计算每一个圈能覆盖哪些玩具，能覆盖掉的玩具 标记为visited
• 计算标记为visited的玩具数目并返回

'''
超时
通过 28/39 个用例
'''

class Solution1:
    def circleGame(self, toys, circles, r: int) -> int:
        '''
        映射玩具的左边界x坐标到坐标轴,从小到大排列
        '''
        nt = len(toys)
        toys.sort(key=lambda x: x[0] - x[2])
        visited = [False]*nt
        '''
        淘汰不在圈内的玩具
        '''
        for cx,cy in circles:
            for i,(tx,ty,tr) in enumerate(toys):
                if tx-tr>cx+r:break
                if tx-tr <cx-r or tx+tr>cx+r or ty-tr<cy-r or ty+tr>cy+r or visited[i]:continue
                if (cx-tx)**2+(cy-ty)**2 > (r-tr)**2:continue
                visited[i]=True
        return len(list(filter(lambda x:x,visited)))

解法 2 - 给定玩具找能套中它的圈 - 超时

在解法1上进行优化

• 用字典来记录圈和玩具左边界
• 记录每一个圈覆盖到的x
• 判断每一个玩具是否能被附近的圈套住
• 根据x范围 快速找玩具附近的圈 xys[tx-tr]['id'],xys[tx+tr]['id']+1
• 一个x对应多个圈的时候，将圈按照下边界排序，线性查找

'''
超时
通过 36/39 个用例
'''
class Solution1:
    def circleGame(self, toys, circles, r: int) -> int:
        '''
        映射玩具和圈的左边界x坐标到坐标轴,从小到大排列
        '''
        nt = len(toys)

        tc = toys + [circle+[r] for circle in circles]
        x12 = {xx for x in tc for xx in [x[0]-x[2],x[0]+x[2]]}
        x12 = sorted(x12)
        '''
        映射圈的y坐标到坐标轴，加入到对应x的坐标中
        '''
        xys = {x:{'id':i,'cs':[],} for i,x in enumerate(x12)}
        circles.sort(key=lambda x:x[0]-r)
        for cx,cy in circles:
            for i in range(xys[cx - r]['id'], xys[cx + r]['id'] + 1):
                xys[x12[i]]['cs'].append([cx,cy])
        visited = [False]*nt

        '''
        判断每一个玩具能否被圈套中
        '''
        for i,(tx,ty,tr) in enumerate(toys):
            flag = False
            for j in range(xys[tx-tr]['id'],xys[tx+tr]['id']+1):
                for cx,cy in xys[x12[j]]['cs']:
                    if tx - tr < cx - r or tx + tr > cx + r or ty - tr < cy - r or ty + tr > cy + r or visited[
                        i]: continue
                    if (cx-tx)**2+(cy-ty)**2 <= (r-tr)**2:
                        flag = True
                        break
                if flag:break
            visited[i] = flag
        '''
        淘汰不在圈内的玩具
        '''
        return len(list(filter(lambda x:x,visited)))

解法 3 解法2的基础上加入 二分查找区间 - 通过

在解法2上进行优化

• 一个x对应多个圈的时候，将圈按照下边界排序，用二分进行查找

'''
优化 判断玩具是否被圈覆盖的时候加入二分
'''
class Solution:
    def circleGame(self, toys, circles, r: int) -> int:
        '''
        映射玩具和圈的左边界x坐标到坐标轴,从小到大排列
        '''
        nt = len(toys)

        tc = toys + [circle+[r] for circle in circles]
        x12 = {xx for x in tc for xx in [x[0]-x[2],x[0]+x[2]]}
        x12 = sorted(x12)
        '''
        映射圈的y坐标到坐标轴，加入到对应x的坐标中
        '''
        xys = {x:{'id':i,'cs':[],} for i,x in enumerate(x12)}
        circles.sort(key=lambda x:x[1]-r)
        for cx,cy in circles:
            for i in range(xys[cx - r]['id'], xys[cx + r]['id'] + 1):
                xys[x12[i]]['cs'].append([cx,cy])
        visited = [False]*nt

        '''
        判断每一个玩具能否被圈套中
        '''
        for i,(tx,ty,tr) in enumerate(toys):
            flag = False
            for j in range(xys[tx-tr]['id'],xys[tx+tr]['id']+1):
                ll = 0
                rr = len(xys[x12[j]]['cs'])-1
                while ll<=rr:
                    mid = (ll+rr)//2
                    cx,cy = xys[x12[j]]['cs'][mid]
                    if cy-r>ty-tr:
                        rr = mid-1
                        continue
                    if cy +r<ty+tr:
                        ll =mid+1
                        continue
                    for mid in range(ll,rr+1):
                        cx, cy = xys[x12[j]]['cs'][mid]
                        if (cx-tx)**2+(cy-ty)**2 <= (r-tr)**2:
                            flag = True
                            break
                    break
                if flag:break
            visited[i] = flag
        '''
        淘汰不在圈内的玩具
        '''
        return len(list(filter(lambda x:x,visited)))

解法4 - 解法2的基础上 映射x的同时映射y

• 在解法2的基础上，将y映射到y轴，也用字典记录下来，找到一个x的时候，可以快速锁定一个小的y的区间范围 ，从而替代用二分去找y这个操作