周赛 24/3/24

第三题 100258 3092. 最高频率的 ID

  • 题目大意：给定两个长度为n的整数数组nums和freq，nums中的每个元素表示一个ID，对应的freq中的元素表示这个ID在集合中此次操作后需要增加或者减少的数目。现要求在每一步操作后，返回出现频率最高的ID数目，若集合为空则为0。

SortedList实现

 from sortedcontainers import SortedList
 class Solution:
     def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
         sl = SortedList(key = lambda x : -x)
         d = defaultdict(int)
         ret = []
         for x,y in zip(nums, freq):
             if d[x]!=0:
                 sl.remove(d[x])
                 d[x]+=y
                 sl.add(d[x])
             else:
                 d[x]=y
                 sl.add(d[x])
             if sl:
                 ret.append(sl[0])
             else:
                 ret.append(0)
         return ret

heap 实现

  • 实现思路：

    • 使用一个字典d来动态记录ID的出现频率，初始化一个空堆heap和结果列表ret。

    • 遍历nums和freq数组，对于每对nums[i]和freq[i]，更新字典d中对应ID的频率。

    • 将(-d[x], x)元组加入堆heap，其中-d[x]表示ID x的出现频率的相反数，x表示ID本身。堆按照频率从高到低排序。

    • 进入循环，检查堆顶元素是否满足当前频率，若不满足则弹出直至满足。

    • 将当前堆顶元素的频率加入结果列表ret。

    • 返回结果列表ret。

 class Solution:
     def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
         d = defaultdict(int)
         heap = []
         ret = []
         for x,y in zip(nums, freq):
             d[x]+=y
             heapq.heappush(heap, (-d[x], x))
             while True:
                 tx, ty = heap[0]
                 if -tx != d[ty]:
                     heapq.heappop(heap)
                     continue
                 ret.append(-tx)
                 break
         return ret

第四题 1002683093. 最长公共后缀查询

Trie树

  • 题目大意： 给定两个字符串数组wordsContainer和wordsQuery，对于每个wordsQuery[i]，需要从wordsContainer中找到一个与wordsQuery[i]有最长公共后缀的字符串。若有多个满足条件的字符串，选择长度最短的一个，若长度相同则选择在wordsContainer中出现较早的一个。返回一个整数数组ans，其中ans[i]表示wordsContainer中与wordsQuery[i]有最长公共后缀的字符串的下标。

  • 实现思路：

    1. 初始化一个变量mi记录wordsContainer中最短字符串的长度，并记录其下标为idx。
    2. 构建字典trie，用于存储wordsContainer中每个字符串的逆序形式，并记录最短字符串的下标和长度。
    3. 遍历wordsQuery，对于每个查询字符串，将其逆序，然后在trie中搜索与之匹配的最长公共后缀，并返回其对应的下标。
    4. 将所有查询结果存入结果列表ret，并返回。
 class Solution:
     def stringIndices(self, c: List[str], q: List[str]) -> List[int]:
         mi = inf
         idx = -1
         ret = []
         for i, w in enumerate(c):
             if len(w)<mi:
                 mi = len(w)
                 idx = i
         trie = {} #dict
         for i, w in enumerate(c):
             w=w[::-1]
             cur=trie
             for wi in w:
                 if wi not in cur:
                     cur[wi] = {}
                 cur = cur[wi]
                 if '#' not in cur:
                     cur['#'] = (i, len(w))
                 elif len(w)<cur['#'][1]:
                     cur['#'] = (i,len(w))
         for i, w in enumerate(q):
             w=w[::-1]
             cur = trie
             ans = idx
             for wi in w:
                 if wi not in cur:
                     break
                 else:
                     cur = cur[wi]
                     ans = cur['#'][0]
             ret.append(ans)
         return ret