leetCode周赛93解题报告 javascript

比赛地址

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. 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. 1 <= A.length = B.length <= 10000
2. 0 <= A[i] <= 10^9
3. 0 <= 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. 1 <= target, startFuel, stations[i][1] <= 10^9
2. 0 <= stations.length <= 500
3. 0 < 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;
};