|
| 1 | +package_20160910_4th_contest; |
| 2 | + |
| 3 | +importjava.util.HashSet; |
| 4 | +importjava.util.Iterator; |
| 5 | +importjava.util.LinkedList; |
| 6 | +importjava.util.Queue; |
| 7 | +importjava.util.Set; |
| 8 | + |
| 9 | +publicclassIntegerReplacement { |
| 10 | +publicstaticintintegerReplacement_failed(intn) { |
| 11 | +if(n ==1)return0; |
| 12 | +intsteps =0; |
| 13 | +while(n !=1){ |
| 14 | +if(n%2 ==1 &&n >1) { |
| 15 | +n -=1; |
| 16 | +steps++; |
| 17 | + } |
| 18 | + |
| 19 | +n /=2; |
| 20 | +steps++; |
| 21 | + } |
| 22 | +returnsteps; |
| 23 | + } |
| 24 | + |
| 25 | +publicstaticintintegerReplacement_failed_2(intn) { |
| 26 | +if(n ==1)return0; |
| 27 | +inttemp =2,steps =1; |
| 28 | +while(temp <=n){ |
| 29 | +temp *=2; |
| 30 | +steps++; |
| 31 | + |
| 32 | +if(temp%2 ==1){ |
| 33 | +temp +=1; |
| 34 | +steps++; |
| 35 | + } |
| 36 | + } |
| 37 | +returnsteps; |
| 38 | + } |
| 39 | + |
| 40 | +publicstaticintintegerReplacement(intn) { |
| 41 | +longmin =Long.MAX_VALUE; |
| 42 | +Set<long[]>set =newHashSet(); |
| 43 | +Queue<long[]>q =newLinkedList(); |
| 44 | +long[]pair =newlong[]{n,0}; |
| 45 | +q.offer(pair); |
| 46 | +while(!q.isEmpty()){ |
| 47 | +intsize =q.size(); |
| 48 | +for(inti =0;i <size;i++){ |
| 49 | +long[]curr =q.poll(); |
| 50 | +if(curr[0] ==1)set.add(curr); |
| 51 | +else { |
| 52 | + |
| 53 | +if (curr[0] %2 ==0) { |
| 54 | +curr[0] /=2; |
| 55 | +curr[1]++; |
| 56 | +q.offer(curr); |
| 57 | + }else { |
| 58 | +long[]minus =newlong[2]; |
| 59 | +minus[0] =curr[0] -1; |
| 60 | +minus[1] =curr[1] +1; |
| 61 | +q.offer(minus); |
| 62 | + |
| 63 | +long[]plus =newlong[2]; |
| 64 | +plus[0] =curr[0] +1; |
| 65 | +plus[1] =curr[1] +1; |
| 66 | +q.offer(plus); |
| 67 | + } |
| 68 | + } |
| 69 | + } |
| 70 | + } |
| 71 | + |
| 72 | +Iterator<long[]>it =set.iterator(); |
| 73 | +while(it.hasNext()){ |
| 74 | +min =Math.min(min,it.next()[1]); |
| 75 | + } |
| 76 | +return (int)min; |
| 77 | + } |
| 78 | + |
| 79 | +publicstaticvoidmain(String...strings){ |
| 80 | +System.out.println(integerReplacement(2147483647)); |
| 81 | +System.out.println(integerReplacement(65535));//should be 17 |
| 82 | +System.out.println(integerReplacement(1234));//should be 14 |
| 83 | +// System.out.println(integerReplacement(1)); |
| 84 | +// System.out.println(integerReplacement(2)); |
| 85 | +// System.out.println(integerReplacement(3)); |
| 86 | +System.out.println(integerReplacement(5));//should be 3 |
| 87 | +// System.out.println(integerReplacement(7)); |
| 88 | + } |
| 89 | +} |