题目来源:https://leetcode.com/problems/time-based-key-value-store/description/

标记难度:Medium

提交次数:1/1

代码效率:33.33%(212ms)

题意

给定一系列set和get操作,其中:

  • 每个set操作包含一个key,一个value和一个timestamp,其中timestamp是严格递增的
  • 每个get操作包含一个key和一个timestamp,要求找出与这个key相等且时间戳<=timestamp的set操作中时间戳最大的set对应的value

所有操作总数不超过12万次。

分析

这个题目咋一看很唬人,其实完全不是那么回事。解题思路很简单:

  • 用一个map维护set操作的key对应的value和timestamp对的列表
  • 对于每个get操作,从key对应的列表中通过二分查找,找到最大的符合要求的timestamp对应的value

如果map用的是Hash Table,记总操作次数为N,那么set的复杂度是O(1),get的复杂度是O(log(N));如果用的是树结构的话,那set的复杂度就是O(log(N)),get的复杂度是O(log^2(N))(不过显然可以把它写得更好一些)。

这次我写了二分查找。一般来说,如果二分查找(m = (l + r) / 2)之后的转移条件是l = m + 1r = m的话,那循环条件就可以写成l < r;但是如果转移条件是l = mr = m - 1的话,循环条件就需要写成l < r-1,然后判断l还是r是解……

代码

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
class TimeMap {
private:
map<string, vector<pair<int, string>>> mmap;

public:
TimeMap() {

}

void set(string key, string value, int timestamp) {
mmap[key].emplace_back(timestamp, value);
}

string get(string key, int timestamp) {
if (mmap.find(key) == mmap.end()) return "";
int n = mmap[key].size();
if (mmap[key][0].first > timestamp) return "";
// 二分查找
int l = 0, r = n - 1;
while (l < r - 1) {
int m = (l + r) / 2;
if (mmap[key][m].first <= timestamp) l = m;
else
r = m - 1;
}
if (mmap[key][r].first <= timestamp) return mmap[key][r].second;
return mmap[key][l].second;
}
};

题目来源:https://leetcode.com/problems/univalued-binary-tree/description/

标记难度:Medium

提交次数:1/2

代码效率:112ms(40.00%)

题意

给定一个wordlist,其中包含了若干个单词(只包含英文字母的字符串),给定一系列query,要求从wordlist中找出匹配单词:

  • 如果wordlist中包含单词与该query相同,则直接返回query
  • 如果在不考虑大小写的情况下,wordlist中包含单词与该query相同(例:"AbC""aBc"是相同的),则返回第一个匹配单词
  • 如果在不考虑大小写和将所有元音字母认为是同一个字母的情况下,wordlist中包含单词与该query相同(例:"Aab""eIb"是相同的),则返回第一个匹配单词

分析

首先一个事实是,O(N*M)N = wordlist.size()M = queries.size())的算法是过不了的,因为N, M <= 5000。那么显然就要用到哈希表了。

  • 首先用一个set<string> exact存储原来的单词
  • 然后用一个map<string, int> lower存储每个单词的lowercase版本到它的索引,如果一个lowercase版本对应多个单词,则只存储第一个出现的单词的索引
  • 然后用一个map<string, int> vowel存储每个单词的lowercase且把所有元音都替换成"a"的版本到它的索引,如果一个替换后的版本对应多个单词,则只存储第一个出现的单词的索引
  • 最后,对于每一个query,分别在这三个结构里查找,如果查到则立刻返回,否则最后返回""

总的来说也不是很难。我WA了一次,主要是因为没看清,替换元音字母的同时也要替换大小写……

代码

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
38
39
40
41
42
43
44
45
46
47
class Solution {
private:
string toLower(string x) {
string l;
for (char ch: x)
l += 'A' <= ch && ch <= 'Z' ? ch - 'A' + 'a' : ch;
return l;
}

string toVowel(string x) {
string v;
for (char ch: x)
v += ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 'a' : ch;
return v;
}

public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
set<string> exact;
map<string, int> lower;
map<string, int> vowel;
for (int i = 0; i < wordlist.size(); i++) {
exact.insert(wordlist[i]);
string l = toLower(wordlist[i]);
if (lower.find(l) == lower.end())
lower[l] = i;
string v = toVowel(l);
if (vowel.find(v) == vowel.end())
vowel[v] = i;
}

vector<string> ans;
for (string x: queries) {
string l = toLower(x);
string v = toVowel(l);
if (exact.find(x) != exact.end())
ans.push_back(x);
else if (lower.find(l) != lower.end())
ans.push_back(wordlist[lower[l]]);
else if (vowel.find(v) != vowel.end())
ans.push_back(wordlist[vowel[v]]);
else
ans.push_back("");
}
return ans;
}
};

题目来源:https://leetcode.com/problems/n-repeated-element-in-size-2n-array/description/

标记难度:Easy

提交次数:4/4

代码效率:

  • 排序:36ms
  • 计数:32ms
  • reduce:40ms
  • 随机:40ms

题意

有一个长度为2N的数组,其中有N+1个不同元素,且只有一个元素出现了N次。返回这个元素。

