企业做网站天津,房地产销售,python游戏编程入门,ui设计主要做什么统计同质子字符串的数目 统计同质子字符串的数目题目描述双指针解题代码演示 回溯算法 统计同质子字符串的数目 难度 - 中等 1759. 统计同质子字符串的数目 题目描述 给你一个字符串 s #xff0c;返回 s 中 同质子字符串 的数目。由于答案可能很大#xff0c;只需返回对 109… 统计同质子字符串的数目 统计同质子字符串的数目题目描述双指针解题代码演示 回溯算法 统计同质子字符串的数目 难度 - 中等 1759. 统计同质子字符串的数目 题目描述 给你一个字符串 s 返回 s 中 同质子字符串 的数目。由于答案可能很大只需返回对 109 7 取余 后的结果。 同质字符串 的定义为如果一个字符串中的所有字符都相同那么该字符串就是同质字符串。 子字符串 是字符串中的一个连续字符序列。 示例 1 输入s “abbcccaa” 输出13 解释同质子字符串如下所列 “a” 出现 3 次。 “aa” 出现 1 次。 “b” 出现 2 次。 “bb” 出现 1 次。 “c” 出现 3 次。 “cc” 出现 2 次。 “ccc” 出现 1 次。 3 1 2 1 3 2 1 13 示例 2 输入s “xy” 输出2 解释同质子字符串是 “x” 和 “y” 。 示例 3 输入s “zzzzz” 输出15 提示 1 s.length 100000 s 由小写字符串组成 双指针解题 这个题的意思就是,要找出字符相等的连续段,找出后,我们用等差数列的求和公式求出就可以了. 等差数列求和公式: num * (num 1) / 2; 双指针解法: 我们用一个指针卡住起始位置.另外一个指针向右滑动,互动到第一个不相等的位置停止,然后利用公式求出数量, 再把起始位置移动到刚才右指针滑动的位置,重复上面过程. 代码演示
class Solution {public int countHomogenous(String s) {int n s.length();int mod (int)1e97;long ans 0;for (int i 0;i n;){int j i;//双指针,一个卡住开头,一个向右滑,滑倒第一个不等的位置.while (j n s.charAt(j) s.charAt(i)){j;}//计算字符串数量,用求和公式long num j - i;ans num * (num 1) / 2;ans % mod;i j;}return (int)ans;}
}回溯算法
leetcode37. 解数独
