记录一些有意思的题。

经典算法

二分搜索

34. 在排序数组中查找元素的第一个和最后一个位置

二分搜索的加强版

4. 寻找两个正序数组的中位数

算是非常经典又非常复杂的一道题了。我的算法和官方题解稍有不同，可以康康（我的题解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    //尝试在 nums1 中找中位数，seq 从 0 开始
    int findNum(const vector<int>& nums1, const vector<int>& nums2, int seq)
    {
        int left = 0, right = nums1.size() - 1;
        while (left <= right)
        {
            // assert left <= ans <= right
            int mid = (left + right) / 2;
            int mid_2 = seq - mid; // 如果 mid 是中位数，mid_2 应当大于等于 mid，mid_2-1 应当小于等于 mid
            if (mid_2 < 0 || (mid_2 < (int)nums2.size() && nums2[mid_2] < nums1[mid]))
            {
                right = mid - 1;
            }
            else if (mid_2 - 1 >= (int)nums2.size() || (mid_2 - 1 >= 0 && nums2[mid_2 - 1] > nums1[mid]))
            {
                left = mid + 1;
            }
            else return nums1[mid];
        }

        return findNum(nums2, nums1, seq); // 反向在 2 数组中找
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if ((n1 + n2) % 2 == 1)
            return findNum(nums1, nums2, (n1 + n2) / 2);
        else
            return (findNum(nums1, nums2, (n1 + n2) / 2) +
                findNum(nums1, nums2, (n1 + n2) / 2 - 1)) / 2.0;
    }
};

线性数据结构

时间线、区间调度问题

这类问题一般是给定很多时间区间（区间的起始时间、终止时间），讨论一定的问题。

这类问题一般可以用贪心/动态规划解，贪心之前需要进行排序。

1024. 视频拼接

求覆盖完整个范围所需子区间的最小值。

结论：按结束时间降序排序，然后从前往后遍历（遍历的时候需要同时考虑其结束时间是否超过了当前开始时间、其开始时间是否比下一次的开始时间更远）。

56. 合并区间

结论：按开始时间升序排序，能够合并的区间一定连续。

还有一种巧妙的做法，注意到线段重合等价于 a[1] >= b[0] || b[1] >= a[0]，于是我们重载 set 的比较类：

1
2
3
4
5
6
struct Cmp {
    bool operator() (const vector<int>& a, const vector<int>& b) const
    {
        return a[1] < b[0];
    }
};

用这个比较类定义的 set 中，如果两个线段重合，这两个线段在 set 中是被认为相等的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Cmp {
    bool operator() (const vector<int>& a, const vector<int>& b) const
    {
        return a[1] < b[0];
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        set<vector<int>, Cmp> s;
        for (auto interval : intervals)
        {
            auto iter = s.find(interval);
            while (iter != s.end())
            {
                interval[0] = min(interval[0], (*iter)[0]);
                interval[1] = max(interval[1], (*iter)[1]);
                s.erase(iter);
                iter = s.find(interval);
            }
            s.insert(interval);
        }
        return vector<vector<int>>(s.begin(), s.end());
    }
};

并查集

树

树的遍历（非递归）

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 先序遍历 144
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode * cur = s.top();
        s.pop();
        if (cur == nullptr)
            continue;
        ans.push_back(cur->val);
        s.push(cur->right);  // 先将右节点入栈，再将左节点入栈，妙啊
        s.push(cur->left);
    }
    return ans;
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 中序遍历 94
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s; //牢记“左链入栈”：每遍历到一个点 p，就 push(p); p = p->left;
    TreeNode* p = root;
    while(p != nullptr)
    {
        s.push(p);
        p = p->left;
    }
    while(!s.empty())
    {
        p = s.top();
        s.pop();
        ans.push_back(p->val);
        p = p->right;
        while(p != nullptr) // 继续“左链入栈”
        {
            s.push(p);
            p = p->left;
        }
    }
    return ans;
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 后序遍历 145
// （调换左右结点遍历顺序后）进行前序遍历，得到的结果反向输出即可
vector<int> postorderTraversal(TreeNode* root) {
    list<int> ans_reverse;
    vector<int> ans;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode * p = s.top();
        s.pop();
        if (p == nullptr)
            continue;
        ans_reverse.push_front(p->val);  // 从头插入结点 p
        s.push(p->left);                 // 由于是反向输出，所以左右节点入栈的顺序也与先序遍历相反
        s.push(p->right);
    }
    for (int i: ans_reverse)
        ans.push_back(i);
    return ans;
}

统一写法

还有一种写法，统一了三种遍历，只需改变入栈的顺序。

链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/comments/495211

动态规划