分析

比赛时我用的是最简单的方法,排序:排序之后直接比较前后的数是否相等。


排序可以说是最low的方法了(复杂度高达O(N^2)),但在比赛时根据KISS原则,这么写也是合理的。

用哈希表显然也可以做,方法十分简单,不多说了。

下一种方法基于一种有趣的观察,我称之为reduce:把一个整个数组的性质(N个重复数字,不妨设为x;其他N个数字都是不重复的)缩小到其中一部分元素的性质。在所有的长度为4的子序列中,其中必然至少有一个出现了两个x。原因是这样的:考虑把这个子序列分成两个长度为2的子序列:由鸽巢原理,其中必然至少有一个数字是x。但是单看长度为2的子序列是无法判断的(因为x只会出现N次,无法保证一定会出现包含两个x的子序列),所以只能看长度为4的子序列。如果至少有一个出现了两个x的长度为2的子序列,则包含这个子序列的长度为4的子序列必然也至少包含两个x;如果每个长度为2的子序列都只有一个x,那么仍然至少存在一个出现了两个x的长度为4的子序列。[1]

最后一种不太有趣的解法是随机。每次随机取两个元素,然后判断它们是否相等,不相等则继续找。

代码

排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
sort(A.begin(), A.end());
for (int i = 1; i < A.size(); i++) {
if (A[i-1] == A[i])
return A[i];
}
return -1;
}
};

计数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
unordered_set<int> s;
for (int x: A) {
if (s.find(x) != s.end()) return x;
s.insert(x);
}
return -1;
}
};

reduce

感觉还是写得有点复杂。不需要用这么多判断。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
for (int i = 0; i < A.size() - 3; i++) {
if (A[i] == A[i+1] || A[i] == A[i+2] || A[i] == A[i+3]) return A[i];
if (A[i+1] == A[i+2] || A[i+1] == A[i+3]) return A[i+1];
if (A[i+2] == A[i+3]) return A[i+2];
}
return -1;
}
};

随机

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
int N = A.size();
while (true) {
int i1 = rand() % N, i2 = rand() % N;
if (i1 == i2) continue;
if (A[i1] == A[i2]) return A[i1];
}
return -1;
}
};

  1. LeetCode Official Solution - 961. N-Repeated Element in Size 2N Array

题目来源:https://leetcode.com/problems/verifying-an-alien-dictionary/description/

标记难度:Easy

提交次数:1/1

代码效率:8ms

题意

给定一堆字符串和一个字母排列order,问在该字母表顺序下,这些字符串是否是排好序的。

分析

这次我还是去参加了internal contest。但是这次的状况比较混乱,第三题出现了函数签名搞错的情况,赛后也没有人统计反馈改题什么的。(虽然也许我知道为什么。)这次我第四题没做出来。


这道题很水。一种方法是手动比较相邻两个字符串的大小(注意“空”和“有字符”的情况的比较)[1];另一种方法就是直接根据字母排列把字符串映射到正常顺序,然后直接比较[2]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
int orderMap[26];
for (int i = 0; i < 26; i++) {
orderMap[order[i] - 'a'] = i;
}
vector<string> mappedWords;
for (string word: words) {
string x = word;
for (int i = 0; i < x.length(); i++)
x[i] = orderMap[x[i] - 'a'] + 'a';
mappedWords.push_back(x);
}
for (int i = 1; i < mappedWords.size(); i++)
if (mappedWords[i] < mappedWords[i-1])
return false;
return true;
}
};

  1. LeetCode Official Solution for 953. Verifying an Alien Dictionary

  2. lee215's Solution for LeetCode 953 - [C++/Python] Mapping to Normal Order

题目来源:https://leetcode.com/problems/repeated-dna-sequences/description/

标记难度:Medium

提交次数:2/3

代码效率:

  • 普通的map:84.31%
  • bitset+Rolling hash:99.74%

题意

有一个只包含ATGC的字符串序列,求其中全部长度为10的且出现了不止一次的序列。

分析

初步的想法

只要使用unordered_map作为Hash表,那就很简单了:只要依次遍历所有长度为10的字符串,然后把它们加入到unordered_map中,最后统计unordered_map中出现长度多于1次的序列即可。显然这个方法是可行的。

交上去之后我居然还写错了一次长度为10的子串的边界条件,所以wa了。

如何加速?

上述做法存在几个显而易见的问题:

  • 最后需要多遍历一次unordered_map,能否节省这一次遍历?
  • unordered_map<string, int>的速度是否太慢?
  • 是否存在对string的更好的hash方法?

所以可以进行如下改进:

  • 用两个Hash表来存储序列,一个存储的是所有出现过的序列,另一个只存储至少出现了两次的序列,这样就可以节省最后的一次遍历了。
  • 改为采用Rolling Hash的方法滚动计算Hash值,并利用位运算进一步减少计算所需的时间。
  • 由于对Hash值的范围进行了限定,因此可以改用其他的数据结构(如bitset)作为Hash表。

