ARST打卡第214周[214/521]

发表于 分类于 阅读次数：
lc1170_比较字符串最小字母出现频次 【TED演讲】在工作中设定好界限 如何将千亿文件放进一个文件系统，EuroSys'23 CFS 论文背后的故事 Ubuntu安装GCC10

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源码安装，但是

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

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