UA的信用卡回国飞机第二件行李没有免费吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

UA的信用卡回国飞机第二件行李没有免费吗？

UA的信用卡回国飞机第二件行李没有免费吗？# Money - 海外理财

c*r2014-11-09 08:11

1 楼

数组只有1-10000，然后size是10001，怎么找到重复的那个
ONSITE题目，让用尽可能多的方法。我能想到的方法是sum之后做减法， Hashtable,
sorting完扫一边，或者boolean数组存。
当时二逼用了swap的算法不停swap，结果最后自己没弄出来。
想问下这题有什么比较好的解法啊？

a*12014-11-09 08:11

2 楼

刚从国内回来，本来以为有ua的信用卡可以多一件免费行李的。（用ua信用卡买的机票
）结果被告知不行，说第二件行李免费只针对美国国内的。不知道是不是这样？

j*62014-11-09 08:11

3 楼

记得有一个XOR的方法

H*V2014-11-09 08:11

4 楼

totally wrong

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

: 刚从国内回来，本来以为有ua的信用卡可以多一件免费行李的。（用ua信用卡买的机票
: ）结果被告知不行，说第二件行李免费只针对美国国内的。不知道是不是这样？

s*r2014-11-09 08:11

5 楼

O(n)
int findDup(int []a,int n){
long ret=0;
for(int i=0;iret+=a[i]-i;
}
return ret;
}

w*x2014-11-09 08:11

6 楼

应该是美国国内第一件免费吧

c*a2014-11-09 08:11

7 楼

sum后减应该最好了吧

h*s2014-11-09 08:11

8 楼

信用卡给的是first checked bag free。
只有美国国内飞才有意义，因为国际的话第一个本来就免费。

刚从国内回来，本来以为有ua的信用卡可以多一件免费行李的。（用ua信用卡买的机票
）结果被告知不行，说第二件行李免费只针对美国国内的。不知道是不是这样？

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

f*t2014-11-09 08:11

9 楼

最优解：
int findDup(int[] A) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= A[i];
ans ^= i;
}
return ans;
}

j*82014-11-09 08:11

10 楼

为啥我用我UA的卡订了3张国内的票，一起飞的，结果第一件也不免费？而且登记group
才是3。。

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

: 信用卡给的是first checked bag free。
: 只有美国国内飞才有意义，因为国际的话第一个本来就免费。
:
: 刚从国内回来，本来以为有ua的信用卡可以多一件免费行李的。（用ua信用卡买的机票
: ）结果被告知不行，说第二件行李免费只针对美国国内的。不知道是不是这样？

c*r2014-11-09 08:11

11 楼

O(n). 一个小bug, i<=n
int findDup(int []a,int n){
long ret=0;
for(int i=0;iret+=a[i]-i;
}
return ret;
}

h*s2014-11-09 08:11

12 楼

我最近订的机票也这样，正奇怪呢。

为啥我用我UA的卡订了3张国内的票，一起飞的，结果第一件也不免费？而且登记group
才是3。。

【在 j*****8 的大作中提到】

: 为啥我用我UA的卡订了3张国内的票，一起飞的，结果第一件也不免费？而且登记group
: 才是3。。

G*A2014-11-09 08:11

13 楼

这个小trick不错

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

: O(n)
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }

j*82014-11-09 08:11

14 楼

刚打了客服，让不要在网上付check fee，去机场托运时把卡给他们看一下就行了。。

group

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

: 我最近订的机票也这样，正奇怪呢。
:
: 为啥我用我UA的卡订了3张国内的票，一起飞的，结果第一件也不免费？而且登记group
: 才是3。。

m*12014-11-09 08:11

15 楼

你怎么知道挂在这个题上面？？你已经给出不少答案了啊

i*y2014-11-09 08:11

16 楼

因为你定的三张票，如果是两张就会显示免费了
三张的话，第三个人的第一件不免费，所以系统会显示25刀。底下有行小字，说每个人
的charge可能会因member级别而不一样，貌似你没看到。

group

【在 j*****8 的大作中提到】

: 为啥我用我UA的卡订了3张国内的票，一起飞的，结果第一件也不免费？而且登记group
: 才是3。。

c*r2014-11-09 08:11

17 楼

我自己一口气说出来以后手贱写了个之前板上看到的swap()的方法，其实复杂度也不咋
地，结果写出问题了...

m*a2014-11-09 08:11

18 楼

最近，UA有单方向的promotion，即便经济舱，中国到美国可以两个免费行李，爸妈昨
天刚到。

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

g*y2014-11-09 08:11

19 楼

这个真不错，还省去了算总和的时间

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

d*e2014-11-09 08:11

