高效寻找素数
统计所有小于非负整数 n 的质数的数量。计数质数
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int countPrimes(int N) {
vector<bool> isPrime(N + 1, true);
// 判断一个数n是否是素数，只需要判断[1,sqrt(n)]中有没有可整除因子
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
// 如果当前值是素数，那么它的倍数肯定不是素数，注意这儿从平方开始
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
螺旋打印矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。螺旋矩阵
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<vector<bool>> st;
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (!matrix.size()) return res;
int m = matrix.size(), n = matrix[0].size();
st = vector<vector<bool>>(m, vector<bool>(n));
int x = 0, y = 0, d = 0;
for (int i = 1; i <= m * n; i ++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || st[nx][ny]) {
d = (d + 1) % 4;
nx = x + dx[d], ny = y + dy[d];
}
res.push_back(matrix[x][y]);
st[x][y] = true;
x = nx, y = ny;
}
return res;
}
TopK问题
输出无序数组中的前K大/小元素或第K大/小元素。最小的k个数,数组中的第K个最大元素
方法1：直接全部排序(只适用于内存够的情况)
当数据量较小的情况下，内存中可以容纳所有数据，则最简单的方法就是将数据全部排序，然后取出前k个或第k个。$O(nlogn)$
1
2
3
4
5
6
7
8
vector<int> getLeastNumbers(vector<int>& arr, int k) {
sort(arr.begin(), arr.end());
vector<int> res;
for (int i = 0; i < k; i++) {
res.push_back(arr[i]);
}
return res;
}
方法2：快速排序的变形(只适用于内存够的情况)
类似于快速排序，首先选一个划分基准，将比这个划分基准大的元素放在它的前面，比它小的元素放在它的后面，此时完成了一趟排序。如果此时这个划分基准的序号idx刚好等于k，那么这个划分基准及其左边的数刚好就是前K个最大的元素；如果idx > k,那么前k大数在idx的左边，那么就继续递归的从idx-1个数中进行一趟排序，如果idx < k，那么再从划分单元的右边继续进行排序，直到找到序号idx刚好等于K位置，再将前k个数进行排序返回即可，这样可以避免topk以外的元素进行排序所带来的不必要的开销。$O(nlogk)$
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
32
33
34
35
36
37
vector<int> getLeastNumbers(vector<int>& arr, int k) {
int idx = findTopK(arr, 0, arr.size() - 1, k);
vector<int> res;
if (idx == -1) return res;
for (int i = 0; i < k; i++) {
res.push_back(arr[i]);
}
return res;
}
int findTopK(vector<int>& nums, int l, int r, int k) {
int idx = -1;
if (l < r) {
int pos = partition(nums, l, r);
int len = pos - l + 1;
if (len == k)
idx = pos;
else if (len < k)
idx = findTopK(nums, pos + 1, r, k - len);
else
idx = findTopK(nums, l, pos - 1, k);
}
return idx;
}
int partition(vector<int>& nums, int l, int r) {
int flag = l;
int idx = l + 1;
for (int i = idx; i <= r; i++) {
if (nums[i] < nums[flag]) {
swap(nums[idx], nums[i]);
idx++;
}
}
swap(nums[idx - 1], nums[flag]);
return idx - 1;
}
方法3：最大堆或最小堆(用于处理海量数据)<>
维护一个大小为k的大顶堆/小顶堆。依次将数据放入小顶堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。当然，如果是求前 K 个最小的数，只需要改为大顶堆即可。$O(nlogk)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> getLeastNumbers(vector<int>& arr, int k) {
priority_queue<int, vector<int>, less<int>> q;
vector<int> res;
for (auto n : arr) {
if (q.size() < k) // 大顶堆中添加元素直到元素个数达到k
q.push(n);
else {
// 和堆顶元素判断，如果比对端元素小，则删除堆顶元素，当前元素入堆
if (q.size() && q.top() > n) q.pop(), q.push(n);
}
}
while (q.size()) {
res.push_back(q.top());
q.pop();
}
return res;
}
方法4：分治法(数据量很大的时候)
将全部数据分成N份，前提是每一份数据都可以读到内存中进行处理，找到每份数据中最大的K个数，此时剩下$N\times K$个数据，如果内存不能容纳$N\times K$个数据，则继续分治处理，分成M份，找出每份数据中最大的K个数，如果$M\times K$个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，然后对这些数据进行排序来获得topk元素。
LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。LRU缓存机制,参考资料
参考代码
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
32
33
34
35
36
class LRUCache {
public:
int cap = 0; // cache 容量
typedef pair<int, int> PII;
unordered_map<int, list<PII>::iterator>m; // 哈希表，key 映射到(key value)在cache中的位置
list<PII> cache; // 双向链表，装着key value 元组
LRUCache(int capacity) { cap = capacity; }
int get(int key) {
if (m.count(key)) { // 如果包含key，则需要把key映射的结点放在链表头
PII t = *m[key]; // 记录当前key映射的结点
cache.erase(m[key]); // 删除key的映射
cache.push_front(t); // 将key映射的结点放在链表头
m[key] = cache.begin(); // key映射修改到链表头
return t.second;
} else {
return -1;
}
}
void put(int key, int value) {
if (m.count(key)) { // 如果包含key，则需要将key映射的结点放在链表头
cache.erase(m[key]); // 先删除key的映射
} else {
if (cache.size() == cap) { //如果缓存满了
auto lastpair = cache.back(); // 获取链表的最后一个结点
int lastkey = lastpair.first; // 得到它的key
m.erase(lastkey); // 从哈希表中key对应的这一项
cache.pop_back(); // 删除链表中的最后一个结点
}
}
cache.push_front({key, value}); // 将当前结点放在链表的第一个位置
m[key] = cache.begin(); // 设置哈希表的key映射到链表的第一个结点
}
};
赛马问题
64匹马，8个跑道，问最少比赛多少场，可以选出跑得最快的4匹马。假定：每场比赛每个跑道只允许一匹马，且不存在并列情形。
第一步：需要8场比赛：
首先把64匹马随机分成8组，并标记组别，遍历组别，比赛8次，记录每组赛马名次，如$A_1>A_2>A_3…>A_8$。可以提出每组中的后四名赛马，剩余64-4*8=32匹赛马待定。
第二步：需要1场比赛：
选出每组的排名第一的赛马进行一次比赛，记录结果，不是一般性，记为$A_1>B_1>C_1>D_1>E_1>F_1>G_1>H_1$。根据这轮比赛结果，首先剔除E、F、G、H这四组的所有赛马（因为本组的第一都没进入前4），剩余16匹马。其次可以确定$A_1$就是第一快的马。还可以进一步细化：D组的2-4名赛马不可能是top4，剔除这三匹马，剩余15-3=12匹马待定。C组的3-4名不可能是top4，剔除这两匹马，剩余12-2 = 10匹马，B4不可能是top4，剔除这一匹马剩余10-1=9匹马待定。
第三步：需要1场或2场：
当前剩余待定9匹马：$A_2>A_3>A_4,B_1>B_2>B_3,C_1>C_2, D_1$。因为可以确定$B_1>C_1>D_1$，因此挑选$A_2>A_3>A_4, B_1>B_2>B_3, C_1>C_2$（或者$A_2>A_3>A_4, B_1>B_2>B_3, C_1>D_1$）等8匹马进行一场比赛，剩余一匹$D_1$或者$C_2$待定，重点关注$C_1$的排名。
仅需1场比赛情形：
当$C_1$排名第3及以后，则选出本场前3名赛马，外加大佬$A_1$，即为所求的Top4匹马
需2场比赛情形:
因为已知$B_1>C_1$,所以$C_1$本场名次区间为[2,8]当$C_1$排名第2时，可推知$B_1$排名本场第一，因此$A_1>B_1>C_1$即为全场Top3匹马，此时可剔除$B_1$,$C_1$两匹马，剩余9-2=7匹马待定（如下）
本轮上场剩余6匹：$A_2>A_3>A_4$，$B_2>B_3$,$C_2$
未上场1匹：$D_1$
将本场剩余7匹赛马再进行一场比赛，一决高低，记录名次，选出本场排名第一的赛马，加上$A_1>B_1>C_1$，即为全场Top4匹马。
