剑指 Offer II 041. 滑动窗口的平均值
简单的队列，我给它加上循环队列，就当成复习
class MovingAverage {
private:
int que[1010] = {0};
int tail = 0,head = 0;
int sz = 0;
int sum = 0;
public:
MovingAverage(int size) {
sz = size;
}
double next(int val) {
que[tail] = val;
tail = (tail+1)%1010;
sum += val;
int len = (tail-head+1010)%1010;
if(len > sz) {
sum -= que[head];
head = (head+1)%1010;
len--;
}
return 1.0*sum/len;
}
};
剑指 Offer II 042. 最近请求次数
本来想用前缀和，但是发现 t t t 的范围太大，由于题目保证每次 p i n g ping ping 调用的 t t t 都单调递增，也就是说每个 t t t 只有一个请求，所以只需计算队列长度即可。
class RecentCounter {
private:
int que[10010] = {0};
int head, tail;
public:
RecentCounter() {
head = tail = 0;
}
int ping(int t) {
que[tail++] = t;
while(que[head] < t-3000) head++;
return tail-head;
}
};
剑指 Offer II 043. 往完全二叉树添加节点
通过层序遍历找出所有没有满孩子的结点并按顺序加入
c
o
n
d
i
d
a
t
e
condidate
condidate 队列。
在插入结点时取
c
o
n
d
i
d
a
t
e
condidate
condidate 队列第一个，即可直接
O
(
1
)
O(1)
O(1) 的时间插入。
class CBTInserter {
private:
queue condidate;
TreeNode* root;
public:
CBTInserter(TreeNode* root) {
this->root = root;
queue que;
que.push(root);
while(que.size()){
auto ptr = que.front(); que.pop();
if(ptr->left) {
que.push(ptr->left);
}
if(ptr->right) {
que.push(ptr->right);
}
if(!ptr->right || !ptr->left) {
condidate.push(ptr);
}
}
}
int insert(int v) {
auto child = new TreeNode(v);
auto node = condidate.front();
if(!node->left) {
node->left = child;
} else {
node->right = child;
condidate.pop();
}
condidate.push(child);
return node->val;
}
TreeNode* get_root() {
return root;
}
};
