Redian新闻
>
DAPA适不适用于有合法身份的?
avatar
DAPA适不适用于有合法身份的?# EB23 - 劳工卡
c*t
1
不用binary O(n^2) 可以输出结果数组。
用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法?
avatar
D*Y
2
一般基督教的节日都说不要送卡。应该什么时候送呢?
小孩上early care, normal school hour还有after school hour。平日里又和教这个
教那个的老师接触。
算下来就很多很多老师了。
怎么送卡呢?
avatar
I*C
3
英文版上写的要在2014年11月20号没有lawful status. 但在USCIS发表的中文版上就没
有lawful status这一条。
avatar
H*s
4
查看下面链接:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence

【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法?

avatar
A*n
5
犹太人的哈纳卡跟圣诞节时间差不多。反正holiday season送应该没错,
你提前一点不要赶在圣诞节那两天就好了,卡上写happy holidays
我们就送主要的两三个老师
avatar
c*2
6
need to be illegal on or before 2014年11月20号
avatar
D*Y
8
谢谢。好似这个节日是fun holiday。

【在 A**n 的大作中提到】
: 犹太人的哈纳卡跟圣诞节时间差不多。反正holiday season送应该没错,
: 你提前一点不要赶在圣诞节那两天就好了,卡上写happy holidays
: 我们就送主要的两三个老师

avatar
C*U
9
我最近想出来一个dp的做法
感觉的比那个wiki上的解法要更自然一点

【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法?

avatar
C*2
10
送礼卡的话可以是$10一張送给孩子所有的老师们,应该也就是8个左右。或自己动手做
礼物,一视同仁。
avatar
c*t
11
求解,我想到的dp都是O(n^2)的

【在 C***U 的大作中提到】
: 我最近想出来一个dp的做法
: 感觉的比那个wiki上的解法要更自然一点

avatar
r*f
12
嗯,统统happy holidays,谁知道到底信什么不信什么

【在 A**n 的大作中提到】
: 犹太人的哈纳卡跟圣诞节时间差不多。反正holiday season送应该没错,
: 你提前一点不要赶在圣诞节那两天就好了,卡上写happy holidays
: 我们就送主要的两三个老师

avatar
C*U
13
我给你举个例子说一下我的想法,顺便版上的大牛们可以看看我的想法对不对,我经常
会想错问题
例子: 5 4 3 2 1 3 4
有一个lists里面的元素是array
1. 5进来,这时候lists是空的,所以我就把5放入到一个array,然后插入到lists里面
这时候lists就是
a) 5
2. 4进来,这时候我们用lists里面的array的最后一个数字来2分查找,因为现在lists
里面只有5,所以我们应该把4单独作为一个array放到lists里面,这时候lists就是
a)4
b)5
3. 3 2 1进来的时候,像前面一样,2分查找到自己的位置,lists变成
a) 1
b) 2
c) 3
d) 4
e) 5
4. 第二个3进来的时候,我们2分查找,会发现3应该放入所有d)前面的array里面。然
而当3放入以后我们没有必要全部保留前面的array,而是只要保留最长的那个,所以当
第二个3放入以后,lists就变成了
a) 1 3
b) 4
c) 5
5 当第二个4进来的时候,我们还是像前面查找,我们发现4应该放入a) b)里面,然后
我们只要保留最长的那个。所以当第二个4放进来以后,我们的lists就变成了
a) 1 3 4
b) 5
这个算法的时间复杂度要用到potential method,稍微有点复杂. potential function
是每一步lists里面array的个数. 空间是O(n),因为在每个时候,一个数字只出现在
lists里面一次.时间是O(nlogn),因为根据potential function,每一步用到O(logn)
的时间。
不知道这个算法和wiki上那个是不是一样.

【在 c********t 的大作中提到】
: 求解,我想到的dp都是O(n^2)的
avatar
i*t
14
可以在中国传统节日送。
这样更特殊,印响更深,
也顺便宣扬中国文化
avatar
c*t
15
我觉得行,而且挺好懂得,第5步你删掉数小于i的也该删去,2,3步都可以这样做,这样5,4,3,2,1做完只剩
a) 1
更简单,而且省空间。再看看有没有大牛指点。

lists

【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法,顺便版上的大牛们可以看看我的想法对不对,我经常
: 会想错问题
: 例子: 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来,这时候lists是空的,所以我就把5放入到一个array,然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来,这时候我们用lists里面的array的最后一个数字来2分查找,因为现在lists
: 里面只有5,所以我们应该把4单独作为一个array放到lists里面,这时候lists就是
: a)4

avatar
c*t
16
再想想,不对呀。如果1 4 2 3 ,你是什么步骤?

lists

【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法,顺便版上的大牛们可以看看我的想法对不对,我经常
: 会想错问题
: 例子: 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来,这时候lists是空的,所以我就把5放入到一个array,然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来,这时候我们用lists里面的array的最后一个数字来2分查找,因为现在lists
: 里面只有5,所以我们应该把4单独作为一个array放到lists里面,这时候lists就是
: a)4

avatar
C*U
17
恩。。。这个例子有问题
应该是原来的保留,然后在最长的后面增加那个数字

【在 c********t 的大作中提到】
: 再想想,不对呀。如果1 4 2 3 ,你是什么步骤?
:
: lists

avatar
c*t
18
俺证实了你的想法可行,而且直观,其实用二维数组即可,不用list.
wiki上的我怎么也实现不了

【在 C***U 的大作中提到】
: 恩。。。这个例子有问题
: 应该是原来的保留,然后在最长的后面增加那个数字

avatar
c*t
19
不用binary O(n^2) 可以输出结果数组。
用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法?
avatar
H*s
20
查看下面链接:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence

