GOOGLE ONSITE9/29

第四题难道不是分别读到两个256长度的int array里， 然后顺序比较这俩256的int array? O(1) space 因为256是常数

sxh53 发表于 2015-11-12 06:15
第四题难道不是分别读到两个256长度的int array里， 然后顺序比较这俩256的int array? O(1) space 因为256 ...

正解，这个是char....

sxh53 发表于 2015-11-12 06:15
第四题难道不是分别读到两个256长度的int array里， 然后顺序比较这俩256的int array? O(1) space 因为256 ...

他说这个方法不是他要的亲

majiamajia 发表于 2015-11-12 06:55
他说这个方法不是他要的亲

那就只有二分或brute force从头比较。

maomaoxiong 发表于 2015-11-12 07:02
那就只有二分或brute force从头比较。

二分…？没有顺序的

brute force不符合复杂度

第四题可不可以利用数学的思想呢？char的话就把他映射到1-256上。分别对两个str算出他们各自的乘积和相加的和： sum_a,sum_b,multiply_a,multiply_b。假设多出的两个char 分别是 a和b。 那么 a+b＝sumb-suma, a*b=multyplyb/multiplya; 然后计算应该就可以了，虽然我觉得如果str过长会有溢出。。。

majiamajia 发表于 2015-11-12 03:26
我也不知道。。。。。我知道了应该就不会被发配去residency program了

请问什么是residency program

aiweiwei 发表于 2015-11-12 13:42
请问什么是residency program

上班几个月然后转正。。

bill701 发表于 2015-11-12 12:48
第四题可不可以利用数学的思想呢？char的话就把他映射到1-256上。分别对两个str算出他们各自的乘积和相加的 ...

这个方法可行。不用乘。直接XOR。如果为0，a = b = (sumb-sumA)/2.

请问lz第三轮第二题是网左边走要减去当前格子的钱数，往右边走是加上钱数吗？那上下怎么看？