20 楼

这个方法妙得很！

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

: O(n)
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }

d*o2014-11-09 08:11

21 楼

这个也是 O(N)
为啥最优？
是因为bit运算比较快吗？

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

d*32014-11-09 08:11

22 楼

O(n)是最好的了，这个是O(N）里的最好的了，空间O(1),而且位运算比加减快

【在 d**********o 的大作中提到】

: 这个也是 O(N)
: 为啥最优？
: 是因为bit运算比较快吗？

v*n2014-11-09 08:11

23 楼

位运算应该比较快

f*t2014-11-09 08:11

24 楼

做加法写的不好还有溢出的风险

【在 d**********o 的大作中提到】

: 这个也是 O(N)
: 为啥最优？
: 是因为bit运算比较快吗？

r*92014-11-09 08:11

25 楼

是这样的swap算法吗？也是O(n).
int f(int *a, int n){
int tmp;
for(int i=0; iwhile(a[i]!=i+1){
tmp=a[i];
a[i]=a[a[i]-1];
if(tmp==a[i]) return tmp;
else{
a[a[i]-1]=tmp;
}
}
}
return -1;
}

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

: 我自己一口气说出来以后手贱写了个之前板上看到的swap()的方法，其实复杂度也不咋
: 地，结果写出问题了...

e*s2014-11-09 08:11

26 楼

拜服。秒杀的解法

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

l*82014-11-09 08:11

27 楼

这个还是可能溢出。

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

: O(n). 一个小bug, i<=n
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }

k*t2014-11-09 08:11

28 楼

有个疑问，如果这个数组是sorted, 是不是可以用binary search？每次看到一个元素
，比较小相邻的两个值，没有相等的话，再根据index和对应的值决定向左或向右。这
样只要O(lgn), 不知这个有没有什么问题？

s*r2014-11-09 08:11

29 楼

你再仔细想想

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

: O(n). 一个小bug, i<=n
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }

s*r2014-11-09 08:11

30 楼

对lz的题目不会溢出
当数组size大到一定程度而且内存能装的下的话
是可能溢出的
位操作可以保证不会溢出

【在 l*********8 的大作中提到】

: 这个还是可能溢出。

s*r2014-11-09 08:11

31 楼

没问题
不过不需要比较相邻的两个值直接比较a[i]和i就可以

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

: 有个疑问，如果这个数组是sorted, 是不是可以用binary search？每次看到一个元素
: ，比较小相邻的两个值，没有相等的话，再根据index和对应的值决定向左或向右。这
: 样只要O(lgn), 不知这个有没有什么问题？

k*t2014-11-09 08:11

32 楼

确实，谢谢拉

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

: 没问题
: 不过不需要比较相邻的两个值直接比较a[i]和i就可以

t*h2014-11-09 08:11

33 楼

如果swap的cost和位运算的一样，应该是swap更好。

f*t2014-11-09 08:11

34 楼

我觉得swap不如位运算。
位运算是把N+1个数全读一遍。
swap概率上平均要读(N+1)/4个数，但对每个数，需要做swap操作的概率是N/(N+1)。也
就是说，要进行N/4次swap。swap的cost不止是位运算的4倍吧。

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

: 如果swap的cost和位运算的一样，应该是swap更好。

r*o2014-11-09 08:11

35 楼

这两个O(n)的算法假定数组是sorted的吧？
如果不是sorted有啥好解法？先排序么？

s*s2014-11-09 08:11

36 楼

