ARST打卡第234周[234/521]

发表于 分类于 阅读次数：
lc274_H指数 【TED演讲】工作不是你的家庭 Rocksdb-Iterator实现 perf-example website share

Algorithm

lc274_H指数

思路:
感觉就是先排序，然后倒序模拟查看至少有i篇论文被引用 citations[i] 次.
当前ans就是 min(i, citations[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int sz = citations.size();
        int ans = 0;
        sort(citations.begin(), citations.end());
        for (int i = sz - 1; i >= 0; i--) {
            int index = sz - i;
            ans = max(ans, min(citations[i], index));
            if (citations[i] < index) {
                break;
            }
        }
        return ans;
    }
};

发现题解 还有二分，计算等方法。

其中二分和排序时间复杂度一样，但是二分的空间复杂度好一点点，计数则只需要O(n),通过计数模拟得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(), tot = 0;
        vector<int> counter(n + 1);
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++;
            } else {
                counter[citations[i]]++;
            }
        }
        for (int i = n; i >= 0; i--) {
            tot += counter[i];
            if (tot >= i) {
                return i;
            }
        }
        return 0;
    }
};
// 链接：https://leetcode.cn/problems/h-index/

Review

【TED演讲】工作不是你的家庭

建立工作边界，防止过度劳累导致丧失工作热情，从而过一个比较好的细水长流的工作和生活。

Tips

Rocksdb Iterator实现：从DBIter 到 TwoLevelIter 的漫长链路

Share

perf-example website share

这个网站的内容非常清晰，一张框架图更是一图胜千言，所以分享推荐。