第 495 场周赛Q1~Q2

题目链接Q13884. 双端字符匹配简单Q23885. 设计事件管理器中等算法原理Q1解法枚举一半即可时间复杂度O(N)1ms击败98.97%由于在左边枚举时找的是“左右”那么枚举右边时找的就是“右左”这本质是一样的因此仅需枚举一半即可Q2解法懒删除堆时间复杂度O(N)219ms击败66.82%用一个堆维护所有的活跃事件堆的排序规则①优先级降序②优先级相同时eventId升序updatePriority把新的(eventId, newPriority)数据扔堆里pollHighest如果堆顶优先级低说明是个旧数据直接弹出Java代码Q1class Solution { public int firstMatchingIndex(String s) { int ns.length(); for(int i0;in/2;i) if(s.charAt(i)s.charAt(n-1-i)) return i; return -1; } }Q2class EventManager { //存储当前活跃事件的envenId→最新优先级保证数据的最终有效性 private final MapInteger,Integer eventPriorityMap; private final PriorityQueueint[] heap; public EventManager(int[][] events) { eventPriorityMapnew HashMap(); //自定义排序①优先级降序②优先级相同时eventId升序 heapnew PriorityQueue((a,b)-{ if(a[1]!b[1]) return b[1]-a[1]; return a[0]-b[0]; }); //初始化事件 for(int[] event:events){ int eventIdevent[0]; int priorityevent[1]; eventPriorityMap.put(eventId,priority); heap.offer(new int[]{eventId,priority}); } } public void updatePriority(int eventId, int newPriority) { eventPriorityMap.put(eventId,newPriority); heap.offer(new int[]{eventId,newPriority}); } public int pollHighest() { //清除堆中无效旧数据 while(!heap.isEmpty()){ int[] topheap.peek(); int eventIdtop[0]; int heapPrioritytop[1]; //校验堆顶数据是否有效事件仍活跃且优先级与最新值一致 if(eventPriorityMap.containsKey(eventId)eventPriorityMap.get(eventId)heapPriority){ //有效数据移除事件并返回 eventPriorityMap.remove(eventId); heap.poll(); return eventId; }else{ //无效数据直接丢弃 heap.poll(); } } //无活跃事件 return -1; } } /** * Your EventManager object will be instantiated and called as such: * EventManager obj new EventManager(events); * obj.updatePriority(eventId,newPriority); * int param_2 obj.pollHighest(); */