Check LintCode 1065 My Calendar I - C++

设计类构造函数不懂class MyCalendar {
private: 
    vector<vector<int>> timeSlots; 
public:
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        if(timeSlots.size() == 0){
            vector<int> times{start, end}; 
            timeSlots.push_back(times); 
            return true; 
        }
        for(int i = 0; i < timeSlots.size(); i++){
            if(!(start >= timeSlots[i][1] || end <= timeSlots[i][0])){
                return false; 
            }
        }
        vector<int> times{start, end}; 
        timeSlots.push_back(times); 
        return true; 
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * bool param_1 = obj.book(start,end);
 */
    1/30/2019更新
    /*方法二:(构造特殊的二叉搜索树 (https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fr=aladdin))
    1. 类似在常见的二叉搜索树中查找某个数一样,如果我们能够实现出一种特殊的二叉搜索树,使得:
    1. 树中每个节点是已加的一个时间段。
    2. 能方便地查找新时间段与树中节点是否重叠。
    2. 这样就能大幅提高效率。庆幸的是,这种想法是可行的。
    3. 具体地,从树根开始搜索,当前搜索节点指向树根。新的时间段与当前节点有三种可能:
    1. 完全在当前节点左侧,则当前节点指向左孩子;
    2. 完全在当前节点右侧,则当前节点指向右孩子;
    3. 有重叠,直接返回false。
    4. 循环该过程,直到当前节点指空。指空说明新的时间段与整棵树无重叠,则把新的时间段添加在当前位置,并返回true。
    6. 复杂度分析:
    1. 时间复杂度:O(N * logN),N是添加成功的时间段数量,对于每一个时间段的搜索需要O(logN),添加需要O(1)。(*注意:*这里的O(N * logN)只能看作是平均时间复杂度,因为搜索最坏需要O(N)。 如果在手动构造二叉搜索树时实现了平衡处理或者使用了TreeMap等标准库,可保证O(N * logN)仍为最坏时间复杂度)
    2. 空间复杂度O(N),用于构造二叉树。
    */
    
    class Node {
    private:
        int start, end;
        Node * left, * right;
    
    public:
        Node(int start, int end) {
            this->start = start;
            this->end = end;
            this->left = this->right = NULL;
        }
        
        bool insert(Node * node) {
            if (node->start >= this->end) {
                if (!this->right) {
                    this->right = node;
                    return true;
                }
                return this->right->insert(node);
            } 
            else if (node->end <= this->start) {
                if (!this->left) {
                    this->left = node;
                    return true;
                }
                return this->left->insert(node);
            } 
            else {
                return false;
            }
        }
    };
    
    class MyCalendar {
    private:
        Node * root;
    public:
        MyCalendar() {
            this->root = NULL;
        }
        
        bool book(int start, int end) {
            if (this->root) {
                return this->root->insert(new Node(start, end));
            } 
            this->root = new Node(start, end);
            return true;
        }
    };
    
    /**
     * Your MyCalendar object will be instantiated and called as such:
     * MyCalendar obj = new MyCalendar();
     * bool param_1 = obj.book(start,end);
     */
    
    
    
    
    2019年3月7日16:51:03 二刷。不需要上面二叉树方法啊,空间和时间复杂度都是O(n)
    class MyCalendar {
    struct pair{
        int start; 
        int end; 
        pair(int a, int b){
            start = a;
            end = b; 
        }
    };    
    public:
        std::vector<pair> times;
        MyCalendar() {
            
        }
        
        bool book(int start, int end) {
            for(int i = 0; i < times.size(); i++){
                if(!(start >= times[i].end || end <= times[i].start)){//判断是否重叠关键!!!!
                    return false; 
                }
            }
            times.push_back(pair(start, end)); 
            return true; 
        }
    };

    Comments

    Popular posts from this blog

    算法的比较

    生命