谷哥店面，直接被教做人
我认为我刷题已经刷的很够了(500+)，但店面还是很卡
背靠背两轮店面，我先分享其中一轮就好
class Solution {
intcapacity;
Solution(int c) { capacity = c; }
void input(int num) {}
intaverage() {}
}
使其输出
Solution solution(2);
solution.average(); // 0
solution.input(2);
solution.average(); // 1
solution.input(3);
solution.average(); // 2.5
solution.input(4);
solution.average(); // 3.5
follow up
计算average 不要算入最高的topK个数字
class Solution {
intcapacity;
inttopK;
Solution(int c, int k) { capacity = c; topK = k; }
void input(int num) {}
intaverage() {}
}
Solution solution(3,1);
solution.input(2);
solution.input(100);
solution.input(4);
solution.average(); // 3
solution.input(200);
solution.average(); // 52
最佳解
用两个priority queue储存是topK裡、不在topK裡
第一题直接做出来，但follow up在没有interviewer的提示下，没写出最佳解，提示完才写出
题目真的不难，但在那个压力下，脑袋卡住，哎… 还是得再努力一点啊
补充内容 (2019-11-15 10:46):
我仔细想想后 我觉得 用两个priority queue是解不出来的
应该是要用两个multiset
实际上在面试中 我是用两个multiset来写 但隐约听到面试官说priority queue之类的
补充内容 (2019-11-15 10:47):
解释一下为什麽要用两个multiset
topK的multiset必须要维持topK个
在sliding window移动的过程中
queue.front pop后
topK的multiset可能不是topK个
这时候必须要从non-topK的multiset补最大的进来
补充内容 (2019-11-17 09:55):
大家注意一下 这题是计算sliding window裡cap个平均值的问题
比如cap=2
{2,4,6,8,10,12,14}
那average输出是{3,5,7,9,11,13}
follow-up一样是sliding window 只是要排除topK大的元素 不去计算