2022-08-27 21:11 东北大学 C++ 发布于四川

关注

京东笔试最后一题

长度n，小写字母组成的字符串中有多少个至少含有2个red子串的字符串,结果取模 1e9 + 7

例如 redared OK

长度6: 1种 redred

思路dp 至少含有2个的不好求，用总的数目 $26^n$ 减去只有0个red子串和只有1个子串。

设 $f(i)$ 为长度i字符串含有0个red子串的字符串个数

设 $g(i)$ 为长度i字符串含有1个red子串的字符串个数

设 $h(i)$ 为长度i字符串至少含有2个red子串的字符串个数

容易知道：

$f(1) = 26^1, f(2) = 26^2, f(3) = 26^3 - 1$

$g(1)=0,g(2)=0,g(3)=1$

dp推理得（注意 1e9 + 7取摸）：

$f(i)=f(i-1)*26-f(i-3)$

$g(i)=g(i-1)*26-g(i-3)+f(i-3)$

$h(i)=26^i-f(i)-g(i)$

全部评论

推荐最新楼层

菜鸡想进大厂～

杭州电子科技大学 Java

有没有大佬解答一下为什么计算g[i]要加上f[i-3]

点赞回复分享

发布于 2022-08-27 21:43 浙江

天气之子

四川音乐学院后端

京东ac的也都挂了

点赞回复分享

发布于 2022-08-29 12:41 四川

henu_暑假拿T恤

门头沟学院数据分析师

弱鸡发一下我的代码，思路是第二维来存，0：无结尾，1：以r结尾，2：re结尾，3：恰好含有一个red，4：恰好含有一个red，且以r结尾，...，6：至少含有两个red

6 回复分享

发布于 2022-08-28 20:07 上海

王悟空

乾象投资_Dev

大佬。我写了个正向思路的，能帮忙check一下吗：https://www.nowcoder.com/discuss/1030758

点赞回复分享

发布于 2022-08-27 22:26 湖南

牛客682994392号

门头沟学院 Java

大佬牛，居然是校友

2 回复分享

发布于 2022-08-27 21:38 辽宁

测控大Fa好

东南大学 Java

大佬沙发沙发

2 回复分享

发布于 2022-08-27 21:16 江苏

77努力鸭

西安电子科技大学测试工程师

牛

1 回复分享

发布于 2022-08-27 21:32 陕西

°给我牙签、我要撬地球-

大连理工大学 golang

仙人思路

1 回复分享

发布于 2022-08-27 21:26 辽宁

牛客ID：416036405

门头沟学院后端

太厉害了，请问有对象么

点赞回复分享

发布于 2023-02-01 14:13 云南

繁华落尽后的嘿嘿

北京航空航天大学 C++

嗨，知道是tp就是不能把规律找出来

点赞回复分享

发布于 2022-08-29 17:26 北京

朴实无*

深圳大学 Java

tql

点赞回复分享

发布于 2022-08-29 16:46 广东

牛客898188433号

深圳大学 Java

太强了！！

点赞回复分享

发布于 2022-08-29 16:34 广东

来点然能量

广东技术师范大学 Java

妙

点赞回复分享

发布于 2022-08-29 11:23 广东

TAICHIFEI

云南大学算法工程师

请问这是哪个岗位的笔试题呀

点赞回复分享

发布于 2022-08-28 18:50 广东

漂亮的牛牛起床了

北京航空航天大学塑料工程师

牛哇，太精妙了！

点赞回复分享

发布于 2022-08-28 16:26 北京

牛客218694145号

武汉大学算法工程师

太强了

点赞回复分享

发布于 2022-08-28 09:07 湖北

牛客308749985号

中日友好临床医学研究所 Java

我g统计错了导致没搞出g的递推公式

点赞回复分享

发布于 2022-08-28 07:12 美国

牛客408632512号

哈尔滨工业大学后端

太牛了，收下我的膝盖

点赞回复分享

发布于 2022-08-28 00:59 海南

牛客381530078号

门头沟学院算法工程师

🐮

点赞回复分享

发布于 2022-08-27 23:50 安徽

从入门_to_转行

华中科技大学 Java

学习了

点赞回复分享

发布于 2022-08-27 22:42 湖北

05-07 12:58

西南科技大学 Java

大佬们看看孩子简历吧，投出去全是已读不回

26届双非不知道咋找得到实习了

kong_kong：1.广投，boss每天200次机会用完， 2.简历上技能和项目经历突出你在这个岗位上的突出优势。 3.还是广投，不要挑地点，公司规模（我当时是线下一个都不去，如果你离得近可以考虑一下去现场） 4.简历写的自己成绩好什么的，奖项也写一写（懂的都懂）

实习，投递多份简历没人回复怎么办

点赞评论收藏

05-10 17:27

门头沟学院

如何预估接口上线后的 QPS

问题引入这个问题其实是一个非常实际的问题，因为我们在开发需求后，例如：新增了一个接口有一个步骤是值得做的，那就是预估这个接口的QPS因为我们是可以去调配对应服务器的数量和运行配置的例如我可以从2个节点新增为4个节点例如我可以将节点的内存从2G变成4G，2核CPU变成4核CPU如果因为 没有正确的预估 以及 没有正确的调整，导致接口的QPS过高，扛不住系统崩溃，那就是严重的外网事故了注意，这里说的预估QPS，是假设有一个真实的项目、真实的环境，预估这个接口上线后会有多少 QPS而不是在预估我们的系统接口本身能抗住多少QPS而不崩溃

点赞评论收藏

04-07 22:40

厦门大学 Web前端

27届前端这个简历有救吗

真得被挂麻了😭😭，投了100多家只有一家小厂约面了，其他基本都是简历挂连面试机会都不给，求牛友给点建议

陈逸轩1205：9✌ 还不随便面

点赞评论收藏

05-03 11:27

Johns Hopkins University 算法工程师

哈哈离谱

#面试吐槽bot# #最离谱的面试经历#

野猪不是猪🐗：我assume that你must技术aspect是solid的，temperament也挺good的，however面试不太serious，generally会feel style上不够sharp

面试吐槽bot

点赞评论收藏

05-07 19:00

首都师范大学硬件产品经理

这些都是不卡学历的大厂

不卡学历的：美团、字节、快手、京东、拼多多(这几个大厂我是明确知道不卡学历，甚至二本可上岸的)除此之外美妆快消行业的还有珀莱雅、欧莱雅、花西子、水羊国际明确卡学历的:互联网：阿里巴巴卡211(但听说有因为专业十实习经历实在是太匹配的，能拿到面试和offer)快消：宝洁，联合利华，谷雨(甚至卡到985)这些仅是我个人了解的一些情况 其实回头来看，不管什么档次的学校，都还是有机会进大厂的，再查的学校实习经历匹配的情况下，都有可能! 所以不要学历自卑。学历自卑是因为你活在学校以学校层次为优先的这个评价体系之内。如果你没有读书的意愿，那不如趁早去找实习去卷赚钱的技能置了

谛凌：快手确实不卡学历，它卡实习

简历直接挂

点赞评论收藏

全站热榜

创作者周榜

正在热议