美团秋招笔试五道编程题（2021-08-22）

恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

第一道：小美的AI学习（100%） 参考代码：

#include 

using namespace std;
using ll     = long long;
using pii    = pair;
const ll mod = 1e9 + 7;

vector color, weight;
vector v;

void dfs(int i, int fa)
{
    if (v[i].size() == 1 && v[i][0] == fa)
        return;
    map mp;
    int Max = 0, sum = weight[i];
    for (auto j : v[i])
    {
        if (j == fa)
            continue;
        dfs(j, i);
        Max = max(Max, mp[color[j]] += weight[j] + 1);
    }
    weight[i] = Max;
}

int main()
{
    int n, k;
    cin >> n >> k;
    color.resize(n);
    weight.resize(n);
    v.resize(n);

    for (int i = 0; i > c;
        color[i] = c;
    }

    for (int i = 1; i > p;
        v[i].push_back(p - 1);
        ***bsp;- 1].push_back(i);
    }

    for (int i = 0; i > weight[i];
    }

    dfs(0, -1);

    for (int i = 0; i  （2+1）*2 = 6
输入 '(()())(())' -->（1+2*2）*（2+1） = 15

思路解析

假设测试用例为：（）（（）（））（（）） 第一步：找到最外层的括号对，可以看到最外层的括号有三对：（）、（（）（））、（（）） 第二步：取出最外层的括号对里面的序列，分别为：空、（）（）、（） 第三步：递推公式: f( “（）（（）（））（（））” ) = ( f( “空” ) +1 ) * ( f( “（）（）” ) +1 ) * ( f( “（）” ) +1 )

再例如s = ‘(()))()’，n = len(s) 步骤为 检测stk后面是否有连续的两个正数，如果有，这两个正数应该“相碰”（相乘）， 因为两个正数挨着，说明这两个完整的括号部分挨着，因此必为相乘操作； stk.size()-2 , stk.size()-1，就是后两位的idx， 相乘之后存在stk.size()-2的位置，因为最后一位需要被pop掉。

此时stk [-1, 4]，如果 ")"进入， 由于最后一位不是‘-1’，说明这个右括号“）”肯定有前面未匹配的左括号“（”在等待。

规律：前面未匹配的左括号比为倒数第二位。因为后面可以匹配的正整数已经相互碰撞成了一个新的整数，所以stk最右侧最多只能连续存在一个正整数。

参考代码

// 关注TechGuide！ 大厂笔经面经闪电速递！

CPP版本

#include 
using namespace std;

using ll     = long long;
const ll mod = 1e9 + 7;

int main()
{
    string s;
    cin >> s;
    int n = s.size();

    vector stk;
    for (int i = 0; i = 2 && stk[stk.size() - 2] > 0)
                {
                    stk[stk.size() - 2] = (stk[stk.size() - 2] * stk[stk.size() - 1]) % mod;
                    stk.pop_back();
                }
            }
            else
            {
                stk[stk.size() - 2] = (1 + stk[stk.size() - 1]) % mod;
                stk.pop_back();
                if (stk.size() >= 2 && stk[stk.size() - 2] > 0)
                {
                    stk[stk.size() - 2] = (stk[stk.size() - 2] * stk[stk.size() - 1]) % mod;
                    stk.pop_back();
                }
            }
        }
    }
    cout