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

标记难度:Medium

提交次数:4/6

代码效率:

  • vector:78.93%
  • queue:48.93%

题意

给定一个完全二叉树,写一个向完全二叉树中插入元素的操作类。

分析

比赛的时候觉得这道题很水,随便写就好了。事实上确实差不多是这样的。


vector

既然是完全二叉树的插入,那么可以利用数组保存堆的思想。如果根在1处,则x的左孩子在2 * x处,右孩子在2 * x + 1处;x的父亲在floor(x / 2)处。于是直接用一个vector做就可以了。预处理花费O(N)时间(因为需要把树中当前的结点都插入);插入花费O(1)时间。听起来还可以。

queue

这个方法来自[1],和上一个解法差不多,都利用了完全二叉树只有最低一层可能不满,只有最低两层的结点可能只有<2个子结点的特性:

  • 用一个队列维护当前还没有获得两个叶子结点的TreeNode*
  • 插入新结点时,尝试插入到队头的结点的左侧或右侧(左侧优先);然后再把新结点插入队尾
  • 如果队头的结点已经有了两个子结点,则把它弹出

不过我看不出题解里使用deque的意义何在……

直接计算

通过阅读12ms的示例代码,我发现了一种比较神奇的解法:不把整棵树缓存下来,直接在树上计算下一个结点的父节点位置。[2]

这种做法的思路大致是这样的:

  • 初始化:通过dfs计算结点数量counter
  • 插入结点:
    • 根据counter计算当前树中层数numRows
    • 根据counternumRows计算出当前结点的父结点是倒数第二层(或最后一层)的第几个结点
    • 通过二分查找找出这个结点并插入

具体内容实在没有时间去写了。

代码

vector

其中初始化时用vector代替queue的trick来自[3]

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 CBTInserter {
private:
vector<TreeNode*> heap;

public:
CBTInserter(TreeNode* root) {
heap.push_back(nullptr);
heap.push_back(root);

for (int i = 1; i < heap.size(); i++) {
TreeNode* x = heap[i];
if (heap[i]->left != nullptr) heap.push_back(heap[i]->left);
if (heap[i]->right != nullptr) heap.push_back(heap[i]->right);
}
}

int insert(int v) {
int n = heap.size();
TreeNode* x = new TreeNode(v);
heap.push_back(x);
int m = n / 2;
if (n % 2 == 0) heap[m]->left = x;
else heap[m]->right = x;
return heap[m]->val;
}

TreeNode* get_root() {
return heap[1];
}
};

queue

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
class CBTInserter {
private:
queue<TreeNode*> q;
TreeNode* root;

public:
CBTInserter(TreeNode* root) {
q.push(root);
this->root = root;

while (!q.empty()) {
TreeNode* p = q.front();
if (p->left != nullptr) {
q.push(p->left);
if (p->right != nullptr) {
q.push(p->right);
q.pop();
}
else break;
}
else break;
}
}

int insert(int v) {
TreeNode* p = q.front();
TreeNode* n = new TreeNode(v);
if (p->left == nullptr) {
p->left = n;
q.push(n);
return p->val;
}
p->right = n;
q.push(n);
q.pop();
return p->val;
}

TreeNode* get_root() {
return root;
}
};

  1. Official Solution for Leetcode 919

  2. Leetcode 919: sample 12 ms submission

  3. lee215's Solution for Leetcode 919: O(1) Insert

题目来源:https://leetcode.com/problems/top-k-frequent-words/description/

标记难度:Medium

提交次数:1/2

代码效率:98.50%

题意

从一个数组中选出出现次数前k多的元素。

分析

这道题和上一道Top K(Leetcode 692)基本是完全一样的——事实上,我是从那边的题解区过来的。区别可能是,这里完全没有对break tie的要求,所以我就直接用HashMap+桶排序做了(其他的做法参见3 ways to solve this problem),然后就过了。

中间错了一次是因为桶的数量开少了一个。

代码

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> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int x: nums)
freq[x]++;

// 这道题的题干中没有提到break tie的问题啊……
// 如果按照没有tie的方法去做,那桶排序将变得非常简单
vector<vector<int>> bucket;
for (int i = 0; i <= nums.size(); i++)
bucket.push_back(vector<int>());
for (auto const& i: freq)
bucket[i.second].push_back(i.first);

