Press "Enter" to skip to content

Huahua's Tech Road

花花酱 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)

花花酱 LeetCode 2023. Number of Pairs of Strings With Concatenation Equal to Target

方法1: Brute Force

枚举所有的(nums[i], nums[j])组合,相加在和target比较。

时间复杂度:O(mn2) m为字符串的最长长度。
空间复杂度:O(m)

优化前 67ms, 49.3M

一些工程上的优化

  • 用string_view作为参数类型,减少一次string copy
  • 先比较长度,再判断内容。
  • string_view.substr 是O(1)时间,和直接用strncmp比较内容是一样的。

优化后 3ms, 12.88MB