笔试:4.6美团笔试(硬件开发方向)

发布于:2024-04-07 ⋅ 阅读:(113) ⋅ 点赞:(0)

二十道选择两道算法题。

选择就不说了,硬件方面目前了解较少。

两道算法题都过了,第一题很简单没有什么好讲的。

第二题看着题目以为会很复杂,没想到一遍过。

小美有一个由 n 个互不相等的正整数构成的数组 a,但她一不小心把 a 弄丢了,他想要重新找到 a。

好在她并不是一无所有,她还记得以下有关 a 的信息:

1. 他完全记得数组 b 的样子,并且 b 是数组 a 删除了某个 a_i 后,剩余的部分做前缀和并打乱的结果。
2. 他完全记得数组 c 的样子,并且 c 是数组 a 删除了某个 a_j 后,剩余的部分做前缀和并打乱的结果。
(保证两次删除的 a_i 和 a_j 不是同一个 a 中的元素)。

请你帮她还原出 a 数组吧。

补充:前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。

输入描述
输入包含三行。
第一行一个正整数 n\ (3 \leq n \leq 10 ^ 5),表示数组 a 的长度。
第二行 n - 1 个正整数 b_i\ (1 \leq b_i \leq 10 ^ {14}),表示题中所述数组 b。
第二行 n - 1 个正整数 c_i\ (1 \leq c_i \leq 10 ^ {14}),表示题中所述数组 c。
(输入保证有唯一解)

输出描述
输出一行 n 个整数,表示你还原出的 a 数组。
4
8 18 14
15 9 1
输出

1 8 6 4
说明
b 数组是 a 中删除了 a[1] 后,求前缀和,再打乱得到的。
c 数组是 a 中删除了 a[4] 后,求前缀和,再打乱得到的。

思路:所谓前缀和,一定是递增的,所以题目中把打乱了完全没有用,通过排序就可以找回打乱前的数组。然后从后往前用当前前缀和减去前一个前缀和即可得到当前数字。两次操作后我们就得到了b和c的原始数组,即删除了一个a中数字的数组。

注意:此时的b,c数组和a的顺序完全一样,只是删除了一个数字。利用这一点我们才可以按照正确的顺序求出a数组。

接下来只需要找到被删除的那个数字并且插入原来数组即可。

接下来使用两个指针指向b,c,如果指针值相等则判断下一个,如果不等则说明在当前位置b,c中有一个删除了a中的一个数字。在删除的数组中,当前指针所指的数据必然为另一个数组中下一个数据(关于这点下面详细解释),将另一个数组中的数据插入删除的数组即可。举个例子1,2,3,4,5,删除2、4,自己想一想就知道了。

关于上面的解释:题目说保证有唯一解,所以删除的两个数字必然不可能连续,如果连续,则我们不可能知道这两个数字在原数组中的顺序,不知道谁先谁后。所以如果发现当前数组中被删了一个数字,那么下一个一定没有被删,两数组中一定都有该数字,只需要通过一个判断与下一个数字比较看哪个数组被删除了即可。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<long long>a(n), b(n - 1), c(n - 1);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        cin >> c[i];
    }
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    for (int i = n - 2; i >= 1; i--)
    {
        b[i] = b[i] - b[i - 1];
        c[i] = c[i] - c[i - 1];
    }
    int pb = 0, pc = 0;
    while (pb < n - 1 && pc < n - 1)
    {
        if (b[pb] == c[pc])
        {
            pb++;
            pc++;
            continue;
        }
        if (b[pb + 1] == c[pc])
        {
            c.insert(c.begin() + pc, b[pb]);
            break;
        }
        else if (c[pc + 1] == b[pb])
        {
            b.insert(b.begin() + pc, c[pc]);
            break;
        }
        else
        {

        }
    }
    if (b.size() == n)
    {
        for (int i = 0; i < n; i++)
        {
            cout << b[i] << ' ';
        }
    }
    else if (c.size() == 0)
    {
        for (int i = 0; i < n; i++)
        {
            cout << c[i] << ' ';
        }
    }
    else
    {

    }
}


网站公告

今日签到

点亮在社区的每一天
去签到