logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
很讨厌做greedy的题
avatar
p*2
2 楼
感觉比DP难一个档次
DP还是比较容易的，毕竟属于brute force，miss不了啥东西。greedy就不一样了，很
难证明正确性，自己做了也不清楚到底对不对。想证明一下，发现特别费脑子。DP想起
来要清晰很多。看来做greedy的题还需要加强呀。
avatar
k*r
3 楼
土土的问,给的mileage只能在ba用么?

【在 k****n 的大作中提到】
: 【 以下文字转载自 Money 讨论区 】
: 发信人: kaplan (被黑了...), 信区: Money
: 标 题: British Airways 100K Mile VISA Deal Alive Again
: 发信站: BBS 未名空间站 (Wed Feb 17 14:40:43 2010, 美东)
: https://applynow.chase.com/FlexAppWeb/renderApp.do?SPID=CQ7P&AFFID=&CELL=
: 6R9F&CID=&CLICK=&PROMO=DF01&
avatar
h*6
4 楼
贪婪算法的问题，看了答案后的反应是：啊？就这么简单，对不对啊？
avatar
P*a
5 楼
貌似可以定AA的

【在 k****r 的大作中提到】
: 土土的问,给的mileage只能在ba用么?
avatar
p*2
6 楼

大牛说的太形象了。能不能给点建议？

【在 h**6 的大作中提到】
: 贪婪算法的问题，看了答案后的反应是：啊？就这么简单，对不对啊？
avatar
e*t
7 楼
国泰的也可以

【在 P****a 的大作中提到】
: 貌似可以定AA的
avatar
s*r
8 楼
是的...刚开始学感觉 greedy 简单，dp 难搞
因为一开始做的 greedy 确实是简单题，dp 入门难一点
后来做多 dp 发现 dp 又容易写 准确率又高
而 greedy 就难搞了 牵扯到数学证明
其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
必深入
avatar
a*e
9 楼
啥是国泰

【在 e****t 的大作中提到】
: 国泰的也可以
avatar
p*2
10 楼

一看就是大牛。先膜拜一下。青蛙跳这个是哪里的竞赛题，貌似F的一道面试题。M<=
100是怎么回事？长度不是10^9这么长吗？能不能详细说说。

【在 s*****r 的大作中提到】
: 是的...刚开始学感觉 greedy 简单，dp 难搞
: 因为一开始做的 greedy 确实是简单题，dp 入门难一点
: 后来做多 dp 发现 dp 又容易写 准确率又高
: 而 greedy 就难搞了 牵扯到数学证明
: 其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
: 比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
: 100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
: 再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
: 还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
: 必深入
avatar
a9
11 楼
君安

【在 a******e 的大作中提到】
: 啥是国泰
avatar
s*r
12 楼
啊 我错了...
这个是 noip 2005 过河
桥每个位置都可以踩 而青蛙不想踩到石子 石子有 1 <= M <= 100 个 青蛙希望从头跳
过尾踩的最少
avatar
k*r
13 楼
good to know. 申请的时候Executive Club Account Number是啥?

【在 P****a 的大作中提到】
: 貌似可以定AA的
avatar
p*2
14 楼

多谢。看来有竞赛经验的人面F有很大的优势。

【在 s*****r 的大作中提到】
: 啊 我错了...
: 这个是 noip 2005 过河
: 桥每个位置都可以踩 而青蛙不想踩到石子 石子有 1 <= M <= 100 个 青蛙希望从头跳
: 过尾踩的最少
avatar
e*t
15 楼
cathay pacific
香港的航空公司

【在 a******e 的大作中提到】
: 啥是国泰
avatar
w*a
16 楼
可以用DP但是greedy更简单，jump game就是个好例子啊。哈哈
avatar
k*r
17 楼
Executive Club Account Number是啥?

【在 e****t 的大作中提到】
: cathay pacific
: 香港的航空公司
avatar
p*2
18 楼

jump game是greedy的吗？

【在 w****a 的大作中提到】
: 可以用DP但是greedy更简单，jump game就是个好例子啊。哈哈
avatar
k*n
19 楼
这个比aa的贵一倍啊

【在 e****t 的大作中提到】
: cathay pacific
: 香港的航空公司
avatar
c*t
20 楼
请问哪里有test cases？多谢！

