asp网站建设运用的技术,做网站总结,定制高端网站建设,网站建设信息平台Leetcode 2940. Find Building Where Alice and Bob Can Meet 1. 解题思路2. 代码实现3. 算法优化 题目链接#xff1a;2940. Find Building Where Alice and Bob Can Meet
1. 解题思路
这一题本质上又是限制条件下求极值的问题#xff0c;算是我最不喜欢的题目类型之一吧…Leetcode 2940. Find Building Where Alice and Bob Can Meet 1. 解题思路2. 代码实现3. 算法优化 题目链接2940. Find Building Where Alice and Bob Can Meet
1. 解题思路
这一题本质上又是限制条件下求极值的问题算是我最不喜欢的题目类型之一吧因为真的挺考验智商的……
很不幸没想到啥好的思路还是分步实现的策略第一步就是找到每一个位置上后续能够访问的全部位置然后第二步就是在对于query的两个位置直接获得他们能够访问的位置然后求公共的最小元素。
显然对于第一个问题我们只需要对原数组进行排序然后从高到低依次插入到有序队列当中此时其插入时队列后方的所有元素就为其能够访问的所有位置。
由此我们就能够在 O ( N ⋅ l o g N ) O(N \cdot logN) O(N⋅logN)的时间复杂度能找到所有坐标上能够访问的所有位置。然后剩下的问题就是如何去找到两个有序数列的最小公共元素。
这里我做了个小trick就是注意到了对于上述问题显然如果两个序列有交集那么显然对于其中起始位置更高的那个序列不妨记作序列A而言其最后一个元素必然也在另一个序列不妨记作序列B当中且满足从某一个位置开始必然有后方元素全在序列B当中而其前方的序列均不在序列A当中。
由此我们就可以使用一个二分搜索来快速找寻上述最小公共坐标了所有query的时间复杂度也为 O ( N ⋅ l o g N ) O(N \cdot logN) O(N⋅logN)。
然而没有想到的是这里居然遇到了内存爆炸的问题就很懵逼……
这里我是通过剪枝和及时删除的方法处理掉了这个问题但是这里多少有点取巧了而且非常的不优雅就很难受了。
所谓剪枝倒是思路还挺自然因为如果有两个坐标 i , j i,j i,j满足 i j ij ij或者 i j ij ij且 h i h j h_i h_j hihj那答案就是 j j j反之亦然。这样我们就可以先去掉很多easy case了。
然后关于及时删除就是首先对query也进行一下排序然后优先做那些可以快速得到后方位置的坐标对应的query然后在他们后续不会再被使用时及时进行删除通过这种方式我们在这道题上面是通过了测试样例不过很取巧就是了……
2. 代码实现
给出python代码实现如下
class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) - List[int]:buildings [(idx, h) for idx, h in enumerate(heights)]buildings sorted(buildings, keylambda x: (x[1], -x[0]), reverseTrue)indexes {x[0]: i for i, x in enumerate(buildings)}res [-1 for _ in queries]queries [(idx, i, j) for idx, (i, j) in enumerate(queries)]for idx, i, j in queries:if i j:res[idx] ielif i j and heights[i] heights[j]:res[idx] jelif i j and heights[i] heights[j]:res[idx] iqueries [(idx, i, j) if indexes[i] indexes[j] else (idx, j, i) for (idx, i, j) in queries if res[idx] -1]queries sorted(queries, keylambda x: indexes[x[2]])trigger defaultdict(list)last_seen defaultdict(int)for idx, i, j in queries:trigger[j].append((idx, i, j))last_seen[i] idxlast_seen[j] idxdef query(i, j):if i j:return ir1, r2 can_reach[i], can_reach[j]n, m len(r1), len(r2)idx bisect.bisect_left(r2, r1[0])if idx m and r1[0] r2[idx]:return r1[0]i 0idx bisect.bisect_left(r2, r1[-1])if idx m or r1[-1] ! r2[idx]:return -1j n-1while i j-1:k (ij) // 2idx bisect.bisect_left(r2, r1[k])if idx m and r1[k] r2[idx]:j kelse:i kreturn r1[j]s []can_reach {}for i, h in buildings:idx bisect.bisect_left(s, i)s.insert(idx, i)if i in last_seen:can_reach[i] s[idx:]for idx, i, j in trigger[i]:res[idx] query(i, j)if last_seen[i] idx:can_reach.pop(i)if j ! i and last_seen[j] idx:can_reach.pop(j)return res提交代码评测得到耗时5336ms占用内存100.2MB。
3. 算法优化
看了一下大佬们的最优解答发现在剪枝这部分大家其实思路是一致的但是在那些复杂case的处理上大佬们的思路实在是太牛了。
他们的思路是直接使用堆排的方式先将所需要比对的位置全部用一个堆排维护起来其实用有序数列也行然后考察每一个位置看它能够作为那些位置的答案。
给出大佬们的实现方法如下
class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) - List[int]:m len(queries)res [-1] * mq []left [[] for _ in heights]for k, (i, j) in enumerate(queries):if i j:i, j j, iif i j or heights[i] heights[j]:res[k] jelse:left[j].append((heights[i], k))h []for i, x in enumerate(heights):while h and h[0][0] x:k heappop(h)[1]res[k] ifor p in left[i]:heappush(h, p)return res提交代码评测得到耗时3680ms占用内存39.5MB。
