h*****g
发帖数: 312 | 1 you are going to take some numbers as an input from a file. You need to
witer a program to find longest increasing sequence. You should process it
as soon as you are taking an input. After finishing the last input
immediately you should be able to tell the sequence. Input: 1 5 3 4 6 4
Output: 3 4 6
http://www.glassdoor.com/Interview/You-are-going-to-take-some-n
any idea? |
i*********7
发帖数: 348 | |
l*********8
发帖数: 4642 | 3 这个不是通常意义上的LIS吧？ 这里的longest increasing sequence要求是连续的
【在 h*****g 的大作中提到】
: you are going to take some numbers as an input from a file. You need to
: witer a program to find longest increasing sequence. You should process it
: as soon as you are taking an input. After finishing the last input
: immediately you should be able to tell the sequence. Input: 1 5 3 4 6 4
: Output: 3 4 6
: http://www.glassdoor.com/Interview/You-are-going-to-take-some-n
: any idea?
|
h*****g
发帖数: 312 | 4 为啥？ 连续的不是substring吗？
【在 l*********8 的大作中提到】
: 这个不是通常意义上的LIS吧？ 这里的longest increasing sequence要求是连续的
|
l*********8
发帖数: 4642 | 5 Input: 1 5 3 4 6 4
Output: 3 4 6
为什么不是 1 3 4 6? |
l*********8
发帖数: 4642 | 6 可能是题目搞错了吧
【在 l*********8 的大作中提到】
: Input: 1 5 3 4 6 4
: Output: 3 4 6
: 为什么不是 1 3 4 6?
|
g**********y
发帖数: 14569 | 7 要是不连续的lis, 一遍扫描没法出来吧。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 l*********8 的大作中提到】
: Input: 1 5 3 4 6 4
: Output: 3 4 6
: 为什么不是 1 3 4 6?
|
f****0
发帖数: 151 | 8 用个queue？把数一个一个放进queue里，同时记录queue里面最长的递增序列的长度，
一旦发现有新的数列比之前的更长，就把之前的全部dequeue。这样最后一个数到了以
后，在queue头里刚开始存的递增数列就是最长数列 |
d*****i
发帖数: 122 | 9 S
【在 f****0 的大作中提到】
: 用个queue？把数一个一个放进queue里，同时记录queue里面最长的递增序列的长度，
: 一旦发现有新的数列比之前的更长，就把之前的全部dequeue。这样最后一个数到了以
: 后，在queue头里刚开始存的递增数列就是最长数列
|
w****x
发帖数: 2483 | 10 有啥区别????????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????????????????
?????????? |
|
|
G******e
发帖数: 229 | 11 Sorry, but why using a queue makes a difference?
【在 f****0 的大作中提到】
: 用个queue？把数一个一个放进queue里，同时记录queue里面最长的递增序列的长度，
: 一旦发现有新的数列比之前的更长，就把之前的全部dequeue。这样最后一个数到了以
: 后，在queue头里刚开始存的递增数列就是最长数列
|
l*********8
发帖数: 4642 | 12 为什么一遍扫描无法出来？
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
【在 g**********y 的大作中提到】
: 要是不连续的lis, 一遍扫描没法出来吧。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
a*******8
发帖数: 110 | 13 应该是要即时更新吧
After finishing the last input
immediately you should be able to tell the sequence. |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | |
f****0
发帖数: 151 | |
l*****a
发帖数: 14598 | 17 这个无数人会的
【在 p*****2 的大作中提到】
: 对了，谁来讲讲LIS nlogn的算法呢？
|
p*****2
发帖数: 21240 | 18
所以我得补功课
【在 l*****a 的大作中提到】
: 这个无数人会的
|
p*****2
发帖数: 21240 | |
l*****a
发帖数: 14598 | 20 my backup.
#include
using namespace std;
vector find_lis(vector &a)
{
vector b, p(a.size());
int u, v;
if (a.size() < 1) return b;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++) {
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a[i]) u=c+1; else v=c;
}
if (a[i] < a[b[u]]) {
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}
// for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
u=b.size()-1;
v=b.back();
while(u) { b[u]=v; v=p[v]; u--; }
return b;
}
【在 p*****2 的大作中提到】
:
: 多谢。得好好看一下。
|
|
|
p*****2
发帖数: 21240 | 21
看C＋＋a代码真费劲。n你咋还不n转java呢？
【在 l*****a 的大作中提到】
: my backup.
: #include
: using namespace std;
: vector find_lis(vector &a)
: {
: vector b, p(a.size());
: int u, v;
: if (a.size() < 1) return b;
: b.push_back(0);
: for (size_t i = 1; i < a.size(); i++) {
|
w****x
发帖数: 2483 | 22
谁考nlogn的算法可以肯定那个人是存心不要你过, 做出来也白做, 欲加之罪何患无辞
【在 l*****a 的大作中提到】
: 这个无数人会的
|
y**********u
发帖数: 6366 | 23 传说中的range minimum query啊
【在 w****x 的大作中提到】
:
: 谁考nlogn的算法可以肯定那个人是存心不要你过, 做出来也白做, 欲加之罪何患无辞
|
l*****a
发帖数: 14598 | 24 １。没什么本质区别吧？
２。这是很早以前存的，正在开始考虑转
【在 p*****2 的大作中提到】
:
: 看C＋＋a代码真费劲。n你咋还不n转java呢？
|
