logo
Redian新闻
>未名空间
>Apple - 家有苹果
>
找个满意的tablet不容易 (转载)
avatar
找个满意的tablet不容易 (转载)# Apple - 家有苹果
g*c
1 楼
在室温下放了两天就不能吃了。。
avatar
F*r
2 楼
一个任意的数组，找出一个严格单调递增的最长子序列。只知道怎么用dynamic
programming.求一个nlogn的算法。谢谢！
avatar
b*e
3 楼
【 以下文字转载自 Military 讨论区 】
发信人: withoutacar (知道错了, 改过来就好.), 信区: Military
标 题: Re: 小结老将的一个语言游戏策略
发信站: BBS 未名空间站 (Tue Dec 21 18:36:07 2010, 美东)
老将的策略就是代表中国人落后.
他找不到中国人落后的地方, 就拿自己举例.
avatar
t*a
4 楼
【 以下文字转载自 PDA 讨论区 】
发信人: per (look back), 信区: PDA
标 题: 找个满意的tablet不容易
发信站: BBS 未名空间站 (Fri Nov 24 01:11:29 2017, 美东)
iPad：没有back键
Samsung Galaxy：有back键，但在右边。跟手机相反，别扭。
avatar
h*r
5 楼
那是你买的就不新鲜

【在 g*c 的大作中提到】
: 在室温下放了两天就不能吃了。。
avatar
c*2
7 楼
避光，要不放冰箱
avatar
j*u
8 楼
写了个只返回count的，要返回子序列在这个基础上加一个index array就可以了。
time O(nlogk), space O(k), k == length of LIS
int LIS(int[] array)
{
if (array == null || array.Length == 0)
return 0;
var incIndex = new List { 0 };
for (int i = 1; i < array.Length; ++i)
{
if (array[i] > array[incIndex.Last()])
incIndex.Add(i);
else
{
int l = 0;
for (int r = incIndex.Count; l <= r;)
{
int m = l + (r - l) / 2;
if (array[i] <= array[incIndex[m]])
r = m - 1;
else
l = m + 1;
}
incIndex[l] = i;
}
}
return incIndex.Count;
}

【在 F**********r 的大作中提到】
: 一个任意的数组，找出一个严格单调递增的最长子序列。只知道怎么用dynamic
: programming.求一个nlogn的算法。谢谢！
avatar
c*e
9 楼
尽量保持干燥

