`
xingbinice
  • 浏览: 42022 次
  • 性别: Icon_minigender_1
  • 来自: 海南
社区版块
存档分类
最新评论

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 的相似度为 KK 为非负整数)。

给定两个字母异位词 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);
};

 

 

0
0
分享到:
评论

相关推荐

    leetcode周赛难度-leetcode:leetcode

    周赛难度LeetCode 题解 一题目列表 细绳 # 标题 标签 困难 解决方案 描述 1 细绳 中等的 2 细绳 中等的 3 细绳 中等的 4 细绳 中等的 DP # 标题 标签 困难 解决方案 描述 1 DP 中等的 2 DP 中等的 3 DP 中等的 4 DP ...

    leetcode周赛积分-leetcode:leetcode刷题记录

    leetcode周赛积分 leetcode 推荐 No. Problems Solutions Tag 32 DP, Stack 周赛 (weekly-content) No. Solutions Completion Date 2020.07.05 刷题记录 No. Problems Solutions Completion Date 329 2020.07.26 16 ...

    leetcode周赛有原题吗-leetcode:leetcodepractice(Java),包含《剑指offer》和少量《leetbook》

    leetcode周赛有原题吗 leetcode 题号 题目 难度 tag 两数之和 简单 两数相加 中等 无重复字符的最长子串 中等 : 最长回文子串 中等 字符串转换整数 (atoi) 中等 盛最多水的容器 中等 罗马数字转整数 简单 0014 最长...

    leetcode周赛难度-leetcode:我的leetcode代码

    leetcode 周赛难度力码 的代码参考。 当然,我也会每周更新一些关于这些问题的注释,但不是全部。 欢迎开 issue 讨论! 要求 Xcode C++ 11 问题 清单(链表) ID 标题 困难 解决方案 笔记 2 中等的 19 中等的 21 简单...

    leetcode周赛153-LeetCode-Contest:LeetCode周赛题解

    leetcode周赛153 LeetCode-Contest LeetCode 周赛题解 已完成比赛 周赛 比赛场次 【A】题 【B】题 【C】题 【D】题 1201 1202 1203 1207 1208 1209 1210 双周赛 比赛场次 【A】题 【B】题 【C】题 【D】题 1246 初始...

    leetcode周赛排名没了-rust4leetcode:使用Rust刷完leetcode

    leetcode周赛排名没了 定个小目标:用Java、Python、Go、Rust、C++、js六种语言把leetcode刷一遍 为什么要创建此repo? 为了自己。leetcode上好的讲解数不胜数,大佬的解法巧妙绝伦,再写题解给别人看那就是班门弄斧...

    leetcode周赛积分-Leetcode:通过GitHub记录Leetcode的过程

    周赛积分按 issue 记录 Leetcode 的流程 每周比赛 日期 11/10/2019 11/16/2019 11/17/2019 12/8/2019 12/15/2019 12/22/2019 数量 问题 等级 话题 日期 409 简单的 Hash Table 10/25/2019 290 简单的 Array Two ...

    leetcode周赛难度-Weekly-Leetcode-with-STCA:每周LC

    周赛难度每周-Leetcode-with-MS 业主:兰 时间:从 19.12.11 Week6 动态规划 指数 标题 解决方案 验收 困难 70 √ 45.6% 简单的 198 √ 41.5% 简单的 303 √ 40.8% 简单的 64 √ 49.7% 中等的 309 √ 45.2% 中等的 ...

    leetcode周赛奖品-Lemaj:Lemaj-提高编码技能和参加比赛的网站

    leetcode 周赛奖品Lemaj - 提高编码技能和参加比赛的网站 Development on Lemaj has just started. Everything is in flux Lemaj 是什么? Lemaj立志成为一个学习编程的网站,它每周都会举办比赛,任何人都可以参加...

    leetcode周赛难度-leetcode-learn::pencil2:在Scala中总结每周练习

    leetcode 周赛难度LeeCode-Study ======== 总结 Scala 每周练习(每周 5 个问题)。 参考 不。 标题 解决方案 困难 标签 地位 001 简单的 Mapping 完毕 002 中等的 LinkedList 完毕 003 中等的 Mapping 完毕 005 ...

    leetcode周赛得分3-mstcBlog:微博

    周赛是LeetCode举办的一种定期比赛,参赛者在限定时间内解决一系列问题,并根据解题质量和速度获得分数。 描述 "leetcode周赛得分3" 很简洁,表明这是作者参加的第三次LeetCode周赛的结果或者是相关记录。可能包含...

    leetcode周赛191-leetcode:一天一天起来

    【标题】"LeetCode周赛191-逐步提升算法能力" 在LeetCode的周赛191中,参赛者们面临了一系列挑战性的算法题目,旨在帮助他们提升编程技巧和解决复杂问题的能力。LeetCode是一个知名的在线编程平台,提供丰富的算法...

    (LeetCode 解题集之 JavaScript & TypeScript 版).zip

    Solutions collection of LeetCode submissions in JavaScript & TypeScript (LeetCode 解题集之 JavaScript & TypeScript 版).zip

    leetcode周赛积分-LEETCODE:leetcode的问题

    周赛积分LEETCODE 来自 Leetcode 的问题。 您可以找到有关算法和数据结构的一些详细信息。 数据结构 地图 问题编号 名称 语境 001 二和 350 两个数组的交集Ⅱ , 两个指针 简单的 015 三和 设置,地图, 中等的 3 无...

    leetcode周赛难度-leetcode:leetcode项目的问题解决进度

    周赛难度leetcode 这是用于跟踪我在项目中解决问题的进度的存储库。 在30_day_challenge文件夹中,我上传了我的解决方案和其他有趣的每月挑战代码。 在weekly_contest或biweekly_contest文件夹上传我的解决方案,我...

    leetcode周赛194-leetcode-contests:leetcode竞赛

    leetcode 周赛194 力码竞赛 固定 每周比赛 197: 每周比赛 196: 每周竞赛 195: 每周比赛 194: 每周竞赛 193:

    leetcode卡-leetcode-weekly-contest-186:第186届LeetCode周赛

    leetcode卡leetcode-weekly-contest-186 第 186 届 LeetCode 周赛 问题清单 拆分字符串后的最大分数 Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty...

    Leetcode:LeetCode解题代码

    《LeetCode解题代码——C++篇》 LeetCode是一个广受程序员喜爱的在线平台,它提供了大量的编程挑战,旨在帮助开发者提升算法和数据结构能力。这个资源包中包含的是用C++语言编写的LeetCode题目的解决方案。通过深入...

    我在leetcode上的解题记录。(C++版).zip

    【标题】"我在LeetCode上的解题记录"指的是作者在LeetCode这个在线编程平台上通过C++语言解决了一系列算法问题,并将这些解决方案整理成一个压缩包文件。LeetCode是一个热门的平台,它提供了一系列的编程挑战,旨在...

Global site tag (gtag.js) - Google Analytics