关于网站建设的期刊文献,传媒网站后台免费模板,西安建设科技专修学院网站,张家港网站制作公司Leetcode 3479. Fruits Into Baskets III 1. 解题思路2. 代码实现 题目链接#xff1a;3479. Fruits Into Baskets III
1. 解题思路
这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。
因此#xff0c;我们只需要将basket按照其capacit…Leetcode 3479. Fruits Into Baskets III 1. 解题思路2. 代码实现 题目链接3479. Fruits Into Baskets III
1. 解题思路
这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。
因此我们只需要将basket按照其capacity进行排序此时考察每一个水果时我们用二分法即可快速找到某一个坐标idx满足其后任意一个箱子都可以用于盛放该水果。此时我们就要从对应的这些篮子当中找到其原始的坐标最小的位置即可。而这就是一个典型的segment tree的问题了。
对于segment tree网上已经有不少相关的介绍了我自己也写过一篇小文章作为备忘经典算法Segment Tree因此这里就不过多展开了有兴趣的读者可以自行去了解一下。
2. 代码实现
给出python代码实现如下
class SegmentTree:def __init__(self, arr):self.length len(arr)self.tree self.build(arr)def feature_func(self, *args):return min(args)def build(self, arr):n len(arr)tree [0 for _ in range(2*n)]for i in range(n):tree[in] arr[i]for i in range(n-1, 0, -1):tree[i] self.feature_func(tree[2*i], tree[2*i1])return treedef update(self, idx, val):idx idx self.lengthself.tree[idx] valwhile idx 1:self.tree[idx // 2] self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx idx // 2returndef query(self, lb, rb):lb self.length rb self.lengthnodes []while lb rb:if lb % 2 1:nodes.append(self.tree[lb])lb 1if rb % 2 0:nodes.append(self.tree[rb])rb - 1lb lb // 2rb rb // 2if lb rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)class Solution:def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) - int:n len(fruits)ordered_baskets sorted([(cap, idx) for idx, cap in enumerate(baskets)])ordered_baskets_capacity [x[0] for x in ordered_baskets]ordered_baskets_index [x[1] for x in ordered_baskets]segment_tree SegmentTree(ordered_baskets_index)ans 0for fruit in fruits:idx bisect.bisect_left(ordered_baskets_capacity, fruit)if idx n:ans 1continueleft_most_avaliable segment_tree.query(idx, n-1)if left_most_avaliable n:ans 1continuebasket (baskets[left_most_avaliable], left_most_avaliable)idx bisect.bisect_left(ordered_baskets, basket)segment_tree.update(idx, n)return ans提交代码评测得到耗时2398ms占用内存43.9MB。
