美团春招前端 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) 解决。

输出：

Yes 或No ，如果进站和出站数据符合入栈和出栈顺序的一种可能，则输出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 个数据，背包的大小

n 和m 的数据范围都不大于5W，巧克力的边长都不大于1W，背包的大小都不大于1e18 。

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

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

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

测试用例

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