vector<int> topk;
while (topk.size() < k) {
for (int j = bucket.size() - 1; j >= 0; j--) {
for (int x: bucket[j])
if (topk.size() < k)
topk.push_back(x);
else
break;
if (topk.size() >= k)
break;
}
}

return topk;
}
};

题目来源:https://leetcode.com/problems/top-k-frequent-words/description/

标记难度:Medium

提交次数:3/3

代码效率:

  • O(n * log(n)):36.84%
  • O(n * log(k)):36.84%

题意

从一个数组中选出出现次数前k多的元素。

分析

显然很容易想到这种解法:用map来统计每种元素出现的数量(O(n * log(n))),然后用priority_queue来选择出现次数前k多的元素(O(n * log(n))),整体时间复杂度为O(n * log(n))。我们可以迅速改进这种算法的时间复杂度(虽然实际运行时间并没有多大改进):用unordered_map来统计每种元素出现的数量(O(n)),然后在保证priority_queue中的元素不超过k个的前提下选择出现次数前k多的元素(O(n * log(k))),这样时间复杂度可以降低到O(n * log(k))

我们还可以进行进一步的优化。这篇题解指出,每种元素出现的数量的值最大为原数组的长度,因此我们并不需要动用优先队列来选择出现次数前k多的元素,用桶排序就可以了。为了保证先输出字典序小的元素,原作者在每个桶里搞了一棵Trie,因此这一处理过程的复杂度为O(n * ave_len)

我想,用Trie处理字符串算是相当聪明的做法了——如果换成其他的有序数据结构或者排序算法,总归会有退化情况的。不过,如果字符串太长,处理时间仍然会变长。(不过我实在懒得去写了。)

C++ STL代码技巧

通过阅读这份代码和查找资料,我感觉我又新学会了很多C++ STL的技巧。

map的一些特点

  • 可以用std::map::count函数统计map中元素的个数。当然,map中的元素不可重复,因此这个函数的输出只可能为0或1。我把这个函数当做find的轻量版来用了……
  • 使用[]操作符访问map中的元素时,如果这个元素不存在,会自动插入该元素并将值置为空。所以代码中直接mmap[x]++是可行的。(What happens if I read a map's value where the key does not exist?

遍历map的几种方法

参考了C++ Loop through Map

  1. 普通方法:迭代器
1
2
3
4
5
6
7
8
9
map<string, int>::iterator it;

for ( it = symbolTable.begin(); it != symbolTable.end(); it++ )
{
std::cout << it->first // string (key)
<< ':'
<< it->second // string's value
<< std::endl ;
}
  1. C++ 11:auto和冒号(我感觉这种写法很像Java)
1
2
3
4
5
6
7
for (auto const& x : symbolTable)
{
std::cout << x.first // string (key)
<< ':'
<< x.second // string's value
<< std::endl ;
}

注意上一种方法里ref的方式是->,这种方法里ref的方式是.

  1. C++ 17:这根本就是Python吧
1
2
3
4
5
6
7
for( auto const& [key, val] : symbolTable )
{
std::cout << key // string (key)
<< ':'
<< val // string's value
<< std::endl ;
}

如何创建最小堆

我记得我之前曾经记录过,简单的创建一个最小堆的方法是:

1
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

但是我没有考虑到如何为自建的类型创建比较方法。对于那些C算法库函数,写个返回bool的普通函数就行了,但对于C++ STL,显然没有这么简单——我果然还是不懂STL啊……简单来说,需要新建一个类,然后在里面重载()运算符,最后把这个类作为参数构造模板。下列代码来自How can I create Min stl priority_queue?

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

struct compare
{
bool operator()(const int& l, const int& r)
{
return l > r;
}
};

int main()
{
priority_queue<int,vector<int>, compare > pq;

pq.push(3);
pq.push(5);
pq.push(1);
pq.push(8);
while ( !pq.empty() )
{
cout << pq.top() << endl;
pq.pop();
}
cin.get();
}

代码

O(n * 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
class Solution {
private:
struct compare
{
bool operator()(const pair<int, string>& p1, const pair<int, string>& p2) {
if (p1.first != p2.first) return p1.first < p2.first;
return p1.second > p2.second;
}
};

public:
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> mmap;
for (string w: words) {
if (mmap.count(w) == 1)
mmap[w]++;
else
mmap[w] = 1;
}
priority_queue<pair<int, string>, std::vector<pair<int, string>>, compare> pq;
for (auto const& x : mmap)
{
pq.push(make_pair(x.second, x.first));
}

vector<string> ans;
for (int i = 0; i < k; i++) {
ans.push_back(pq.top().second);
pq.pop();
}
return ans;
}
};

O(n * log(k))

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
class Solution {
private:
struct compare
{
// 改为构造最小堆
bool operator()(const pair<int, string>& p1, const pair<int, string>& p2) {
if (p1.first != p2.first) return p1.first > p2.first;
return p1.second < p2.second;
}
};

public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> mmap; // 即HashMap
for (string w: words) {
mmap[w]++; // 直接+即可
}
priority_queue<pair<int, string>, std::vector<pair<int, string>>, compare> pq;
for (auto const& x : mmap) {
pq.push(make_pair(x.second, x.first));
if (pq.size() > k) // 需要保持pq的size不超过k,否则就是O(n * log(n))了
pq.pop();
}

vector<string> ans;
for (int i = 0; i < k; i++) {
ans.insert(ans.begin(), pq.top().second);
pq.pop();
}
return ans;
}
};

