ARST打卡第239周[239/521]

发表于 分类于 阅读次数：
lc1094_拼车 TED_传递快乐，传递帮助 TrivialMove让大文件出现在高层 hexo文件头转hugo文件头

Algorithm

lc1094_拼车

思路:
暴力方法就是遍历这最多1000个站点，每次把站点上的左右区间最大1000都相加乘客数，时间复杂度是 O(n^2) 是 1e6 .

感觉好一点的优化方案是使用线段树来进行一个操作。

先迅速写完暴力法吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> nums(1010, 0);
        for (auto& trip : trips) {
            int numP = trip[0];
            int from = trip[1];
            int to = trip[2];
            // 这里 to 已经下车，wa了一发
            for (int i = from; i < to; i++) {
                nums[i] += numP;
                if (nums[i] > capacity) {
                    return false;
                }
            }
        }
        return true;
    }
};

暴力AC了，学习一下 题解

一开始一直想的前缀和好像不行，看题解发现果然不行，题解用的差分数组，差分数组是前缀和的逆运算。

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
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int to_max = 0;
        for (const auto& trip: trips) {
            to_max = max(to_max, trip[2]);
        }

        vector<int> diff(to_max + 1);
        for (const auto& trip: trips) {
            diff[trip[1]] += trip[0];
            diff[trip[2]] -= trip[0];
        }

        int count = 0;
        for (int i = 0; i <= to_max; ++i) {
            count += diff[i];
            if (count > capacity) {
                return false;
            }
        }
        return true;
    }
};

// 链接：https://leetcode.cn/problems/car-pooling/description/

Review

TED_传递快乐，传递帮助

教育就是一切，用作品用自己的影响力，去让世界变得更好，让世界减少不自由。

Tips-TrivialMove让大文件出现在高层

Compaction Trivial Move

开发 RocksDB 的时候发现一个奇怪的现象，就是 target_file_size_base 明明限制了 l1 文件生成大小，但是居然还有大于此大小的文件在 l1 层。

看 LOG 日志发现是 Trivial Move 操作。(因为我插入的数据没有重叠，于是rocksdb用的 Compaction Trivial Move )
因此知道 rocksdb 的 target_file_size_base 只限制 compaction 生成的文件的大小，并不限制其他方式到达层级的大小。

Share-hexo文件头转hugo文件头

在 hexo 博客中有很多文件的时候，一一去改文件头变成了一件很奢侈的事情，于是就有了自动化脚本修改的念头。

在前人的肩膀上继续 PR 修改，于是有了这个项目的 PR 更新:
hexo2hugo

可以支持 hexo 文件头转 hugo 文件头的如下内容项:

  • date 更新为 UTC+8
  • updated 更新为 lastmod 的 UTC+8
  • tags, categories 支持单行也支持多行格式转数组括号格式