嗯,即使是我,最终也会发现Leetcode中有些题太水了而不值得专门写一篇post,有些题太愚蠢了而不值得专门写一篇post,等等。但有时候还是有一些可写的东西,所以就放在这里好了。

在LeetCode中卡时

点开0ms Solution的时候常常会见到这样一段:

1
2
3
4
5
static int speedup=[](){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();

函数内部的内容很好理解:关闭C和C++标准输入输出流的同步,并且将cincout解除绑定(在切换时不再自动flush)。[1]但外面包的那一堆看起来很不好懂。事实上这是一个立即执行的Lambda表达式。[2]

简单来说,Lambda表达式的一种形式是[captures] (params) {body},此时返回值是由return语句推导的。例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 泛型 lambda , operator() 是有二个形参的模板
auto glambda = [](auto a, auto&& b) { return a < b; };
bool b = glambda(3, 3.14); // ok

// 泛型 lambda , operator() 是有一个形参的模板
auto vglambda = [](auto printer) {
return [=](auto&&... ts) // 泛型 lambda , ts 是形参包
{
printer(std::forward<decltype(ts)>(ts)...);
return [=] { printer(ts...); }; // 空型 lambda (不接收参数)
};
};
auto p = vglambda([](auto v1, auto v2, auto v3) { std::cout << v1 << v2 << v3; });
auto q = p(1, 'a', 3.14); // 输出 1a3.14
q(); // 输出 1a3.14

所以上图就是一个没有参数、返回值为0且立即执行的Lambda表达式。之所以要写成这样好像也很容易理解,全局变量会先初始化,此时就可以在开始真正的输入输出之前进行优化了。如果直接写到函数里,那这个时候都已经完成读入了……

(感谢rd同学告诉我那是个Lambda函数)

17. Letter Combinations of a Phone Number

题目来源:https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

难度:Medium

知识点:字符串

把数字串映射到字母串,每个数字的映射方法是电话按键(例:2 -> abc),问一共有多少种可能的映射方法。

直接……做就……好了。

以及,能不硬编码就不要硬编码……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) return {};

vector<string> ans = {""};
vector<string> a2;
vector<string> maps = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for (char c: digits) {
for (string x: ans) {
for (char a: maps[c - '0'])
a2.push_back(x + a);
}
swap(ans, a2);
a2.clear();
}
return ans;
}
};

23. Merge k Sorted Lists

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

难度:Hard

知识点:优先队列

多个有序链表合并。和有序数组合并非常相似,直接用优先队列就好了。

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 Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* head = nullptr, *p = nullptr;
priority_queue<pair<int, ListNode*>> pq;
for (ListNode* q: lists) {
if (q != nullptr)
pq.emplace(-q->val, q);
}
while (!pq.empty()) {
ListNode* q = pq.top().second;
pq.pop();
if (head == nullptr) {
head = p = q;
}
else {
p->next = q;
p = p->next;
}
q = q->next;
if (q != nullptr) pq.emplace(-q->val, q);
}
return head;
}
};

50. Pow(x, n)

题目来源:https://leetcode.com/problems/powx-n/description/

难度:Medium

知识点:快速幂

这道题的有趣之处是增加了对负数幂的考察(当然这也不是很难)。不过,在-2147483648上卡一下还是令人不那么愉快……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
double myPow(double x, int n) {
if (n == -2147483648) {
double y = myPow(x, n / 2);
return y * y;
}
if (n < 0) return myPow(1 / x, -n);
if (n == 0) return 1;
if (n == 1) return x;
double y = myPow(x * x, n / 2);
if (n % 2 == 0) return y;
else return y * x;
}
};

54. Spiral Matrix

题目来源:https://leetcode.com/problems/spiral-matrix/description/

难度:Medium

知识点:数组

题意就是绕着一个二维数组矩形向里转圈。比较平凡的做法是开一个布尔数组当做是墙;稍微好一点的做法就是维护每侧已经被访问的厚度。总之也不是很难。

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:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
// 又卡了一下大小为0的矩阵……
if (matrix.size() == 0) return {};

