hackerrank的xor题目 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

hackerrank的xor题目

hackerrank的xor题目# JobHunting - 待字闺中

a*32013-03-05 08:03

1 楼

https://www.hackerrank.com/challenges/xor-key
public class Solution {

static void xor(int[] ar, int number, int left, int right){
int max=0;
for(int i=left;i<=right;i++){
int temp=number^ar[i];
if(temp>max)
max=temp;
}
System.out.println(max);
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int test_case = in.nextInt();
for(int i=0;iint n=in.nextInt();
int count=in.nextInt();
int[] ar = new int[n];
for(int j=0;jar[j]=in.nextInt();
}
for(int k=0;kint number=in.nextInt();
int left=in.nextInt()-1;
int right=in.nextInt()-1;
xor(ar, number, left, right);
}

}
}
}
提交答案第一个test case过了，但是后面的几个全部超时。感觉这个时间复杂度全用
在读input里面啊，是不是我理解错了第一行T test case的意思? 我的理解是有T个这
样的input，用在最外面的for loop里面

p*e2013-03-05 08:03

2 楼

这是哪个track啊
hackerrank对代码优化要求很高，不同test case差别很大
search那个track的Arithmetic Progressions我的code死活过不了后面3个test case
但是前面的都只要0.1s

a*32013-03-05 08:03

3 楼

Bit Manipulation
我没有什么头绪去优化。。求各位指导一下

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

: 这是哪个track啊
: hackerrank对代码优化要求很高，不同test case差别很大
: search那个track的Arithmetic Progressions我的code死活过不了后面3个test case
: 但是前面的都只要0.1s

p*22013-03-05 08:03

4 楼

话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*e2013-03-05 08:03

5 楼

Arithmetic过了没
求指导

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

: 话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*22013-03-05 08:03

6 楼

没做。看样子比median还难吧？

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

: Arithmetic过了没
: 求指导

p*e2013-03-05 08:03

7 楼

分数两个差不多

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

:
: 没做。看样子比median还难吧？

a*32013-03-05 08:03

8 楼

向二爷学习

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

: 话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*22013-03-05 08:03

9 楼

昨天没搞过，恶心的我工作了两天。等我恢复一下吧。

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

: 分数两个差不多

a*32013-03-05 08:03

10 楼

大牛是按什么顺序做的？

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

: Arithmetic过了没
: 求指导

p*e2013-03-05 08:03

11 楼

不敢当，才刚开始，Track 2 search

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

:
: 大牛是按什么顺序做的？

p*22013-03-05 08:03

12 楼

我觉得可以按照分数的高低来做。先做分数低的。一天能做一题平均就不错了。

a*32013-03-05 08:03

13 楼

二爷可以写完了总结一下。方便吾等菜鸟学习。毕竟网上没有答案，不会就真不会了

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

: 我觉得可以按照分数的高低来做。先做分数低的。一天能做一题平均就不错了。

A*u2013-03-05 08:03

14 楼

我也做median了
没过

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

: 话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*22013-03-05 08:03

15 楼

你用的什么算法？我感觉我算法应该还可以呀。最后只能过3个test case。不知道哪里
搞错了。算法就是用的CC150上的。
网上看到一个python的答案，用了一个我没听说过的数据结构或者算法。python直接有
类库，scala貌似还要自己写，就没继续研究下去。

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

: 我也做median了
: 没过

p*22013-03-05 08:03

16 楼

刚做了一道DP又超时。哎。

g*d2013-03-05 08:03

17 楼

超时就用scanf吧……我听某ACM大牛说的

g*d2013-03-05 08:03

18 楼

大牛用cin cout都嫌慢，用scanner之类估计都慢的不行了，对于这种性能要求较高的
场合

p*22013-03-05 08:03

19 楼

我先用scala，再用java。考虑到这个问题了，因此先用scanner, 再用bufferreader,
再用tokenizer还是不行呀。

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

: 超时就用scanf吧……我听某ACM大牛说的

p*22013-03-05 08:03

20 楼

要求还是挺高的。同样的题在其他OJ里应该就过了。我又想起以前做interviewstreet
时的情景了，真是绞尽脑汁呀。挺累的。感觉得几个人联手来做。一个人，如果不是
ACMer真的挺难搞的。

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

: 大牛用cin cout都嫌慢，用scanner之类估计都慢的不行了，对于这种性能要求较高的
: 场合

a*32013-03-05 08:03

21 楼

p*e2013-03-05 08:03

22 楼

a*32013-03-05 08:03

23 楼

Bit Manipulation
我没有什么头绪去优化。。求各位指导一下

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

p*22013-03-05 08:03

24 楼

话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*e2013-03-05 08:03

