京东C++后台笔试代码,多叉树、动态规划

求多叉树根节点的所有子树中节点数量的最大值。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

unordered_map<int, unordered_set<int>> tree;

int getChildNum(int node, int parent)
{
    int childNum = 0;
    for (int child : tree[node])
    {
        if (child == parent)
        {
            continue;
        }
        childNum++;
        childNum += getChildNum(child, node);
    }
    return childNum;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        tree[x].insert(y);
        tree[y].insert(x);
    }
    int maxChildNum = 0;
    for (int child : tree[1])
    {
        int childNum = getChildNum(child, 1) + 1;
        maxChildNum = max(maxChildNum, childNum);
    }
    cout << maxChildNum << endl;
    return 0;
}

动态规划,以串的长度递增的顺序求最大值。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int m;
    cin >> m;
    vector<string> strs(m);
    for (int i = 0; i < m; i++)
    {
        cin >> strs[i];
    }
    string t;
    cin >> t;
    int tLength = t.length();
    vector<int> counts(tLength + 1);
    string formed;
    for (int i = 0; i < tLength; i++)
    {
        int count = counts[i];
        formed += t[i];
        for (string &str : strs)
        {
            int strLength = str.length();
            if (strLength > i + 1)
            {
                continue;
            }
            if (str == formed.substr(i - strLength + 1))
            {
                count = max(count, counts[i - strLength + 1] + 1);
            }
        }
        counts[i + 1] = count;
    }

    int result = counts[tLength];
    cout << result << endl;

    return 0;
}
#京东##笔试题目#
全部评论
有没有dalao能帮我翻译成Java😂
点赞 回复 分享
发布于 2019-04-13 21:58
第二题可以KMP+贪心区间调度来着
点赞 回复 分享
发布于 2019-04-13 21:47
都100%AC了吗
点赞 回复 分享
发布于 2019-04-13 21:44

相关推荐

这不纯纯作弊了吗😢😢😢
编程界菜鸡:信这个的这辈子有了,这智商你靠啥都没用
你找工作的时候用AI吗?
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
评论
点赞
31
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务