【在 s*****r 的大作中提到】
: 啊 我错了...
: 这个是 noip 2005 过河
: 桥每个位置都可以踩 而青蛙不想踩到石子 石子有 1 <= M <= 100 个 青蛙希望从头跳
: 过尾踩的最少
avatar
d*e
21 楼
没有就空着，卡批准了会给你一个

【在 k****r 的大作中提到】
: Executive Club Account Number是啥?
avatar
c*t
22 楼
写了一个，大侠看看对不对，有没有什么可以优化的。
public int frogJump(int bridgeLength, int s, int t, int m,
HashSet stones) {
int[] dp = new int[bridgeLength + 1];
for (int i = s; i <= t; i++) {
if (stones.contains(i))
dp[i] = 1;
}
for (int i = t + 1; i <= bridgeLength; i++) {
int prev_stones = Integer.MAX_VALUE;
for (int j = s; j <= t; j++) {
prev_stones = Math.min(prev_stones, dp[i - j]);
}
dp[i] = prev_stones;
if (stones.contains(i))
dp[i]++;
}
return dp[bridgeLength];
}

【在 s*****r 的大作中提到】
: 是的...刚开始学感觉 greedy 简单，dp 难搞
: 因为一开始做的 greedy 确实是简单题，dp 入门难一点
: 后来做多 dp 发现 dp 又容易写 准确率又高
: 而 greedy 就难搞了 牵扯到数学证明
: 其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
: 比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
: 100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
: 再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
: 还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
: 必深入
avatar
R*g
23 楼
这个有人instant decline吗？
avatar
c*t
24 楼
没人理，发现原题桥长100+，lz给的10^9，自己优化了一下空间。 BTW, 小青蛙肯定累
死在桥中间了。
public int frogJump2(int bridgeLength, int s, int t, int m,
HashSet stones) {
int[] dp = new int[t];
for (int i = s; i <= t; i++) {
if (stones.contains(i))
dp[i-1] = 1;
}
for (int i = t; i < bridgeLength; i++) {
int index = i%t;
int prev_stones = Integer.MAX_VALUE;
for (int j = s; j <= t; j++) {
prev_stones = Math.min(prev_stones, dp[j-1]);
}
dp[index] = prev_stones;
if (stones.contains(i))
dp[index]++;
}
return dp[(bridgeLength-1)%t];
}