【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法?

avatar
C*U
22
我最近想出来一个dp的做法
感觉的比那个wiki上的解法要更自然一点

【在 c********t 的大作中提到】
: 不用binary O(n^2) 可以输出结果数组。
: 用了binary,我只会求出最大长度 O(nlogn),无法输出最终结果数组,谁见过解法?

avatar
c*t
23
求解,我想到的dp都是O(n^2)的

【在 C***U 的大作中提到】
: 我最近想出来一个dp的做法
: 感觉的比那个wiki上的解法要更自然一点

avatar
C*U
24
我给你举个例子说一下我的想法,顺便版上的大牛们可以看看我的想法对不对,我经常
会想错问题
例子: 5 4 3 2 1 3 4
有一个lists里面的元素是array
1. 5进来,这时候lists是空的,所以我就把5放入到一个array,然后插入到lists里面
这时候lists就是
a) 5
2. 4进来,这时候我们用lists里面的array的最后一个数字来2分查找,因为现在lists
里面只有5,所以我们应该把4单独作为一个array放到lists里面,这时候lists就是
a)4
b)5
3. 3 2 1进来的时候,像前面一样,2分查找到自己的位置,lists变成
a) 1
b) 2
c) 3
d) 4
e) 5
4. 第二个3进来的时候,我们2分查找,会发现3应该放入所有d)前面的array里面。然
而当3放入以后我们没有必要全部保留前面的array,而是只要保留最长的那个,所以当
第二个3放入以后,lists就变成了
a) 1 3
b) 4
c) 5
5 当第二个4进来的时候,我们还是像前面查找,我们发现4应该放入a) b)里面,然后
我们只要保留最长的那个。所以当第二个4放进来以后,我们的lists就变成了
a) 1 3 4
b) 5
这个算法的时间复杂度要用到potential method,稍微有点复杂. potential function
是每一步lists里面array的个数. 空间是O(n),因为在每个时候,一个数字只出现在
lists里面一次.时间是O(nlogn),因为根据potential function,每一步用到O(logn)
的时间。
不知道这个算法和wiki上那个是不是一样.

【在 c********t 的大作中提到】
: 求解,我想到的dp都是O(n^2)的
avatar
c*t
25
我觉得行,而且挺好懂得,第5步你删掉数小于i的也该删去,2,3步都可以这样做,这样5,4,3,2,1做完只剩
a) 1
更简单,而且省空间。再看看有没有大牛指点。

lists

【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法,顺便版上的大牛们可以看看我的想法对不对,我经常
: 会想错问题
: 例子: 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来,这时候lists是空的,所以我就把5放入到一个array,然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来,这时候我们用lists里面的array的最后一个数字来2分查找,因为现在lists
: 里面只有5,所以我们应该把4单独作为一个array放到lists里面,这时候lists就是
: a)4

avatar
c*t
26
再想想,不对呀。如果1 4 2 3 ,你是什么步骤?

lists

【在 C***U 的大作中提到】
: 我给你举个例子说一下我的想法,顺便版上的大牛们可以看看我的想法对不对,我经常
: 会想错问题
: 例子: 5 4 3 2 1 3 4
: 有一个lists里面的元素是array
: 1. 5进来,这时候lists是空的,所以我就把5放入到一个array,然后插入到lists里面
: 这时候lists就是
: a) 5
: 2. 4进来,这时候我们用lists里面的array的最后一个数字来2分查找,因为现在lists
: 里面只有5,所以我们应该把4单独作为一个array放到lists里面,这时候lists就是
: a)4

avatar
C*U
27
恩。。。这个例子有问题
应该是原来的保留,然后在最长的后面增加那个数字

【在 c********t 的大作中提到】
: 再想想,不对呀。如果1 4 2 3 ,你是什么步骤?
:
: lists

avatar
c*t
28
俺证实了你的想法可行,而且直观,其实用二维数组即可,不用list.
wiki上的我怎么也实现不了

【在 C***U 的大作中提到】
: 恩。。。这个例子有问题
: 应该是原来的保留,然后在最长的后面增加那个数字

avatar
l*a
32
1 2 3 4 5 6 7 9 3 8 11 4 5 6 4 19 7 1 7 17 12 16
测试了一下,
跑不出正确答案。
错误结果是st.size() = 7

【在 C***U 的大作中提到】
: 恩
: 这个很强
: set st;
: set::iterator it;
: st.clear();
: for(i=0; i: st.insert(array[i]);
: it=st.find(array[i]);
: it++;
: if(it!=st.end()) st.erase(it);

avatar
l*b
33
想输出那个序列得要有一个数组记录每个数值在数列中之前的那个值,所以要多开一个
数组记录这个信息吧.
每次用binary search push进去一个之后那个数之前的一个数就是这个. 写得太烂了,
有空重写一下.
class Solution {
private:
vector s;
vector pre;
int push(int k) {
if(s.empty()){
s.push_back(k);
return -1;
}
if(k >= s.back()){
s.push_back(k);
return s[s.size()-2];
}
int l = 0, r = s.size()-1, mid;
while(l < r)
(s[mid = (l+r)/2] > k) ? r = mid : l = mid+1;
s[r] = k;
return (r-1 >= 0) ? s[r-1] : -1;
}
public:
int max_inc_seq (int a[], int n) {
int i;
for(i = 0; i < n; ++i)
pre.push_back(push(a[i]));
cout << "longest increasing: " << s.size() << '\n';
int pt = s.back();
i = n - 1;
while(pt != -1) {
cout << pt << " ";
for(; a[i] != pt ; i-- );
pt = pre[i--];
}
cout << '\n';
s.clear();
pre.clear();
return 0;
}
};
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。