翻译-CMake教程

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

CMake是什么?

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

阅读全文

zgrab2源码阅读

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

zgrab2主程序

主程序main.go/cmd/zgrab2/main.go下,主要流程是:

阅读全文

44. Wildcard Matching

题目解析

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

方法一 贪心

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

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

阅读全文

148. Sort List

题目解析

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

方法一 快速排序

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

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

阅读全文

406. Queue Reconstruction by Height

题目解析

题目的意思是数组每个元素有两个值[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]]

阅读全文

301. Remove Invalid Parentheses

题目解析

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

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

阅读全文

146. LRU Cache

题目解析

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

阅读全文

394. Decode String

题目解析

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

方法

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

阅读全文

287. Find the Duplicate Number

题目解析

找到数组中重复的元素,难点在于不能修改原数组、空间复杂度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

阅读全文

347. Top K Frequent Elements

题目解析

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

方法一 排序

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

阅读全文