【在 c********t 的大作中提到】
: 写了一个，大侠看看对不对，有没有什么可以优化的。
: public int frogJump(int bridgeLength, int s, int t, int m,
: HashSet stones) {
: int[] dp = new int[bridgeLength + 1];
: for (int i = s; i <= t; i++) {
: if (stones.contains(i))
: dp[i] = 1;
: }
: for (int i = t + 1; i <= bridgeLength; i++) {
: int prev_stones = Integer.MAX_VALUE;
avatar
P*r
25 楼
申了。。RP爆发一下通过吧
avatar
s*r
26 楼
原题桥长就是 10^9 只是很多网页上显示成了 109
noip 是要求 1s 内出解的 大概 10^7 的算法才行 loop 到 10^9 是肯定超时的
其实题目暗示挺明显了 这么长的桥才这么少石子 通过这个条件优化时间的

【在 c********t 的大作中提到】
: 没人理，发现原题桥长100+，lz给的10^9，自己优化了一下空间。 BTW, 小青蛙肯定累
: 死在桥中间了。
: public int frogJump2(int bridgeLength, int s, int t, int m,
: HashSet stones) {
: int[] dp = new int[t];
: for (int i = s; i <= t; i++) {
: if (stones.contains(i))
: dp[i-1] = 1;
: }
: for (int i = t; i < bridgeLength; i++) {
avatar
k*r
27 楼
不妙啊,以前申卡都是立马approved,怎么这个要等15天:(((

【在 P******r 的大作中提到】
: 申了。。RP爆发一下通过吧
avatar
c*t
28 楼
好像明白了，是直接判断有多少个连续长度超过T的石子路段？

【在 s*****r 的大作中提到】
: 原题桥长就是 10^9 只是很多网页上显示成了 109
: noip 是要求 1s 内出解的 大概 10^7 的算法才行 loop 到 10^9 是肯定超时的
: 其实题目暗示挺明显了 这么长的桥才这么少石子 通过这个条件优化时间的
avatar
k*n
29 楼
好像都这样

【在 k****r 的大作中提到】
: 不妙啊,以前申卡都是立马approved,怎么这个要等15天:(((
avatar
r*o
30 楼
这个100K Mile可以换个什么机票??
avatar
c*s
31 楼
possible 2 us-china roundtrip on aa

【在 r****o 的大作中提到】
: 这个100K Mile可以换个什么机票??
avatar
k*n
32 楼
两张上海-美国的往返机票
哈哈

【在 r****o 的大作中提到】
: 这个100K Mile可以换个什么机票??
avatar
t*e
33 楼
从美国哪个地方飞呢？

【在 k****n 的大作中提到】
: 两张上海-美国的往返机票
: 哈哈
avatar
k*r
34 楼
veli nice,赶紧再给我ld申请一张

【在 k****n 的大作中提到】
: 两张上海-美国的往返机票
: 哈哈
avatar
h*a
35 楼
这个miles多久过期的？

【在 k****n 的大作中提到】
: 两张上海-美国的往返机票
: 哈哈
avatar
AE
36 楼
小地方直接在BA,选partner就能找着,如果大城市被BA cover了，
可以去AA找好了，打电话BA订。

从美国哪个地方飞呢？

【在 t*****e 的大作中提到】
: 从美国哪个地方飞呢？
avatar
r*o
37 楼

我靠 疯了,立马给全家申请了.

【在 k****n 的大作中提到】
: 两张上海-美国的往返机票
: 哈哈
avatar
T*g
38 楼
刚定了，AA从芝加哥到上海

【在 t*****e 的大作中提到】
: 从美国哪个地方飞呢？
avatar
AE
39 楼
能给儿子也申请一张吗？有SSN啊， hoho

我靠 疯了,立马给全家申请了.

【在 r****o 的大作中提到】
:
: 我靠 疯了,立马给全家申请了.
avatar
t*e
40 楼
BA的电话超级难打，我试过，skype了30分钟才接通

【在 AE 的大作中提到】
: 小地方直接在BA,选partner就能找着,如果大城市被BA cover了，
: 可以去AA找好了，打电话BA订。
:
: 从美国哪个地方飞呢？
avatar
t*e
41 楼
这边肯定是要从AA芝加哥转机啊
单程有么？

【在 T********g 的大作中提到】
: 刚定了，AA从芝加哥到上海
avatar
k*r
42 楼
有问题啊,没法留备份,无论pdf还是打印机都打不出左边100k miles那些信息

【在 t*****e 的大作中提到】
: 这边肯定是要从AA芝加哥转机啊
: 单程有么？
avatar
m*r
43 楼
截屏

【在 k****r 的大作中提到】
: 有问题啊,没法留备份,无论pdf还是打印机都打不出左边100k miles那些信息
avatar
l*i
44 楼
print screen可以吗？

【在 k****r 的大作中提到】
: 有问题啊,没法留备份,无论pdf还是打印机都打不出左边100k miles那些信息
avatar
T*g
45 楼
中飞美，美飞中单程都可以

【在 t*****e 的大作中提到】
: 这边肯定是要从AA芝加哥转机啊
: 单程有么？
avatar
l*i
46 楼
不过这次不想上两次那样正式。。很奇怪。。
avatar
i*o
47 楼
就是说如果BA cover的城市，如果AA有航班，可以定AA的是吗？
怎么我记得是BA cover的城市，必须选择BA的航班？

【在 AE 的大作中提到】
: 小地方直接在BA,选partner就能找着,如果大城市被BA cover了，
: 可以去AA找好了，打电话BA订。
:
: 从美国哪个地方飞呢？
avatar
t*e
48 楼
要多少miles换呢？也是5w mile？

【在 T********g 的大作中提到】
: 中飞美，美飞中单程都可以
avatar
k*r
49 楼
co-ask,mileage能转让么? 能用儿子的帐号定票么?

【在 AE 的大作中提到】
: 能给儿子也申请一张吗？有SSN啊， hoho
:
: 我靠 疯了,立马给全家申请了.
avatar
m*r
50 楼
想钱想封了吧？
你儿子有信用记录吗？
还想申请信用卡？

【在 k****r 的大作中提到】
: co-ask,mileage能转让么? 能用儿子的帐号定票么?
avatar
t*e
51 楼
这个可以用来卖的，给别人订票
用你儿子的帐号可以定啊，问题是信用卡公司给开么？

【在 k****r 的大作中提到】
: co-ask,mileage能转让么? 能用儿子的帐号定票么?
avatar
c*e
52 楼
她想给孩子买票。
应该可以

【在 m*r 的大作中提到】
: 想钱想封了吧？
: 你儿子有信用记录吗？
: 还想申请信用卡？
avatar
m*r
53 楼
你是啥眼神?

【在 c********e 的大作中提到】
: 她想给孩子买票。
: 应该可以
avatar
t*e
54 楼
她是想用儿子的帐号订票，，，不是给儿子定票

【在 c********e 的大作中提到】
: 她想给孩子买票。
: 应该可以
avatar
k*r
55 楼
哇哈哈哈,这不想从小给他创造记录么,他也要买机票啊,很make sense啊, kakaka

【在 m*r 的大作中提到】
: 想钱想封了吧？
: 你儿子有信用记录吗？
: 还想申请信用卡？
avatar
c*e
56 楼
嗯，没想到她真得疯了。神医就是敢想。

【在 m*r 的大作中提到】
: 你是啥眼神?
avatar
a9
57 楼
不是成人才可以申请信用卡来着？

【在 k****r 的大作中提到】
: 哇哈哈哈,这不想从小给他创造记录么,他也要买机票啊,很make sense啊, kakaka
avatar
m*r
58 楼
信用记录都是gradually 建立的
为啥都开始申请学生开？

【在 k****r 的大作中提到】
: 哇哈哈哈,这不想从小给他创造记录么,他也要买机票啊,很make sense啊, kakaka
avatar
s*r
59 楼
有75刀年费？
avatar
t*o
60 楼
nod

【在 s***r 的大作中提到】
: 有75刀年费？
avatar
k*r
61 楼
啊,不会吧,没看到,亏大了

【在 t**o 的大作中提到】
: nod
avatar
T*g
62 楼
2.5w 加38刀税费

【在 t*****e 的大作中提到】
: 要多少miles换呢？也是5w mile？
avatar
m*n
63 楼
亚洲最好的航空公司, 你这个土妞

【在 a******e 的大作中提到】
: 啥是国泰
avatar
t*e
64 楼
thx

【在 T********g 的大作中提到】
: 2.5w 加38刀税费
avatar
s*r
65 楼
一般年费啥时候交？一开始还是一年最后交？
可以前3个月搞够点数后 马上兑换机票 然后CANCEL卡么？呵呵

【在 t**o 的大作中提到】
: nod
avatar
c*s
66 楼
unavailable
avatar
k*y
67 楼
这么快就死了？？？？

【在 c*********s 的大作中提到】
: unavailable
avatar
d*e
68 楼
开卡就交

【在 s***r 的大作中提到】
: 一般年费啥时候交？一开始还是一年最后交？
: 可以前3个月搞够点数后 马上兑换机票 然后CANCEL卡么？呵呵
avatar
AE
69 楼
记得可以先给儿子申请一张附卡，等有了信用记录就可以申请卡了

哇哈哈哈,这不想从小给他创造记录么,他也要买机票啊,很make sense啊, kakaka

【在 k****r 的大作中提到】
: 哇哈哈哈,这不想从小给他创造记录么,他也要买机票啊,很make sense啊, kakaka
avatar
k*r
70 楼
太黑了吧,送你两张机票,至少给人家交一年年费意思意思吧

【在 s***r 的大作中提到】
: 一般年费啥时候交？一开始还是一年最后交？
: 可以前3个月搞够点数后 马上兑换机票 然后CANCEL卡么？呵呵
avatar
t*o
71 楼
方法可行 但是损rp啊

【在 k****r 的大作中提到】
: 太黑了吧,送你两张机票,至少给人家交一年年费意思意思吧
avatar
k*r
72 楼
真的假的? 附卡不用给ssn,哪来的信用记录?

【在 AE 的大作中提到】
: 记得可以先给儿子申请一张附卡，等有了信用记录就可以申请卡了
:
: 哇哈哈哈,这不想从小给他创造记录么,他也要买机票啊,很make sense啊, kakaka
avatar
m*n
73 楼
卡妈 你实在太外行了,

【在 k****r 的大作中提到】
: 真的假的? 附卡不用给ssn,哪来的信用记录?
avatar
l*l
74 楼
娃不是一出生就有ssn了吗？
avatar
k*r
75 楼
第一个儿子,我怎么知道那些东西,555555555

【在 m******n 的大作中提到】
: 卡妈 你实在太外行了,
avatar
t*u
76 楼
joint的 附卡 可以 赞记录

【在 k****r 的大作中提到】
: 真的假的? 附卡不用给ssn,哪来的信用记录?
avatar
T*g
77 楼
不要唧唧歪歪了，没有的就申请一张，自用怎么也能省快两千刀了
avatar
j*i
78 楼
从BA网站上,我看到USA-China
Either 120000* BA MilesGreen tick
or from 60000* BA Miles + USD640

【在 k****n 的大作中提到】
: 两张上海-美国的往返机票
: 哈哈
avatar
k*r
79 楼
啊,哦. 不过难道大家已经都给婴儿们拿附卡攒记录了? 我土了,55555

【在 t*********u 的大作中提到】
: joint的 附卡 可以 赞记录
avatar
k*r
80 楼
sorry,我不该把贴子顶上来的,对不住了

【在 k******y 的大作中提到】
: 这么快就死了？？？？
avatar
AE
81 楼

从BA网站上,我看到USA-you need to find AA or jpl, if BA covers, no partner
allowed in BA.com. you
need to call.
China
Either 120000* BA MilesGreen tick
or from 60000* BA Miles + USD640

【在 j***i 的大作中提到】
: 从BA网站上,我看到USA-China
: Either 120000* BA MilesGreen tick
: or from 60000* BA Miles + USD640
avatar
j*i
82 楼
谢谢。这就是说不能直接到AA.com 上用这个mileage, right? 这末说同样的mileage,
AA可以换两张，BA只能换一张往返。

【在 AE 的大作中提到】
:
: 从BA网站上,我看到USA-you need to find AA or jpl, if BA covers, no partner
: allowed in BA.com. you
: need to call.
: China
: Either 120000* BA MilesGreen tick
: or from 60000* BA Miles + USD640
avatar
b*t
83 楼
AA only needs 50K for a roundtrip from/to China through BA.com.

谢谢。这就是说不能直接到AA.com 上用这个mileage, right? 这末说同样的mileage,
AA可以换两张，BA只能换一张往返。

【在 j***i 的大作中提到】
: 谢谢。这就是说不能直接到AA.com 上用这个mileage, right? 这末说同样的mileage,
: AA可以换两张，BA只能换一张往返。
avatar
l*i
84 楼
shit missed
avatar
e*i
85 楼
很好,刚拿到那100K,上次半的.
avatar
W*y
86 楼
Missed too. Already have 3 Chase cards, thinking about closing one to
accommodate the BA card if it becomes alive again.

【在 l******i 的大作中提到】
: shit missed
avatar
x*u
87 楼
oos:(
avatar
t*n
88 楼
我也想申请一张，可是这个链接好像不work 了，
你们可以吗？

SPID=CQ7P&AFFID=&CELL=
avatar
t*e
89 楼
dead

【在 t**********n 的大作中提到】
: 我也想申请一张，可是这个链接好像不work 了，
: 你们可以吗？
:
: SPID=CQ7P&AFFID=&CELL=
avatar
t*b
90 楼
dead?
avatar
t*e
91 楼
昨天贴出来没多久就dead了

【在 t****b 的大作中提到】
: dead?
相关阅读
平时做项目干工作都是用python，面试用java可以吗？Career path求建议：芯片公司vs网络产品公司内推，洛杉矶大公司senior java software engineer , lead java developerF, G, T 等公司面试心得有没做cfd的?提供fb内推亚麻股价大跌，微软史无前例裁员。西雅图日子不好过 (转载)老话题: 硅谷 120K vs 西雅图 105K美国公司如何与老板，老板的老板相处都说f家累，到底有多累现在还有考ood的么Onsite面试没怎么问技术问题，大部分是行为问题谁知道ICC怎么运作的？求问relocation上税问道G家的题请教个面试题， tree和hashmap的区别我这状况在版上算top 5%吗关于海外面fb的问题面试中遇到不会的题咋办这下热闹啦 Sinaapp.com域名没续费
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。