Description
现在需要找一些 11 位的手机号码(不含前导零),要出现至少 3 个相邻的相同数字,且不能同时出现 4 和 8 。问区间 [l,r] (1010≤l≤r<1011) 中有多少符合上述条件的手机号码。
Source
Solution
考虑用 记忆化搜索 实现 数位DP 。
用 fpos,pre1,pre2,four,eight,isThree 表示 当前到了第 12−pos 位,前一位数是 pre1,前一位数的前一位数是 pre2,是否存在 4,是否存在 8,是否存在 3 位数连续 的电话号码个数。因为固定 11 位,只需要保证第 1 位非零,所以不需要判断前导零。还有一个细节,当 l=1010 时,l−1 会变成 10 位数,显然不符合题意,这时计算就会出错,所以需要特判。具体实现详见代码,时间复杂度为 O(lg3n) 。
Code
1 |
|
Be the first person to leave a comment!