动态规划的题，emmm 做多了就明白套路了，做少了的话，还是多看答案，然后自己写吧。注意勤复习。

877. 石子游戏

两人博弈取石子，dp[i][j] 指取完 i 到 j（闭区间）的石子后，先手比后手高的分数。dp 转移方程中由于有先后手的交换，会有 dp[][] = piles[] - dp[][] 的出现。

1000. 合并石头的最低成本

NOI 1995 石子合并，非常经典的区间 dp。dp[i][j] 表示将 i 到 j（闭区间）的石子合并为一堆所需的最小总代价，而 for 中还需要一维表示在哪里合并。

312. 戳气球

类似于合并石子的区间 dp，但注意由于这道题的 dp 转移方程中包含两端的气球值，所以 dp 转移方程有些不同，但同样是需要三个 for 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxCoins(vector<int>& nums) {
    const int n = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));   //dp[i, j] 表示戳爆 [i, j] 间的所有气球的最高总得分
    for (int len = 0; len < n; len++)
        for (int start = 1, end = start + len; end <= n; start++, end++)
            for (int i = start; i <= end; i++)              // 此次戳爆第 i 个气球
                dp[start][end] = max(
                    dp[start][end],
                    dp[start][i - 1] + dp[i + 1][end] + nums[start - 1] * nums[i] * nums[end + 1]
                );
    return dp[1][n];
}

41. 接雨水

一道印象很深的题，因为题面非常直观。

84. 柱状图中最大的矩形

题面很像接雨水。

另外 85. 最大矩形 也用到了这个题的算法。

数学题

线性筛

204. 计数质数

每个合数 t 只会在 j=t最大的质因数, i=t/j 时被筛掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countPrimes(int n) {
        vector<bool> is_prime(n, 1);
        vector<int> primes;
        for (int i = 2; i < n; i++)
        {
            if (is_prime[i])
                primes.push_back(i);
            for (int j : primes)
            {
                if (i*j >= n)
                    break;
                is_prime[i*j] = 0;
                if (i % j == 0)
                    break;
            }
        }
        return primes.size();
    }
};

不过面试一般不会要求这么高吧，会基础的埃氏筛应该就可以了；而且

巧妙的算法

41. 缺失的第一个正数

置换法

实现上需要注意细节，如需要使用 while 反复交换（我第一次使用的是 if）；交换的终止条件是 arr[n] != arr[arr[n]-1] 而不是 n != arr[n]-1（后者会被 [1, 1] 这种数组卡掉）。

8. 字符串转换整数 (atoi)

这个题虽然可以写一堆 if，但是官方题解的有限自动机让我眼前一亮。有空一定实现一次。

巧妙的 C++ 语法

std::stoi

C 提供 int atoi(const char *)，而对于 string 类型，想要使用 aoti 只能使用 const char * string::c_str() 方法。不过，也可以使用 int std::stoi(const string &)：

1
2
string str = "-233";
atoi(str.c_str()) == stoi(str); // true

string::substr

1
string substr (size_t pos = 0, size_t len = npos) const;

总是要忘记它的定义。string::npos 的值为从 pos 到字符串最后的长度。

集合的交集

349. 两个数组的交集

Python 版本就非常简洁：

1
2
def intersection(nums1, nums2):
    return list(set(nums1) & set(nums2))

没想到 C++ 也自带集合求交，见set-集合运算。

巧妙的数据结构

单调栈

简单、好用的数据结构。

数据结构上，递减栈为从栈底往栈顶依次递减的栈（栈里可存元素，也可以存数组下标）。算法上，一个数入栈前，将小于等于它的数全部出栈。

对于某些要计算“某数后面第一个比他大/小的数”的题目，有奇效，如 739. 每日温度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> s; // 递减栈
        vector<int> ans(T.size());
        for (int i = T.size() - 1; i >= 0; i--)
        {
            while(!s.empty() && T[s.top()] <= T[i])
            {
                s.pop();
            }
            ans[i] = s.empty() ? 0 : s.top() - i;
            s.push(i);
        }
        return ans;
    }
};

单调队列

和单调栈相对应的就是单调队列了。

数据结构上，递减队列为从队首往队尾依次递减的双向队列（队列里存数组下标），其本质是类似于单调栈，但是由于题目常常加了一个长度限制，所以也需要让元素从前面出队。

算法上，一个数 i 入队列前，

  1. （如果有，）将超出边界的队首元素出队 pop_front()；
  2. 将小于等于 i 的队尾元素全部出队 pop_back()。

