统计只含单一字母的子串
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 0.0 MB
/*
* LeetCode 1180: 统计只含单一字母的子串
* 题目思路:
* 1. 使用Java Stream对字符串进行操作。
* 2. 利用map和reduce方法计算单一字符子串的数量。
* 3. 遍历字符串,计算每个字符连续出现的次数,然后将其转换为子串数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int countLetters(String S) {
return IntStream.range(0, S.length())
.mapToObj(i -> {
int j = i;
while (j < S.length() && S.charAt(i) == S.charAt(j)) j++;
int length = j - i;
i = j - 1;
return length * (length + 1) / 2;
})
.mapToInt(Integer::intValue)
.sum();
}
}
解释
方法:
这个题解通过遍历字符串来计算所有只含单一字母的子串的数量。首先,在字符串末尾添加一个空格作为哨兵字符,以便处理字符串的最后一个字符组成的子串。使用变量`st`来标记当前连续字符子串的起始位置。循环中,当遇到与`st`位置字符不同的字符时,计算从`st`到当前位置前一个位置之间的子串数,使用公式`(i-st) * (i-st+1) / 2`进行计算,然后更新`st`为当前字符的位置。这种方法有效地利用了数学公式计算连续字符的组合方式,避免了多重循环,提高了效率。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在字符串末尾添加一个哨兵字符,这个做法是如何帮助处理字符串末尾字符的?
▷🦆
公式`(i-st) * (i-st+1) / 2`是如何推导出来的,它代表什么意义?
▷🦆
如果输入字符串是空,这个算法是否还能正确返回结果为0?
▷🦆
在算法中,变量`rst`是如何累加每一个连续字符子串的数量的,这种方式是否有可能导致数据溢出?
▷