【在 g*c 的大作中提到】
: 在室温下放了两天就不能吃了。。
avatar
h*3
10 楼
私下问了jerryju 大虾，大概弄明白了。照葫芦画瓢写了个c++版本的，
打印出最大长度和最大序列。
jerryju大虾别骂我抄袭啊。
void mit_LIS(int arr[],int len)
{
vector incIndex;
vector preIndex;
int index;
incIndex.push_back(0);
preIndex.push_back(-1);
for ( int i=1;i{
if ( arr[i] >= arr[incIndex[incIndex.size()-1]] )
{
preIndex.push_back(incIndex[incIndex.size()-1]);
incIndex.push_back(i);
}
else
{
int l=0,r=incIndex.size()-1,m;
while ( l<=r )
{
m = l + (r-l)/2;
if ( arr[i] <= arr[incIndex[m]] )
r = m - 1;
else
l = m + 1;
}
incIndex[l] = i;
index = l > 0 ? incIndex[l-1]:-1;
preIndex.push_back(index);
}
}
cout << " the length of LIS is " << incIndex.size() << endl;
index = incIndex[incIndex.size()-1];
do
{
cout << arr[index] << " ";
index = preIndex[index];
}while ( index != -1);
}

【在 j*****u 的大作中提到】
: 写了个只返回count的，要返回子序列在这个基础上加一个index array就可以了。
: time O(nlogk), space O(k), k == length of LIS
: int LIS(int[] array)
: {
: if (array == null || array.Length == 0)
: return 0;
: var incIndex = new List { 0 };
: for (int i = 1; i < array.Length; ++i)
: {
: if (array[i] > array[incIndex.Last()])
avatar
g*A
11 楼
嗯
放冰箱
avatar
j*u
12 楼
呵呵，多谢share!
一个小问题是你最后print的LIS是逆序的，可以用stack revert一下

【在 h*********3 的大作中提到】
: 私下问了jerryju 大虾，大概弄明白了。照葫芦画瓢写了个c++版本的，
: 打印出最大长度和最大序列。
: jerryju大虾别骂我抄袭啊。
: void mit_LIS(int arr[],int len)
: {
: vector incIndex;
: vector preIndex;
: int index;
: incIndex.push_back(0);
: preIndex.push_back(-1);
avatar
F*r
13 楼
大家有没有发现这个link上的source code，http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp。
做binary search, v 不是指向c-1,而是c... 俩位的code都是c-1...这个有什么说法么？

【在 j*****u 的大作中提到】
: 呵呵，多谢share!
: 一个小问题是你最后print的LIS是逆序的，可以用stack revert一下
avatar
L*r
15 楼
排序？

【在 F**********r 的大作中提到】
: 一个任意的数组，找出一个严格单调递增的最长子序列。只知道怎么用dynamic
: programming.求一个nlogn的算法。谢谢！
avatar
s*y
17 楼
yes. it is.

【在 g**e 的大作中提到】
: 你这个是O(n^2)的
:
: ln
avatar
g*e
18 楼
wiki后面提供了一个O(nlgn)的，用到binary search

【在 s*****y 的大作中提到】
: yes. it is.
avatar
s*y
19 楼
o
Maybe I miss that. I will look at it now.
Thanks

【在 g**e 的大作中提到】
: wiki后面提供了一个O(nlgn)的，用到binary search
avatar
g*s
20 楼
不明白会了O(n)为啥还要找O（nlgn）的？除非你是老师，要教学生。
否则，你就用O（n）的算出来，得到结果你再做一遍无用的排序，这样就把算法拉到
nlgn了。 ：）
avatar
F*r
21 楼
这题有O(n)解法么？

【在 g***s 的大作中提到】
: 不明白会了O(n)为啥还要找O（nlgn）的？除非你是老师，要教学生。
: 否则，你就用O（n）的算出来，得到结果你再做一遍无用的排序，这样就把算法拉到
: nlgn了。 ：）
avatar
g*s
22 楼
DP is O(n).
【 在 FrLeafClover (4LeafClover) 的大作中提到: 】
avatar
j*u
23 楼
愿闻其详

【在 g***s 的大作中提到】
: DP is O(n).
: 【 在 FrLeafClover (4LeafClover) 的大作中提到: 】
avatar
g*s
24 楼
二楼的link里面有。这时很经典的DP问题。

【在 j*****u 的大作中提到】
: 愿闻其详
avatar
s*o
25 楼
这个好像没有比较阿（新发现的和已经发现的比较， 像二楼中的L = max(L, j+1)），怎么能得出最
长的序列？那位大虾指导一下？

【在 h*********3 的大作中提到】
: 私下问了jerryju 大虾，大概弄明白了。照葫芦画瓢写了个c++版本的，
: 打印出最大长度和最大序列。
: jerryju大虾别骂我抄袭啊。
: void mit_LIS(int arr[],int len)
: {
: vector incIndex;
: vector preIndex;
: int index;
: incIndex.push_back(0);
: preIndex.push_back(-1);
avatar
j*a
26 楼

有O（n）的解法？你记错了？

【在 g***s 的大作中提到】
: 二楼的link里面有。这时很经典的DP问题。
avatar
g*e
27 楼
自己再好好看看DP是不是O(n)

【在 g***s 的大作中提到】
: 二楼的link里面有。这时很经典的DP问题。
avatar
j*u
28 楼
这是很经典的DP问题，但我只知道O(nlogk)的解。

【在 g***s 的大作中提到】
: 二楼的link里面有。这时很经典的DP问题。
avatar
g*s
29 楼
我以为是求连续递增序列，这个是O（n）。
不连续是没有O（n）的算法。

【在 g**e 的大作中提到】
: 自己再好好看看DP是不是O(n)
avatar
c*0
30 楼
DP 是 n^2
binary search 是 nlog(n)
avatar
s*o
31 楼
刚才输入到VS里运行了下，好像这个C++的运行结果有问题。那位再验证一下？其实这
个题和
careercup 9.7有点类似。

最长的序列？那位大

【在 s****o 的大作中提到】
: 这个好像没有比较阿（新发现的和已经发现的比较， 像二楼中的L = max(L, j+1)），怎么能得出最
: 长的序列？那位大虾指导一下？
avatar
r*r
32 楼
L= incIndex.Count
当往incIndex里新添元素的时候，L自己就加1了。而当当前的array[i]小于
array[incIndex.Last()]的时候（else那一种情况），j必然小于L，所以L就不用变了
另外三楼四楼群的代码和wikipedia上的算法比较有一个bug，“incIndex[l] = i”之
前需要先判断array[i]是否小于array[incIndex[l]]，是的话才需要更新incIndex[l]
的值

，怎么能得
出最

【在 s****o 的大作中提到】
: 这个好像没有比较阿（新发现的和已经发现的比较， 像二楼中的L = max(L, j+1)），怎么能得出最
: 长的序列？那位大虾指导一下？
avatar
F*r
33 楼
re这个。另外那个查找，algorithm上是v = c 而不是c-1...有什么说法没？

【在 r********r 的大作中提到】
: L= incIndex.Count
: 当往incIndex里新添元素的时候，L自己就加1了。而当当前的array[i]小于
: array[incIndex.Last()]的时候（else那一种情况），j必然小于L，所以L就不用变了
: 另外三楼四楼群的代码和wikipedia上的算法比较有一个bug，“incIndex[l] = i”之
: 前需要先判断array[i]是否小于array[incIndex[l]]，是的话才需要更新incIndex[l]
: 的值
:
: ，怎么能得
: 出最
avatar
s*y
34 楼
看了各位大牛的实现后，写了个O(nlgk)的C实现
#include
#include
//assume input array size < 20
#define ARRAY_SIZE 20
/*P[k] —stores the position of the
predecessor of X[k] in the longest increasing subsequence ending at X[k].*/
static int P[ARRAY_SIZE];
/*M[j] stores the position k of the smallest value X[k]
such that there is an increasing subsequence of length j ending
at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here)*/
static int M[ARRAY_SIZE];
void Find_Lis(int input[], int size, int lis[], int *lis_length)
{
int i, j, k;
int index = 0;
int tmp;

M[0] = 0; //init the base;
for (i = 1; i < size; i++) {
if (input[i] > input[M[index]]) {
P[i] = M[index];
index++;
M[index] = i;
continue;
}

//binary search for the smallest k within array M that input[i] <
input[k]
k = index;
for (j = 0; j < k ; ) {
tmp = j + (k-j)/2;
if (input[M[tmp]] < input[i])
j = tmp+1;
else
k = tmp;
}

if (input[i] < input[M[j]]) {
if (j > 0)
P[i] = M[j-1];
M[j] = i;
}
}
*lis_length = index + 1; //LIS length

j = M[index]; //last index of the LIS
for (i = index; i >= 0; i--) {
lis[i] = input[j];
j = P[j];
}
return;
}
int main() {
int test[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
int lis[20], lis_length;
Find_Lis(test, sizeof(test) / sizeof(int), lis, &lis_length);
return 0;
}

【在 F**********r 的大作中提到】
: re这个。另外那个查找，algorithm上是v = c 而不是c-1...有什么说法没？
avatar
s*b
35 楼
现在的牛人都直接贴code。。。
哪位能把算法总结一下，wiki那个页面好像访问不了，我又比较弱看code不是太懂啊。
不太明白binary search 那段的作用。
avatar
s*y
36 楼
concentrate on the definitoin of these two arrays:
M[j] — stores the position k of the smallest value X[k] such that there
is an increasing subsequence of length j ending at X[k] on the range k ≤ i
(note we have j ≤ k ≤ i here).
P[k] — stores the position of the predecessor of X[k] in the longest in
creasing subsequence ending at X[k].
Then you will know what the binary search for.

【在 s*******b 的大作中提到】
: 现在的牛人都直接贴code。。。
: 哪位能把算法总结一下，wiki那个页面好像访问不了，我又比较弱看code不是太懂啊。
: 不太明白binary search 那段的作用。
相关阅读
用了一年半的iphone5s报废了求推荐：macbook pro 接 显示器【包子求助】att A1549版iphone6在中国能不能用 (转载)[出售]BRAND-NEW MacBook Pro 13" RETINA MF840LL/A $1200 OBO (转载)iphone照片删除了，怎么还占用空间？iPad上的微信无法接视频电话，但是可以打出去，什么问题新Macbook和MBP选哪个好呢？我今天才意识到流媒体这个市场很大不用智能手机的牛人们，你们见过么？MBP safari忽然不工作怎么回事？Apple TV airplay 很卡 求助国内能连icloud吗？果子的写作风格十年一剑终成空 苹果缘何败走智能电视IPhone 6过两个月会降价吗？Apple Photos如何为某个album生成一个sharing URL？问关于买iphone6的问题。谢谢就凭一点macbook就秒杀所有其他笔记本关于apple care的问题mac safari pdf怎么下载到特定文件夹
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。