建设仿优酷视频网站,wordpress 免费注册,宁波seo网络推广优化价格,济南做网站的公司有哪些My Calendar的book方法实现指定开始时间、结束时间#xff0c;在重叠次数要求不同的情况下怎么实现。 729 My Calendar I 要求任意两个事件之间不能重叠。如果要插入的事件和已经插入的事件不重叠#xff0c;则插入#xff1b;否则不插入。 731 MyCalendar II 要求任意三个…My Calendar的book方法实现指定开始时间、结束时间在重叠次数要求不同的情况下怎么实现。 729 My Calendar I 要求任意两个事件之间不能重叠。如果要插入的事件和已经插入的事件不重叠则插入否则不插入。 731 MyCalendar II 要求任意三个时间之间不能重叠但两个事件可以重叠。同样如果满足要求则事件可以插入否则不能插入。 732 MyCalendar III 则是要求返回插入当前事件之后整个Calendar中重叠次数最多是多少。
729 My Calendar I
要求任意两个事件之间不能重叠可以利用二叉查找树BST。每个节点代表一个事件包含startend。如果要插入的事件范围全部在当前节点左侧或者右侧则可以插入。否则不可以插入。 class MyCalendarV3 {class Node{int start,end;Node left,right;Node(int start,int end){this.start start;this.end end;}}Node root;public boolean book(int start, int end) {if(insertable(start,end,root)){root insert(start,end,root);return true;}return false;}private Node insert(int start, int end, Node cur) {if(curnull) return new Node(start,end);if(startcur.end) {cur.right insert(start, end, cur.right);}else if(end cur.start) {cur.left insert(start, end, cur.left);}return cur;}private boolean insertable(int start, int end, Node cur) {if(curnull) return true;if(startcur.end) {return insertable(start, end, cur.right);}else if(end cur.start) {return insertable(start, end, cur.left);}return false;}
}
731 My Calendar II
要求任意三个时间之间不能重叠但两个事件可以重叠。在上面解题的基础上需要将有重叠区域的做节点分裂并且标记是不是已经重复。如果已经重复的节点再次遇到重叠则不允许插入。这个节点分裂则是整个过程中比较复杂的部分。 例如MyCalendar.book(10, 20); MyCalendar.book(50, 60); 之后树应该是这样的。 当要插入(10,40)的时候首先会遇到与curNode(10,20)节点重叠。节点分裂为[10,10),[10,20),[20,40)三个部分。[10,10)插入curNode的左节点[20,40)插入curNode的右节点。在插入右节点的时候又需要与已经存在的右节点(50,60)做比较。[20,40)作为节点(50,60)的左节点插入。如下图所示。节点(10,20)被标记为overlaptrue。下次再碰到这个区域的重叠的事件则可以直接返回false。 当然节点[10,10)是没有意义的。既包含10又不包含10是空集应该去掉。 以上展示了一个节点分裂的过程。插入的startend当前节点的curNode.leftcurNode.right这四个数之间有大小关系。如果按照从小到大分别记为n1,n2,n3,n4则(n1,n2)是curNode的左子树(n3,n4)作为curNode的右子树curNode.leftn2,curNode.rightn3。
class MyCalendarTwoV2 {class Node{int start,end;boolean overlap;Node left,right;Node(int start,int end){this.start start;this.end end;}}Node root;public MyCalendarTwoV2() {}public boolean book(int start, int end) {if(!insertable(start,end,root)){return false;}root insert(start,end,root);return true;}private Node insert(int start, int end, Node cur) {if(startend) return cur;if(curnull){return new Node(start,end);}if(start cur.end) {cur.right insert(start,end,cur.right);}else if(end cur.start){cur.left insert(start,end,cur.left);}else{cur.overlap true;int a Math.min(start, cur.start);int b Math.max(start, cur.start);int c Math.min(end, cur.end);int d Math.max(end, cur.end);cur.left insert(a,b,cur.left);cur.right insert(c,d,cur.right);cur.start b;cur.end c;}return cur;}/*** 判断startend 是否可插入* param start* param end* param curNode* return*/private boolean insertable(int start, int end, Node cur) {if(startend) return true;if(curnull) return true;if(start cur.end) {return insertable(start,end,cur.right);}else if(end cur.start){return insertable(start,end,cur.left);}else{if(cur.overlap){return false;}else{if(startcur.start end cur.end){return true;}else{return insertable(start,cur.start,cur.left) insertable(cur.end,end,cur.right);}}}}
}
732 My Calendar III
要求返回插入当前事件之后整个Calendar中重叠次数最多是多少。在上题基础上把Boolean 变量换成计数的int类型。当本区域发生一次重叠则计数加1。 对于分裂产生的节点次数不能简单设置为1。 参考上图分析一下分裂插入的左子树部分。假设curNode当前区域已经出现了count次。如果分裂后的区域是[start,curNode.left)这是一个新的区域次数为1如果分裂后是[curNode.left,start)那么次数就应该是count因为[curNode.left,start)肯定包含在[curNode.left,curNode.right)范围内。同理分析一下右子树部分。
class MyCalendarThree {class Node{int start,end;int k 1;Node left,right;Node(int start,int end,int k){this.start start;this.end end;this.k k;}}Node root;int maxK1;public MyCalendarThree() {}/*** * param start* param end* return*/public int book(int start, int end) {root insert(start,end,root,1);return maxK;}private Node insert(int start, int end, Node cur,int val) {if (start end)return cur;if (cur null) {return new Node(start, end,val);}if (start cur.end) {cur.right insert(start, end, cur.right,val);} else if (end cur.start) {cur.left insert(start, end, cur.left,val);} else {int a Math.min(start, cur.start);int b Math.max(start, cur.start);int c Math.min(end, cur.end);int d Math.max(end, cur.end);//细节是这里cur.left insert(a, b, cur.left,startcur.start?val:cur.k);cur.right insert(c, d, cur.right,endcur.end?val:cur.k);cur.start b;cur.end c;cur.k val;}maxK Math.max(maxK, cur.k);return cur;}
}
My Calendar的其他思路
BST只是一种解决思路。还可以使用其他。例如729 可以使用TreeMap判断重叠区域。731 可以在利用729类的基础上判断是否有重叠区域。732还有一种timeline的思路。把所有区域看做是一条线上的点。这种思路非常赞。遇到start值加1遇到end值减1。求得在一个线段内重复的次数。 例如MyCalendarThree.book(10, 20); // returns 1 MyCalendarThree.book(50, 60); // returns 1 MyCalendarThree.book(10, 40); // returns 2
[10,20)2次 [20,40)1次 [40,50)0次 [50,60)1次
class MyCalendarThreeV2 {private TreeMapInteger, Integer timeline new TreeMap();public int book(int s, int e) {timeline.put(s, (timeline.get(s)!null?timeline.get(s):0) 1); // 1 new event will be// starting at [s]timeline.put(e, (timeline.get(e)!null?timeline.get(e):0) - 1); // 1 new event will be// ending at [e];int ongoing 0, k 0;for (int v : timeline.values())k Math.max(k, ongoing v);return k;}
}
参考资料 网页1 网页2 网页3 网页4
