西维蜀黍的OJ Blog

🐒 Software engineer | 📷 Photographer | 👹 Urban explorer

[Topic] Sum

解析 15 3Sum 排序后,如何保证插入结果集的triplet不重复? Approach 1: 用一个set来记录已经插入结果集的triplet,如果当前triplet已经存   ...


[Topic] Trapping Rain Water

题目 11 Container With Most Water 42 Trapping Rain Water 解析 11 Container With Most Water 面积公式 = min(h[l], h[r]) * (r - l) 判断 height[l] 和 height[r]的大小,如果 height[l] 小,l++,因为此时移动 r,并不会改变结果   ...


[Notes] Array

题目

双指针

在处理数组和链表相关问题时,双指针技巧是经常用到的,双指针技巧主要分为两类:左右指针和快慢指针。

所谓左右指针,就是两个指针相向而行或者相背而行;而所谓快慢指针,就是两个指针同向而行,一快一慢。

快慢指针

左右指针

  ...


[Notes] Sliding Window

滑动窗口算法

说起滑动窗口算法,很多读者都会头疼。这个算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案么。LeetCode 上有起码 10 道运用滑动窗口算法的题目,难度都是中等和困难。该算法的大致逻辑如下:

int left = 0, right = 0;

while (left < right && right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

这个算法技巧的时间复杂度是 O(N),比字符串暴力算法要高效得多。

另外,虽然滑动窗口代码框架中有一个嵌套的 while 循环,但算法的时间复杂度依然是 O(N),其中 N 是输入字符串/数组的长度。

为什么呢?简单说,指针 left, right 不会回退(它们的值只增不减),所以字符串/数组中的每个元素都只会进入窗口一次,然后被移出窗口一次,不会说有某些元素多次进入和离开窗口,所以算法的时间复杂度就和字符串/数组的长度成正比。

  ...


[Notes] Topological Sort(拓扑排序)

  ...