leetCode周赛89解题报告 javascript

 

比赛地址

https://leetcode.com/contest/weekly-contest-89 

852. Peak Index in a Mountain Array

我们把符合下列属性的数组 A 称作山脉：

• A.length >= 3
• 存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

 

示例 1：

输入：[0,1,0]
输出：1

示例 2：

输入：[0,2,1,0]
输出：1

 

提示：

1. 3 <= A.length <= 10000
2. 0 <= A[i] <= 10^6
3. A 是如上定义的山脉

题解：条件说明给定数组已经满足山脉、只要找到位置高于左右两边的点即是峰顶。

 

/**
 * @param {number[]} A
 * @return {number}
 */
var peakIndexInMountainArray = function(A) {
    for (var i = 1; i < A.length - 1; i++) {
        if (A[i - 1] < A[i] && A[i] > A[i + 1]) {
            return i;
        }
    }
};

 

 

 

 

 

853. Car Fleet

N  辆车沿着一条车道驶向位于 target 英里之外的共同目的地。

每辆车 i 以恒定的速度 speed[i] （英里/小时），从初始位置 position[i] （英里） 沿车道驶向目的地。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。

此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。

车队 是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。

即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。

 

会有多少车队到达目的地?

 

示例：

输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
解释：
从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。

提示：

 

1. 0 <= N <= 10 ^ 4
2. 0 < target <= 10 ^ 6
3. 0 < speed[i] <= 10 ^ 6
4. 0 <= position[i] < target
5. 所有车的初始位置各不相同。

题解：贪心算法，中等难度。将所有车按初始位置排序，终点近的排在前面，依次遍历计算出到达目的地所需时间，如果追不上前面车辆，则刷新前面最慢车队的时间并且 增加车队。

 

/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function(target, position, speed) {
    if (!position || position.length == 0) {
        return 0;
    }
    var cars = [];
    for (var i = 0; i < position.length; i++) {
        cars.push({pos: position[i], spd: speed[i]});
    }
    cars.sort((a,b)=>b.pos-a.pos); // 按初始位置排序，终点近的排在前面
    var maxt = (target - cars[0].pos) / cars[0].spd;
    var ans = 1;
    for (var i = 1; i < cars.length; i++) {
        var t = (target - cars[i].pos) / cars[i].spd;
        if (maxt < t) { // 如果追不上前面车辆
            maxt = t; // 刷新前面最慢车队的时间
            ans++; // 增加车队
        }
    }
    return ans;
};

 

 

 

 

 

855. Exam Room

在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。

当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。请确保每次调用 ExamRoom.leave(p) 时都有学生坐在座位 p 上。

 

示例：

输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出：[null,0,9,4,2,null,5]
解释：
ExamRoom(10) -> null
seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
seat() -> 9，学生最后坐在 9 号座位上。
seat() -> 4，学生最后坐在 4 号座位上。
seat() -> 2，学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5，学生最后坐在 5 号座位上。

 

提示：

1. 1 <= N <= 10^9
2. 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
3. 调用 ExamRoom.leave(p) 时需要确保当前有学生坐在座位 p 上。

题解：中等难度。由于座位的数据量为10^9，不可用数组完整表示每个位置是否有人，故只能按顺序存储已经有人的座位。插入时，查找空隙最大的相邻有人的两个位置，取得中间位置坐下一个人；学生离场时同样由于座位可能较多、二分查找位置是必要的。

 

/**
 * @param {number} N
 */
var ExamRoom = function(N) {
    this.n = N;
    this.arr = [];
};

/**
 * @return {number}
 */
ExamRoom.prototype.seat = function() {
    var gas = this.arr[0];
    var index = 0;
    var ans = 0;
    for (var i = 1; i < this.arr.length; i++) {
        var g = (this.arr[i] - this.arr[i - 1]) >> 1;
        if (gas < g) {
            gas = g;
            index = i;
            ans = this.arr[i - 1] + ((this.arr[i] - this.arr[i - 1]) >> 1);
        }
    }
    var g = this.n - 1 - this.arr[this.arr.length - 1];
    if (gas < g) {
        gas = g;
        index = this.arr.length;
        ans = this.n - 1;
    }
    this.arr.splice(index, 0, ans);
    return ans;
};

/** 
 * @param {number} p
 * @return {void}
 */
ExamRoom.prototype.leave = function(p) {
    var f = 0;
    var r = this.arr.length - 1;
    while(f < r) {
        var m = f + ((r - f) >> 1);
        if (this.arr[m] < p) {
            f = m + 1;
        }
        else {
            r = m;
        }
    }
    if (this.arr[r] == p) {
        this.arr.splice(r, 1);
    }
};

/** 
 * Your ExamRoom object will be instantiated and called as such:
 * var obj = Object.create(ExamRoom).createNew(N)
 * var param_1 = obj.seat()
 * obj.leave(p)
 */

 

 

 

 

 

854. K-Similar Strings

如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K（K 为非负整数）。

给定两个字母异位词 A 和 B ，返回 A 和 B 的相似度 K 的最小值。

 

示例 1：

输入：A = "ab", B = "ba"
输出：1

示例 2：

输入：A = "abc", B = "bca"
输出：2

示例 3：

输入：A = "abac", B = "baca"
输出：2

示例 4：

输入：A = "aabc", B = "abca"
输出：2

 

提示：

1. 1 <= A.length == B.length <= 20
2. A 和 B 只含有集合 {'a', 'b', 'c', 'd', 'e'} 中的小写字母。

题解：困难难度，但看数据量貌似不大，故考虑暴力查找。如果交换两位置的字母，两位置都与目标串匹配则称此次交换为完美交换，若有完美交换则直接交换则直接交换，若无完美交换则将所有该位置需要的字母依次交换尝试，选取次数较少的方案。注意递归暴力求解时候每层计算完成需要将交换过的位置还原，以便正确的递归回溯查找。

 

/**
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var kSimilarity = function(A, B) {
    var a = A.split("");
    var b = B.split("");
    var dfs = function(i) {
        if (i == a.length) {
            return 0;
        }
        if (a[i] == b[i]) {
            return dfs(i + 1);
        }
        // 若有完美交换则直接交换则直接交换
        var ans = a.length;
        for (var j = i + 1; j < a.length; j++) {
            if (a[i] == b[j] && a[j] == b[i]) {
                a[i] = b[i];
                a[j] = b[j];
                ans = 1 + dfs(i + 1);
                a[i] = b[j];
                a[j] = b[i];
                return ans;
            }
        }
        // 若无完美交换则将所有该位置需要的字母依次交换尝试，选取次数较少的方案
        var temp = a[i];
        a[i] = b[i];
        for (var j = i + 1; j < a.length; j++) {
            if (a[j] == b[i]) {
                var aj = a[j];
                a[j] = temp;
                ans = Math.min(ans, 1 + dfs(i + 1));
                a[j] = aj;
            }
        }
        a[i] = temp;
        return ans;
    }
    return dfs(0);
};