有人注意到Citi Prestige卡的做工非常烂吗？ - 未名空间MITBBS历史存档

有人注意到Citi Prestige卡的做工非常烂吗？# Money - 海外理财

S*s2017-03-15 07:03

1 楼

是Facebook发的准备材料上的题目：
An atm can only dispense values of $1, $5, $20, and $50. Return the number
of unique ways that a $ amount of X can be tendered.
($1, $5) is distinct from ($5, $1)
Input: 4 Output: 1
Input: 6 Output: 3
Input: 100 Output: 954515231698
按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
private static Integer atm(Integer x) {
if (x <= 0)
return x == 0 ? 1 : 0;
return atm(x - 1) + atm(x - 5) + atm(x - 20) + atm(x - 100);
}

m*a2017-03-15 07:03

2 楼

其他的citi卡都没这个问题，第一次拿到那张卡时候，有些地方仿佛被烫过的样子，边
缘完全没有光洁，让我仿佛山寨盗用。当时我还安慰自己，也许是那个做工lot比较差
。今天拿到了一张替换卡，结果做工还是一样的烂。而且更甚。那个背面烫伤的号码，
字迹边缘不整齐，仿佛你用手指扣就能擦掉的感觉。Citi难道没人监控卡的质量吗？不
求Chase那种金属卡，但至少弄到和其他citi卡一样的质量啊。

D*a2017-03-15 07:03

3 楼

use an array to cache the result of atm(x) so you don't overflow the stack.

【在 S********s 的大作中提到】

: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)

u*n2017-03-15 07:03

4 楼

AMEX给以前的塑料卡换金属卡嘛？

h*t2017-03-15 07:03

5 楼

Leetcode climbing stairs 的变形题，用DP. Return long.

t*u2017-03-15 07:03

6 楼

coask

【在 u***n 的大作中提到】

: AMEX给以前的塑料卡换金属卡嘛？

I*g2017-03-15 07:03

7 楼

我输入1000的时候，都没有溢出
结果是
3809781405817283560133557648078873264200227888228196162666466870535154840891
97209663212281002759381072062453715265566609468

【在 S********s 的大作中提到】

: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)

y*i2017-03-15 07:03

8 楼

???
ours look perfectly fine to me

【在 m*****a 的大作中提到】

: 其他的citi卡都没这个问题，第一次拿到那张卡时候，有些地方仿佛被烫过的样子，边
: 缘完全没有光洁，让我仿佛山寨盗用。当时我还安慰自己，也许是那个做工lot比较差
: 。今天拿到了一张替换卡，结果做工还是一样的烂。而且更甚。那个背面烫伤的号码，
: 字迹边缘不整齐，仿佛你用手指扣就能擦掉的感觉。Citi难道没人监控卡的质量吗？不
: 求Chase那种金属卡，但至少弄到和其他citi卡一样的质量啊。

m*32017-03-15 07:03

9 楼

牛叉！

m*a2017-03-15 07:03

10 楼

100% sure it is poorer.
I post this because I am and have been so so "impressed" by the card quality
. No other card can compete, period. This new card actually slightly
warpping (if you press one edge, you can get about 2mm gap from the opposite
edge of the card to the desk). I attach a picture of what the printed
number looks like. Remember I just get it. It is brand new, not worn out for
one year in my pocket.

【在 y****i 的大作中提到】

: ???
: ours look perfectly fine to me

z*m2017-03-15 07:03

11 楼

用dp，把前面的结果存起来
coin change problem的变形
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha

【在 S********s 的大作中提到】

: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)

f*e2017-03-15 07:03

12 楼

我的prestige正面印刷的已经快摩掉了。

【在 m*****a 的大作中提到】

: 其他的citi卡都没这个问题，第一次拿到那张卡时候，有些地方仿佛被烫过的样子，边
: 缘完全没有光洁，让我仿佛山寨盗用。当时我还安慰自己，也许是那个做工lot比较差
: 。今天拿到了一张替换卡，结果做工还是一样的烂。而且更甚。那个背面烫伤的号码，
: 字迹边缘不整齐，仿佛你用手指扣就能擦掉的感觉。Citi难道没人监控卡的质量吗？不
: 求Chase那种金属卡，但至少弄到和其他citi卡一样的质量啊。

c*m2017-03-15 07:03

13 楼

是dp+长整数相加吧？

v*n2017-03-15 07:03

14 楼

确实是，而且塑料也起皮了。完全不如之前的做工好

t*e2017-03-15 07:03

15 楼

楼主的题目是前后次序有影响，在此基础上该怎么改？