至于Rolling Hash如何和位运算结合起来,我见到的一种比较好的平衡了编写难度和运行时间的写法[1]是这样的:

  • 把4个字符分别映射为0、1、2、3
  • 对每一个新的序列计算Hash值时,先令hash = (hash << 2) | charMap[ch]
  • 显然hash的长度固定为20bit,其最大值为(1 << 20) - 1(全为1),因此可以通过hash &= (1 << 20) - 1的方法来去掉最前面的项

此处使用的应该是Polynomial rolling hash,很类似于四进制的一种想法(也因此能保证hash函数是双射的)。


从中至少可以学到几点:

  1. 位运算是个很好用的东西(前提是没有写错)
  2. bitset在适当的时候可以拿来代替Hash表或者大数组,但一般来说并不是一个关键数据结构

代码

普通的map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.length();
unordered_map<string, int> mmap;
vector<string> ans;

for (int i = 0; i <= n - 10; i++) {
string str = s.substr(i, 10);
mmap[str]++;
}
for (const auto& k: mmap) {
if (k.second > 1)
ans.push_back(k.first);
}
return ans;
}
};

bitset+Rolling hash

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
38
// 参考了https://leetcode.com/submissions/detail/180202097/
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.length();
if (n < 11) return {};

// cheap mapping
int charToInt[200];
charToInt['A'] = 0;
charToInt['C'] = 1;
charToInt['G'] = 2;
charToInt['T'] = 3;

const int MASK = (1 << 20) - 1;
int rhash = 0;
for (int i = 0; i < 9; i++)
rhash = (rhash << 2) | charToInt[s[i]];

// use bitset as hash table
bitset<(1 << 20)> onceSet;
bitset<(1 << 20)> twiceSet;
vector<string> ans;
for (int i = 9; i < n; i++) {
rhash = (rhash << 2) | charToInt[s[i]];
rhash &= MASK;
// 简化代码逻辑
if (twiceSet[rhash]) continue;
if (onceSet[rhash]) {
ans.push_back(s.substr(i - 9, 10));
twiceSet.set(rhash);
}
else
onceSet.set(rhash);
}
return ans;
}
};

  1. sample 4 ms submission

题目来源:https://leetcode.com/problems/word-subsets/description/

标记难度:Medium

提交次数:1/1

代码效率:176ms

题意

给定字符串数组AB,如果字符串b中每个字符的出现次数都<=该字符在a中的出现次数,则称ba的子集。如果对于B中的每个字符串bb都是a的子集,则称a为“universal”。问A中有多少个字符串是“universal”的。

分析

这道题也非常简单。如果a是“universal”的,说明

$$\forall b \in B, \forall char, count_{char}(a) \geq count_{char}(b)$$

$$\forall char, \forall b \in B, count_{char}(a) \geq count_{char}(b)$$

$$\forall char, count_{char}(a) \geq \max_{\forall b \in B}{count_{char}(b)}$$

只要a满足以上条件就可以了。[1]

代码

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
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
int allb[26], b[26], a[26];
memset(allb, 0, sizeof(allb));
for (string bs: B) {
memset(b, 0, sizeof(b));
for (char ch: bs)
b[ch - 'a']++;
for (int i = 0; i < 26; i++)
allb[i] = max(allb[i], b[i]);
}

vector<string> ans;
for (string as: A) {
memset(a, 0, sizeof(a));
for (char ch: as)
a[ch - 'a']++;
bool ok = true;
for (int i = 0; i < 26; i++)
if (a[i] < allb[i]) {
ok = false;
break;
}
if (ok)
ans.push_back(as);
}
return ans;
}
};

  1. Leetcode 916 Solution

题目来源:https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/description/

标记难度:Easy

提交次数:1/1

代码效率:12ms

题意

给定若干个元素,问每种元素的数量的最大公约数。

分析

这次比赛时我正在上《信号处理原理》。所以就随便写了一下。前三题过于水了,一共花了不到20分钟……然后我觉得第四题应该要用对抗搜索,就直接上课了,没去管它。后来我发现我居然是51 / 3579名,4道题都做出来的一共41个人,而做出来三道题的超过了1000个人。所以这是一次拼手速的比赛。


直接用hash表统计元素数量加gcd算法就好了,这道题真的水……

代码

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 {
private:
int gcd(int x, int y) {
if (x % y == 0) return y;
return gcd(y, x % y);
}

public:
bool hasGroupsSizeX(vector<int>& deck) {
int h[10005];
memset(h, 0, sizeof(h));
for (int d: deck)
h[d]++;
int g = -1;
for (int i = 0; i < 10000; i++) {
if (g == 1) break;
if (h[i] > 0) {
if (g == -1)
g = h[i];
else
g = gcd(h[i], g);
}
}
return g > 1;
}
};

题目来源:https://leetcode.com/problems/online-election/description/

标记难度:Medium

提交次数:2/4

代码效率:

  • 使用BST进行离线计算:248ms
  • 线性扫描:384ms
  • 二维链表:396ms

题意

给定N个时间点,在times[i]时刻,就有一个人投票给person[i]。对于若干个时刻t,请给出t时刻领先的人。

分析

