The 14th day of the special assault version of the sword offer

剑指 Offer II 041. 滑动窗口的平均值

简单的队列,I add a circular queue to it,Consider it a rehearsal

class MovingAverage {
    
private:
    int que[1010] = {
    0};
    int tail = 0,head = 0;
    int sz = 0;
    int sum = 0;    
public:
    /** Initialize your data structure here. */
    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. 最近请求次数

Originally wanted to use prefix sum,但是发现 $t$ 的范围太大,Because of the subject guarantee every time $ping$ 调用的 $t$ 都单调递增,也就是说每个 $t$ 只有一个请求,So just calculate the queue length.

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. 往完全二叉树添加节点
Find all nodes that do not have full children through layer-order traversal and join them in order $condidate$ 队列.
Taken when inserting a node $condidate$ first in queue,即可直接 $O(1)$ 的时间插入.

class CBTInserter {
    
private:
    queue<TreeNode*> condidate;
    TreeNode* root;    
public:
    CBTInserter(TreeNode* root) {
    
        this->root = root;
        queue<TreeNode*> 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;
    }
};