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

x33g5p2x  于2021-11-21 转载在 其他  
字(1.2k)|赞(0)|评价(0)|浏览(288)

题目

https://leetcode.com/problems/my-calendar-i/

题解

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

  1. class Node {
  2. int l;
  3. int r;
  4. boolean used; // 当前范围已全覆盖
  5. Node left;
  6. Node right;
  7. public Node(int l, int r) {
  8. this.l = l;
  9. this.r = r;
  10. }
  11. }
  12. class MyCalendar {
  13. Node info;
  14. public MyCalendar() {
  15. info = new Node(0, 1 << 30);
  16. }
  17. public boolean book(int start, int end) {
  18. if (canAdd(info, start, end - 1)) { // [左闭,右闭]区间
  19. add(info, start, end - 1);
  20. return true;
  21. } else {
  22. return false;
  23. }
  24. }
  25. public boolean canAdd(Node info, int L, int R) {
  26. if (info.used) return false;
  27. // 当前范围从未开垦且可以全覆盖,则不分发直接返回
  28. if (info.left == null && L <= info.l && info.right == null && R >= info.r - 1) return true;
  29. // 分发至左右子树
  30. int m = (info.l + info.r) / 2;
  31. if (L < m) {
  32. if (info.left != null && !canAdd(info.left, L, R)) return false;
  33. }
  34. if (R >= m) {
  35. if (info.right != null && !canAdd(info.right, L, R)) return false;
  36. }
  37. return true;
  38. }
  39. public void add(Node node, int L, int R) {
  40. if (L <= node.l && R >= node.r - 1) {
  41. node.used = true;
  42. return;
  43. }
  44. // 分发至左右子树
  45. int m = (node.l + node.r) / 2;
  46. if (L < m) {
  47. if (node.left == null) {
  48. node.left = new Node(node.l, m);
  49. }
  50. add(node.left, L, R);
  51. }
  52. if (R >= m) {
  53. if (node.right == null) {
  54. node.right = new Node(m, node.r);
  55. }
  56. add(node.right, L, R);
  57. }
  58. }
  59. }
  60. /** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */

相关文章