翻译自文章https://www.johnlamp.net/cmake-tutorial.html

CMake是什么？

CMake是开源跨平台的构建工具，由Kitware开发。CMake提供一个简单的构建C/C++项目的方式。实际上CMake不算一个完全的构建工具，它实际上是生成你系统构建工具的配置文件（比如Make）。

因为在项目里使用了zgrab2，所以想学习它的设计，顺便学习go语言

zgrab2主程序

主程序main.go在/cmd/zgrab2/main.go下，主要流程是：

题目解析

实现通配符匹配，*可以匹配任意字符或者0个字符，？匹配一个任意字符

方法一 贪心

这道题最关键的是*，因为它的特性能够匹配任意多字符。
对于下面样例，si是s的索引，pi是p的索引

1
2

s = "abc"
p = "a*c"

题目解析

在单链表上使用O(nlgn)的排序算法

方法一 快速排序

快速排序有一种partition需要从两边往里交换，这种在单链表上行不通，这里改为维持一个low指针，在它之前的节点（包括low指向的）的值都小于目标。
比如：

1
2

输入: 3->4->2->1->6
输出: 1->2->3->4->6

题目解析

题目的意思是数组每个元素有两个值[H, K]，第一个值是身高，第二个值是身高大于的此元素个数。比如下面的例子

1
2
3
4
5

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题目解析

删除不合法的括号，比如下面的样例

1
2

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

题目解析

创建一个LRU（Least Recently Used cache）最近使用的缓存会留在其中，最久的会被踢出去。这道题关键在于O(1)的时间复杂度。对于LRU需要一个类似队列的结构，同时当其中一个元素被使用后(get)，需要将其提到队列最后，这样就最晚被删除，寻找这个元素需要O(1)，那么得使用hashmap来贮存key对应的位置，同时提到最后这个操作也需要O(1)，那么就需要使用双端链表，如果用vector，删除操作需要O(n).

题目解析

将2[bc]这样格式的字符串变成bcbc,2表示中括号里字符串重复的次数。

方法

主要是字符串的操作，遇到]时再进行操作，取出[abc]里的字符串，同时使用isdigit判断数字来获得重复次数，使用stoi将字符串转换为数字，然后使用str.replace(size_t pos, size_t len, const string & str)来替换解码后的字符串，需要注意的是索引i，再字符串解码后需要变成i+1+newStr.size()。

题目解析

找到数组中重复的元素，难点在于不能修改原数组、空间复杂度O(1)、时间复杂度小于O(n^2)

方法

在这里一共n个元素，有n+1种元素，因为重复元素可以多于1，说明每个元素最多能有n-1个能放在对应索引上。
如果将元素的值作为索引，可以发现规律，比如：

1
2
3
4

输入: [1,3,4,2,2]
可以看成：
索引：0 1 2 3 4
  值：1 3 4 2 2

题目解析

从数组中找到出现频率前K多的元素

方法一 排序

使用map来获得所有元素的频率，然后排序，找到前k个元素。时间复杂度是O(nlgn) 耗时20ms