题目来源:https://leetcode.com/problems/reorder-log-files/description/

标记难度:Medium

提交次数:1/1

代码效率:

  • 剪枝:120ms
  • 不剪枝:120ms

题意

给定一棵二叉查找树、LR,返回[L, R]中的结点的值的和。

分析

这个题总的来说很简单。直接DFS,然后根据当前node的值进行剪枝即可。(事实上不剪枝也能过,而且没慢多少。)

代码

不剪枝

1
2
3
4
5
6
7
8
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
if (root == NULL) return 0;
return rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R) +
(L <= root->val && root->val <= R ? root->val : 0);
}
};

剪枝

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
if (root == NULL) return 0;
int sum = 0;
if (root->val > L) sum += rangeSumBST(root->left, L, R);
if (root->val < R) sum += rangeSumBST(root->right, L, R);
return sum + (L <= root->val && root->val <= R ? root->val : 0);
}
};

题目来源: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/insert-into-a-binary-search-tree/description/

标记难度:Easy

提交次数:1/1

代码效率:15.50%

题意

在二叉搜索树中插入元素。

分析

感觉和Leetcode 700是同一系列的题目。同样直接插入就可以了。

代码

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL)
return new TreeNode(val);
TreeNode* p = root;
while (p != NULL) {
if (val < p->val) {
if (p->left == NULL) {
p->left = new TreeNode(val);
break;
}
p = p->left;
}
else {
if (p->right == NULL) {
p->right = new TreeNode(val);
break;
}
p = p->right;
}
}
return root;
}
};

题目来源:https://leetcode.com/problems/search-in-a-binary-search-tree/description/

标记难度:Easy

提交次数:1/1

代码效率:14.34%

题意

在二叉搜索树中查找元素。

分析

水题。直接按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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* p = root;
while (p != NULL) {
if (p->val == val)
break;
if (val < p->val)
p = p->left;
else
p = p->right;
}
return p;
}
};

题目来源:https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/

标记难度:Easy

提交次数:1/1

代码效率:12.62%

题意

给定一个二叉搜索树,返回树中任意两个结点之间差的最小值。

分析

Leetcode有些题目,真是水得有点过头……这道题数据规模只有100,简直是直接枚举都能做了。当然正确的做法是中序遍历。我最开始还以为要像173题那样手写一个找后继的方法,结果发现根本不用,直接中序遍历然后记录上一个元素就行了。

甚至更水的是,这道题和530题基本一模一样(通过评论区的提示得知……),直接用同一份代码交上去就可以AC了,于是我收获了两个AC……

不过,一个有趣的问题是,如果我们把530题的描述改一下,从“差的绝对值”改成“绝对值的差”会怎么样?这样改过之后,我觉得我们实际上获得了0-2棵子BST,以及一棵“反的”子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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int last;
int minDif;
void traverse(TreeNode* cur) {
if (cur == NULL)
return;
traverse(cur->left);
if (last != -1)
minDif = min(minDif, cur->val - last);
last = cur->val;
traverse(cur->right);
}

public:
int minDiffInBST(TreeNode* root) {
last = -1;
minDif = 1000000;
traverse(root);
return minDif;
}
};

题目来源:https://leetcode.com/problems/reverse-pairs/description/

标记难度:Hard

提交次数:1/4

代码效率:93.15%

题意

计算数组中重要逆序对的数量。称(i, j)为重要逆序对,当且仅当i < jnums[i] > 2 * nums[j]

分析

其实思路并不是很难。归并排序求逆序对的思路已经很平常了,这道题中直接把计数的条件改一改,只统计另一半数组中至少为当前的数的两倍的数的数量(而不是单纯“大于”)就可以了。

但是我提交了4次。第一次是数组边界写错了,后面几次都是被卡在这个*2上了——我还是第一次见到卡2 * (int) 2147483647这个位置的题,也可能是我孤陋寡闻吧。当然,我承认这么做有点道理,这和单纯比大小是不一样的。反正我最后手动在比较的时候把intcast成long long了。

