比赛地址
https://leetcode-cn.com/contest/weekly-contest-93
868. 二进制间距
给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。
如果没有两个连续的 1，返回 0 。
示例 1：
输入：22 输出：2 解释： 22 的二进制是 0b10110 。 在 22 的二进制表示中，有三个 1，组成两对连续的 1 。 第一对连续的 1 中，两个 1 之间的距离为 2 。 第二对连续的 1 中，两个 1 之间的距离为 1 。 答案取两个距离之中最大的，也就是 2 。
示例 2：
输入：5 输出：2 解释： 5 的二进制是 0b101 。
示例 3：
输入：6 输出：1 解释： 6 的二进制是 0b110 。
示例 4：
输入：8 输出：0 解释： 8 的二进制是 0b1000 。 在 8 的二进制表示中没有连续的 1，所以返回 0 。
提示：
1 <= N <= 10^9
题解：简单难度，转二进制字符串遍历间距。
/**
* @param {number} N
* @return {number}
*/
var binaryGap = function(N) {
var s = N.toString(2);
var ans = 0;
var pre = -1;
for (var i = 0; i < s.length; i++) {
if (s[i] == "1") {
if (pre != -1) {
ans = Math.max(ans, i - pre);
}
pre = i;
}
}
return ans;
};
869. 重新排序得到 2 的幂
从正整数 N 开始，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：1 输出：true
示例 2：
输入：10 输出：false
示例 3：
输入：16 输出：true
示例 4：
输入：24 输出：false
示例 5：
输入：46 输出：true
提示：
1 <= N <= 10^9
题解：根据N的取值范围，存储2的0～30次方31个数字中每位数字的次数，以此对比N的每位数字的数量，这样计算量较小，不必从1～N遍历。
/**
* @param {number} N
* @return {boolean}
*/
var reorderedPowerOf2 = function(N) {
var cal = function(arr, n) {
var k = 0;
while(n > 0 && k++ < 10) {
arr[n % 10]++;
n = Math.floor(n / 10);
}
}
var counts = new Array(10).fill(0);
cal(counts, N);
for (var i = 0; i < 31; i++) {
var need = new Array(10).fill(0);
cal(need, 1 << i);
for (var j = 0; j < 10; j++) {
if (need[j] != counts[j]) {
break;
}
}
if (j == 10) {
return true;
}
}
return false;
};
870. 优势洗牌
给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
返回 A 的任意排列，使其相对于 B 的优势最大化。
示例 1：
输入：A = [2,7,11,15], B = [1,10,4,11] 输出：[2,11,7,15]
示例 2：
输入：A = [12,24,8,32], B = [13,25,32,11] 输出：[24,32,8,12]
提示：
1 <= A.length = B.length <= 100000 <= A[i] <= 10^90 <= B[i] <= 10^9
题解：贪心思路，将A、B排序，从小到大对应位置依次摆入A比B大的值。
/**
* @param {number[]} A
* @param {number[]} B
* @return {number[]}
*/
var advantageCount = function(A, B) {
var n = A.length;
var b = [];
for (var i = 0; i < n; i++) {
b.push({p:i, v:B[i]});
}
b.sort((a,b)=>a.v-b.v);
A.sort((a,b)=>a-b);
var p = 0;
var ans = new Array(n).fill(-1);
// 从小到大对应位置依次摆入A比B大的值
for (var i = 0; i < n; i++) {
while(p < n) {
if (A[p] > b[i].v) {
ans[b[i].p] = A[p];
A[p++] = -1;
break;
}
p++;
}
}
var p = 0;
// 其余位置再没有A比B大的，随意填充
for (var i = 0; i < n; i++) {
if (A[i] != -1) {
while(p < n) {
if (ans[p] == -1) {
ans[p++] = A[i];
break;
}
p++;
}
}
}
return ans;
};
871. 最低加油次数
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。
示例 1：
输入：target = 1, startFuel = 1, stations = [] 输出：0 解释：我们可以在不加油的情况下到达目的地。
示例 2：
输入：target = 100, startFuel = 1, stations = [[10,100]] 输出：-1 解释：我们无法抵达目的地，甚至无法到达第一个加油站。
示例 3：
输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 输出：2 解释： 我们出发时有 10 升燃料。 我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。 然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料）， 并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。 我们沿途在1两个加油站停靠，所以返回 2 。
提示：
1 <= target, startFuel, stations[i][1] <= 10^90 <= stations.length <= 5000 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
题解：若是暴力求解会超时，本题需要优先队列贪心求解。将当前燃料能到达的所有站点的加油量入队，每次取最大的油量，以此循环直至到达终点。
/**
* 优先级队列类
*/
var PQueue = function() {
//记录数组
this._records = [];
//优先级比较方法
this._cmp_func = function(a, b) {
return b - a;
};
};
//将记录插入队列
PQueue.prototype.enQueue = function(record) {
this._records.push(record);
};
//删除并返回队头记录
PQueue.prototype.deQueue = function() {
var pos = 0;
for (var i = 1; i < this._records.length; i++) {
if (this._cmp_func(this._records[pos], this._records[i]) > 0) {
pos = i;
}
}
return this._records.splice(pos, 1)[0];
};
//判断队列是否为空
PQueue.prototype.isEmpty = function() {
return this._records.length == 0;
};
/**
* @param {number} target
* @param {number} startFuel
* @param {number[][]} stations
* @return {number}
*/
var minRefuelStops = function(target, startFuel, stations) {
var pq = new PQueue();
var ans = 0;
var i = 0;
var fuel = startFuel;
while(true) {
if (fuel >= target) {
return ans;
}
while(i < stations.length && stations[i][0] <= fuel) {
pq.enQueue(stations[i++][1]);
}
if (pq.isEmpty()) {
return -1;
}
fuel += pq.deQueue();
ans++;
}
};
以上优先队列的实现，插入时间为O(1)，出队时间为O(N)。如果对出队时间要求较高，可以用堆来实现，类似堆排序，出队时间优化至O(logN)。
/**
* 优先级队列类
*/
var PQueue = function() {
//记录数组
this._records = [];
//优先级比较方法
this._cmp_func = function(a, b) {
return b - a;
};
};
//堆向上调整
PQueue.prototype._heapUpAdjust = function(index) {
var records = this._records;
var record = records[index];
var cmp_func = this._cmp_func;
while (index > 0) {
var parent_index = Math.floor((index - 1) / 2);
var parent_record = records[parent_index];
if (cmp_func(record, parent_record) < 0) {
records[index] = parent_record;
index = parent_index;
} else {
break;
}
}
records[index] = record;
};
//堆向下调整
PQueue.prototype._heapDownAdjust = function(index) {
var records = this._records;
var record = records[index];
var cmp_func = this._cmp_func;
var length = records.length;
var child_index = 2 * index + 1;
while (child_index < length) {
if (child_index + 1 < length && cmp_func(records[child_index], records[child_index + 1]) > 0) {
child_index ++;
}
var child_record = records[child_index];
if (cmp_func(record, child_record) > 0) {
records[index] = child_record;
index = child_index;
child_index = 2 * index + 1;
} else {
break;
}
}
records[index] = record;
};
//将记录插入队列
PQueue.prototype.enQueue = function(record) {
var records = this._records;
records.push(record);
this._heapUpAdjust(records.length - 1);
};
//删除并返回队头记录
PQueue.prototype.deQueue = function() {
var records = this._records;
if (!records.length)
return undefined;
var record = records[0];
if (records.length == 1) {
records.length = 0;
} else {
records[0] = records.pop();
this._heapDownAdjust(0);
}
return record;
};
//判断队列是否为空
PQueue.prototype.isEmpty = function() {
return this._records.length == 0;
};