int n1 = 0, n2 = matrix.size() - 1, m1 = 0, m2 = matrix[0].size() - 1;
int mx[4] = {0, 1, 0, -1}, my[4] = {1, 0, -1, 0};
int k = 0;
int r = 0, c = 0;
vector<int> ans;
while (n1 <= n2 && m1 <= m2) {
// cout << r << ' ' << c << endl;
ans.push_back(matrix[r][c]);
int nr = r + mx[k];
int nc = c + my[k];
if (nr < n1 || nr > n2 || nc < m1 || nc > m2) {
if (k == 0) n1++;
if (k == 1) m2--;
if (k == 2) n2--;
if (k == 3) m1++;
k = (k + 1) % 4;
nr = r + mx[k];
nc = c + my[k];
}
r = nr;
c = nc;
}
return ans;
}
};

66. Plus One

题目来源:https://leetcode.com/problems/plus-one/description/

难度:Easy

知识点:高精度加法

简化版的高精度加法,只考虑+1的情况。唯一的问题可能是在于,数组是正序给的,首位进位稍微有点麻烦。(当然,也可以说:传参是引用,不要直接在参数上改。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
digits[n-1]++;
for (int i = n - 1; i > 0; i--) {
digits[i - 1] += digits[i] / 10;
digits[i] %= 10;
}
if (digits[0] >= 10) {
digits.insert(digits.begin(), digits[0] / 10);
digits[1] %= 10;
}
return digits;
}
};

108. Convert Sorted Array to Binary Search Tree

题目来源:https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

难度:Easy

知识点:Tree

这道题要求把一个排序好的序列转成一棵二叉搜索树,且这棵树是平衡的(任意一个结点的两棵子树的深度之差不超过1)。方法就是每次尽量把序列分成相等的两半,如果不相等右侧多一个结点也没关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
TreeNode* dfs(int l, int r, vector<int>& nums) {
if (l == r) return new TreeNode(nums[l]);
if (l > r) return NULL;
int m = (l + r) / 2;
TreeNode* root = new TreeNode(nums[m]);
root->left = dfs(l, m - 1, nums);
root->right = dfs(m + 1, r, nums);
return root;
}

public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return dfs(0, nums.size() - 1, nums);
}
};

139. Word Break

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

难度:Medium

知识点:DP

问给定的一组字符串能否拼成另一个字符串。很简单的DP。我闲的没事干所以写了个Trie……

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
class Solution {
private:
struct TrieNode {
bool isEnd;
TrieNode* ch[26];

TrieNode() {
isEnd = false;
memset(ch, 0, sizeof(ch));
}
};

public:
bool wordBreak(string s, vector<string>& wordDict) {
TrieNode* root = new TrieNode();
for (string word: wordDict) {
TrieNode* p = root;
for (char c: word) {
if (p->ch[c - 'a'] == NULL)
p->ch[c - 'a'] = new TrieNode();
p = p->ch[c - 'a'];
}
p->isEnd = true;
}
int n = s.length();
bool f[n + 1];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; i++) {
if (i != 0 && !f[i - 1]) continue;
TrieNode* p = root;
for (int j = i; j < n; j++) {
p = p->ch[s[j] - 'a'];
if (p == NULL) break;
if (p->isEnd) f[j] = true;
}
}
return f[n-1];
}
};

140. Word Break II

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

难度:Hard

知识点:DP

这道题和上一道的区别是,要求把全部可能的组成方式都打出来——不过,这仍然是一道DP,至少需要记忆化的思想,因为直接递归打印是会超时的。(以及这道题的Solution要求suscribe,我看不到。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
map<string, vector<string>> f;

public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
if (f.find(s) != f.end()) return f[s];
vector<string> ans;
for (string word: wordDict) {
if (word.length() <= s.length() && s.substr(0, word.length()) == word) {
// cout << word << endl;
if (word == s)
ans.push_back(word);
else {
vector<string> a = wordBreak(s.substr(word.length(), s.length() - word.length()), wordDict);
for (string x: a)
ans.push_back(word + ' ' + x);
}
}
}
f[s] = ans;
return ans;
}
};

237. Delete Node in a Linked List

题目来源:https://leetcode.com/problems/delete-node-in-a-linked-list/description/

难度:Easy

知识点:链表

这道题的傻逼之处在于,明明是要删除链表中的结点,最后却变成了(不得不)交换链表中结点的值,这一点也不科学。我的第一个想法是把给定结点(node)之后的值依次前移然后删掉最后一个结点;题解中给出了只需赋值一次的方法,把node->val替换成node->next->valnode->next也替换成node->next->next。但这方法仍然不怎么样。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* p = node;
while (p->next != nullptr) {
p->val = p->next->val;
if (p->next->next == nullptr) break;
p = p->next;
}
p->next = nullptr;
}
};

