【215】 Kth Largest Element in an Array （無(wú)序數(shù)組中最小/大的K個(gè)數(shù)）(2018年11月30日第一次復(fù)習(xí))

給了一個(gè)無(wú)序數(shù)組,，可能有重復(fù)數(shù)字,，找到第 k 個(gè)最大的元素并且返回這個(gè)元素值。

題解：直接用直接用個(gè)堆保存數(shù)組中最大的 K 個(gè)數(shù),。時(shí)間復(fù)雜度是 O(NlogK)。

 1 //時(shí)間復(fù)雜度是 O(NlogK), 用堆輔助,。
 2 class Solution {
 3 public:
 4     int findKthLargest(vector<int>& nums, int k) {
 5         const int n = nums.size();
 6         priority_queue<int, vector<int>, greater<int>> pq;
 7         for (int i = 0; i < n;   i) {
 8             if (pq.size() < k) {
 9                 pq.push(nums[i]);
10             } else {
11                 if (pq.top() < nums[i]) {
12                     pq.pop();
13                     pq.push(nums[i]);
14                 }
15             }
16         }
17         return pq.top();
18     }
19 };

本題可以有 O(N) 的解法,，詳見(jiàn)《劍指offer》或者《程序員代碼面試指南》P336

【218】 The Skyline Problem（2019年2月5日，算法群打卡復(fù)習(xí)）

給了一個(gè)tuple list,， 每個(gè)三元組 [a, b, h] 代表一個(gè)樓的x軸坐標(biāo)是在[a, b],，樓的高度是 h，返回所有樓輪廓的左上角坐標(biāo)。

題解：用了一個(gè) multiset 來(lái)存這個(gè)樓是進(jìn)來(lái)還是出去,，如果是進(jìn)來(lái),，就存[a, h], 如果是出去，就存[b, -h],。 然后遍歷這個(gè) multiset,，如果這個(gè)樓是進(jìn)來(lái)的話，就看當(dāng)前高度它是不是最高的,，如果是,，那么這個(gè)點(diǎn)在答案中，如果這個(gè)樓是出去的話,，先把這個(gè)高度刪除,，然后看當(dāng)前這個(gè)高度是不是比剩下所有樓都高，如果是,，就把當(dāng)前坐標(biāo)和剩下的最高的樓組成的坐標(biāo)加入答案中,。

 1 class Solution {
 2 public:
 3     vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
 4         for (auto& b : buildings) {
 5             record.insert(make_pair(b[0], b[2]));
 6             record.insert(make_pair(b[1], -b[2]));
 7         }
 8         vector<pair<int, int>> ret;
 9         for (auto& r : record) {
10             bool entry = r.second > 0 ? true : false;
11             int idx = r.first, h = abs(r.second);
12             // printf("idx = %d, h = %d, entry = %d\n", idx, h, entry);
13             if (entry) {
14                 if (h > getMaxHeight()) {
15                     ret.push_back(make_pair(idx, h));
16                 }
17                 height.insert(h);
18             } else {
19                 auto iter = height.find(h);
20                 height.erase(iter);
21                 if (h > getMaxHeight()) {
22                     ret.push_back(make_pair(idx, getMaxHeight()));
23                 }
24             }
25         } 
26         return ret;
27     }
28     struct kcmp {
29         bool operator() (const pair<int, int>& p1, const pair<int, int>& p2) const {
30             if (p1.first == p2.first) {
31                 return p1.second > p2.second;
32             }
33             return p1.first < p2.first;
34         }
35     };
36     multiset<pair<int, int>, kcmp> record;    
37     multiset<int> height;
38     int getMaxHeight() {
39         if (height.empty()) {return 0;}
40         return *height.rbegin();
41     }
42 };

【239】 Sliding Window Maximum

【253】 Meeting Rooms II

題意是252的升級(jí)版，給了一個(gè)數(shù)組,，數(shù)組里面的每個(gè)元素代表一個(gè)會(huì)議的開(kāi)始時(shí)間和結(jié)束時(shí)間,，問(wèn)想安排下所有的會(huì)議，至少需要多少個(gè)會(huì)議室,。

題解：這個(gè)題目在 sort 的分類里面說(shuō)過(guò),，鏈接：https://www.cnblogs.com/zhangwanying/p/9914941.html 

【264】 Ugly Number II

【295】 Find Median from Data Stream （2018年11月30日，堆的題目）

給了一個(gè)數(shù)據(jù)流,，設(shè)計(jì)api接口,，addNum() 用于接收一個(gè)數(shù)，findMedian() 用于返回?cái)?shù)據(jù)流的中位數(shù),。返回?cái)?shù)據(jù)流的中位數(shù),。

Example:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

題解：這題是今天看算法課看到的一個(gè)題，我們用一個(gè)大根堆存儲(chǔ)數(shù)據(jù)流比較小的一半數(shù)字,，用一個(gè)小根堆存數(shù)據(jù)流的比較大的一半數(shù)字,。（這兩個(gè)堆的元素個(gè)數(shù)要么相等，要么存小數(shù)的那個(gè)堆比存大數(shù)的那個(gè)堆多存一個(gè)數(shù),。）中位數(shù)如果兩個(gè)堆元素個(gè)數(shù)相差 1 ,，那么就返回大根堆的堆頂。不然返回兩個(gè)堆頂?shù)钠骄鶖?shù),。

 1 class MedianFinder {
 2 public:
 3     /** initialize your data structure here. */
 4     MedianFinder() {
 5         
 6     }
 7     void addNum(int num) {
 8         lowhalf.push(num);
 9         int k = lowhalf.top(); lowhalf.pop();
10         highhalf.push(k);
11         if (lowhalf.size() < highhalf.size()) {
12             k = highhalf.top(); highhalf.pop();
13             lowhalf.push(k);
14         }
15         return;
16     }
17     double findMedian() {
18         if (lowhalf.size() == highhalf.size()) {
19             return (double)(lowhalf.top()   highhalf.top()) / 2;
20         }
21         return (double)lowhalf.top();
22     }
23     priority_queue<int, vector<int>, greater<int>> lowhalf;  //小根堆存大的那邊
24     priority_queue<int> highhalf; //大根堆存小的那邊 
25 };
26 
27 /**
28  * Your MedianFinder object will be instantiated and called as such:
29  * MedianFinder obj = new MedianFinder();
30  * obj.addNum(num);
31  * double param_2 = obj.findMedian();
32  */

【313】 Super Ugly Number

【347】 Top K Frequent Elements

【355】 Design Twitter （2018年12月3日,，heap專題）

實(shí)現(xiàn)四個(gè) api。 

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:
Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

題解：用個(gè) unordered_map 標(biāo)記用戶關(guān)系,，然后一個(gè) vector 存儲(chǔ) twitter post

 1 class Twitter {
 2 public:
 3     /** Initialize your data structure here. */
 4     Twitter() {
 5         
 6     }
 7     
 8     /** Compose a new tweet. */
 9     void postTweet(int userId, int tweetId) {
10         twit.push_back(make_pair(userId, tweetId));
11     }
12     
13     /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
14     vector<int> getNewsFeed(int userId) {
15         set<int> people = followRelation[userId];
16         people.insert(userId);
17         vector<int> ret;
18         int idx = twit.size() - 1, cnt = 0;;
19         while (cnt < 10 && idx >= 0) {
20             auto p = twit[idx--];
21             int uid = p.first, tid = p.second;
22             if (people.find(uid) != people.end()) {
23                 ret.push_back(tid);
24                 cnt  ;
25             }
26         }
27         return ret;
28     }
29     
30     /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
31     void follow(int followerId, int followeeId) {
32         followRelation[followerId].insert(followeeId);
33     }
34     
35     /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
36     void unfollow(int followerId, int followeeId) {
37         if (followRelation.find(followerId) == followRelation.end()) { return; }
38         if (followRelation[followerId].find(followeeId) == followRelation[followerId].end()) {return;}
39         followRelation[followerId].erase(followeeId);
40     }
41     
42     unordered_map<int, set<int>> followRelation;
43     vector<pair<int, int>> twit;  // (user, id)
44 };
45 
46 /**
47  * Your Twitter object will be instantiated and called as such:
48  * Twitter obj = new Twitter();
49  * obj.postTweet(userId,tweetId);
50  * vector<int> param_2 = obj.getNewsFeed(userId);
51  * obj.follow(followerId,followeeId);
52  * obj.unfollow(followerId,followeeId);
53  */

【358】 Rearrange String k Distance Apart

【373】 Find K Pairs with Smallest Sums （2018年12月1日）

給了兩個(gè)整數(shù)數(shù)組 nums1 和 nums2,， 和一個(gè)整數(shù) k,，求 nums1 和 nums2 的笛卡爾積中（就是 nums1 中選擇一個(gè)數(shù)字 n1，nums2 中選擇一個(gè)數(shù)字 n2 組成pair）,，sum 最小的 k 個(gè)pair,。

題解：本題就是自定義排序的大根堆，pair排序的規(guī)則是 sum 大的在堆頂,。

 1 class Solution {
 2 public:
 3     vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
 4         if (nums1.empty() || nums2.empty()) {return vector<pair<int, int>>();}
 5         priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
 6         for (auto n1 : nums1) {
 7             for (auto n2 : nums2) {
 8                 pq.push(make_pair(n1, n2));
 9                 if (pq.size() > k) { pq.pop(); }
10             }
11         }
12         vector<pair<int, int>> ret; //可能nums1和nums2的組合的pair不夠 k 個(gè),，所以不能一開(kāi)始初始化為 k 個(gè)結(jié)果。
13         while (!pq.empty()) {
14             ret.push_back(pq.top());
15             pq.pop();
16         }
17         return ret;
18     }
19     struct cmp{
20         bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {
21             return p1.first   p1.second < p2.first   p2.second;
22         }
23     };
24 };

