ARTS-week53

发表于 分类于 本文字数： 2.6k 阅读时长 ≈ 2 分钟

Algorithms

Island Perimeter
思路: 每块格子有四条边，题中提到岛屿上没有湖，相连的陆地同时会丢掉1条边，先给每个陆地默认加四条边，检查陆地的左边和上边是否有陆地，将右边和下边交给其他的陆地去计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int cnt = 0;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if(grid[i][j] == 1) {
                    cnt += 4;
                    if(i > 0 && grid[i-1][j] == 1)
                        cnt -= 2;
                    if(j > 0 && grid[i][j-1] == 1)
                        cnt -= 2;
                }
            }
        }
        return cnt;
    }
};

Heaters

思路: 二分查找。 

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
class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        if(heaters.empty() || houses.empty()) {
            return 0;
        }
        
        sort(heaters.begin(), heaters.end());
        
        int res = 0;
        int n = heaters.size();
        
        for (int house : houses) {
            int left = 0, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (heaters[mid] < house) {
                    left = mid + 1;
                }
                else {
                    right = mid;
                }
            }
            
            int dist1 = (right == n) ? INT_MAX : heaters[right] - house;
            int dist2 = (right == 0) ? INT_MAX : house - heaters[right - 1];
            res = max(res, min(dist1, dist2));
        }
        return res;
    }
};

Review

本周阅读英文文章:
1、How to Survive a Ransomware Attack

2、Fooling real cars with Deep Learning

3、The Current and the Future States of DNS security (2019)

Technique

在编译一个工具时，make报了错，说缺少了manifest，这以前没见过呢…

那先说一下Fossil是什么，根据官方文档的描述，Fossil是一个简单，高可靠性的分布式软件配置管理系统，具有Bug跟踪，Wiki，内置的Web界面等功能，免费、开源。

使用Fossil进行版本管理的项目中会存在manifest文件，其中包含了项目的文件列表及其各自的校验和等。以Sqlite源码中的manifest为例，挑出其中的一部分，源码地址: https://github.com/sqlite/sqlite/blob/master/manifest 

1
2
3
4
5
6
7
C Fix\sa\sproblem\swith\squeries\sof\sthe\sform\s"SELECT\smin(<expr>)\s...\sWHERE\s<expr>=?"\swhere\sthere\sis\san\sindex\son\s<expr>.\sFix\sfor\s[71e183ca].
D 2019-08-03T16:37:40.150
F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
P fd598e475d353363e19adc27a671170f11ae9f6d8cad58cb2303fb2ad8ac6bec
R cc89bfbc259b9b7136163b32cac7f905
U dan
Z 99d6ce70f917d34037e260832ba76b7f

如果所示，manifest中有一些Card，每个Card的使用方式不一样，定义如下: 

1
2
3
4
5
6
7
8
9
10
11
B baseline-manifest
C checkin-comment
D time-and-date-stamp
F filename ?hash? ?permissions? ?old-name?
N mimetype
P artifact-hash+
Q (+|-)artifact-hash ?artifact-hash?
R repository-checksum
T (+|-|*)tag-name * ?value?
U user-login
Z manifest-checksum

其中每个manifest中必须只有一个C Card记录提交的注释，只有一个D Card记录时间，F Card用于标识文件，P Card记录当前manifest的父版本，R Card是manifest提及的所有文件的checksum，U Card用于记录用户信息，Z Card用来记录当前manifest的checksum。更详细的解释查看官方文档好了: https://fossil-scm.org/fossil/doc/trunk/www/fileformat.wiki#manifest

分享一篇以存储格式、文件集以及改动集的方式来介绍Fossil的文章，是在解决这个问题的时候找到的:
分布式版本管理工具的内涵【三】Fossil篇

Share

感兴趣的同学可以抽时间看一下《FP50优秀网络安全解决方案白皮书》