记一次笔试

AmsChan ... 2021-09-29 笔试
  • 笔试
大约 4 分钟

# 前言

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

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

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

太菜了我 😭

# 第一题 删除字符串

# 描述

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

# 样例

输入: str="They are students",sub="aeiou"
输出: "Thy r stdnts"
1
2

# 代码

做的时候脑抽了没 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;
}
1
2
3
4
5
6
7
8
9
10

# 第二题 购买通行证

# 描述

亚历克斯计划参观博物馆,并在柜台购买相同的通行证。管理员决定不出售团体通行证,一次只提供一张通行证。如果访客需要一张以上的通行证,他/她必须再次重新排队到柜台并购买下一张通行证。亚历克斯想购买许多通行证。访客顺序和每位访客需要的通行证数量是已知的,亚历克斯需要多少时间才能买到所有的通行证?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) 亚克斯获得门票,他已经买到了所需要的所有门票
1
2
3
4
5
6
7
8

# 代码

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

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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;
}
1
2
3
4
5
6
7
8
9
10
11

# 第三题 寻找峰值

# 描述

给定一个整数数组(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也同样正确。
1
2
3

# 代码

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

findPeak(A) {
    for(let i = 1; i < A.length-1; i++) {
        if(A[i] > A[i-1] && A[i] > A[i+1] ) {
            return i;
        }
    }
}
1
2
3
4
5
6
7

# 第四题 数组划分

# 描述

给出一个整数数组 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
1
2
3
4
5
6
7

# 代码

题目要求真正的划分数组,而不是仅仅计算比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;
}
1
2
3
4
5
6
7
8
9
10
11
12

也可以先排序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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16