【在 z***m 的大作中提到】

: 用dp，把前面的结果存起来
: coin change problem的变形
: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha

p*a2017-03-15 07:03

16 楼

下个月登陆Amex官网申请换卡即可

【在 t*********u 的大作中提到】

: coask

z*m2017-03-15 07:03

17 楼

对每个case，直接乘以 n!,.
比如算出的C[1,5]为x，直接乘以2。如果是C[1 2 5]就乘以3！

【在 t*******e 的大作中提到】

:
: 楼主的题目是前后次序有影响，在此基础上该怎么改？

t*u2017-03-15 07:03

18 楼

关键是不知道是不是换的是金属卡

【在 p*******a 的大作中提到】

: 下个月登陆Amex官网申请换卡即可

t*e2017-03-15 07:03

19 楼

不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
代码你是怎么做的么

【在 z***m 的大作中提到】

: 对每个case，直接乘以 n!,.
: 比如算出的C[1,5]为x，直接乘以2。如果是C[1 2 5]就乘以3！

i*r2017-03-15 07:03

20 楼

Amex哪些卡可以换金属卡？

【在 u***n 的大作中提到】

: AMEX给以前的塑料卡换金属卡嘛？

y*82017-03-15 07:03

21 楼

请问准备材料是从哪搞到的

h*s2017-03-15 07:03

22 楼

Platinum，年费550刀那个。

【在 i********r 的大作中提到】

: Amex哪些卡可以换金属卡？

w*i2017-03-15 07:03

23 楼

感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个SetLong>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
列数目，然后在set里求和。
另外dp表可以用长度为50的滚动数组，减少内存开销。

p*t2017-03-15 07:03

24 楼

已知组合数求排列数不需要具体列出来所有的排列吧。。。

【在 w*******i 的大作中提到】

: 感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个Set: Long>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
: 列数目，然后在set里求和。
: 另外dp表可以用长度为50的滚动数组，减少内存开销。

z*m2017-03-15 07:03

25 楼

找unique的元素个数，设为n，然后乘以n！

【在 t*******e 的大作中提到】

:
: 不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
: 代码你是怎么做的么

y*h2017-03-15 07:03

26 楼

这样可以不可以？
public long tellMoneyCombinations(int money) {
long[] f = new long[money+1];
f[0] = f[1] = 1;
for(int i=2; i<=money; i++) {
f[i] = f[i-1];
if(i>=5) f[i]+=f[i-5];
if(i>=20) f[i]+=f[i-20];
if(i>=50) f[i]+=f[i-50];
}
return f[money];
}

s*z2017-03-15 07:03

27 楼

动态规划。
问下楼主，我怎么没看到有准备材料？就是HR邮件里面那一堆么？

s*z2017-03-15 07:03

28 楼

这样不可以。有重复的

【在 y*****h 的大作中提到】

: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }

t*a2017-03-15 07:03

29 楼

这个是对的

【在 y*****h 的大作中提到】

: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }

t*a2017-03-15 07:03

30 楼

题目就是要有重复的。

【在 s*******z 的大作中提到】

: 这样不可以。有重复的

x*92017-03-15 07:03

31 楼

一般情况下，在OJ上，这种DP题都是让你MOD一个大质数的。
所以不用太担心溢出。
gl, hf

S*s2017-03-15 07:03

32 楼

是Facebook发的准备材料上的题目：
An atm can only dispense values of $1, $5, $20, and $50. Return the number
of unique ways that a $ amount of X can be tendered.
($1, $5) is distinct from ($5, $1)
Input: 4 Output: 1
Input: 6 Output: 3
Input: 100 Output: 954515231698
按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
private static Integer atm(Integer x) {
if (x <= 0)
return x == 0 ? 1 : 0;
return atm(x - 1) + atm(x - 5) + atm(x - 20) + atm(x - 100);
}

D*a2017-03-15 07:03

33 楼

use an array to cache the result of atm(x) so you don't overflow the stack.

【在 S********s 的大作中提到】

: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)

h*t2017-03-15 07:03

34 楼

Leetcode climbing stairs 的变形题，用DP. Return long.

I*g2017-03-15 07:03

35 楼

我输入1000的时候，都没有溢出
结果是
3809781405817283560133557648078873264200227888228196162666466870535154840891
97209663212281002759381072062453715265566609468

【在 S********s 的大作中提到】

: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)

m*32017-03-15 07:03

36 楼

牛叉！

z*m2017-03-15 07:03

37 楼

用dp，把前面的结果存起来
coin change problem的变形
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha

【在 S********s 的大作中提到】

