Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 3517. Smallest Palindromic Rearrangement I

这题考查的是排序吧… 还有rbegin的使用。

普通排序:时间 O(nlogn) / 空间 O(1)

前半部分顺序排序,后半部分逆序排序。

计数排序:时间:O(n),空间:O(n) -> O(1)

首尾一起写

花花酱 LeetCode 3508. Implement Router

算是比较复杂的题目了,主要考察数据结构的选择和应用。

Note that queries for addPacket will be made in increasing order of timestamp.
把题目简化了不少,注意timestamp可能会想同,非严格单调递增。

forwardPacket 的 FIFO,需要deque或者list
getCount 特定key的范围查询,hashmap + vector / deque
addPacket 需要用hashtable 去重。还要remove最旧的packet,最后的选择落到的deque上。

deque两头可以添加/删除,还能random access做二分搜索,真是居家旅行必备之数据结构。

时间复杂度:addPacket: O(1),forwardPacket:O(1),getCount:O(logN) N为dst的packet数量。
空间复杂度:O(M)

花花酱 LeetCode 2161. Partition Array According to Given Pivot

最直接的方法就是扫描三遍,<, = , > pivot。

时间复杂度:O(n)
空间复杂度:O(1) // no extra space used except for output

花花酱 LeetCode 2024. Maximize the Confusion of an Exam

数据规模高达5 *104,我们只能使用O(n)的算法了。

可以想到的就是滑动窗口(sliding window),由于最长长度未知,我们可以使用动态滑动窗口。

记录当前滑动窗口中T和F出现的次数,如果其中较少的一个<=k,那么就可以全部替换它,使得整个滑动窗口都变成相同的值。如果这个时候滑动窗口长度大于当前最大长度,我们就把滑动窗口变大,右侧+1,并更新最大长度。否则,减少滑动窗口,左侧-1。

时间复杂度:O(n)
空间复杂度:O(2)