当前位置:首页 » 《随便一记》 » 正文

leetcode 729. My Calendar I | 729. 我的日程安排表 I(线段树)_寒泉

14 人参与  2022年06月01日 12:00  分类 : 《随便一记》  评论

点击全文阅读


题目

https://leetcode.com/problems/my-calendar-i/
在这里插入图片描述

题解

看了左神课之后,自己实现了下改造后的线段树(非常不优雅),因为数组放不下,所以自建 Node 结构。

class Node {
    int l;
    int r;
    boolean used; // 当前范围已全覆盖
    Node left;
    Node right;

    public Node(int l, int r) {
        this.l = l;
        this.r = r;
    }
}

class MyCalendar {
    Node info;

    public MyCalendar() {
        info = new Node(0, 1 << 30);
    }

    public boolean book(int start, int end) {
        if (canAdd(info, start, end - 1)) { // [左闭,右闭]区间
            add(info, start, end - 1);
            return true;
        } else {
            return false;
        }
    }

    public boolean canAdd(Node info, int L, int R) {
        if (info.used) return false;
        // 当前范围从未开垦且可以全覆盖,则不分发直接返回
        if (info.left == null && L <= info.l && info.right == null && R >= info.r - 1) return true;
        // 分发至左右子树
        int m = (info.l + info.r) / 2;
        if (L < m) {
            if (info.left != null && !canAdd(info.left, L, R)) return false;
        }
        if (R >= m) {
            if (info.right != null && !canAdd(info.right, L, R)) return false;
        }
        return true;
    }

    public void add(Node node, int L, int R) {
        if (L <= node.l && R >= node.r - 1) {
            node.used = true;
            return;
        }
        // 分发至左右子树
        int m = (node.l + node.r) / 2;
        if (L < m) {
            if (node.left == null) {
                node.left = new Node(node.l, m);
            }
            add(node.left, L, R);
        }
        if (R >= m) {
            if (node.right == null) {
                node.right = new Node(m, node.r);
            }
            add(node.right, L, R);
        }
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

在这里插入图片描述


点击全文阅读


本文链接:http://zhangshiyu.com/post/41155.html

子树  发至  覆盖  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1