Press "Enter" to skip to content

Posts tagged as “medium”

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

花花酱 LeetCode 2012. Sum of Beauty in the Array

数据规模比较大,算法必须是O(n)的。

可以预先使用O(n)时间计算nums[0] .. nums[i]的最大值,存在left[i]中,以及nums[i] .. nums[n-1]的最小值存在right[i]中。然后再按题目的定义计算即可。

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

花花酱 LeetCode 1992. Find All Groups of Farmland

已经告诉你所有的农田都是规整的矩形,题目难度一下子降低了。
对于每一个农田的左上角,找到它的宽度和高度即可。
然后把整个农田矩形标记为林地/非农田即可。

时间复杂度:O(m*n) 每个格子最多遍历3遍。
空间复杂度:O(1)