博客主页 🏗️
wy的leetcode刷题记录_Day61
wy的leetcode刷题记录_Day61

Author:

wy-1226

©

Wordage:

共计 2663 字

needs:

约 2 分钟

Popular:

261 ℃

Created:

目 录

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;
    }

收获

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

文章二维码
wy的leetcode刷题记录_Day61
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 14 小时 23 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视