implement the class 初始的 number pool 包含 [1...MAXLong]元素 checkout 返回number pool最小的元素,并取出 checkin 插入元素到number pool中 考虑只存checkout的元素,没太想清楚各种情况。。。 谁能说说最优的方案么
interface NumberPool { public long checkout(); public void checkin(long i); } implement the class 初始number pool contains [1...MAXLong] checkout 返回最小的元素 checkin 插入元素 考虑只存checkout的元素,没太想清楚各种情况。。。 谁能说说最优的方案么 还要发code 给他。。。在线等。。。
【在 l***d 的大作中提到】 : implement the class : 初始的 number pool 包含 [1...MAXLong]元素 : checkout 返回number pool最小的元素,并取出 : checkin 插入元素到number pool中 : 考虑只存checkout的元素,没太想清楚各种情况。。。 : 谁能说说最优的方案么
M*s
6 楼
Don't worry. He will pick up very quickly from friends in daycare.
T*n
7 楼
down?
r*e
8 楼
用一个set保存已经checkout的元素,同时用变量m记录下一个被checkout的元素 checkin(i): 如果 i 不在set里,没有影响; 如果 i 在set里,set.remove(i), if (i < m) m = i; checkout() ret = m m = 从set.upper_bound(m)开始找,下一个不在set里的 set.insert(ret) return ret
【在 l***d 的大作中提到】 : implement the class : 初始的 number pool 包含 [1...MAXLong]元素 : checkout 返回number pool最小的元素,并取出 : checkin 插入元素到number pool中 : 考虑只存checkout的元素,没太想清楚各种情况。。。 : 谁能说说最优的方案么
x*a
9 楼
还是WORRY啊,所以才想先让他接触一下。省得到时候FRUSTRATE了和老师发脾气。
【在 M********s 的大作中提到】 : Don't worry. He will pick up very quickly from friends in daycare.
c*m
10 楼
You mean down?
r*e
11 楼
初始条件是所有的数都在pool里,直接用heap太占空间
【在 j*****y 的大作中提到】 : 难道不是用 min heap ? : : interface NumberPool { : public long checkout(); : public void checkin(long i); : } : implement the class : 初始number pool contains [1...MAXLong] : checkout 返回最小的元素 : checkin 插入元素
【在 r*******e 的大作中提到】 : 用一个set保存已经checkout的元素,同时用变量m记录下一个被checkout的元素 : checkin(i): : 如果 i 不在set里,没有影响; : 如果 i 在set里,set.remove(i), if (i < m) m = i; : checkout() : ret = m : m = 从set.upper_bound(m)开始找,下一个不在set里的 : set.insert(ret) : return ret
-The interval tree is a binary search tree where each node in the tree stores a (key,value) pair: the key is the left end of an interval, and the value is the right end. -The interval tree for this problem is special in that the intervals are non -overlapping. -Initially, the tree only contain 1 node, the (1, MaxLong) pair. -Check out value v: find the largest key that is smaller than v, look at its value, assuming it looks like (k0,v0); if v0 is less than v, then v is not in the pool, and the check out fails; otherwise, remove that node (interval) and spilt the interval into two (k0, v-1), (v+1, v0), and insert them back into the tree. -Check in v: find two intervals: (a) the largest key that is smaller than v, say (k0,v0), and (b) the smallest key that is larger than v, say (k1,v1), in the interval tree (they are consecutive intervals for sure). ---if v < v0, then v is already in the pool, the check in can be ignored. ---else if v0 == v-1 && v+1 == k1, then merge (k0,v0) and (k1,v1) into (k0, v1), by removing them from the tree and inserting back the merged interval ---else if v0 == v-1, update (k0,v0) to (k0,v) ---else if v+1 == k1, remove (k1,v1) from tree and insert back (v+1,v1) ---else, insert new node (v,v) that's it.