868. Binary Gap
简单题,就是求一个数字二进制形式中两个1的最大间隔位置,比如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
869. Reordered Power of 2
一个数字各个位的数重排后能不能变成2的幂,注意不能有前导0,也就是说类似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