计算滑动窗口（一个固定大小的区间）的最值有奇效，如 239. 滑动窗口最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++)
        {
            if (!q.empty() && q.front() <= i - k)
                q.pop_front(); // 因窗口大小而出队
            while (!q.empty() && nums[q.back()] <= nums[i])
                q.pop_back(); // 因小于当前值而出队
            q.push_back(i);
            if (i >= k - 1)
                ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

双堆：数据流中位数

对于求数据流/滑动窗口的题目，可以维护 大顶堆放小一半的数 + 小顶堆放大一半的数（保证两堆大小相等或大顶堆比小顶堆大 1），两堆的顶就是中位数。

对于滑动窗口，由于有删除的需求，可以使用 multiset 替代堆。

在维护左右大小的时候，如果分情况讨论会非常复杂，不如 push/remove 的时候先保证两堆大小相等或大顶堆比小顶堆大 1，然后再检查是否符合大顶小于小顶，不符合就交换。这样思路更清晰，代价时间复杂度的常数变大了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 数据流的中位数，使用双堆实现
class MedianFinder {
public:
    priority_queue<int> big_heap; // 存小的数，保证大小等于 small_heap，或比 small_heap 多一
    priority_queue<int, vector<int>, greater<int>> small_heap; // 存大的数
    
    void swap_top()
    {
        int b = big_heap.top();
        big_heap.pop();
        int s = small_heap.top();
        small_heap.pop();
        big_heap.push(s);
        small_heap.push(b);
    }

    void addNum(int num) {
        // 保证两堆大小相等或大顶堆比小顶堆大 1
        if (big_heap.size() == small_heap.size())
            big_heap.push(num);
        else
            small_heap.push(num);
        assert(big_heap.size() == small_heap.size() || big_heap.size() == small_heap.size() + 1);

        // 检查是否符合大顶小于小顶，不符合就交换。
        if (small_heap.size() > 0 && big_heap.top() > small_heap.top())
            swap_top();
        assert(small_heap.empty() || big_heap.top() <= small_heap.top());
    }
    
    double findMedian() {
        if (big_heap.size() == small_heap.size())
            return ((double)big_heap.top() + (double)small_heap.top()) / 2;
        else
            return big_heap.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// 滑动窗口中位数，使用双 multiset 实现
class MedianFinder {
public:
    multiset<int, greater<int>> big_heap; // 存小的数，保证大小等于 small_heap，或比 small_heap 多一
    multiset<int> small_heap; // 存大的数
    
    // 检查是否符合大顶小于小顶，不符合就交换。
    void make_balance()
    {
        if (small_heap.size() > 0 && *big_heap.begin() > *small_heap.begin())
        {
            big_heap.insert(big_heap.end(), *small_heap.begin());
            small_heap.insert(small_heap.end(), *big_heap.begin());
            big_heap.erase(big_heap.begin());
            small_heap.erase(small_heap.begin());
        }
        assert(small_heap.empty() || *big_heap.begin() <= *small_heap.begin());
    }

    void insert(int num)
    {
        // 保证两堆大小相等或大顶堆比小顶堆大 1
        if (big_heap.size() == small_heap.size())
            big_heap.insert(num);
        else
            small_heap.insert(num);
        assert(big_heap.size() == small_heap.size() || big_heap.size() == small_heap.size() + 1);

        make_balance();
    }

    void remove(int num)
    {
        // 保证两堆大小相等或大顶堆比小顶堆大 1
        if (num > *big_heap.begin())
        {
            assert(small_heap.find(num) != small_heap.end());
            small_heap.erase(small_heap.find(num));
            if (big_heap.size() - 2 == small_heap.size())
            {
                small_heap.insert(small_heap.end(), *big_heap.begin());
                big_heap.erase(big_heap.begin());
            }
        }
        else
        {
            assert(big_heap.find(num) != big_heap.end());
            big_heap.erase(big_heap.find(num));
            if (big_heap.size() + 1 == small_heap.size())
            {
                big_heap.insert(big_heap.end(), *small_heap.begin());
                small_heap.erase(small_heap.begin());
            }
        }
        assert(big_heap.size() == small_heap.size() || big_heap.size() == small_heap.size() + 1);

        make_balance();
    }
    
    double findMedian() {
        if (big_heap.size() == small_heap.size())
            return ((double)*big_heap.begin() + (double)*small_heap.begin()) / 2;
        else
            return *big_heap.begin();
    }
};

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        MedianFinder mf;
        vector<double> ans;
        for (int i = 0; i < k; i++)
            mf.insert(nums[i]);
            ans.push_back(mf.findMedian());
        for (int window = 0; window + k < nums.size(); window++)
        {
            mf.remove(nums[window]);
            mf.insert(nums[window+k]);
            ans.push_back(mf.findMedian());
        }
        return ans;
    }
};