868. Binary Gap
简单题，就是求一个数字二进制形式中两个１的最大间隔位置，比如22的二进制0b10110，最大距离就是2，0b100001，最大距离是5。
class Solution { public int binaryGap(int N) { String bs = Integer.toBinaryString(N); int ans = 0; int lasone = -1; for (int i = bs.length()-1; i >= 0; i--) { if (bs.charAt(i) == '0') continue; if (lasone == -1) { lasone = i; } else { ans = Math.max(ans, lasone - i); lasone = i; } } return ans; } }
869. Reordered Power of 2
一个数字各个位的数重排后能不能变成２的幂，注意不能有前导０，也就是说类似10是不能重排成01的。 起始考虑将数字重排是比较复杂，换个思路，2的次方数起始是很少的，早10^9次方内也就30个，所以只需要拿这30个数来和N比较，看他们有没有相同个数的数字。
class Solution { public boolean reorderedPowerOf2(int N) { if (N == 1) return true; int num = 2; while (num <= 1000000000) { if (isSame(num, N)) { return true; } num = num<<1; } return false; } private boolean isSame(int x, int y) { int[] cnt1 = new int[10]; int[] cnt2 = new int[10]; while (x != 0) { cnt1[x%10]++; x /= 10; } while (y != 0) { cnt2[y%10]++; y /= 10; } for (int i = 0; i < 10; i++) { if (cnt1[i] != cnt2[i]) return false; } return true; } }
870. Advantage Shuffle
起始就是hdoj 1502田忌赛马，但要求的结果不一样而已。这里我用了个pair来记录B中每个数字对应的位置。
import java.util.Arrays; import java.util.Comparator; class Solution { private class Pair { public int i; public int v; public Pair(int x, int y) { this.i = x; this.v = y; } } public int[] advantageCount(int[] A, int[] B) { Pair[] pairs = new Pair[B.length]; for (int i = 0; i < B.length; i++) { pairs[i] = new Pair(i, B[i]); } Arrays.sort(A); Arrays.sort(pairs, new Comparator<Pair>() { @Override public int compare(Pair o1, Pair o2) { return o1.v - o2.v; } }); int n = A.length; int[] res = new int[n]; for(int ts = 0, tf = n-1, ks = 0, kf = n-1; kf >= ks || tf >= ts; ) { if(A[ts] > pairs[ks].v){//比较最慢的马，能赢就赢 res[pairs[ks].i] = A[ts]; ts++; ks++; } else if(A[ts] < pairs[ks].v){//不能赢，就用田忌最慢的消耗齐王最快的 res[pairs[kf].i] = A[ts]; ts++; kf--; } else if(A[tf] > pairs[kf].v){//比较双方最快的马，能赢就赢 res[pairs[kf].i] = A[tf]; tf--; kf--; } else if(A[tf] < pairs[kf].v){//不能赢就用田忌最慢的马消耗齐王最快的马 res[pairs[kf].i] = A[ts]; ts++; kf--; } else if(A[ts] < pairs[kf].v){//拿田忌最慢的和齐王最快的比，如果慢，就消耗 res[pairs[kf].i] = A[ts]; ts++; kf--; } else{//如果一样，后边都是平局 res[pairs[kf].i] = A[ts]; ts++; kf--; } } return res; } }
