京东CPP开发方向编程题题解

第一题:
答案就是根节点(1号节点)的子树中,最大的那棵子树的节点数。DFS一遍即可。

第二题:
对于每个S串,都在T串中找一遍,把对应位置标记上state[i][j]表示T串第i位能和S[j]这个串匹配上
然后dp就可以啦,用dp[i]表示T串前i个字符最多的划分数量。
用state找到和第i位匹配的最短串的长度,记为minLen。
dp[i] = max(dp[i-1], dp[i-minLen]+1),若minLen存在
dp[i] = dp[i-1],若minLen不存在
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;
int len[10];
char S[10][100005];
char T[100005];
int state[100005];
int dp[100005];
long long hsh[100005];
long long mi[100005];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s", S[i]), len[i] = strlen(S[i]);
    scanf("%s", T);
    mi[0] = 1;
    for (int i = 1; i <= 100000; i++)
        mi[i] = mi[i - 1] * 31 % mod;
    int lenT = strlen(T);
    hsh[0] = T[0] - 'a' + 1;
    for (int i = 1; i < lenT; i++)
        hsh[i] = (hsh[i - 1] * 31 + T[i] - 'a' + 1) % mod;
    for (int i = 0; i < n; i++)
    {
        long long curHsh = 0;
        for (int j = 0; j < len[i]; j++)
            curHsh = (curHsh * 31 + S[i][j] - 'a' + 1) % mod;
        if (curHsh == hsh[len[i]-1])
            state[len[i]-1] |= 1 << i;
        for (int j = len[i]; j < lenT; j++)
            if ((hsh[j] - hsh[j - len[i]] * mi[len[i]] % mod + mod) % mod == curHsh)
                state[j] |= 1 << i;
    }
    for (int i = 0; i < lenT; i++)
    {
        int minL = 1e9;
        for (int j = 0; j < n; j++)
            if (state[i] & (1 << j))
                minL = min(minL, len[j]);
        if (minL == 1e9)
        {
            if (i > 0)
                dp[i] = dp[i-1];
        }
        else if (i-minL < 0)
            dp[i] = max(dp[i-1], 1);
        else
            dp[i] = max(dp[i-1], dp[i-minL]+1);
    }
    printf("%d", dp[lenT - 1]);
    return 0;
}

#京东##题解##笔试题目##春招#
全部评论
第一题直接递归求根结点的最大子树的节点数 第二题按照串的长度递增的顺序动态规划就行了😮 40多分钟做完
点赞 回复
分享
发布于 2019-04-13 20:50
点赞 回复
分享
发布于 2019-04-13 21:05
百信银行
校招火热招聘中
官网直投

相关推荐

点赞 18 评论
分享
牛客网
牛客企业服务