b*******m 发帖数: 10 | 1 1: 给一个hashset, 有insert search delete 接口, 现在一个ttl(time to live)
的功能
1: 假设存数据的每个数据的expire time是相同的, 这个简单,做出来了,
2: 如果每个数据的expire time不同, 该用什么样式的数据结构, 怎么实现
2: 空间有很多固定点, 找出距离当前位置距离最近的 k个点, 时间复杂度尽量少
3: 有n个东西每个东西的size不同,现在放到大小固定的框中,问如果放,使得用到
的框最少 |
f*******t 发帖数: 7549 | 2 这不三道题么…第三题bin packing难度碉堡了
【在 b*******m 的大作中提到】 : 1: 给一个hashset, 有insert search delete 接口, 现在一个ttl(time to live) : 的功能 : 1: 假设存数据的每个数据的expire time是相同的, 这个简单,做出来了, : 2: 如果每个数据的expire time不同, 该用什么样式的数据结构, 怎么实现 : 2: 空间有很多固定点, 找出距离当前位置距离最近的 k个点, 时间复杂度尽量少 : 3: 有n个东西每个东西的size不同,现在放到大小固定的框中,问如果放,使得用到 : 的框最少
|
w*****t 发帖数: 485 | 3 1.2 如果每个数据的expire time不同, 该用什么样式的数据结构, 怎么实现
可以考虑优先队列,每个数据进来后,可以根据expire time算出结束的时间戳,将 {
exp_time, data} 放入优先队列中,然后定时check队列的头部元素,时间到了就pop,
并delete(data).
【在 b*******m 的大作中提到】 : 1: 给一个hashset, 有insert search delete 接口, 现在一个ttl(time to live) : 的功能 : 1: 假设存数据的每个数据的expire time是相同的, 这个简单,做出来了, : 2: 如果每个数据的expire time不同, 该用什么样式的数据结构, 怎么实现 : 2: 空间有很多固定点, 找出距离当前位置距离最近的 k个点, 时间复杂度尽量少 : 3: 有n个东西每个东西的size不同,现在放到大小固定的框中,问如果放,使得用到 : 的框最少
|
j*****y 发帖数: 1071 | 4 1.2, 是不是可以用一个 max heap ? key 就是每个 数据的 ttl = current time
stamp + expire time.
【在 b*******m 的大作中提到】 : 1: 给一个hashset, 有insert search delete 接口, 现在一个ttl(time to live) : 的功能 : 1: 假设存数据的每个数据的expire time是相同的, 这个简单,做出来了, : 2: 如果每个数据的expire time不同, 该用什么样式的数据结构, 怎么实现 : 2: 空间有很多固定点, 找出距离当前位置距离最近的 k个点, 时间复杂度尽量少 : 3: 有n个东西每个东西的size不同,现在放到大小固定的框中,问如果放,使得用到 : 的框最少
|
l****i 发帖数: 2772 | 5 为什么不是min heap?
【在 j*****y 的大作中提到】 : 1.2, 是不是可以用一个 max heap ? key 就是每个 数据的 ttl = current time : stamp + expire time.
|
r**h 发帖数: 1288 | |
c********t 发帖数: 5706 | 7 应该是min heap吧。
第三题,以前想过一次,没想出来怎么做。
【在 l****i 的大作中提到】 : 为什么不是min heap?
|
Q****s 发帖数: 1301 | |
j*****y 发帖数: 1071 | 9 能给出状态方程吗?
背包九讲里面没这个阿
【在 Q****s 的大作中提到】 : 第三题就是背包问题
|
p*****p 发帖数: 379 | 10 第三题greedy对么,对于当前的bin,找放进去以后剩余空间最少的那个,如果没有,
就新开一个
O(n^2)
【在 b*******m 的大作中提到】 : 1: 给一个hashset, 有insert search delete 接口, 现在一个ttl(time to live) : 的功能 : 1: 假设存数据的每个数据的expire time是相同的, 这个简单,做出来了, : 2: 如果每个数据的expire time不同, 该用什么样式的数据结构, 怎么实现 : 2: 空间有很多固定点, 找出距离当前位置距离最近的 k个点, 时间复杂度尽量少 : 3: 有n个东西每个东西的size不同,现在放到大小固定的框中,问如果放,使得用到 : 的框最少
|
j*****y 发帖数: 1071 | 11 poj有道这样的题是用 greedy,不过那里的例子简单多了
http://poj.org/problem?id=1017
【在 p*****p 的大作中提到】 : 第三题greedy对么,对于当前的bin,找放进去以后剩余空间最少的那个,如果没有, : 就新开一个 : O(n^2)
|