leetcode
leetcode 1551 ~ 1600
统计同质子字符串的数目

统计同质子字符串的数目

难度:

标签:

题目描述

代码结果

运行时间: 67 ms, 内存: 16.3 MB


/*
 * 题目思路:
 * 使用 Java Stream API 处理字符串的同质子字符串计数问题。
 * 由于需要对每个字符进行遍历和分组,我们可以使用 Streams 和 Collectors 来实现。
 * 统计每个字符的连续段的长度,并计算每段的同质子字符串数量。
 */

import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int countHomogenous(String s) {
        long MOD = 1000000007;
        long count = IntStream.range(0, s.length())
            .filter(i -> i == 0 || s.charAt(i) != s.charAt(i - 1))
            .mapToObj(i -> {
                int j = i;
                while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
                long len = j - i;
                return len * (len + 1) / 2;
            })
            .collect(Collectors.summingLong(Long::longValue));
        return (int) (count % MOD);
    }
}

解释

方法:

该题解采用了一次遍历的方法来统计同质子字符串的数量。它通过维护一个计数器 c 来记录当前同质子字符串的长度,当遇到与上一个字符不同的字符时,就计算以前一个字符为结尾的所有同质子字符串的数量,并将计数器 c 重置为 1。该方法利用了等差数列求和公式来快速计算同质子字符串的数量。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到使用计数器c来记录当前同质子字符串的长度,那么在遇到新字符时,具体是如何处理当前记录的同质子字符串的计数的?
在遇到一个新的字符时,首先需要计算以前一个字符为结尾的所有同质子字符串的数量。这是通过使用计数器c,代表最新的字符连续出现的次数,来实现的。计算完成后,计数器c会被重置为1,表示新字符的开始。然后,更新变量last为当前的新字符,以便在后续的遍历中使用。
🦆
在题解的代码中,为什么在每次字符变更时,需要使用等差数列求和公式`(c + 1) * c / 2`来计算同质子字符串的数量?
等差数列求和公式`(c + 1) * c / 2`用于快速计算连续的同质子字符可以形成的不同长度的子串数量。例如,如果一个字符连续出现c次,那么可以形成c个长度为1的子串,c-1个长度为2的子串,直到1个长度为c的子串。这些可以通过求和公式直接算出总和,避免了多次循环计算的需求,提高了算法的效率。
🦆
题解中提到最后需要对最终的同质子字符串总数进行取余操作,这样的操作有什么特定的目的吗?
对最终的同质子字符串总数进行取余操作(使用模数`10^9 + 7`),主要是为了防止计算结果过大导致的整数溢出问题,并且满足某些编程竞赛和工业应用中对结果大小的常见限制。`10^9 + 7`是一个大质数,使用这个数作为模数可以保证结果在一个安全的数值范围内,同时也是满足某些算法竞赛的标准模数。
🦆
如果输入字符串s为空怎样处理?题解中有没有对这种边界情况进行处理?
如果输入字符串s为空,那么在题解的代码中,由于字符串遍历开始前没有特定字符,计数器c初始值为0,并且不会进入循环体。因此,最终的总同质子字符串数量total也将为0。这样的处理意味着空输入字符串会直接返回总数为0,有效地处理了这种边界情况。

相关问题