328. Odd Even Linked List

题目来源:https://leetcode.com/problems/odd-even-linked-list/description/

难度:Easy

知识点:链表

  • [ ]: 做完328。。。

463. Island Perimeter

题目来源:https://leetcode.com/problems/island-perimeter/description/

难度:Easy

知识点:图

这道题都明确给出了,地图上有且只有一个方格组成的岛,那就直接判断每个方块有几条边框和水邻接就可以了。

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) {
if (grid.size() == 0) return 0;
int n = grid.size(), m = grid[0].size();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) continue;
if (i == 0 || grid[i-1][j] == 0) ans++;
if (i == n -1 || grid[i+1][j] == 0) ans++;
if (j == 0 ||grid[i][j-1] == 0) ans++;
if (j == m - 1 || grid[i][j+1] == 0) ans++;
}
}
return ans;
}
};

657. Robot Return to Origin

题目来源:https://leetcode.com/problems/robot-return-to-origin/description/

难度:Easy

知识点:字符串

给定一个机器人上下左右移动的路线,问机器人最后有没有回到原来的位置。第一想法是模拟,自然是能过的;不过事实上,回到原点这件事等价于上下位移为0且左右位移为0,所以直接判断位移量就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool judgeCircle(string moves) {
int x = 0, y = 0;
for (char ch: moves) {
if (ch == 'R') y++;
if (ch == 'L') y--;
if (ch == 'U') x--;
if (ch == 'D') x++;
}
return x == 0 && y == 0;
}
};

832. Flipping an Image

题目来源:https://leetcode.com/problems/flipping-an-image/description/

难度:Easy

知识点:数组

把一个二维数组表示的图片先翻转再反色。没什么特别好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
int n = A.size(), m = A[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - j - 1; j++)
swap(A[i][j], A[i][n - j - 1]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
A[i][j] = 1 - A[i][j];
}
return A;
}
};

840. Magic Squares In Grid

题目来源:https://leetcode.com/problems/magic-squares-in-grid/description/

难度:Easy

知识点:数组

(数组是知识点不就相当于没有吗)

这道题就是在一个二维数组里寻找所有可能的三阶幻方。因为判断条件比较多,而三阶幻方的阶数又很小,不如直接对每个3x3的方框进行暴力判断。我写了横纵和的递推,当然事实上对角线之和,以及各个数字的出现次数这些都能递推,但就三阶幻方而言,这么做太大张旗鼓了,还不如直接暴力算了。

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 {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
if (n < 3 || m < 3) return 0;

int ans = 0;
int downSum[n][m], rightSum[n][m];

for (int i = 0; i < m; i++)
downSum[0][i] = grid[0][i] + grid[1][i] + grid[2][i];
for (int i = 1; i <= n - 3; i++)
for (int j = 0; j < m; j++)
downSum[i][j] = downSum[i-1][j] - grid[i-1][j] + grid[i+2][j];

for (int i = 0; i < n; i++)
rightSum[i][0] = grid[i][0] + grid[i][1] + grid[i][2];
for (int i = 0; i < n; i++)
for (int j = 1; j <= m - 3; j++)
rightSum[i][j] = rightSum[i][j-1] - grid[i][j-1] + grid[i][j+2];

int f[20];
for (int i = 0; i <= n - 3; i++)
for (int j = 0; j <= m - 3; j++) {
int sum = rightSum[i][j];
if (rightSum[i+1][j] != sum || rightSum[i+2][j] != sum || downSum[i][j] != sum
|| downSum[i][j+1] != sum || downSum[i][j+2] != sum)
continue;
if (grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2] != sum || grid[i+2][j] + grid[i+1][j+1] + grid[i][j+2] != sum)
continue;

memset(f, 0, sizeof(f));
for (int i1 = 0; i1 < 3; i1++)
for (int j1 = 0; j1 < 3; j1++)
f[grid[i+i1][j+j1]]++;
bool ok = true;
for (int k = 1; k <= 9; k++)
if (f[k] != 1) {
ok = false;
break;
}
if (!ok) continue;
ans++;
}
return ans;
}
};

852. Peak Index in a Mountain Array

题目来源:https://leetcode.com/problems/peak-index-in-a-mountain-array/description/

难度:Easy

知识点:数组,二分查找

(根本就没有把二分查找用在这种题目上的必要……)

