美团春招前端 2023.3.25 笔经

选择题只记录了部分的题目,并且只是回忆部分题目内容。

1.计算机基础部分 选择题(20 * 2分)

  • Linux 查看ip 指令
  • 几级封锁能够避免重复读取
  • UDP伪首部的第四个字段
  • Oracel数据库的最小存储单元是什么
  • “abba”与”aa”匹配几趟才判断匹配失败
  • 一个数组按照顺序查找,平均查找长度是多少
  • 给定元素出现频率,求一个元素的哈夫曼树的编码
  • dijkstra 算法某一步骤的集合
  • LRU算法
  • 哪个是O(n + m)的字符串匹配算法
  • MongoDB的存储模型
  • POP3…邮件…加密端口
  • 设计模式 假设一个对象发送请求,它往往是动态变化的,这时候用什么设计模式

2.行测 选择题(10 * 2分)

这部分都不记得题目大多数内容了,只写出部分内容没有什么价值,略过。

3.编程题

列车进出站问题

类似判断给定入栈和出栈元素顺序,判断出栈顺序的是否正确的问题。

输入:

  • T(1 ≤ T ≤ 10),表示有多少组数据,之后有T * 3行:

给定多组数据,每组数据有三行数据:

  • n 火车进站和出站总数
  • x1, x2, ... , xn 进站列车的数据
  • y1, y2, ... , yn 列车出站的问题

n 的数据不记得是5W还是10W了,总之不影响能O(n) 解决。

输出:

YesNo ,如果进站和出站数据符合入栈和出栈顺序的一种可能,则输出Yes ,否则输出No

测试用例:

输入
3
3
1 2 3
1 2 3
3
1 2 3
3 2 1
3
1 2 3
3 1 2
输出
Yes
Yes
No

AC代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cstdio>

using namespace std;

// 忘记数据是5W还是10W了,总之都是O(n)解决
const int N = 100010;

int T;
int n;
int x[N], y[N];

int main()
{
    scanf("%d", &T);
    while(T -- ){
        scanf("%d", &n);
        for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
        for(int i = 0; i < n; i ++) scanf("%d", &y[i]);
        
        int point = 0;
        bool ans = false;
        stack<int> stk;
        for(int i = 0; i < n; i ++) {
            // 每次迭代都把这个入栈元素push进去
            stk.push(x[i]);
            // 当栈顶元素和出栈指针匹配则弹出,并且指针指向下一个出栈元素
            // 直到栈空或者不等于出栈元素
            while(stk.size() && stk.top() == y[point]) {
                point ++;
                stk.pop();
            }
        }
        // 当栈里面还有元素的时候,说明卡死了,栈弹不出去,肯定是不符合顺序的
        if(stk.size() == 0) ans = true;
        if(ans) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

背包最多能装的巧克力个数

给你n 个巧克力和m 个背包,每个巧克力是正方形的,占用的背包大小为这个巧克力的面积,求每个背包最多能装下多少个巧克力。

每个查询不影响后面的查询,前面装了某些巧克力,这些巧克力也能用于下一次查询。

输入:

三行数据

  • n 巧克力的个数,m 背包的个数
  • n 个数据,每个巧克力的边长
  • m 个数据,背包的大小

nm 的数据范围都不大于5W,巧克力的边长都不大于1W,背包的大小都不大于1e18

问最多能装下多少个巧克力,那肯定是先找最小的那部分巧克力,装到装不下为止。

所以先把巧克力的边长进行排序,然后计算出前缀和,每个前缀和表示当前多少个最小的巧克力大小加起来的总和,这样也要求数组是升序的,所以必须先进行排序。

当算出前缀和之后,我们就可以根据前缀和进行二分查找,找到一个小于或等于背包大小的一个最大的前缀和下标,因为已经算好的前缀和就是前多少个最小的巧克力的大小总和,所以这个下标就是能装多少个最大的巧克力。同时前缀和是升序的,所以可以用二分查找来找到答案。

测试用例

输入
5 5
1 2 2 4 5
1 3 7 9 15
输出
1 1 2 3 3

AC代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 50010;

// a巧克力,q背包
int a[N], sum[N];
LL q[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%lld", &q[i]);
    
    sort(a, a + n);
    for(int i = 1; i <= n; i ++) {
        sum[i] += sum[i - 1] + a[i - 1] * a[i - 1];
    }
    
    for(int i = 0; i < m; i ++) {
        int l = 0, r = n;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(sum[mid] > q[i]) r = mid - 1;
            else if(sum[mid] == q[i]) {
                r = mid;
                break;
            } else l = mid + 1;
        }
        
        printf("%d\n", r);
    }
    
    return 0;
}

总结

体验很好,算法题不难(可能也是运气好出到的算法都会吧),都是比较基础的算法,不像某电子股票跌了出买股票😅,就是计算机基础没准备太多做的不好,填了再考一次再多攒点经验。

#23届找工作求助阵地##我的求职思考#
全部评论
佬后续什么时候有结果?
点赞 回复 分享
发布于 2023-03-28 12:09 甘肃

相关推荐

11-24 11:23
门头沟学院 C++
点赞 评论 收藏
分享
object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
11-01 08:48
门头沟学院 C++
伤心的候选人在吵架:佬你不要的,能不能拿户口本证明过户给我。。球球了
点赞 评论 收藏
分享
评论
点赞
10
分享
牛客网
牛客企业服务