这道题的设计好像不是很适合在线方法,所以我觉得离线还是比较合适的。

BST+二分查找

我比赛的时候用了一种相当之麻烦的方法——仍然是用优先队列的思想,在TreeSet中存储(person, votes, recency)的元组,然后在每个有人投票的时间点,更新TreeSet,并找出当前领先的人,保存下来;之后在查询的时候进行二分查找。这种方法的复杂度大约是O(N * log(N) + M * log(N))(假定M是查询的总次数)。

线性扫描+二分查找

事实上找出各个时刻领先的人并不需要这么麻烦。事实上personstimes数组都是已经排好序的了。因此,可以用一个map来维护每个人的票数,然后在每个时刻更新被投票的人的票数,并判断当前领先的人是否会变成这个人。如果不变的话,完全可以忽略这个时间点。这种方法的复杂度大约是O(N + M * log(N))[1]

二维链表

我感觉这是一种特别神奇的做法……简单来说,我觉得可以维护一个vector<vector<pair<int, int>>,其中外层vector的含义是,所有投的是某人的第i票的选票;内层vector按时间顺序存储了每张选票的(person, time)。用题目中的例子来描述一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]

+------+ +---+ +---+ +---+ +---+
| Head |----| 1 |------| 2 |------| 3 |------| 4 | count
+------+ +-+-+ +-+-+ +-+-+ +---+
| | | |
+-+-+ -+-+-+- -+-+-+- -+-+-+- |
|0,0| |1, 10| |0, 20| |0, 30| |
+-+-+ -+-+-+- -+-+-+- -+-+-+- | Most recent
| | | |
+-+-+ -+-+-+- -+-+-+- |
|1,5| |0, 15| |1, 25| |
+-+-+ -+-+-+- -+-+-+- v

然后很显然,每个外层vector的第一个元素都是递增的,每个内层vector自己也是递增的。对于每个时间点,我们可以首先对外层vector进行二分查找,然后再在内层进行二分查找。整体复杂度是O(N + M * log(N)^2)[2]

以及,我觉得这种做法有些像Leetcode 460中给出的HashMap+List方法。

代码

BST

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class TopVotedCandidate {
private:
vector<pair<int, int>> timesOfVote; // time, vote
vector<int> times;
vector<int> leaders;
int N;

struct VotedPerson {
int person;
int recency;
int votes;

VotedPerson(int p, int r, int v) {
person = p;
recency = r;
votes = v;
}

friend bool operator < (const VotedPerson& p1, const VotedPerson& p2) {
if (p1.votes != p2.votes) return p1.votes > p2.votes;
return p1.recency > p2.recency;
}

friend bool operator == (const VotedPerson& p1, const VotedPerson& p2) {
return p1.person == p2.person && p1.recency == p2.recency && p1.votes == p2.votes;
}
};

public:
TopVotedCandidate(vector<int> persons, vector<int> times) {
N = persons.size();
for (int i = 0; i < N; i++) {
timesOfVote.emplace_back(times[i], persons[i]);
}
sort(timesOfVote.begin(), timesOfVote.end());

unordered_map<int, int> recMap; // person to recency
unordered_map<int, int> voteMap; // person to vote
set<VotedPerson> treeSet;
for (int i = 0; i < N; i++) {
int person = timesOfVote[i].second;
int time = timesOfVote[i].first;
int recency = recMap[person];
int votes = voteMap[person];
auto it = treeSet.find(VotedPerson(person, recency, votes));
if (it != treeSet.end()) treeSet.erase(it);
recMap[person] = recency = i;
voteMap[person]++;
votes++;
treeSet.insert(VotedPerson(person, recency, votes));

this->times.push_back(time);
this->leaders.push_back(treeSet.begin()->person);
}
}

int q(int t) {
auto it = upper_bound(times.begin(), times.end(), t);
it--;
return leaders[it - times.begin()];
}
};

线性扫描

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
class TopVotedCandidate {
private:
vector<int> leader;
vector<int> ctimes;

public:
TopVotedCandidate(vector<int> persons, vector<int> times) {
unordered_map<int, int> voteMap;
int curLeader = -1, curLeadVotes = -1;
for (int i = 0; i < persons.size(); i++) {
voteMap[persons[i]]++;
if (voteMap[persons[i]] >= curLeadVotes) {
curLeadVotes = voteMap[persons[i]];
curLeader = persons[i];
leader.push_back(curLeader);
ctimes.push_back(times[i]);
}
}
}

int q(int t) {
auto it = upper_bound(ctimes.begin(), ctimes.end(), t);
return leader[it - ctimes.begin() - 1];
}
};

