Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc" Output: 10 Explanation: The substrings containing at least one occurrence of the characters a, b and c are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” and “abc” (again). Example 2:

Input: s = "aaacb" Output: 3 Explanation: The substrings containing at least one occurrence of the characters a, b and c are “aaacb”, “aacb” and “acb”. Example 3:

Input: s = "abc" Output: 1

Constraints:

3 <= s.length <= 5 x 10^4 s only consists of a, b or c characters.

基本思路是对于每一个字符，如果想要找到以它为结尾的符合要求的子串，那么我们只要找到距离它最远的另外两个字符的出现位置。这样我们就找到了一个每个字符都至少包含一次的最短子串，以这个子串结尾的所有子串都符合要求。使用前缀表记录字符上一次出现的位置就可以了

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

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.length(), res = 0;
        if (n < 3)
            return 0;

        vector<vector<int>> prefix(n, vector<int>(3, -1));
        prefix[0][s[0] - 'a'] = 0;

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1];
            prefix[i][s[i] - 'a'] = i;
            int minIdx = INT_MAX;
            for (int j = 0; j < 3; j++) {
                if (j == s[i] - 'a')
                    continue;
                minIdx = min(prefix[i][j], minIdx);
            }
            if (minIdx == -1)
                continue;
            res += (minIdx + 1);
        }
        
        return res;
    }
};

另一个野路子算法，不使用前缀表，而是使用二分搜索来找到每个字符都至少包含一次的最短子串。

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

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.length(), res = 0;
        if (n < 3)
            return 0;

        vector<vector<int>> cnt(n + 1, vector<int>(3, 0));

        for (int i = 1; i <= n; i++) {
            cnt[i] = cnt[i - 1];
            cnt[i][s[i - 1] - 'a']++;
        }

        for (int i = 3; i <= n; i++) {
            if (cnt[i][0] && cnt[i][1] && cnt[i][2]) {
                int t = bshelper(cnt, i);
                res += (t + 1);
            }
        }
        return res;
    }

    int bshelper(const vector<vector<int>>& cnt, int end) {
        int left = 0, right = end, mid;
        vector<int> tmp(3, 0);
        while (left < right) {
            mid = (left + right) / 2 + 1;
            for (int i = 0; i < 3; i++) {
                tmp[i] = cnt[end][i] - cnt[mid][i];
            }
            if (tmp[0] && tmp[1] && tmp[2]) {
                left = mid;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }
};

さらば、全てのエヴァンゲリオン

「所有的故事都必将迎来终结。」

这次试验受到油猴脚本“解除B站区域限制”所使用的在阿里云用云函数搭建B站反向代理、以及awslambdaproxy项目启发，使用阿里云函数+Custom Container实现Socks代理。

本文默认读者已经有一定的公有云平台/阿里云以及Linux系统和Docker使用经验，并且已经拥有可以部署云函数的阿里云账号。本文不会详细解释阿里云的使用细节，关于如何部署/管理阿里云资源请参考阿里云文档。

注意⚠️：笔者在此只简述工作原理及搭建简易POC，不保证任何可靠性及安全性。鉴于笔者的水平有限，文中不免出现错误，请不吝指出。

使用阿里云免费额度一定要注意，由于本文所述的云函数几乎是一直运行，因此极其容易被反薅羊毛。

Note：全是剧透

终于来到最后一篇了，之前的两篇：

• 日本游记（一）
• 日本游记（二）

说来也很巧，我第三次无日本是在我敲下这些字的时候的整整一年前，不多也不少。这次去主要是带着父母去关西玩一趟，所以有很多地方都是我第一次去的时候就已经去过的，这一篇我打算只写一写我之前没去过的地方，最后再聊一聊我接下来想去的地方。

上篇文章写了我在16年春天第一次去日本自由行的经历，这一篇我打算写一写我19年春天第二次去的时候的事。时隔三年，仍然是樱花季，只不过这次是从旧金山出发，单程飞机就要10个多小时，远没有从中国飞去方便，而且机票价格也不便宜，樱花季往返机票价格接近2000美元。不过这次我已经开始拿工资了，可支配资金还是绰绰有余的。

我现在坐在湾区的家里，本来如果没有这次疫情的话，我此时此刻应该在准备飞往洛杉矶然后转机飞往东京开始我的两周红叶+北海道游，而不是坐在这里敲键盘。这应该是我第四次去日本旅游了，本来计划的好好的，前三次有两次是樱花季去的，一次是冬天，这次就挑红叶季去，哪知人算不如天算，疫情没完没了，再好的计划也都泡了汤。我也只能百无聊赖地呆在家里等着下周感恩节放假，顶多在湾区附近开车逛逛。既然如此，那我就趁着这个时间回忆一下前几次的旅行，权当望梅止渴吧。

写着写着发现要写完三次游记实在是太长，所以会分成几篇文章。

⚠️大量图片预警

不知不觉入职Google也已经半年多了，在家工作也有半年多了。工作上的事情渐渐熟悉，想写写这半年多来的一些感受。

GitHub Actions真的是非常好用的东西，基于它的事件驱动的工作流可以自动化很多以前我都得手动做的东西。以前当然也可以通过别的CI平台来做，但是GitHub Actions跟GitHub深度集成还是让它成为我的第一选择。最重要的还免费。

这次我是通过GitHub Actions来实现在Issues发布的内容，自动转换为Hexo文章，然后push到repo，再自动生成、部署。

https://blog.xiadong.info/2020/11/04/This is a test blog post/这篇文章就是这样写的，本文也是。

test message.

Title

bold

italic

1. list1
2. list2