扁平化网站后台,网站建设设计,廊坊优化外包,江苏城乡和住房建设厅网站文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路
这题可以先求按了多少次相同连续的按钮#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/