二维链表

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
38
39
40
class TopVotedCandidate {
private:
vector<vector<pair<int, int>>> bucket; // (time, person)

public:
TopVotedCandidate(vector<int> persons, vector<int> times) {
unordered_map<int, int> voteMap;
for (int i = 0; i < persons.size(); i++) {
voteMap[persons[i]]++;
int c = voteMap[persons[i]];
while (bucket.size() < c) bucket.push_back(vector<pair<int, int>>());
bucket[c-1].emplace_back(times[i], persons[i]);
}
}

int q(int t) {
int l = 0, r = bucket.size();
// upper_bound, then -1
while (l < r) {
int mid = l + (r - l) / 2;
if (bucket[mid][0].first <= t)
l = mid + 1;
else
r = mid;
}
int i = l - 1;

l = 0, r = bucket[i].size();
while (l < r) {
int mid = l + (r - l) / 2;
if (bucket[i][mid].first <= t)
l = mid + 1;
else
r = mid;
}
int j = l - 1;
if (j < 0) j = 0;
return bucket[i][j].second;
}
};

  1. [C++/Java/Python] Binary Search in Times

  2. 911. Online Election, Approach 2: Precomputed Answer + Binary Search

题目来源:https://leetcode.com/problems/merge-two-sorted-lists/description/

标记难度:Easy

提交次数:4/9

代码效率:

  • map O(n):3.13%
  • HashMap + list O(1):45.28%
  • TreeSet + map O(log(n)):23.78%
  • 简单版map + list O(1):11.36%

题意

实现LFU缓存。

分析

map O(n)

这是我想出来的第一种做法:用三个map分别记录每个key对应的值(valueMap)、访问次数(freqMap)和最近访问时间(recentMap)。

  • get(int key):在valueMap中查找key对应的值,然后更新freqMaprecentMap
  • put(int key, int value)
    • 如果不需要换出,则直接更新三个map中维护的值
    • 如果需要换出,则遍历当前的所有key,从中找出访问频率最小的最不频繁访问的元素,把它换出,再插入新元素

这种做法显然不是很聪明。

HashMap + list O(1)

