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)
|