25 楼

Arithmetic过了没
求指导

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

: 话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*22013-03-05 08:03

26 楼

没做。看样子比median还难吧？

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

: Arithmetic过了没
: 求指导

p*e2013-03-05 08:03

27 楼

分数两个差不多

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

:
: 没做。看样子比median还难吧？

a*32013-03-05 08:03

28 楼

向二爷学习

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

: 话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*22013-03-05 08:03

29 楼

昨天没搞过，恶心的我工作了两天。等我恢复一下吧。

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

: 分数两个差不多

a*32013-03-05 08:03

30 楼

大牛是按什么顺序做的？

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

: Arithmetic过了没
: 求指导

p*e2013-03-05 08:03

31 楼

不敢当，才刚开始，Track 2 search

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

:
: 大牛是按什么顺序做的？

p*22013-03-05 08:03

32 楼

我觉得可以按照分数的高低来做。先做分数低的。一天能做一题平均就不错了。

a*32013-03-05 08:03

33 楼

二爷可以写完了总结一下。方便吾等菜鸟学习。毕竟网上没有答案，不会就真不会了

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

: 我觉得可以按照分数的高低来做。先做分数低的。一天能做一题平均就不错了。

A*u2013-03-05 08:03

34 楼

我也做median了
没过

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

: 话说我昨天做了median那题也没过。还没心情再花时间搞呢。

p*22013-03-05 08:03

35 楼

: 我也做median了
: 没过

p*22013-03-05 08:03

36 楼

刚做了一道DP又超时。哎。

g*d2013-03-05 08:03

37 楼

超时就用scanf吧……我听某ACM大牛说的

g*d2013-03-05 08:03

38 楼

大牛用cin cout都嫌慢，用scanner之类估计都慢的不行了，对于这种性能要求较高的
场合

p*22013-03-05 08:03

39 楼

我先用scala，再用java。考虑到这个问题了，因此先用scanner, 再用bufferreader,
再用tokenizer还是不行呀。

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

: 超时就用scanf吧……我听某ACM大牛说的

p*22013-03-05 08:03

40 楼

: 大牛用cin cout都嫌慢，用scanner之类估计都慢的不行了，对于这种性能要求较高的
: 场合

a*32013-03-05 08:03

41 楼

median注意两个问题吧，第一个是相加溢出，这个hackrank上经常这么坑人的
第二个是如何保证较小的代价插入和寻找中间的数吧。我用C++的std::deque，主要是
写代码快，方便。插入近似O(sqrt(n)),随机访问也是O(sqrt(n))
其他语言如果没有的话，二叉树也可以模拟吧，只不过每个节点记录下自己子节点有多
少个数，这样寻找中间那个数就是O(logn)的吧，插入是O(logn)

d*32013-03-05 08:03

42 楼

median 这题我怎么记得貌似用数组很暴力的就过了。。。

a*32013-03-05 08:03

43 楼

反正数组我过不了，中间插入代价蛮大的

p*22013-03-05 08:03

44 楼

多谢讨论。我是用的Long，所以应该不会溢出。想过用TreeMap，但是查找中点也是线
性的应该。如果自己实现BST的话，感觉还需要做balanced，否则估计也过不了。C++有
deque倒是个优势，不知道Java／Scala有没有相对应的数据结构。

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

: median注意两个问题吧，第一个是相加溢出，这个hackrank上经常这么坑人的
: 第二个是如何保证较小的代价插入和寻找中间的数吧。我用C++的std::deque，主要是
: 写代码快，方便。插入近似O(sqrt(n)),随机访问也是O(sqrt(n))
: 其他语言如果没有的话，二叉树也可以模拟吧，只不过每个节点记录下自己子节点有多
: 少个数，这样寻找中间那个数就是O(logn)的吧，插入是O(logn)

p*22013-03-05 08:03

45 楼

你用的什么语言呢？

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

: median 这题我怎么记得貌似用数组很暴力的就过了。。。

e*i2013-03-05 08:03

46 楼