一种合并的方法

我之前从来没有听说过inplace_merge这个函数。又一次在StephanPochmann的题解中看到了一些闻所未闻的东西之后,我去查了一下,发现:原来STL算法库里为我们提供了一个原址合并算法啊!

1
2
3
4
5
6
7
8
9
10
template<class Iter>
void merge_sort(Iter first, Iter last)
{
if (last - first > 1) {
Iter middle = first + (last - first) / 2;
merge_sort(first, middle);
merge_sort(middle, last);
std::inplace_merge(first, middle, last);
}
}

利用这个算法来实现归并排序无疑是非常简单明了的。

另一个问题是,inplace_merge是如何实现的?我之前从未想过归并算法可以是原址的。事实是,确实可以。请参见Practical In-Place Merging这篇论文和相应的实现(InplaceMerge.hh)。不过这个算法的确有点复杂。

类似于逆序对的题目

讨论区里有一篇非常好的文章,对相似类型的题目进行了一个整体的讨论。简单来说,此类题目的共同点是:将数组分解,然后解决子问题。

通常我们有两种分解数组(子问题)的方法:

  1. 顺序分解:T(i, j) = T(i, j - 1) + C
  2. 二分分解:T(i, j) = T(i, m) + T(m + 1, j) + C,其中m = (i + j) / 2

(是的,我之前没有想过,其实顺序分解也是可以做到O(n * log(n))的。)

顺序分解对于本题来说,也就意味着,顺序扫描数组,寻找以当前的数为逆序对的第二个元素的逆序对的数量。显然直接扫描是可以的,但是复杂度会上升到O(n^2)。为了提高搜索的效率,我们注意到,子数组内部的顺序不重要,因此我们可以把它转换成一棵二叉搜索树(或者任何类似的东西)。这样效率就可以提高到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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
private:
int* tmp;
int split(int l, int r, vector<int>& nums) {
if (l == r)
return 0;
int m = (l + r) >> 1;
int sum = 0;
sum += split(l, m, nums);
sum += split(m+1, r, nums);

// 统计important逆序对的数目
int i = l, j = m+1;
while (i <= m && j <= r) {
// 第一次遇到卡这里的题目……
while (i <= m && (long long)nums[i] <= (long long)(nums[j]) * 2)
i++;
if (i > m)
break;
sum += m - i + 1;
j++;
}
// 合并
i = l;
j = m+1;
int k = 0;
while (i <= m && j <= r) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
while (i <= m)
tmp[k++] = nums[i++];
while (j <= r)
tmp[k++] = nums[j++];
for (i = l; i <= r; i++)
nums[i] = tmp[i - l];

return sum;
}

public:
int reversePairs(vector<int>& nums) {
// 只是普通的求逆序对算法的一个变形
if (nums.size() == 0)
return 0;

tmp = new int[nums.size() + 1];
int sum = split(0, nums.size() - 1, nums);
delete[] tmp;
return sum;
}
};

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

标记难度:Medium

提交次数:1/1

代码效率:98.53%

题意

写一个二叉搜索树的迭代器,包括初始化、next()hasNext()操作,要求平摊时间复杂度为O(1),空间复杂度为O(h)。

分析

因为空间复杂度是O(h),所以肯定不能把整个树直接存成一个数组然后直接查找,而是要利用树的性质。好吧,其实《数据结构》里在迭代版中序遍历中讲了这个东西。

中序遍历过程

与所有遍历一样,中序遍历的实质功能也可理解为,为所有节点赋予一个次序,从而将半线性的二叉树转化为线性结构。于是一旦指定了遍历策略,即可与向量和列表一样,在二叉树的节点之间定义前驱与后继关系。其中没有前驱(后继)的节点称作首(末)节点。
对于后面将要介绍的二叉搜索树,中序遍历的作用至关重要。相关算法必需的一项基本操作,就是定位任一节点在中序遍历序列中的直接后继。为此,可实现succ()接口如代码5.16所示。

