wy的leetcode刷题记录_Day61

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2022-12-26

前言

@TOC

1759. 统计同构子字符串的数目

今天的每日一题是：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" 。

思路

方法一：暴力解法：遍历整个字符串，每一次遍历到不同的字符我们将前面的切除掉，然后计算当前字符串得分，得分规则设当前字符重复n次，得分为递增求和公式temp+temp*(temp-1)/2，超时原因是字符串切割次数过多。（超时）
方法二：改进简单模拟：遍历整个字符串，每一次迭代我们不进行字符串的切分，使用一个变量来记录当前对比的字符即可，对于一个字符的重复了n次那么其贡献值为n*(n+1)/2，然后我们再跳到下一个不同的字符，并跟新对比的字符以及出现次数。

代码

class Solution {
public:
    int countHomogenous(string s) {
        int n=s.size();
        if(n==1)
            return 1;
        if(n==0)
            return 0;
        int ans=0;
        for(int i=0;i<n;)
        {
            if(i==n)
                break;
            int temp=helper(s);
            if(temp==1)
            {
                ans++;
                i++;
            }
            else
            {
                ans+=temp+temp*(temp-1)/2;
                i+=temp;
            }
            s=s.substr(temp);
        }
        return ans;
    }

    int helper(string s)
    {
        char Compare=s[0];
        int res=1;
        int n=s.size();
        if(n==1)
            return 1;
        for(int i=1;i<n;i++)
        {
            if(s[i]==Compare)
                res++;
            else
                return res;
        }
        return res;
    }
};

class Solution {
public:
    int countHomogenous(string s) {
        long long MOD = 1000000007;

        int n=s.size();
        if(n==1)
            return 1;
        if(n==0)
            return 0;
        int ans=0;
        char prev=s[0];
        int temp=1;
        for(int i=1;i<n;i++)
        {
            if(i==n)
                break;
            //int temp=helper(s);
            if(prev==s[i])
            {
                temp++;
            }
            else{
                prev=s[i];
                ans+=(temp + 1) * temp / 2;
                temp=1;
            }


            //s=s.substr(temp);
        }
        ans+=(long)(long)(temp + 1) * temp / 2%MOD;
        return ans%MOD;
    }

收获

多观察才能知道自己哪里需要改进