Contents

ARST打卡第238周[238/521]

Algorithm

lc828_统计子串中的唯一字符

思路: 暴力做法是双层遍历字串,然后hash映射统计只出现一次的字符. O(n^3), 不行。

优化: 在第二重遍历的时候就直接hash记录。 O(n^2), 还是不行。

怎么重复利用呢? 看数据范围 1e5 需要保证时间复杂度在 O(nlogn), 暂时想不到好办法。

看看题解

其中计算一个字符的贡献太精巧了!只能说这个 hard 主要难在思路和那个鬼斧神工的前后插入。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int uniqueLetterString(string s) {
        unordered_map<char, vector<int>> index;
        for (int i = 0; i < s.size(); i++) {
            index[s[i]].emplace_back(i);
        }
        int res = 0;
        for (auto &&[_, arr]: index) {
            arr.insert(arr.begin(), -1);
            arr.emplace_back(s.size());
            for (int i = 1; i < arr.size() - 1; i++) {
                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
            }
        }
        return res;
    }
};

Review

【TED演讲】16岁语言天才分享:我是如何掌握20多门外语的?

语言代表文化,学习语言就是在学习文化,让我们变得更加开放包容。

用别人使用的语言和对方沟通,可以把意思表达到别人的心里,而不只是脑子里。

Tips

为什么说黑底白字界面主题配色是最垃圾的、最不该用的?

Share

推荐阅读_现代C++语言核心特性解析 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/books/cpp_core_features_analysis.jpeg

这本书对cpp学习来说感觉很好,从cpp制定标准的各种历史背景来讲解各种cpp语言特性的变化,让人方便知道前因后果,从而变得更加容易理解和感觉有趣,也让读者体验到了设计编程语言时的种种取舍。非常推荐所有学习cpp的人读这本书。

这本书的代码整理: modern_cpp_core_features_analysis