免费网站后台管理模板下载,衣柜东莞网站建设技术支持,二建证从住房建设厅网站调出流程,微信网站地址文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路
这题可以先求按了多少次相同连续的按钮#xff0c;所有的连续相同按钮表示的方案数的乘积就是本题答案
我们的关键问题就转换成了按n个连续相同按钮表示的方案数
设f(i)表示按i个连续相同按钮表示的方案数
如… 文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路
这题可以先求按了多少次相同连续的按钮所有的连续相同按钮表示的方案数的乘积就是本题答案
我们的关键问题就转换成了按n个连续相同按钮表示的方案数
设f(i)表示按i个连续相同按钮表示的方案数
如果按钮是三个字符的 f(i) f(i - 1) f(i - 2) f(i - 3)如果按钮是四个字符的 f(i) f(i - 1) f(i - 2) f(i - 3) f(i - 4)
题解代码
impl Solution {pub fn count_texts(pressed_keys: String) - i32 {let pressed_keys pressed_keys.as_bytes();let n pressed_keys.len();let mut f3 vec![0; (n 1).max(5)];let mut f4 vec![0; (n 1).max(5)];(f3[1], f3[2], f3[3], f3[4], f4[1], f4[2], f4[3], f4[4]) (1, 2, 4, 7, 1, 2, 4, 8);for i in 5..n {f3[i] (f3[i - 1] f3[i - 2] f3[i - 3]) % 1000000007;f4[i] (f4[i - 1] f4[i - 2] f4[i - 3] f4[i - 4]) % 1000000007;}let mut c 1;let mut ans 1usize;for i in 1..n {if pressed_keys[i] pressed_keys[i - 1] {c 1;} else {match pressed_keys[i - 1] {b7 | b9 {ans * f4[c];}_ {ans * f3[c];}}c 1;ans % 1000000007;}}match pressed_keys[n - 1] {b7 | b9 {ans * f4[c];}_ {ans * f3[c];}}(ans % 1000000007) as i32}
}题目链接
https://leetcode.cn/problems/count-number-of-texts/