: 是Facebook发的准备材料上的题目：
: An atm can only dispense values of $1, $5, $20, and $50. Return the number
: of unique ways that a $ amount of X can be tendered.
: ($1, $5) is distinct from ($5, $1)
: Input: 4 Output: 1
: Input: 6 Output: 3
: Input: 100 Output: 954515231698
: 按照提示的解法，输入100的时候就溢出了。请问有什么办法可以避免？
: private static Integer atm(Integer x) {
: if (x <= 0)

c*m2017-03-15 07:03

38 楼

是dp+长整数相加吧？

t*e2017-03-15 07:03

39 楼

楼主的题目是前后次序有影响，在此基础上该怎么改？

【在 z***m 的大作中提到】

: 用dp，把前面的结果存起来
: coin change problem的变形
: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-cha

z*m2017-03-15 07:03

40 楼

对每个case，直接乘以 n!,.
比如算出的C[1,5]为x，直接乘以2。如果是C[1 2 5]就乘以3！

【在 t*******e 的大作中提到】

:
: 楼主的题目是前后次序有影响，在此基础上该怎么改？

t*e2017-03-15 07:03

41 楼

不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
代码你是怎么做的么

【在 z***m 的大作中提到】

: 对每个case，直接乘以 n!,.
: 比如算出的C[1,5]为x，直接乘以2。如果是C[1 2 5]就乘以3！

y*82017-03-15 07:03

42 楼

请问准备材料是从哪搞到的

w*i2017-03-15 07:03

43 楼

感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个SetLong>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
列数目，然后在set里求和。
另外dp表可以用长度为50的滚动数组，减少内存开销。

p*t2017-03-15 07:03

44 楼

已知组合数求排列数不需要具体列出来所有的排列吧。。。

【在 w*******i 的大作中提到】

: 感觉dp表里只存长整数不行啊。要能区别出顺序，dp表里的每一项都存一个Set: Long>>，其中list长度为4，表示4种钱币的出现次数，这样可以由一个组合推出不同排
: 列数目，然后在set里求和。
: 另外dp表可以用长度为50的滚动数组，减少内存开销。

z*m2017-03-15 07:03

45 楼

找unique的元素个数，设为n，然后乘以n！

【在 t*******e 的大作中提到】

:
: 不能吧，比如[1,1,1,1,1,1]组成6只有1中，但[1,5], [5,1]组成6是两种。你能分享下
: 代码你是怎么做的么

y*h2017-03-15 07:03

46 楼

这样可以不可以？
public long tellMoneyCombinations(int money) {
long[] f = new long[money+1];
f[0] = f[1] = 1;
for(int i=2; i<=money; i++) {
f[i] = f[i-1];
if(i>=5) f[i]+=f[i-5];
if(i>=20) f[i]+=f[i-20];
if(i>=50) f[i]+=f[i-50];
}
return f[money];
}

s*z2017-03-15 07:03

47 楼

动态规划。
问下楼主，我怎么没看到有准备材料？就是HR邮件里面那一堆么？

s*z2017-03-15 07:03

48 楼

这样不可以。有重复的

【在 y*****h 的大作中提到】

: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }

t*a2017-03-15 07:03

49 楼

这个是对的

【在 y*****h 的大作中提到】

: 这样可以不可以？
: public long tellMoneyCombinations(int money) {
: long[] f = new long[money+1];
: f[0] = f[1] = 1;
: for(int i=2; i<=money; i++) {
: f[i] = f[i-1];
: if(i>=5) f[i]+=f[i-5];
: if(i>=20) f[i]+=f[i-20];
: if(i>=50) f[i]+=f[i-50];
: }

t*a2017-03-15 07:03

50 楼

题目就是要有重复的。

【在 s*******z 的大作中提到】

: 这样不可以。有重复的

x*92017-03-15 07:03

51 楼

一般情况下，在OJ上，这种DP题都是让你MOD一个大质数的。
所以不用太担心溢出。
gl, hf

l*42017-03-15 07:03

52 楼

public static long atm(int x) {
long[] arr = new long[x+1];
Arrays.fill(arr, -1);
return helper(arr, x);
}
private static long helper(long[] arr, int x) {
if (x < 0) {
return 0;
}
if (x == 0) {
return 1;
}
if (arr[x] < 0) {
arr[x] = helper(arr, x-1) + helper(arr, x-5) + helper(arr, x-20)
+ helper(arr, x-50);
}
return arr[x];
}

s*l2017-03-15 07:03

53 楼

我也好奇
哪里给的或者找到的facebook复习材料啊？