这是一种相对比较复杂的方法,原理是这样的[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Increasing frequencies
---------------------------------->

+------+ +---+ +---+ +---+
| Head |----| 1 |----| 5 |----| 9 | Frequencies
+------+ +-+-+ +-+-+ +-+-+
| | |
+-+-+ +-+-+ +-+-+ |
|2,3| |4,3| |6,2| |
+-+-+ +-+-+ +-+-+ | Most recent
| | |
+-+-+ +-+-+ |
key,value pairs |1,2| |7,9| |
+---+ +---+ v

作者在代码中维护了两个数据结构:

  • unordered_map<int, pair<list<LRUNode>::iterator, list<pair<int, int>>::iterator>> kv_:存放每个key对应的桶的头结点,以及key在桶中对应的具体结点
  • list<LRUNode> cache_:所有桶组成的链表;其中LRUNode = (int freq, list<pair<int, int>> vals),表示频率freqkey组成的链表,其中pair的第一项表示key,第二项表示value

具体实现的核心是三个成员函数:

  • promote(int key, int val):找到key对应的桶的头结点ikey在桶中对应的结点j,以及下一个频率对应的桶k,在有必要的情况下取出j->second;然后从i中删除j,把i插入到k的最末端。
  • evict():找到频率最小的桶i,以及位于桶头部的访问最不频繁的结点j,然后从ikv_中删除j
  • insert(int key, int val):找到频率最小的桶i,如果i对应的频率不是1,则在cahce_头部插入一个新的桶,对应的频率为1;最后在该桶的末端插入(key, val)

利用上述函数很容易实现getput,我就不写了。


我的实现方法则比较复杂。维护4个map和一个list

  • unordered_map<int, int> valMap:存放keyvalue的对应关系
  • unordered_map<int, int> freqMap:存放key和访问频率的对应关系
  • unordered_map<int, list<list<int>>::iterator> headMap:存放访问频率和桶的对应关系
  • unordered_map<int, list<int>::iterator> nodeMap:存放key和桶中结点的对应关系
  • list<list<int>> buckets:桶

实现了一个更新函数touch(int key),主要功能是将key的访问频率+1,即把keyheadMap[freqMap[key]]对应的桶中删除,放入headMap[freqMap[key] + 1]对应的桶中,并更新各map之间的关系。

  • get(int key):在valMap中查找key,如果key不存在则返回-1;如果存在则执行touch(key),然后返回valMap[key]
  • put(int key, int value)
    • 如果key已经存在,则执行touch(key),并更新valMap
    • 如果key不存在且需要换出,则在buckets中找到当前对应频率值最低的桶,将桶中最末一个元素删除,并更新其他map
    • 最后将(还不存在的)key插入访问频率1对应的桶中,更新其他map

TreeSet + map O(log(n))

上一种方法实在是太繁琐了,于是我又发现了另一种利用TreeSet(或者说优先队列)的方法。[2]

  • 维护一个集合treeSet(对C++来说,用priority_queue有一些缺陷,所以此处实际上用的是set),其中的元素是(frequency, recency, key)
  • unordered_map<int, int> valMap,用于存储keyvalue的对应关系。
  • unordered_map<int, (frequency, recency, key)> keyMap,用于存储keyfreqrecency的对应关系。

实现一种touch(int key)操作:在treeSet中删除当前的keyMap[key],更新key的访问频率(keyMap[key].frequency++),并将更新后的keyMap[key]重新插入到treeSet中。

  • get(int key):在valMap中查找key,如果找不到则返回-1;否则执行touch(key)
  • put(int key, int value)
    • 如果key已经存在,则执行touch(key)
    • 如果key不存在且需要换出,则通过treeSet->begin()找到当前的LFUkey,从treeSet和其他map中删除该key对应的元素。
    • 最后,令keyMap[key] = (1, curTime, key)valMap[key] = value,将keyMap[key]插入到treeSet中。

由于treeSet中按值查找、删除和插入的复杂度都是O(log(n)),所以这种方法的时间复杂度是O(log(n)),比之前的方法稍微高一点,不过写起来方便多了。

以及,随便说一下C++中鸡肋一般的priority_queue。事实上,像这道题中这样的需求——插入元素、寻找最小元素、删除最小元素、元素下滤(显然对元素的操作只会使frequencyrecency增加)——是很适合堆的。然而C++中并没有为priority_queue提供修改其中元素的接口,如果想要实现,大概只能自己继承这个类然后重写。Java中的PriorityQueue倒是有remove接口,但时间复杂度是O(n)。那还不如用set(Java中的TreeSet)和运算符重载算了。

不过我之前从未想过,set可以实现和priority_queue类似的功能这回事,而且时间复杂度差不多。嗯,只是差不多而已,此处又想起了邓公的话:

由上可见,上滤调整过程中交换操作的累计次数,不致超过全堆的高度$\lfloor \log_2{(n)} \rfloor$。 而在向量中, 每次交换操作只需常数时间,故上滤调整乃至整个词条插入算法整体的时间复杂度,均为$O(\log{n})$。这也是从一个方面,兑现了10.1节末尾就优先级队列性能所做的承诺。
当然,不难通过构造实例说明,新词条有时的确需要一直上滤至堆顶。然而实际上,此类最坏情况通常极为罕见。以常规的随机分布而言,新词条平均需要爬升的高度,要远远低于直觉的估计(习题[10-6])。[3]

不过,我觉得在这道题的语境下,优先队列的上滤过程恐怕没有那么大的优势(因为插入的新元素的frequency必然为1,因此很可能会上升到堆中比较高的位置),下滤过程倒可能有类似的效果(因为下滤时作为排序的第一关键字的frequency只增加了1,因此很可能不需要下降很多层)。

简单版map + list O(1)

这是最简单的一种方法了。本质上也是利用桶排序,但是这种方法利用了一个我们之前都没有注意到的事实:插入新key时,它的frequency必然是1。因此我们并不需要一个有序集或一个链表来维护最小的访问频率,因为在删除一个访问频率最小的结点之后,插入的新结点的频率(1)必然是现在的最小频率。这样,我们就可以用一个unordered_map<int, list<int>>来存储访问频率和桶的对应的关系了。

其余的想法和第一种桶排序是非常类似的。具体内容看代码和注释好了。


有一件很有趣的事情。在这种方法中,我仍然需要维护一个unordered_map<int, list<int>::iterator> iterMap,用于从桶中删除元素;但是Java里有一个比较神奇的东西,叫LinkedHashSet,同时实现了链表和哈希表的特性,所以Java代码会看起来好看一点。[4]不过也许它内部也就是把一个HashSet<Type, ListNode>和一个ListNode<Type>这样拼起来的。

代码

map O(n)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class LFUCache {
private:
unordered_map<int, int> valueMap;
unordered_map<int, int> freqMap;
unordered_map<int, int> recentMap;

int time;
int cap;
int num;

public:
LFUCache(int capacity) {
time = 0;
num = 0;
cap = capacity;
}

int get(int key) {
auto i = valueMap.find(key);
if (i == valueMap.end())
return -1;

recentMap[key] = time;
freqMap[key]++;

time++;
return i->second;
}

void put(int key, int value) {
// 这是一个不容易注意到的corner case
// 虽然毫无意义。
if (cap == 0)
return;

if (valueMap.find(key) != valueMap.end()) {
valueMap[key] = value;
freqMap[key]++;
recentMap[key] = time;

time++;
return;
}
if (num >= cap) {
// find LFU
int minKey = -1, minFreq, minRec;
// 遍历所有的key,找到其中freq和recent最小的
for (auto const& i: freqMap) {
int freq = i.second;
int recent = recentMap[i.first];
if (minKey == -1 || freq < minFreq || (freq == minFreq && recent < minRec)) {
minKey = i.first;
minFreq = freq;
minRec = recent;
}
}
// cout << minKey << ' ' << minFreq << ' ' << minRec << endl;
valueMap.erase(minKey);
freqMap.erase(minKey);
recentMap.erase(minKey);
num--;
}

valueMap[key] = value;
freqMap[key]++;
recentMap[key] = time;
num++;

time++;
return;
}
};

HashMap + list O(1)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class LFUCache {
private:
unordered_map<int, int> valMap; // key --> value
unordered_map<int, int> freqMap; // key --> frequence
unordered_map<int, list<list<int>>::iterator> headMap; // frequence --> bucket head
unordered_map<int, list<int>::iterator> nodeMap; // key --> node in list
list<list<int>> buckets; // buckets

int cap;
int num;

/* increase the frequence of @key */
void touch(int key) {
int freq = freqMap[key];
auto head = headMap[freq]; // head of the bucket containing key
auto node = nodeMap[key]; // the list node containing key
head->erase(node); // delete the key from this bucket
// find new bucket head
auto newHead = head;
if (headMap.find(freq + 1) != headMap.end())
newHead = headMap[freq + 1];
else {
// Note: that's "insert before" for C++
buckets.insert(head, list<int>());
newHead--;
}
// insert the key into another bucket
// put the most recent values in the front
newHead->push_front(key);
// delete empty bucket (for convenience of finding LFU)
if (head->empty()) {
buckets.erase(head);
headMap.erase(freq);
}
// update the maps
freqMap[key]++;
headMap[freq + 1] = newHead;
nodeMap[key] = newHead->begin();
}

public:
LFUCache(int capacity) {
cap = capacity;
num = 0;
}

int get(int key) {
if (valMap.find(key) == valMap.end()) return -1;
touch(key); // update frequence
return valMap[key];
}

void put(int key, int value) {
if (cap == 0) return;

// Only update value
if (valMap.find(key) != valMap.end()) {
valMap[key] = value;
touch(key);
return;
}
// Need to evict a LFU key-value pair
if (num >= cap) {
// find the head of the bucket of minimum frequency
auto head = buckets.end();
head--;
// find least visited key of this frequency and delete it
int evict = head->back();
head->pop_back();
int freq = freqMap[evict];
// if this bucket becomes empty, then delete it
if (head->empty()) {
headMap.erase(freq);
buckets.pop_back();
}
// delete the evicted key
valMap.erase(evict);
freqMap.erase(evict);
nodeMap.erase(evict);
num--;
}

// find the head of frequency 1
if (headMap.find(1) == headMap.end()) {
buckets.push_back(list<int>());
auto head = buckets.end(); head--;
headMap[1] = head;
}
// insert new key at the front of list
auto head = headMap[1];
head->push_front(key);
nodeMap[key] = head->begin();
valMap[key] = value;
freqMap[key] = 1;
num++;
}
};

TreeSet + map O(log(n))

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class LFUCache {
private:
struct Tuple {
int key;
int freq;
int recent;

Tuple() {}

Tuple(int x, int y, int z): key(x), freq(y), recent(z) {}

// For ordered set
friend bool operator < (const Tuple& a, const Tuple& b) {
if (a.freq != b.freq) return a.freq < b.freq;
return a.recent < b.recent;
}

friend bool operator == (const Tuple& a, const Tuple& b) {
return a.key==b.key && a.freq==b.freq && a.recent==b.recent;
}
};

unordered_map<int, int> valMap;
unordered_map<int, Tuple> keyMap;
set<Tuple> treeSet;
int num;
int cap;
int time;

public:
LFUCache(int capacity) {
num = 0;
time = 0;
cap = capacity;
}

int get(int key) {
if (valMap.find(key) == valMap.end()) return -1;
// Erase old Tuple and insert new one
treeSet.erase(keyMap[key]);
keyMap[key].freq++;
keyMap[key].recent = time;
treeSet.insert(keyMap[key]);
time++;
return valMap[key];
}

void put(int key, int value) {
if (cap <= 0) return;

if (valMap.find(key) != valMap.end()) {
treeSet.erase(keyMap[key]);
keyMap[key].freq++;
keyMap[key].recent = time;
valMap[key] = value;
treeSet.insert(keyMap[key]);
}
else {
if (num >= cap) {
// Find LFU (ordered set head)
auto iter = treeSet.begin();
int evict = iter->key;
treeSet.erase(iter);
valMap.erase(evict);
keyMap.erase(evict);
num--;
}
keyMap[key] = Tuple(key, 1, time);
treeSet.insert(keyMap[key]);
valMap[key] = value;
num++;
}
time++;
}
};

简单版map + list O(1)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class LFUCache {
private:
unordered_map<int, int> valMap;
unordered_map<int, int> freqMap;
unordered_map<int, list<int>::iterator> iterMap;
unordered_map<int, list<int>> bucketMap;
int minFreq;
int cap;
int num;

// visit @key
void touch(int key) {
int freq = freqMap[key];
auto iter = iterMap[key];
bucketMap[freq].erase(iter); // erase key from old bucket
if (freq == minFreq && bucketMap[freq].empty()) // update minFreq
minFreq++;
bucketMap[freq + 1].push_front(key); // insert key to new bucket
iterMap[key] = bucketMap[freq + 1].begin();
freqMap[key]++;
}

public:
LFUCache(int capacity) {
cap = capacity;
num = 0;
minFreq = 1;
}

int get(int key) {
if (freqMap.find(key) == freqMap.end()) return -1;
touch(key);
return valMap[key];
}

void put(int key, int value) {
if (cap == 0) return;

if (freqMap.find(key) != freqMap.end()) {
valMap[key] = value;
touch(key);
return;
}
if (num >= cap) {
int evict = bucketMap[minFreq].back(); // find LFU
// delete LFU
bucketMap[minFreq].pop_back();
valMap.erase(evict);
freqMap.erase(evict);
iterMap.erase(evict);
num--;
}
// because the freq of new key is 1, minFreq will certainly become 1
minFreq = 1;
bucketMap[1].push_front(key);
valMap[key] = value;
freqMap[key] = 1;
iterMap[key] = bucketMap[1].begin();
num++;
}
};

  1. C++ list with hashmap with explanation

  2. Java solution using PriorityQueue, with detailed explanation

  3. 《数据结构(C++语言版)》(第三版) P290,清华大学出版社,2013.9

  4. JAVA O(1) very easy solution using 3 HashMaps and LinkedHashSet

题目来源:https://leetcode.com/problems/merge-two-sorted-lists/description/

标记难度:Hard

提交次数:1/1

代码效率:

  • 手写链表+map:92.93%
  • list+map:33.54%

题意

实现一个LRU缓存的功能。

分析

这个问题的标准答案显然是:

  • 用一个map<int, int>维护(key, value)
  • 用一个双向链表维护访问顺序
  • 用一个map<int, Node*>查询key在链表中对应的结点

然后具体操作是:

  • 查询:在map<int, int>中查询有没有这个key,如果找到了,则在map<int, Node*>中找到它对应的Node*,在链表中把它的位置移到链表最前面
  • 插入:
    • 如果不需要删除旧结点,则新建一个Node*,把它插入到链表最前面;维护map<int, int>map<int, Node*>
    • 如果需要删除旧结点,则把链表最末端的Node*取出来并删掉,得到对应的key,在两个map中删除对应元素;然后再插入新结点

手写一个双向链表并不难,不过更好的方法是利用std::list,我之前从未用过。list满足链表的一般性质,也就是迭代器只会因为删除而失效,不会因为其他原因失效。[1]

代码

手写list

一个事实是,在使用了哨兵结点headtail之后,在deleteNodeinsertBeforeinsertAfter函数中,其实都不需要检查空结点了。[2]

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class LRUCache {
private:
struct Node {
int key;
Node* prev;
Node* next;

Node(int k) {
key = k;
prev = next = nullptr;
}
};

void deleteNode(Node* node) {
Node* prev = node->prev;
Node* next = node->next;
if (prev != nullptr)
prev->next = next;
if (next != nullptr)
next->prev = prev;
}

void insertBefore(Node* node, Node* i) {
Node* prev = node->prev;
if (prev != nullptr) prev->next = i;
i->prev = prev;
i->next = node;
node->prev = i;
}

void insertAfter(Node* node, Node* i) {
Node* next = node->next;
if (next != nullptr) next->prev = i;
i->prev = node;
i->next = next;
node->next = i;
}

void moveToFront(Node* node) {
deleteNode(node);
insertAfter(head, node);
}

int capacity;
int num;
unordered_map<int, int> valMap;
unordered_map<int, Node*> nodeMap;
Node* head;
Node* tail;

public:
LRUCache(int capacity) {
this->capacity = capacity;
num = 0;
head = new Node(-1);
tail = new Node(-1);
head->next = tail;
tail->prev = head;
}

int get(int key) {
auto i = valMap.find(key);
if (i == valMap.end())
return -1;
moveToFront(nodeMap[key]);
return i->second;
}

void put(int key, int value) {
if (valMap.find(key) != valMap.end()) {
valMap[key] = value;
moveToFront(nodeMap[key]);
}
else {
if (num < capacity) {
Node* node = new Node(key);
nodeMap[key] = node;
valMap[key] = value;
insertAfter(head, node);
num++;
}
else {
// evict out a least used one
Node* node = tail->prev;
deleteNode(node);
nodeMap.erase(node->key);
valMap.erase(node->key);

node->key = key;
nodeMap[key] = node;
valMap[key] = value;
insertAfter(head, node);
}
}
}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

STL list

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class LRUCache {
private:
int capacity;
int num;
unordered_map<int, int> valMap;
unordered_map<int, list<int>::iterator> posMap;
list<int> orderList;

void moveToFront(int key) {
orderList.erase(posMap[key]);
orderList.push_front(key);
posMap[key] = orderList.begin();
}

public:
LRUCache(int capacity) {
this->capacity = capacity;
num = 0;
}

int get(int key) {
auto i = valMap.find(key);
if (i == valMap.end())
return -1;
moveToFront(key);
return i->second;
}

void put(int key, int value) {
if (valMap.find(key) != valMap.end()) {
valMap[key] = value;
moveToFront(key);
}
else {
if (num < capacity) {
valMap[key] = value;
orderList.push_front(key);
posMap[key] = orderList.begin();
num++;
}
else {
// evict out a least used one
int evict = orderList.back();
orderList.pop_back();
valMap.erase(evict);
posMap.erase(evict);

valMap[key] = value;
orderList.push_front(key);
posMap[key] = orderList.begin();
}
}
}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

  1. C++11 code 74ms - Hash table + List

  2. Hashtable + Double linked list (with a touch of pseudo nodes)