LeetCode + 《剑指Offer II》刷题笔记。

队列

滑动窗口

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class MovingAverage {
public:
    queue<int> q;
    int capacity;
    double sum;
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        capacity=size;
    }
    
    double next(int val) {
        if(q.size()==capacity){
            sum-=q.front();
            q.pop();
        }
        sum+=val;
        q.push(val);
        return sum/q.size();
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

时间复杂度：初始化和每次调用 next 的时间复杂度都是 O(1)
空间复杂度：O(size)

933 Number of Recent Calls

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class RecentCounter {
public:
    vector<int> v;
    RecentCounter() {
        
    }
    
    int ping(int t) {
        int num=0;
        int temp=t-3000;
        v.push_back(t);
        for(int x:v){
            if(x<=t && x>=temp){
                num+=1;
            }
        }
        return num;
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

时间复杂度：初始化 O(1)，每次调用 print 的时间复杂度都是 O(n)
空间复杂度：O(n)

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class RecentCounter {
public:
    queue<int> q;
    RecentCounter() {
        
    }
    
    int ping(int t) {
        q.push(t);
        while(q.front()<(t-3000)){
            q.pop();
        }
        return q.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

时间复杂度：均摊 O(1)，每个元素至多入队出队各一次。
空间复杂度：O(1)

二叉树的广度优先搜索

时间复杂度：O(n)
空间复杂度：O(n)。如果把父节点已经遍历到但自身尚未到达的节点存储在队列之中，那么最多需要存储一层的节点。在一棵满的二叉树中，最下面一层的节点数最多，最多可能有（n+1）/2个节点，因此，二叉树BFS的空间复杂度是O（n）。

二叉树的BFS很容易知道每层最左边或最右边的节点，或者每层的最大值、最小值等。如果关于二叉树的面试题提到层这个概念，那么基本上可以确定该题目需要运用BFS。

919 Complete Binary Tree Inserter

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class CBTInserter {
public:
    queue<TreeNode*> q;
    TreeNode* root;
    CBTInserter(TreeNode* root) {
        this->root=root;
        
        q.push(root);
        while(q.front()->left!=nullptr && q.front()->right!=nullptr){
            TreeNode* cur=q.front();
            q.pop();
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    
    int insert(int val) {
        TreeNode* node=new TreeNode(val);
        TreeNode* parent=q.front();
        if(parent->left==nullptr){
            parent->left=node;
        }else{
            parent->right=node;
            q.pop();
            q.push(parent->left);
            q.push(parent->right);
        }
        return parent->val;
    }
    
    TreeNode* get_root() {
        return this->root;
    }
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(val);
 * TreeNode* param_2 = obj->get_root();
 */

CBTInserter的构造函数CBTInserter(TreeNode* root)按照BFS的顺序从根节点开始遍历输入的完全二叉树，如果一个节点的左右子节点都已经存在，就不可能再在这个节点添加新的子节点，因此可以从队列中删除这个节点，并将它的左右子节点都添加到队列之中。

因此，CBTInserter构造函数中队列的判断条件为：

while(q.front()->left!=nullptr && q.front()->right!=nullptr)

时间复杂度：

构造函数：O(n)

insert函数：O(1)

get_root函数：O(1)
空间复杂度：O(n)

515 Find Largest Value in Each Tree Row

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> res;
        if(!root) return res;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            int maxValue=INT_MIN;
            for(int i=0;i<size;i++){
                TreeNode* cur=q.front();
                q.pop();
                maxValue=max(maxValue,cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            res.push_back(maxValue);
        }
        return res;
    }
};

注意：要有if(!root) return res;,否则提交会有Runtime Error。

时间复杂度：O(n)
空间复杂度：O(n)

513 Find Bottom Left Tree Value

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode* cur=q.front();
                if(i==0) res=cur->val;
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* cur=q.front();
            q.pop();
            if(cur->right) q.push(cur->right);
            if(cur->left) q.push(cur->left);
            res=cur->val;
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

199 Binary Tree Right Side View

BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode* cur=q.front();
                q.pop();
                if(i==0){
                    res.push_back(cur->val);
                }
                if(cur->right) q.push(cur->right);
                if(cur->left) q.push(cur->left);
            }
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        dfs(root,res,0);
        return res;
    }
    void dfs(TreeNode* root,vector<int>& res,int depth){
        if(!root) return;
        if(depth==res.size()){
            res.push_back(root->val);
        }
        dfs(root->right,res,depth+1);
        dfs(root->left,res,depth+1);
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

LeetCode Queue

Table of Contents

队列