Leetcode contests 93 题解

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;
    }
}