2018 年美团在线笔试编程题解题报告

Bittersweet2018-3-23
本文最后更新于 545 天前(2018-3-23),其中的信息可能已经有所发展或者不再适用于现阶段。
本文全长 1241 字,全部读完大约需要 4 分钟。

最近各大 IT 企业的实习招聘都已如火如荼的开展,笔者本着“广撒网”的战略投了很多家公司的简历。现在不少知名IT公司(例如阿里、华为、美团)的笔试都已经转移到了线上来进行。笔者于昨晚参加了美团的在线笔试,相比于之前阿里和华为的笔试,美团的考查范围更广,难度也稍微高一些(会问很多计算机领域的基础知识,计网、操作系统、数据结构、算法甚至数据库都有涉及)。闲话不多说,我们接下来就一起看一下美团的两道编程题:

【笔者原创,仅供参考,若有纰漏,欢迎指正】

第一题 字符串距离

问题描述:

给定两个字符串 S 和 T,设 |S| 和 |T| 分别表示 S 和 T 的长度,保证 S 和 T 只包含两种字符a和b,并且 1 <= |T| <= |S| <= N,【N是一个不是很大的整数,笔者忘了具体的数据范围(逃】。定义两个等长字符串的距离为相应位置的不同字符个数的和,例如”abb”和”bab”的距离是 2(第一个字符、第二个字符不同)。两个不等长字符串 S 和 T,对于 S 字符串,它和 T 一样长的连续子串总共有 |S| – |T| + 1 个,这些连续子串和 T 的距离之和就是 S 和 T 的距离,例如“abba”和“ab”,考察 abba 的所有长度为 2 的连续子串,有 ab bb ba,它们和 ab 的距离分别为 0 1 2,故答案为 0+1+2=3。现在给定 S 和 T,求它们的距离。

输入格式:

共两行,第一行是 S,第二行是 T。

输出格式:

一个整数,代表 S 和 T 的距离。

解:

最暴力的做法,两层 for 循环,O(n²),C/C++(时限 2s)能过 70%, Java(时限 4s)能过 90%。。。

优化一下,我们转化思路,以T中的每一个字符对最终结果的贡献度来看这道题。下面我们设 S=aaabbb,T=babb,则可以用下图中的方法来计算答案:

Screenshot_20180323_140213.png

看!如果我们能在 O(1) 的时间内得出T中每个字符的“贡献度”,那么整个算法将是 O(n) 的(只需要遍历一遍 T 即可)!根据这个思路,我们首先形式化的定义一下“贡献度”:设 w=|S|-|T|+1,则 T 中第 i 个字符(i=0…|T|-1)的贡献度 F(i)=S[i…i+w) 这个子串里所有和 T[i] 不同的字符数目之和。仔细观察 F(i) 的定义,我们发现,问题的关键变成了快速地求出串 S 中某一特定连续子串中包含某种字符的数目。只要我们能在不多于 O(n) 的时间内求出这一数目,我们就可以在线性时间内得到整个问题的解。

那么如何求出串 S 中某一特定连续子串中包含某种字符的数目呢?相信聪明的读者已经发现,使用动态规划(DP)的思想,可以通过线性时间内的预处理得到这个数据。我们定义两个数组 a[i] 和 b[i],分别表示 S 串长度为 i 的前缀含有 a 和含有 b 的个数。则可以得到:

$$ a[i+1]= \begin{cases} a[i]+1&S[i]=\text{'a'}\\ a[i]& S[i]\neq\text{'a'} \end{cases} $$$$ b[i+1]= \begin{cases} b[i]+1&S[i]=\text{'b'}\\ b[i]& S[i]\neq\text{'b'} \end{cases} $$

根据这个递推规则我们就可以在 O(n) 时间内通过对 S 的预处理得到 a[] 和 b[],并且在常数时间内通过计算 a[i+w] – a[i] 得到 S[i…i+w) 中字符 a 的数目(b 同理)。到此问题已解决,我们得到了时间复杂度为 O(n) 的算法,附上代码:

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 100010;

int main()
{
    string s, t;
    cin >> s >> t;
    long long int ans = 0;
    long long int w = s.length() - t.length() + 1;
    long long int a[MAXN], b[MAXN];
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    a[0] = b[0] = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        if (s[i] == 'a')
        {
            a[i + 1] = a[i] + 1;
            b[i + 1] = b[i];
        }
        else
        {
            a[i + 1] = a[i];
            b[i + 1] = b[i] + 1;
        }
    }
    for (int i = 0; i < t.length(); ++i)
    {
        if (t[i] == 'a')
            ans += b[i + w] - b[i];
        else
            ans += a[i + w] - a[i];
    }
    cout << ans << endl;
    return 0;
}

第二题 最小整数

问题描述:

给定一串数字字符,求使用这些数字字符拼不出来的最小整数。

输入格式:

一串数字字符

输出格式:

一个整数

样例输入 1:

123456789

样例输出 1:

10

样例输入 2:

55666777788

样例输出 2:

1

解:

仔细研究一些样例之后,我们不难找到如下规律:按照 0987654321 的顺序寻找给定个数最少的那个数字字符,如果最少的个数对应多个数字字符,那就应该让这个数字字符尽可能靠近上述顺序的右侧,不妨设这样找到的数字字符是 c(c = '0'…'9'),它的个数是 F[c](0 <= F[c] <= N,N 为给定串长度上限)。则可以分为两种情况:

  1. c 是 '0',这代表 '1'…'9' 都至少有一个,并且 F[0] 是 F[0…9] 之中最小的,那么显然此时最小组不成的整数是“1后面加上 F[0]+1 个 0 组成的整数”。
  2. c 不是'0',这代表 '1'…'9' 中至少缺少一种数字字符(且 c 就是缺少的那些数字字符中最小的那个),那么显然此时最小组不成的整数是“F[c]+1 个 c 组成的整数”。

由此,可以写出解题代码如下:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int F[10];
    char t;
    memset(F, 0, sizeof(F));
    while (cin >> t)
    {
        ++F[t - '0'];
    }
    int c = 0;
    for (int i = 9; i >= 1; --i)
    {
        if (F[i] <= F[c])
            c = i;
    }
    if (c == 0)
    {
        cout << 1;
        for (int i = 0; i < F[c] + 1; ++i)
            cout << 0;
    }
    else
    {
        for (int i = 0; i < F[c] + 1; ++i)
            cout << c;
    }
    cout << endl;
    return 0;
}
除特殊说明以外,本网站文章采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。