1
2
3
4
5
6
7
8
9
10
11
12
// 代码5.16 二叉树节点直接后继的定位
template <typename T> BinNodePosi(T) BinNode<T>::succ() { //定位节点v的直接后继
BinNodePosi(T) s = this; //记录后继的临时变量
if (rChild) { //若有右孩子,则直接后继必在右子树中,具体地就是
s = rChild; //右子树中
while (HasLChild(*s)) s = s->lChild; //最靠左(最小)的节点
} else { //否则,直接后继应是“将当前节点包含于其左子树中的最低祖先”,具体地就是
while (IsRChild(*s)) s = s->parent; //逆向地沿右向分支,不断朝左上方移动
s = s->parent; //最后再朝右上方移动一步,即抵达直接后继(如果存在)
}
return s;
}

这里,共分两大类情况。若当前节点有右孩子,则其直接后继必然存在,且属于其右子树。此时只需转入右子树,再沿该子树的最左侧通路朝左下方深入,直到抵达子树中最靠左(最小)的节点。
反之,若当前节点没有右子树,则若其直接后继存在, 必为该节点的某一祖先,且是将当前节点纳入其左子树的最低祖先。于是首先沿右侧通路朝左上方上升,当不能继续前进时,再朝右上方移动一步即可。
作为后一情况的特例,出口时s可能为NULL。这意味着此前沿着右侧通路向上的回溯,抵达了树根。也就是说,当前节点是全树右侧通路的终点——它也是中序遍历的终点,没有后继。
(摘自《数据结构(C++语言版)》(第三版),清华大学出版社,2013.9)

我的代码实现得不怎么漂亮,不过里面被注释掉的关键的一句代码path.push(_cur);变相实现了“右侧通路朝左上方上升,当不能继续前进时,再朝右上方移动一步”这个操作:栈中实际上存储的就是经过这个操作之后能够得到的结点,因此右转时的结点是不能入栈的。

代码

我的代码

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
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
TreeNode* _root;
TreeNode* _cur;
stack<TreeNode*> path;

public:
BSTIterator(TreeNode *root) {
_root = root;
_cur = root;
// 找到树中最小的结点
while (_cur != NULL && _cur->left != NULL) {
path.push(_cur);
_cur = _cur->left;
}

// cout << _cur->val << endl;
}

/** @return whether we have a next smallest number */
bool hasNext() {
// 和next()的判断逻辑相同:
// 当前结点有右子树,或者仍然有向上回溯的空间
return _cur != NULL;
}

/** @return the next smallest number */
int next() {
int smallest = _cur->val;
// cout << smallest << ' ' << path.size() << endl;
// 寻找_cur的后继
// _cur的右子树不为空,此时后继必为_cur的右子树中最靠左的结点
if (_cur->right != NULL) {
// 必须注释掉这句话,因为path(这个名字起得不好)指的并不是从root到当前结点的路径上的所有结点
// 而是“右子树仍未被访问到的结点”
// path.push(_cur);
_cur = _cur->right;
while (_cur->left != NULL) {
path.push(_cur);
_cur = _cur->left;
}
}
// _cur的右子树为空,此时需要向上回溯
// 因为TreeNode的定义中没有提供父结点指针,所以只好用栈来记录了
// 当然,按照邓公的意见,这样可以省空间,应该是最好的……
else {
if (path.size() > 0) {
_cur = path.top();
path.pop();
}
else
_cur = NULL;
}

return smallest;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

Sample 20ms Submission

我刚发现在提交后的结果页面点时间会得到相应的标程,惊了,Leetcode真是越来越强了。

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
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
stack<TreeNode *> s;
void addToStack(TreeNode * root){
while(root){
s.push(root);
root=root->left;
}
}

BSTIterator(TreeNode *root) {
addToStack(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
return s.size()>0;
}

/** @return the next smallest number */
int next() {
int res = s.top()->val;
TreeNode * top = s.top();
s.pop();
if(top-> right){
addToStack(top->right);
}

return res;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/