2018.11.28 UPDATE:这道题有一道Follow Up(Leetcode 162);不应该说二分查找完全没有意义,毕竟可以把复杂度降到log……

题意是,给定一个单增再单减的数组,问最大值的元素对应的index

直接扫一遍找到第一个开始单减的数就好了……

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

859. Buddy Strings

题目来源:https://leetcode.com/problems/buddy-strings/description/

难度:Easy

知识点:字符串

这道题就是给你两个字符串,让你判断交换其中一个字符串的两个字母之后两个字符串能否相等。很简单,不过有一些细节,比如,如果两个字符串相等但是每种字母最多只有一个,则不能通过交换使得这两个字符串相等(虽然它们本来就是相等的)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool buddyStrings(string A, string B) {
int n = A.length();
if (n != B.length()) return false;
int differCnt = 0, dif[2];
int cnt[26];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; i++) {
cnt[A[i] - 'a']++;
if (A[i] != B[i]) {
if (differCnt >= 2) return false;
dif[differCnt++] = i;
}
}
if (differCnt == 1) return false;
if (differCnt == 2 && A[dif[0]] == B[dif[1]] && A[dif[1]] == B[dif[0]]) return true;
if (differCnt == 0) {
for (int i = 0; i < 26; i++)
if (cnt[i] >= 2) return true;
}
return false;
}
};

  1. stackoverflow - Significance of ios_base::sync_with_stdio(false); cin.tie(NULL);

  2. cppreference - Lambda 表达式

题目来源: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)

题意

试题编号:201712-2

试题名称:游戏

时间限制:1.0s

内存限制:256.0MB

问题描述

有n个小朋友围成一圈玩游戏,小朋友从1至n编号,2号小朋友坐在1号小朋友的顺时针方向,3号小朋友坐在2号小朋友的顺时针方向,……,1号小朋友坐在n号小朋友的顺时针方向。

游戏开始,从1号小朋友开始顺时针报数,接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数(即数的个位)为k,则该小朋友被淘汰出局,不再参加以后的报数。当游戏中只剩下一个小朋友时,该小朋友获胜。

例如,当n=5, k=2时:
1号小朋友报数1;
2号小朋友报数2淘汰;
3号小朋友报数3;
4号小朋友报数4淘汰;
5号小朋友报数5;
1号小朋友报数6淘汰;
3号小朋友报数7;
5号小朋友报数8淘汰;
3号小朋友获胜。

给定n和k,请问最后获胜的小朋友编号为多少?

输入格式

输入一行,包括两个整数n和k,意义如题目所述。

输出格式

输出一行,包含一个整数,表示获胜的小朋友编号。

样例输入1

1
5 2

样例输出1

1
3

样例输入2

1
7 3

样例输出2

1
4

数据规模和约定

对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ k ≤ 9。

分析

一个普通的链表绕圈和删除问题。

代码

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
#include <iostream>
using namespace std;

struct Node {
int num;
Node* next;

Node() {
num = 0;
next = NULL;
}

Node(int x) {
num = x;
next = NULL;
}
};

int main() {
int n, k;
cin >> n >> k;
if (n == 1) {
cout << 1 << endl;
return 0;
}

Node* head = new Node(1);
Node* p = head;
for (int i = 2; i <= n; i++) {
p->next = new Node(i);
p = p->next;
}
p->next = head;

Node* last = p;
p = head;
int i = 1;
while (p->next != p) {
if (i % k == 0 || i % 10 == k) {
p = p->next;
delete last->next;
last->next = p;
}
else {
last = p;
p = p->next;
}
i++;
}
cout << p->num << endl;
return 0;
}

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

标记难度:Easy

提交次数:1/1

代码效率:100.00%

题意

合并两个已排序的链表。

分析

注意边界情况。以及和链表搞来搞去实在并不能算是一件很有趣味的事情。

代码

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(-1); // 新增的头结点,没有实际意义。当然也可以不加,写起来更麻烦一点。
ListNode* p = head;
// 其实我刚才写了半天才发现自己理解错了。我以为要求是把两个list交替拼接起来。
// 但实际上是合并排序……
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
p = p->next;
}
else {
p->next = l2;
l2 = l2->next;
p = p->next;
}
}
if (l1 != NULL)
p->next = l1;
else if (l2 != NULL)
p->next = l2;

p = head->next;
delete head;
return p;
}
};