Contents

ARST打卡第214周[214/521]

Algorithm

lc1170_比较字符串最小字母出现频次

比较自然的模拟的思路,然后想到了后缀和

 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
/* 
时间 8 ms 击败 92.5%
内存 14.5 MB 击败 21.19%
 */
class Solution {
public:
    // 简单模拟,直接先计算words的f数值,
    // 然后把f的值计数,预处理成后缀和
    // 然后再依次计算query的f对比值再O(1)获取后缀和得出答案
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        // 一开始是f值的频次,后面变成频次后缀和
        // 以下c风格的初始化数组的代码,在leetcode会运行报错...
        // int fcnt_suf_sum[11];
        // memset(fcnt_suf_sum, 0, 11);
        // vector<int> fcnt_suf_sum(11, 0);
        vector<int> fcnt_suf_sum(12, 0);
        for (auto s : words) {
            fcnt_suf_sum[f(s)]++;
        }
        for (int i=9; i>0; i--) {
            fcnt_suf_sum[i] += fcnt_suf_sum[i+1];
        }
        vector<int> ans;
        for (auto q : queries) {
            // int tmp = f(q);
            // if (tmp == 10) {
            //     // 一开始没有处理这里,导致LeetCode报错堆栈溢出了
            //     // cout << "tmp == 10" << endl;
            //     // 其实可以把数组开大一位,让fcnt_suf_sum[11] = 0即可
            //     ans.emplace_back(0);
            //     continue;
            // }
            // ans.emplace_back(fcnt_suf_sum[tmp+1]);
            ans.emplace_back(fcnt_suf_sum[f(q)+1]);
        }
        return ans;
    }

    int f(const string s) {
        vector<int> cnt(26, 0);
        for (char c : s) {
            cnt[c - 'a']++;
        }
        for (int i=0; i<26; i++) {
            if (cnt[i] > 0) {
                return cnt[i];
            }
        }
        return 0;
    }
};

题解 的f函数写得很巧妙,比我的计数法效果更好,因为题解的时间复杂度比我好

而且题解很多地方都尽量用了引用,所以减少了内存拷贝,所以空间复杂度比我更好,学习一下

 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
/* 
时间 4 ms 击败 99.34%
内存 11.1 MB 击败 93.38%
 */
class Solution {
public:
    int f(string &s) {
        int cnt = 0;
        char ch = 'z';
        for (auto c : s) {
            if (c < ch) {
                ch = c;
                cnt = 1;
            } else if (c == ch) {
                cnt++;
            }
        }
        return cnt;
    }

    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> count(12);
        for (auto &s : words) {
            count[f(s)]++;
        }
        for (int i = 9; i >= 1; i--) {
            count[i] += count[i + 1];
        }
        vector<int> res;
        for (auto &s : queries) {
            res.push_back(count[f(s) + 1]);
        }
        return res;
    }
};

Review

【TED演讲】在工作中设定好界限

我们都不擅长告诉他人我们自己需要怎么被对待。 但是如果告诉别人自己的边界,将获得长期的良性循环! 因此在工作和各种关系中,都尽早告知边界,并保持边界的一致性,反复强调,这样才能长久愉快相处!

Tips

如何将千亿文件放进一个文件系统,EuroSys'23 CFS 论文背后的故事

介绍了百度的CFS系统,主要思想精髓是:

  1. 把数据操作分析到最原子的不可分的操作状态,然后去满足做这些状态的支持
  2. 因此得出可以分离元数据中的inode和attr部分
  3. 因此得到的分片在单节点的架构只需要特殊处理rename,其他元数据操作均不需要分布式锁

十分精妙,推荐阅读

Share-Ubuntu安装GCC10

使用包安装的方式安装

其他安装方法(源码安装)对比

其实还可以用gcc源码安装,但是

  • 源码安装下载包太久
  • 需要很多工具来编译
  • 而且很多坑
  • 而且编译时间很久

整体来说都比较复杂… 别问我怎么知道的,我会哭的很小声