美文网首页
【教3妹学算法-每日3题(2)】统计子串中的唯一字符

【教3妹学算法-每日3题(2)】统计子串中的唯一字符

作者: 程序员小2 | 来源:发表于2022-07-05 09:04 被阅读0次

插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
坚持不懈,越努力越幸运,大家一起学习鸭~~~

3妹

3妹:"池塘边的榕树上, 知了在声声叫着夏天"
2哥:"操场边的秋千上,只有蝴蝶停在上面"
3妹:没想到2哥也会唱这类歌曲啊。
2哥:这首哥在我小时候已经很流行了。3妹怎么想起来唱这首歌了?
3妹:2哥在追忆青春,而我正值青春,不会去追忆,所以只能追忆一下童年了,哈哈哈哈。
2哥:“你的童年我的童年好像都一样?”
3妹:“小小肩膀大大书包,上呀上学堂?”,哈哈哈哈。
2哥:哈哈哈哈

讲课

题目:

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符,并返回唯一字符的个数。

例如:s = "LEETCODE" ,则其中 "L", "T","C","O","D" 都是唯一字符,因为它们只出现一次,所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ,我们需要返回 countUniqueChars(t) 的总和,其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意,某些子字符串可能是重复的,但你统计时也必须算上这些重复的子字符串(也就是说,你必须统计 s 的所有子字符串中的唯一字符)。

示例 1:

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为:"A","B","C","AB","BC" 和 "ABC"。
其中,每一个子串都由独特字符构成。
所以其长度总和为:1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2:

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外,其余与示例 1 相同。
示例 3:

输入:s = "LEETCODE"
输出:92

提示:

1 <= s.length <= 10^5
s 只包含大写英文字符

思路:

对于每个字母分别计数
我们直接对于每个字符 c,计算出仅包含 c 一次的子串个数。使用和方法一相同的例子,考虑字母 "A",并且有 S[10] = S[14] = S[20] = "A",我们可以计算出仅包含 S[14] 的子串个数为 4 * 6 = 24,其中 4 表示子串的开始位置可以选择 11, 12, 13, 14,6 表示子串的结束位置可以选择 14, 15, 16, 17, 18, 19,根据乘法原理,子串的个数为 24。我们对于字母 "A" 出现的其它位置(例如 S[10] 和 S[20])分别进行同样的计数,并且需要考虑边界情况,就可以得到仅包含字母 "A" 一次的子串个数。

最后对于每个字符 c,将计数结果进行累加,就得到了最终的答案。

java代码1:

class Solution {
    public int uniqueLetterString(String S) {
        Map<Character, List<Integer>> index = new HashMap();
        for (int i = 0; i < S.length(); ++i) {
            char c = S.charAt(i);
            index.computeIfAbsent(c, x-> new ArrayList<Integer>()).add(i);
        }

        long ans = 0;
        for (List<Integer> A: index.values()) {
            for (int i = 0; i < A.size(); ++i) {
                long prev = i > 0 ? A.get(i-1) : -1;
                long next = i < A.size() - 1 ? A.get(i+1) : S.length();
                ans += (A.get(i) - prev) * (next - A.get(i));
            }
        }

        return (int) ans % 1_000_000_007;
    }
}

相关文章

网友评论

      本文标题:【教3妹学算法-每日3题(2)】统计子串中的唯一字符

      本文链接:https://www.haomeiwen.com/subject/poejbrtx.html