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 湖南

测控大Fa好

东南大学 Java

大佬沙发沙发

2 回复分享

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

牛客682994392号

门头沟学院 Java

大佬牛，居然是校友

2 回复分享

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

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

大连理工大学 golang

仙人思路

1 回复分享

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

77努力鸭

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

牛

1 回复分享

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

菜狗工程师

上海交通大学人工智能

点赞回复分享

发布于 2022-08-27 21:19 广东

华墨

京东方_后端开发

大佬！

点赞回复分享

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

无尽蔚蓝

阿里巴巴_Lazada_Java开发工程师

感谢大佬

点赞回复分享

发布于 2022-08-27 21:32 上海

取个名字好难哟

门头沟学院 Python

太强了太强了

点赞回复分享

发布于 2022-08-27 22:08 四川

热爱可抵岁月长

哈尔滨工业大学 golang

大佬，第二个式子为什么要减去g(i-3)呀

点赞回复分享

发布于 2022-08-27 22:39 吉林

从入门_to_转行

华中科技大学 Java

学习了

点赞回复分享

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

牛客381530078号

门头沟学院算法工程师

🐮

点赞回复分享

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

牛客408632512号

哈尔滨工业大学后端

太牛了，收下我的膝盖

点赞回复分享

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

牛客308749985号

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

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

点赞回复分享

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

牛客218694145号

武汉大学算法工程师

太强了

点赞回复分享

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

漂亮的牛牛起床了

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

牛哇，太精妙了！

点赞回复分享

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

TAICHIFEI

云南大学算法工程师

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

点赞回复分享

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

昨天 10:41

微软_软件开发经理

双非逆袭微软|简历优化实战案例详解 C9 博士算法岗

大家好，我是微软程序 YK这次实战案例是来自一位C9的博士同学,求职岗位立算法工程师,意向公司为：华为整个辅导流程分为几个阶段:简历诊断->快速迭代->复盘->快速送代->复盘...... 5天完成4次快速送代。首先我们来看看他的简历：简历诊断:相对优势:C9院校背景,博士学历,参与某重点保密项目的科研经验,这些要素都积累到相对优势。可优化点:结构:个人信息只需保留:姓名、电话、邮箱、求职岗位;"民族"、"籍贯"、"出生年月"、"政治面貌"对于求职华为没有帮 助...

投递微软等公司10个岗位 > 简历中的项目经历要怎么写简历被挂麻了，求建议

点赞评论收藏

昨天 14:35

中南大学 C++

双非本中九硕电子信息CV，自学开发不知道选java还是c++

今天给大家分享的是一位粉丝的提问，双非本中九硕电子信息CV，自学开发不知道选java还是c++接下来把粉丝的具体提问和我的回复分享给大家，希望也能给一些类似情况的小伙伴一些启发和帮助。同学提问：up主你好，我是杭州双非本天津中九硕，本硕专业都是电子信息工程，硕士方向是CV，本科做过一些机器人相关的比赛拿了奖，现在研一，研究生打算能毕业就行，因为感觉现在读研搞的东西都是算法相关，看到相关的帖子基本双九或者博士才好找纯算法。现在实验室的方向基本都是为了好发论文，有点脱离实际生产，招工作的东西只能自己去学，硕士学自己的东西的时间有限，听说Java比较好上手，C++比较难，害怕学C++达不到入职要...

投递OPPO等公司10个岗位 > 计算机就业职业规划辅导

点赞评论收藏

02-16 12:56

门头沟学院嵌入式软件开发

求大佬看看

大佬们 ，有什么建议吗 ，双非本 一段实习 想在3月份找大厂实习，还有什么需要改的吗？

点赞评论收藏

昨天 16:35

西安邮电大学 C++

腾讯天美后台开发实习，一面凉经（30min）

项目遇到的难点，如何解决的？有对项目进行压测吗？描述一下Go的GMP模型？开启多个协程，如何保证都能正常结束？说一下切片是怎么实现的？长度可变是如何实现的？大概说一下第二个项目的实现过程？为什么选择使用redis保存上传进度，有做过什么考虑？上传过程中，redis出现了问题，这时出现了什么后果？如何解决提高服务的可靠性？有去了解搭建过redis集群吗？使用rabbitmq主要是实现了什么功能？如何实现的？C++:C++的struct中没有任何变量，sizeof为多少？有了解过C++11的右值引用吗？如何让函数在进入main函数之前被调用？多进程和多线程各自的应用场景？说一下交换机和路由器的工作...

查看15道真题和解析

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 面试被问“你的缺点是什么?”怎么答 #

15769次浏览 286人参与

# 第一份工作应该选高薪还是热爱？ #

11886次浏览 122人参与

# 机械人，你在招聘流程中的企业有哪些？ #