【实习】记一次笔试

前言

四道算法题，30 分钟，都是 LeetCode 的简单和中等题

第一题 Ac 80%，第二题没做出来，剩下两题都 Ac 100%

睡完午觉刚起床就做了，可能是脑子不太清醒，感觉应该可以全做出来的

太菜了我 😭

第一题 删除字符串

描述

给出两个字符串 str 和 sub，你的任务是在 str 中完全删除那些在 sub 中存在的字符。

样例

输入: str="They are students"，sub="aeiou"
输出: "Thy r stdnts"

代码

做的时候脑抽了没 Ac 100%，结束后重新看了一下，直接用正则表达式匹配，能 Ac 100%，但是速度太慢了，应该有更好的方法。

CharacterDeletion(str, sub) {
    let modeStr='['
    for(let i = 0; i < sub.length; i++) {
        modeStr += sub.charAt(i) + '|';
    }
    modeStr += ']';
    let reg = new RegExp(modeStr, 'gm');
    str = str.replace(reg, '');
    return str;
}

第二题 购买通行证

描述

亚历克斯计划参观博物馆，并在柜台购买相同的通行证。管理员决定不出售团体通行证，一次只提供一张通行证。如果访客需要一张以上的通行证，他/她必须再次重新排队到柜台并购买下一张通行证。亚历克斯想购买许多通行证。访客顺序和每位访客需要的通行证数量是已知的，亚历克斯需要多少时间才能买到所有的通行证？Alex 在队列中的位置将被给定，每次交易需要 1 个时间单位。可以忽略每次转到行后面所需的时间。

样例

输入: arr=[1,2,5],k=1
输出: 4
解释:
有3个人 0,1,2 在排队。亚历克斯的编号是1
第一个时间点，队列为0(1)<-1(2)<-2(5)，编号0获得门票。
第二个时间点，队列为1(2)<-2(5) 亚克斯获得门票，并返回队伍最末端
第三个时间点，队列为2(5)<-1(1) 编号2获得门票，并返回队伍最末端
第四个时间点，队列为1(1)<-2(4) 亚克斯获得门票，他已经买到了所需要的所有门票

代码

这道题一开始没看懂，后来看懂了有思路但没做出来，结束后又花了点时间去做，最简陋的实现，时间复杂度没眼看

buyPasses(arr, k) {
    let time = 0;
    let i = 0;
    while (1) {
        if (arr[i]) {
            arr[i]--;
            time++;
            if (i === k && !arr[i]) {
                return time;
            }
        }
        i++;
        if (i === arr.length) {
            i = 0;
        }
    }
    return time;
}

下面是题解中的做法，没看懂……

buyPasses(arr, k) {
    let time = 0;
    arr.forEach((el, i) => {
        if(i <= k) {
            time += el >　arr[k] ? arr[k] : el;
        } else {
            time += el >　arr[k]-1 ? arr[k]-1 : el;
        }
    });
    return time;
}

第三题 寻找峰值

描述

给定一个整数数组(size 为n)，其具有以下特点：

• 相邻位置的数字是不同的
• A[0] < A[1] 并且 A[n - 2] > A[n - 1]

假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。

• 数组保证至少存在一个峰
• 如果数组存在多个峰，返回其中任意一个就行
• 数组至少包含 3 个数

样例

输入：A = [1, 2, 1, 3, 4, 5, 7, 6]
输出：1
解释：返回任意一个峰顶元素的下标，6也同样正确。

代码

这是最直观的实现，时间复杂度还是比较高

findPeak(A) {
    for(let i = 1; i < A.length-1; i++) {
        if(A[i] > A[i-1] && A[i] > A[i+1] ) {
            return i;
        }
    }
}

第四题 数组划分

描述

给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：

• 所有小于k的元素移到左边
• 所有大于等于k的元素移到右边

返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。

样例

输入：nums = [], k = 9
输出：0
解释：空数组，输出0

输入：nums = [3,2,2,1], k = 2
输出：1
解释：真实的数组为[1,2,2,3].所以返回 1

代码

题目要求真正的划分数组，而不是仅仅计算比k小的整数，也不难，把>=k的数push到另一个数组，最后在合并就好了

partitionArray(nums, k) {
    let small = [];
    if(nums.length) {
        nums.forEach(el => {
            if(el < k) {
                small.push(el);
            }
        });
        return small.length;
    }
    return 0;
}

也可以先排序sort，如何使用indexOf查找 k 也行

partitionArray(nums, k) {
    if(nums.length) {
        nums.sort((a, b) => a - b);
        if(k < nums[0]) {
            return 0;
        } else if(k > nums[nums.length-1]) {
            return nums.length;
        }
        let index = nums.indexOf(k);
        if(index === nums.length-1) {
            return 0;
        }
        return index;
    }
    return 0;
}