【378】 Kth Smallest Element in a Sorted Matrix

【407】 Trapping Rain Water II

【451】 Sort Characters By Frequency

【502】 IPO

【659】 Split Array into Consecutive Subsequences

【692】 Top K Frequent Words （2018年11月30日）

給了一個(gè)string類型的數(shù)組 words,，在給定整數(shù)k,，請(qǐng)嚴(yán)格按照出現(xiàn)頻率順序打印出現(xiàn)次數(shù)前 k 名的字符串。（出現(xiàn)頻率相同的按照字典順序打?。?/p>

題解：用個(gè) unordered_map 存儲(chǔ)每個(gè)單詞出現(xiàn)的次數(shù),，然后建立一個(gè)小根堆，里面存 k 個(gè)pair,，（小根堆自定義排序class）,，然后遍歷一遍map,，把最后剩下在堆里的 k 個(gè)pair的字符串提取出來(lái),。 

 1 class Solution {
 2 public:
 3     vector<string> topKFrequent(vector<string>& words, int k) {
 4         const int n = words.size();
 5         unordered_map<string, int> mp;
 6         for (auto w : words) { mp[w]  ; }
 7 
 8         priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;  
 9         for (auto ele : mp) {
10             pq.push(ele);
11             if (pq.size() > k) { pq.pop(); }
12         }
13         vector<string> ret(k, "");
14         int idx = k-1;
15         while (!pq.empty()) {
16             auto p = pq.top();
17             pq.pop();
18             ret[idx--] = p.first;
19         }
20         return ret;
21     }
22     //自定義比較函數(shù)，為啥我想小的排前面要寫(xiě)大于,。,。
23     struct cmp {
24         bool operator()(const pair<string, int> a, const pair<string, int>& b) {
25             if (a.second == b.second) {
26                 return a.first < b.first;
27             }
28             return a.second > b.second;
29         }
30     };
31 };

    //自定義比較函數(shù)，為啥我想小的排前面要寫(xiě)大于,。,。（優(yōu)先隊(duì)列的自定義比較函數(shù)要搞明白，還是不懂?。?nbsp;

【703】 Kth Largest Element in a Stream

給個(gè)數(shù)字流,，總是返回最大的第K個(gè)元素

解法就是用一個(gè)只有K個(gè)元素的堆，維護(hù)這這些數(shù)字里面從最大的第K個(gè)到最大的元素,。

[最小元素...第K大的元素..最大元素],， 這個(gè)堆總維護(hù)后半段的K個(gè)

【719】 Find K-th Smallest Pair Distance

【743】 Network Delay Time （2018年12月4日）

一個(gè)社交網(wǎng)絡(luò)里面有 N 個(gè)結(jié)點(diǎn)，標(biāo)號(hào)為 1 ～ N,，給了一個(gè) times 數(shù)組,，里面的元素 t(u, v, w) 代表從 u結(jié)點(diǎn) 到 v結(jié)點(diǎn)需要 w 的時(shí)間，給了一個(gè)源點(diǎn) K,， 問(wèn)從 K 開(kāi)始傳播一條信息,，到每個(gè)結(jié)點(diǎn)需要至少多少時(shí)間，如果從 K 到一個(gè)結(jié)點(diǎn)不可達(dá),，就返回 -1,。

題解：floyed求最短路,。

 1 class Solution {
 2 public:
 3     int networkDelayTime(vector<vector<int>>& times, int N, int K) {
 4         vector<vector<int>> g(N 1, vector<int>(N 1, INT_MAX));
 5         for (auto t : times) {
 6             int u = t[0], v = t[1], cost = t[2];
 7             g[u][v] = cost;
 8         }
 9         //floyed
10         for (int f = 1; f <= N;   f) {
11             for (int i = 1; i <= N;   i) {
12                 g[i][i] = 0;
13                 for (int j = 1; j <= N;   j) {
14                     if (g[i][f] != INT_MAX && g[f][j] != INT_MAX) {
15                         g[i][j] = min(g[i][f]   g[f][j], g[i][j]);
16                     }
17                 }
18             }
19         }
20         int ret = INT_MIN;
21         for (int i = 1; i <= N;   i) {
22             if (i == K) {continue;}
23             if (g[K][i] == INT_MAX) {
24                 ret = -1;
25                 break;
26             }
27             ret = max(ret, g[K][i]);
28         }             
29         return ret;            
30     }
31 };

此外，我沒(méi)看出來(lái)跟 heap 有啥關(guān)系,。

【759】 Employee Free Time

【767】 Reorganize String

【778】 Swim in Rising Water

【786】 K-th Smallest Prime Fraction

【787】 Cheapest Flights Within K Stops

【818】 Race Car

【857】 Minimum Cost to Hire K Workers

【864】 Shortest Path to Get All Keys

【871】 Minimum Number of Refueling Stops

【882】 Reachable Nodes In Subdivided Graph