|
| 1 | +package_20160827_2nd_contest; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.List; |
| 5 | + |
| 6 | +publicclassEliminationGame { |
| 7 | + |
| 8 | +//then I turned to Discuss and found this post: https://discuss.leetcode.com/topic/55870/share-my-solutions-for-contest-2 |
| 9 | +//instead of literally removing half of the elements in each scan, this solution is just moving the pointer to point to next start position |
| 10 | +//So brilliant! |
| 11 | +publicintlastRemaining(intn) { |
| 12 | +intremaining =n; |
| 13 | +intstart =1; |
| 14 | +intstep =2; |
| 15 | +booleanforward =true; |
| 16 | +while(remaining >1){ |
| 17 | +remaining /=2; |
| 18 | +if(forward)start =start +step*remaining -step/2; |
| 19 | +elsestart =start -step*remaining +step/2; |
| 20 | +step *=2; |
| 21 | +forward = !forward; |
| 22 | + } |
| 23 | +returnstart; |
| 24 | + } |
| 25 | + |
| 26 | +//I tried brute force, all producing the correct output, but got TLE by OJ. |
| 27 | +publicstaticintlastRemaining_brute_force_TLE(intn) { |
| 28 | +List<Integer>list =newArrayList(); |
| 29 | +for(inti =0;i <n;i++){ |
| 30 | +list.add(i+1); |
| 31 | + } |
| 32 | +booleanforward =true; |
| 33 | +while(list.size() >1){ |
| 34 | +intsize =list.size()/2; |
| 35 | +if(list.size() ==1)returnlist.get(0); |
| 36 | +if(forward){ |
| 37 | +if(list.size() ==1)returnlist.get(0); |
| 38 | +for(inti =0;i <=size &&i <list.size();i++){ |
| 39 | +list.remove(i); |
| 40 | + } |
| 41 | +forward =false; |
| 42 | + }else { |
| 43 | +if(list.size() ==1)returnlist.get(0); |
| 44 | +for(inti =list.size()-1,count =0;i >=0 &&count <=size;count++){ |
| 45 | +list.remove(i); |
| 46 | +i -=2; |
| 47 | + } |
| 48 | +forward =true; |
| 49 | + } |
| 50 | + } |
| 51 | +returnlist.get(0); |
| 52 | + } |
| 53 | + |
| 54 | +publicstaticvoidmain(String...strings){ |
| 55 | +System.out.println(lastRemaining_brute_force_TLE(5204)); |
| 56 | +System.out.println(lastRemaining_brute_force_TLE(5058)); |
| 57 | +// System.out.println(lastRemaining(10)); |
| 58 | +// System.out.println(lastRemaining(9)); |
| 59 | +// System.out.println(lastRemaining(3)); |
| 60 | + } |
| 61 | + |
| 62 | +} |