C code as following. Passed first test case. Could not figure out why failed
the others. Please help
//////////////////////////////
#include
#include
#include
#include
int main() {
int nCases;
scanf("%d\n", &nCases);

for(int i=0;i{
int N;
int Q;
scanf("%d %d\n",&N, &Q);

short int *A=malloc((N+1)*sizeof(short int));
for(int j=1;j<=N;++j) scanf("%d ", &A[j]);

scanf("\n");

for(int j=0;j{
short int a;
int p;
int q;
scanf("%d %d %d\n", &a, &p, &q);
long aa= a<<16|a ;

int end;
short int res=0;
if( ((p-q)&1)==0 )
{
res=(a^A[q]);
end=q-1;
}
else end=q;

long *head=&A[p];
short int curr=0;
long lCurr=0;
short int left, right;
while( head{
lCurr= aa^(*head++);
left=(short int)lCurr;
right=(short int)(*( (short int*)&lCurr + 1) );

if( leftcurr=right;
else
curr=left;

if(res
}

printf("%d\n", res);

}
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT *
/
return 0;
}

e*i2013-03-05 08:03

47 楼

Fixed some pointer casting issue. Now it scored 42+ points but still failed
test case 1,2,3,4,5,10 due to TLE.
/////////////////////
#include
#include
#include
#include
int main() {
int nCases;
scanf("%d\n", &nCases);

for(int i=0;i{
int N;
int Q;
scanf("%d %d\n",&N, &Q);

short int *A=(short int *)malloc((N+1)*sizeof(short int));
for(int j=1;j<=N;++j) scanf("%hd ", &A[j]);

scanf("\n");

for(int j=0;j{
short int a;
int p;
int q;
scanf("%hd %d %d\n", &a, &p, &q);
long aa= a<<16|a ;

int end;
short int res=0;
if( ((p-q)&1)==0 )
{
res=(a^A[q]);
end=q-1;
}
else end=q;

long *head=(long *)&A[p];
short int curr=0;
long lCurr=0;
short int left, right;
while( head{
lCurr= aa^(*head++);
left=(short int)lCurr;
right=(short int)(*( (short int*)&lCurr + 1) );

if( leftcurr=right;
else
curr=left;

if(res
}

printf("%d\n", res);

}
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT *
/
return 0;
}

r*h2013-03-05 08:03

48 楼

同最后三个过不了
另外billboard那一题我也是卡在最后三个case，郁闷死了

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

r*h2013-03-05 08:03

49 楼

search部分做了4个整题加上两个半题就完全卡住了。。。
大牛们求带啊

interviewstreet

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

:
: 你用的什么语言呢？

p*22013-03-05 08:03

50 楼

我看了一下，我也是做了4题

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

: search部分做了4个整题加上两个半题就完全卡住了。。。
: 大牛们求带啊
:
: interviewstreet

a*32013-03-05 08:03

51 楼

二爷有空也可以做下weekly contest，挺有意思的

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

:
: 我看了一下，我也是做了4题

p*22013-03-05 08:03

52 楼

刚做了一题，挺不错。不过前边做的两题太累了。这两天懒惰了。感觉需要做做
leetcode放松一下了。

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

:
: 二爷有空也可以做下weekly contest，挺有意思的

p*e2013-03-05 08:03

53 楼

紧跟二爷学习..

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

:
: 刚做了一题，挺不错。不过前边做的两题太累了。这两天懒惰了。感觉需要做做
: leetcode放松一下了。

a*32013-03-05 08:03

54 楼

billboard普通dp最后几个case就是会超时的。。。
这题我卡了两个月，后来想通了，有个sliding window优化可以做，有了就能过了

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

: 同最后三个过不了
: 另外billboard那一题我也是卡在最后三个case，郁闷死了

p*22013-03-05 08:03

55 楼

大牛一般一天做几题呀？

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

: billboard普通dp最后几个case就是会超时的。。。
: 这题我卡了两个月，后来想通了，有个sliding window优化可以做，有了就能过了

a*32013-03-05 08:03

56 楼

hackerrank一天能做很多题么？其实我也很菜。。我做题很慢
我去年9,10月份做的比较多，最近找工作，在做些面试题，练一次bugfree准确率什么
的。
自从从interviewstreet迁移到hackerrank之后，我觉得那个网站界面不直观，也是剩
下题目都太难了，做不动了。。。

r*h2013-03-05 08:03

57 楼

一语惊醒梦中人呀
果然直接的DP重复计算太多了，修正之后就AC了lol

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

: billboard普通dp最后几个case就是会超时的。。。
: 这题我卡了两个月，后来想通了，有个sliding window优化可以做，有了就能过了

s*x2013-03-05 08:03

58 楼

这题有人全过了么？
我现在前面的都过了，就是最后一个超时

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

: https://www.hackerrank.com/challenges/xor-key
: public class Solution {
:
: static void xor(int[] ar, int number, int left, int right){
: int max=0;
: for(int i=left;i<=right;i++){
: int temp=number^ar[i];
: if(temp>max)
: max=temp;
: }

g*d2013-03-05 08:03

59 楼

今天几个题目都是自己测的找不出有问题的test case,但是提交上去过不了.手感很不
好啊这周。上周周末还心说稍微做出来点感觉了
有的相加溢出的，换成long long基本上就好了（64 bit）