关注
将串分成四类:
1. 没有3连 + 末尾两个数字不同, A[L]
2. 没有3连 + 末尾两个数字相同, B[L]
3. 恰有1个3连 + 末尾两个数字不同, C[L]
4. 恰有1个3连 + 末尾两个数字相同, D[L]
有如下递推关系:
A[2] = S * (S - 1)
B[2] = S
C[2] = 0
D[2] = 0
令R = S - 1以方便书写
A[L+1] = A[L] * R + B[L] * R
B[L+1] = A[L]
C[L+1] = C[L] * R + D[L] * R
D[L+1] = B[L] + C[L]
最后输出结果C[L] + D[L]之和即可。
时间复杂度为O(L)
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-25 12:52
中国石油大学(华东)青岛校区 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
234919次浏览 2192人参与
# kpi面有什么特征 #
33103次浏览 231人参与
# 你认为哪个岗位找工作最卷 #
13605次浏览 48人参与
# 职场人,说说你的烦心事 #
8669次浏览 77人参与
# 一人一个landing小技巧 #
79368次浏览 1125人参与
# 职场上哪些事情令人讨厌 #
16736次浏览 86人参与
# 秋招最大的收获是什么? #
33919次浏览 299人参与
# 小红书求职进展汇总 #
56140次浏览 486人参与
# 聊聊你的职场新体验 #
157490次浏览 1369人参与
# 机械制造岗投递时间线 #
22752次浏览 346人参与
# 职场吐槽大会 #
205530次浏览 1638人参与
# 研究所VS国企,该如何选 #
180669次浏览 1769人参与
# 为了找工作你投递了多少公司? #
10194次浏览 142人参与
# 大家每天通勤多久? #
42027次浏览 331人参与
# 通信硬件牛牛的实习日记 #
7186次浏览 65人参与
# 职场破防瞬间 #
234968次浏览 2127人参与
# 总结:哪家公司面试体验感最好 #
47664次浏览 338人参与
# tplink提前批进度交流 #
162774次浏览 1378人参与
# 找工作前vs找工作后的心路变化 #
9598次浏览 103人参与
# 担心入职之后被发现很菜怎么办 #
126504次浏览 755人参与