我觉得这个swap应该没问题吧，你当初是这么写的？
// O(n)
int findDuplicate(vector A) {
// let A[i] == i for i=1, 2, ..., 1000
while(A[0] != A[A[0]]) {
swap(A[0], A[A[0]];
}
return A[0];
}

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

: 我自己一口气说出来以后手贱写了个之前板上看到的swap()的方法，其实复杂度也不咋
: 地，结果写出问题了...

l*s2014-11-09 08:11

37 楼

这个不对，while外面还应该有一层循环

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

: 我觉得这个swap应该没问题吧，你当初是这么写的？
: // O(n)
: int findDuplicate(vector A) {
: // let A[i] == i for i=1, 2, ..., 1000
: while(A[0] != A[A[0]]) {
: swap(A[0], A[A[0]];
: }
: return A[0];
: }

b*i2014-11-09 08:11

38 楼

最优解：
int findDup(int[] A, int n) {
int ans = n;

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

s*s2014-11-09 08:11

39 楼

我觉得不用一个外层循环了，
前提条件是1－10000这10000个数放到10001个slot中，而且只有一个重复。
我们只要能找到一个A[A[0]] == A[0]就足够了。
你觉得呢？

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

: 这个不对，while外面还应该有一层循环

s*s2014-11-09 08:11

40 楼

这个最初的ans应该初始化成0吧？

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

:
: 最优解：
: int findDup(int[] A, int n) {
: int ans = n;

b*i2014-11-09 08:11

41 楼

you are right, I was starting from 1

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

: 这个最初的ans应该初始化成0吧？

b*i2014-11-09 08:11

42 楼

not really. Please gives code

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

: 对lz的题目不会溢出
: 当数组size大到一定程度而且内存能装的下的话
: 是可能溢出的
: 位操作可以保证不会溢出

w*o2014-11-09 08:11

43 楼

這個能找到duplicates regardless of the range, as long as there's only one
duplicate.
i.e. 1000-2000, given size 1001.
相反，這個就有點欠缺了，需要做一點變形，而且比上面這個慢點，還要考慮overflow。

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

c*p2014-11-09 08:11

44 楼

我前2天也被问这个了。

o*72014-11-09 08:11

45 楼

碰到过一个类似的：
数组只有1-10000，然后size也是10000，因为有一个miss了，有一个重复了，怎么找
到miss那个

u*o2014-11-09 08:11

46 楼

这题也好玩，可以用XOR做吗？

【在 o********7 的大作中提到】

: 碰到过一个类似的：
: 数组只有1-10000，然后size也是10000，因为有一个miss了，有一个重复了，怎么找
: 到miss那个

a*e2014-11-09 08:11

47 楼

why need "ans ^= i"?

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

s*n2014-11-09 08:11

48 楼

这个程序正确是建立在这个等式成立：ans = (0-n)^(0-n)^dup
这个数学上如何证明呢？

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

m*82014-11-09 08:11

49 楼

这是加减两个操作如果是公式算只用减一个操作

【在 G****A 的大作中提到】

: 这个小trick不错

m*82014-11-09 08:11

50 楼

thats it

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

h*p2014-11-09 08:11

51 楼

这种看似简单的题有些时候最容易出问题了

a*u2014-11-09 08:11

52 楼

我今天也被面了这道题，我只说了partition的办法，好像比较满意。楼下的办法好牛

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

: 数组只有1-10000，然后size是10001，怎么找到重复的那个
: ONSITE题目，让用尽可能多的方法。我能想到的方法是sum之后做减法， Hashtable,
: sorting完扫一边，或者boolean数组存。
: 当时二逼用了swap的算法不停swap，结果最后自己没弄出来。
: 想问下这题有什么比较好的解法啊？

s*n2014-11-09 08:11

53 楼

XOR有下列性质：
XOR is associative, so (x ^ y) ^ z = x ^ (y ^ z)
XOR is commutative: x ^ y = y ^ x
XOR is its own inverse: x ^ y = 0 if x = y
XOR has zero as an identity: x ^ 0 = x
所以 ans = (0-n)^(0-n)^dup = dup

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

: 这个程序正确是建立在这个等式成立：ans = (0-n)^(0-n)^dup
: 这个数学上如何证明呢？

T*u2014-11-09 08:11

54 楼

找到m^n和m-n能算出两个来吗？方法比较笨了。

【在 o********7 的大作中提到】

: 碰到过一个类似的：
: 数组只有1-10000，然后size也是10000，因为有一个miss了，有一个重复了，怎么找
: 到miss那个

k*j2014-11-09 08:11

55 楼

这题是1-10000
而不是从0开始的，
为什么不是
: ans ^= A[i];
: ans ^= (i+1);
??

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

u*o2014-11-09 08:11

56 楼

你好我想和你讨论一下你的办法。如果我没理解错，m是array, n是INDEX，
如果ARRAY里有 0， 1， 2， 3， 3
他们的index是0，1，2，3，4
m^n结果是 3^4 = 000
m-n 结果是3-4=-1.
知道这两个方程怎么求出3是重复的，4是没出现的呢？

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

: 找到m^n和m-n能算出两个来吗？方法比较笨了。

x*02014-11-09 08:11

57 楼

mark

s*r2014-11-09 08:11

58 楼

重复的不止一个吧

c*e2014-11-09 08:11

59 楼

mark

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

z*e2014-11-09 08:11

60 楼

swap
xor
plus
这种题目真心烂大街

s*n2014-11-09 08:11

61 楼

这个没有问题吗？用上面的code跑了一下，会出问题呀，还是我的理解有问题。
findDup({0,1,2,2,3}）=6;
findDup({0,1,2,3,3}) =7;
e.g.:
For {0,1,2,3,3}, when i =4:
ans = ans^A[4] = ans^3= 0^3=3;
ans = ans^i =3^4=7;

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

: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }

s*n2014-11-09 08:11

62 楼

....., 又试了这个解法，把long改成int了，可是结果也不一样了。
findDup({0,1,2,2,3}）=-2;
findDup({0,1,2,3,3}) =-1;
e.g.:
For {0,1,2,3,3},
i=0, ret=0-0=0;
i=1, ret=1-1=0;
i=2, ret=2-2=0;
i=3, ret=3-3=0;
i=4, ret=3-4=-1;
是不是我理解力真有问题了，今天不适合做题了。。。

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

: O(n). 一个小bug, i<=n
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }

u*o2014-11-09 08:11

63 楼

这题数不能从0开始啊，必须是从1开始，才能保证和下标一个个消掉。
原题是数组只有1-10000，然后size是10001
你的例子的话呢，就是
findDup({1,2,2,3,4})
要用0进数组的话得改一下下标。

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

:
: ....., 又试了这个解法，把long改成int了，可是结果也不一样了。
: findDup({0,1,2,2,3}）=-2;
: findDup({0,1,2,3,3}) =-1;
: e.g.:
: For {0,1,2,3,3},
: i=0, ret=0-0=0;
: i=1, ret=1-1=0;
: i=2, ret=2-2=0;
: i=3, ret=3-3=0;

s*n2014-11-09 08:11

64 楼

明白了，两种解法都是这个问题，不能从0开始。
多谢多谢！！！

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

: 这题数不能从0开始啊，必须是从1开始，才能保证和下标一个个消掉。
: 原题是数组只有1-10000，然后size是10001
: 你的例子的话呢，就是
: findDup({1,2,2,3,4})
: 要用0进数组的话得改一下下标。

p*e2014-11-09 08:11

65 楼

应该这样吧
// A[] has (n+1) elements, range: (1...n), only one duplicate
int findDup(int A[], int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= A[i];
ans ^= (i+1);
}
ans ^= A[n];
return ans;
}

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

:
: 明白了，两种解法都是这个问题，不能从0开始。
: 多谢多谢！！！

s*n2014-11-09 08:11

66 楼

我理解的还不够透彻，我trace一下，i+1，好像不对。
{1，1，2，3，4} = 4；
个人觉得要理解上面所提到的，不要去考虑下标了。
XOR有下列性质：
XOR is associative, so (x ^ y) ^ z = x ^ (y ^ z)
XOR is commutative: x ^ y = y ^ x
XOR is its own inverse: x ^ y = 0 if x = y
XOR has zero as an identity: x ^ 0 = x
所以 ans = (0-n)^(0-n)^dup = dup

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

: 应该这样吧
: // A[] has (n+1) elements, range: (1...n), only one duplicate
: int findDup(int A[], int n) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= (i+1);
: }
: ans ^= A[n];
: return ans;

L*e2014-11-09 08:11

67 楼

I wrote the following methods and ran some testings, it works OK. You need
go through the whole list. In your code, i < n, it never touches the last
element.
/**
* A[] has (n+1) elements, range: (1...n), only one duplicate
* @param a
* @return
*/
public static int findDup(int[] a){
int sum = 0;
for (int i = a.length - 1; i >= 0; i--){
sum += (a[i] - i);
}
return sum;
}
public static int findDup2(int[] a){
int sum = 0;
for (int i = 0; i < a.length; i++){
sum ^= i;
sum ^= a[i];
}
return sum;
}

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

:
: 我理解的还不够透彻，我trace一下，i+1，好像不对。
: {1，1，2，3，4} = 4；
: 个人觉得要理解上面所提到的，不要去考虑下标了。
: XOR有下列性质：
: XOR is associative, so (x ^ y) ^ z = x ^ (y ^ z)
: XOR is commutative: x ^ y = y ^ x
: XOR is its own inverse: x ^ y = 0 if x = y
: XOR has zero as an identity: x ^ 0 = x
: 所以 ans = (0-n)^(0-n)^dup = dup

x*i2014-11-09 08:11

68 楼

a[0]^a[1]^.......a[10000]^10001就可以了吧....

s*w2014-11-09 08:11

69 楼

没见过能解这种两元方程组的方法
可以用 +xi-i 搞一遍得 xdup-xmiss = a
*xi/i 搞一遍得 xdup/xmiss = b
这个两元方程组总会解吧

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

: 你好我想和你讨论一下你的办法。如果我没理解错，m是array, n是INDEX，
: 如果ARRAY里有 0， 1， 2， 3， 3
: 他们的index是0，1，2，3，4
: m^n结果是 3^4 = 000
: m-n 结果是3-4=-1.
: 知道这两个方程怎么求出3是重复的，4是没出现的呢？