腾讯百度阿里华为常见算法面试题TOP100(5)：子串、堆
之前总结过字节跳动TOP50算法面试题：
字节跳动常见算法面试题top50整理_沉迷单车的追风少年-CSDN博客_字节算法面试题
子串
560.和为K的子数组
class Solution {
public:int subarraySum(vector<int>& nums, int k) {// 寻找在区间[i, j]的和为k的值// 用pre[i]代表前i的和// 那么寻找满足 pre[i] - pre[j - 1] == k的值// 移项可得pre[j - 1] = pre[i] - k// 只需要寻找符合条件的j的个数// 又因为j是小于i的，我们用sum表示pre[i]int ans = 0;// 哈希表的key是pre[i]; value是出现的次数;unordered_map<int, int> hash;hash[0] = 1;int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];// 如果哈希表中能找到pre[j - 1], 那么满足条件if (hash.find(sum - k) != hash.end()) {ans += hash[sum - k];}hash[sum] ++;}return ans;}
};239.滑动窗口最大值
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> ans;// 单调队列deque<int> q;// 先把前k个都加入到单调队列中for (int i = 0; i < k; i++) {while (!q.empty() && q.back() < nums[i]) {q.pop_back();}q.push_back(nums[i]);}// 前k个元素是第一个窗口，先放入一个ans.push_back(q.front());for (int i = k; i < nums.size(); i++) {// 如果滑出去的是队列头部最大的，那么删除队列头部if (nums[i - k] == q.front()) {q.pop_front();}// 删除队列中所有比当前元素大的，保证队列的单调性while (!q.empty() && q.back() < nums[i]) {q.pop_back();}q.push_back(nums[i]);ans.push_back(q.front());}return ans;}
};76.最小覆盖子串
class Solution {
public:string minWindow(string s, string t) {// 滑动窗口// windows表示当前窗口, need表示需要凑齐的字符unordered_map<char, int> windows, need;int left = 0;int right = 0;int count = 0; // 记录当前窗口windows中符合need的总数int len = INT_MAX;int start = 0;for (auto elem : t) {need[elem] ++;}while (right < s.size()) {// 向右移动窗口char c = s[right];right ++;// 更新窗口if (need.count(c)) {windows[c] ++;if (windows[c] == need[c]) {count ++;}}// 左边收缩窗口while (count == need.size()) { // 此时已经全覆盖// 更新最小覆盖子串if (right - left < len) {start = left; // 记录最小子串的起始位置len = right - left;}// 移出窗口char d = s[left];left ++;// 更新窗口if (need.count(d)) {if (windows[d] == need[d]) {count --;}windows[d] --;}}}return len == INT_MAX ? "" : s.substr(start, len);}
};堆
215.数组中的第K个最大元素
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> p;for (auto& num : nums) {p.push(num);}while (--k) {p.pop();}return p.top();}
};class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 小根堆// 先放入k个元素到小根堆中// 小根堆中维护最大的k个元素priority_queue<int, vector<int>, greater<int> > p;for (int i = 0; i < k; i++) {p.push(nums[i]);}for (int i = k; i < nums.size(); i++) {if (nums[i] > p.top()) {p.pop();p.push(nums[i]);}}return p.top();}
};347.前K个高频元素
class Solution {
private:class mycomparison {public:bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 求前k大, 用小根堆; 求前k小, 用大根堆。// 每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogkvector<int> ans(k);unordered_map<int, int> map;for (int i = 0; i < nums.size(); i++) {map[nums[i]] ++;}// 定义一个k个大小的小顶堆priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;for (auto it = map.begin(); it != map.end(); it ++) {pri_que.push(*it);// 超出大小就把堆顶最小的元素删除if (pri_que.size() > k) {pri_que.pop();}}// 倒序输出小顶堆for (int i = k - 1; i >= 0; i--) {ans[i] = pri_que.top().first;pri_que.pop();}return ans;}
};295.数据流的中位数
class MedianFinder {
private:priority_queue<int, vector<int>, less<int> > maxqueue; // 大顶堆priority_queue<int, vector<int>, greater<int> > minqueue; // 小顶堆
public:MedianFinder() {}void addNum(int num) {// 每次先插入到小顶堆,然后将小顶堆的最小元素取出来插入到大顶堆当中// 这样就能保证小顶堆的元素都比大顶堆的大minqueue.push(num);maxqueue.push(minqueue.top());minqueue.pop();// 处理两个顶堆长度失衡的情况// 不这样处理的话会出现所有的num都被插入到了大顶堆当中if (minqueue.size() < maxqueue.size()) {minqueue.push(maxqueue.top());maxqueue.pop();}}double findMedian() {if (maxqueue.size() == minqueue.size()) {return (maxqueue.top() + minqueue.top()) / 2.0;}return minqueue.top();}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/