网站开发倒计时,怎么查看网站哪个公司做的,vs怎么添加做网站,win8风格企业网站文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路
我们使用逆向思维发现如果连续按存在三个字母的按键#xff0c;最后一个按键表示的字母可以是某个字母连续出现一次、两次、三次这三种情况的方案数之和 我们发现连续按存在三个字母的按键#xff0c;当连续按… 文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路
我们使用逆向思维发现如果连续按存在三个字母的按键最后一个按键表示的字母可以是某个字母连续出现一次、两次、三次这三种情况的方案数之和 我们发现连续按存在三个字母的按键当连续按i次时其方案数f[i] f[i - 1] f[i - 2] f[i - 3] 其中f[i - 1]表示最后一个按键表示的最后一个字母连续出现一次的方案数 f[i - 2]表示最后一个按键表示的最后一个字母连续出现l两次的方案数 f[i - 3]表示最后一个按键表示的最后一个字母连续出现三次的方案数
类似的按存在四个字母的按键当连续按i次时其方案数f[i] f[i - 1] f[i - 2] f[i - 3] f[i - 4]
然后我们只需要计算所有连续的字母其出现了几次然后将其方案数相乘就是最终的结果
题解代码
func countTexts(pressedKeys string) int {const mod 1000000007n : len(pressedKeys)f3, f4 : make([]int, 0, n 1), make([]int, 0, n 1)f3 append(f3, 1, 1, 2, 4)f4 append(f4, 1, 1, 2, 4)for i : 4; i n; i {f3 append(f3, (f3[i - 1] f3[i - 2] f3[i - 3]) % mod)f4 append(f4, (f4[i - 1] f4[i - 2] f4[i - 3] f4[i - 4]) % mod)}ans, cnt : 1, 0for i : 0; i n; i {cntif i n - 1 || pressedKeys[i] ! pressedKeys[i 1] {if pressedKeys[i] 7 || pressedKeys[i] 9 {ans ans * f4[cnt] % mod} else {ans ans * f3[cnt] % mod}cnt 0}}return ans
}题目链接
https://leetcode.cn/problems/count-number-of-texts/description/
