Problem
LeetCode 346. Moving Average from Data Stream
LeetCode : 1429. First Unique Number
[queue][hash table]
LeetCode : 2073. Time Needed to Buy Tickets
[queue][Array]
— — —
LeetCode 1696. Jump Game VI
[monotonic queue]
LeetCode 346. Moving Average from Data Stream
class MovingAverage {
public:
/** Initialize your data structure here. */
queue<int> q;
int q_size = 0;
int nowSum = 0;
MovingAverage(int size) {
q_size = size;
}
double next(int val) {
if(q.size() < q_size) {
nowSum += val;
q.push(val);
} else if(q.size() == q_size) {
nowSum -= q.front();
nowSum += val;
q.pop();
q.push(val);
}
return (double)nowSum / q.size();
}
};
LeetCode : 1429. First Unique Number
class FirstUnique {
public:
unordered_map <int, int> um;
queue<int> q;
FirstUnique(vector<int>& nums) {
for(int i = 0;i < nums.size();i++) {
um[nums[i]]++;
}
for(int i = 0;i < nums.size();i++) {
if(1 == um[nums[i]]) {
q.push(nums[i]);
}
}
}
int showFirstUnique() {
if(q.empty()) {
return -1;
}
while(um[q.front()] > 1) {
q.pop();
}
if(q.empty()) {
return -1;
}
return q.front();
}
void add(int value) {
if(um.find(value) == um.end()) {
q.push(value);
}
um[value]++;
}
};/**
* Your FirstUnique object will be instantiated and called as such:
* FirstUnique* obj = new FirstUnique(nums);
* int param_1 = obj->showFirstUnique();
* obj->add(value);
*/
LeetCode : 2073. Time Needed to Buy Tickets
class Solution {
public:
int timeRequiredToBuy(vector<int>& tickets, int k) {
queue<int> q;
int t = 0;
for(int i = 0;i < tickets.size();i++) {
q.push(i);
}
while(tickets[k] != 0) {
int nowp = q.front();
q.pop();
tickets[nowp]--;
if(tickets[nowp] != 0) {
q.push(nowp);
}
t++;
}
return t;
}
};