题目来源:https://leetcode.com/problems/find-median-from-data-stream/description/

标记难度:Hard

提交次数:2/2

代码效率:

  • vector版本:17.75%
  • 优先队列版本:17.75%

题意

写一个读入数据流并随时按要求输出中位数的工具类。

分析

我最开始的想法就是直接维护一个有序vector。这样做显然是可以的,但是每次插入的代价都是O(N),看起来比较高。

交上去之后,我立刻想到了一种优化方法:维护一个二叉搜索树,这样插入和查询的代价就基本上都是O(log(N))了。不过我并没有写这个方法,因为我在题解里看到了一种很聪明的方法——维护两个堆。大根堆中存储较小的一半元素,小根堆中存储较大的一半元素,维护两个堆的大小大致相等,这样就可以直接通过这两个堆的堆顶计算中位数了。

代码

vector版本

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 MedianFinder {
private:
vector<int> nums;

public:
/** initialize your data structure here. */
MedianFinder() {
// 最简单的方法就是直接把所有数缓存下来,排序,每次返回中间的值
// 但其实我感觉这样是不行的。
// 也许能用int做些文章?
// 或许应该保存一棵二叉搜索树,找median比较方便?
// 我感觉把所有数都存下来可能是必要的。
}

void addNum(int num) {
auto i = lower_bound(nums.begin(), nums.end(), num);
nums.insert(i, num);

/*for (int x: nums)
cout << x << ' ';
cout << endl;*/
}

double findMedian() {
if (nums.size() % 2 != 0)
return nums[nums.size() / 2];
return (nums[nums.size() / 2 - 1] + nums[nums.size() / 2]) / 2.0;
}
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/

优先队列版本

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
class MedianFinder {
// maxHeap: 较小的一半元素
// minHeap:较大的一半元素
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
public:
/** initialize your data structure here. */
MedianFinder() {

}

void addNum(int num) {
// cout << num << ' ' << maxHeap.size() << ' ' << minHeap.size() << endl;
if (minHeap.size() == 0 || num > minHeap.top())
minHeap.push(num);
else
maxHeap.push(num);
// 维护maxHeap.size==minHeap.size || maxHeap.size==minHeap.size-1
while (maxHeap.size() > minHeap.size()) {
minHeap.push(maxHeap.top());
maxHeap.pop();
}
while (minHeap.size() > maxHeap.size() + 1) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}

double findMedian() {
double ans;
if (minHeap.size() == 0)
return 0;
if (maxHeap.size() == minHeap.size())
ans = (maxHeap.top() + minHeap.top()) / 2.0;
else
ans = minHeap.top();
return ans;
}
};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/