X

LEETCODE 1180. Count Substrings with Only One Distinct Letter 解题思路分析

题目大意:

统计只含单一字母的子串

给你一个字符串 S,返回只含 单一字母 的子串个数。

示例1:

输入: "aaaba" 
输出: 8 
解释: 只含单一字母的子串分别是 "aaa", "aa", "a", "b"。 
 "aaa" 出现 1 次。 
 "aa" 出现 2 次。 
 "a" 出现 4 次。 
 "b" 出现 1 次。 
 所以答案是 1 + 2 + 4 + 1 = 8。 

示例 2:

输入: S = "aaaaaaaaaa" 
输出: 55 

提示:

  1. 1 <= S.length <= 1000
  2. S[i] 仅由小写英文字母组成。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1180

解题思路分析:

目的是统计只含单一字母的子串,也就是说子字符串中只能含有一种字符,那么我们可以将字符串中连续相同的部分分开,比如aaaba可以分成aaa,b,a三部分。接下来就是如何求某一长度的字符串能产生几种子字符串的问题。这其实是等差数列求和问题。比如字符串aaa。长度为3的个数只有1个,长度为2的有2个,长度为1的有3个。结果就是1+2+3。 同理例如aaaaaaaaaa(10个a),结果应该是1+2+3+…+9+10=55。这样我们求出所有分割后的子字符串的等差数列和,再相加即是返回结果。

实现代码:

public int countLetters(String S) {
    int sameLength=1; // 当前连续相同字符的个数
    int res=1; // 返回结果
    // 从下标1(第2位)开始循环
    for(int i=1;i<S.length();i++){
        // 如果当前字符与前一位不同
        if(S.charAt(i)!=S.charAt(i-1)){
            // sameLength还原为1(长度为当前字符)
            sameLength=1;
        }else{
            // 如果与前字符相同,sameLength加一。
            // 这一步相当于制作等差数列
            sameLength++;
        }
        // 将sameLength加入返回结果
        res+=sameLength;
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Substrings with Only One Distinct Letter.

Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Count Substrings with Only One Distinct Letter.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1180-count-substrings-with-only-one-distinct-letter-解题思路分析/
Categories: leetcode
kwantong: