子串分值——20年模拟赛

简介: 子串分值——20年模拟赛

题目链接:

image.gif编辑

输入描述

输入一行包含一个由小写字母组成的字符串 S。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

ababc

image.gif

输出

21

image.gif

运行限制

    • 最大运行时间:1s
    • 最大运行内存: 256M

    JAVA解法(通过50%,要进行快读才能那100%):

    import java.util.Arrays;
    import java.util.Scanner;
        public class 子串分值 {
            static int num=0;
            public static void s(String str) {
                int book[]=new int [26];
                int n=0;
                for(int i=0;i<str.length();i++) {
                    book[str.charAt(i)-'a']++;
                }
                for(int i=0;i<book.length;i++) {
                    if(book[i]==1) num++;
                }
            }
            public static void main(String[] args) {
                Scanner sc=new Scanner(System.in);
                String str=sc.nextLine() ;
                for(int i=0 ; i<str.length() ; i++){
                    for(int k= i ; k<str.length() ; k++){
                        String res = str.substring(i , k+1);
                        s(res);
                    }
                }
                System.out.println(num);
            }
    }

    image.gif

    C++解法:

    #include<stdio.h>        
    #include<string.h>
    #define N 100002
    int main()
    {
        char s[N];
        int last[26];    //记录 a~z中每个字符最后被扫描的位置,即下标 
        int pre[N];        //记录前面与第i个字符相同的字符的位置,即下标 
        int next[N];    //记录后面与第i个字符相同的字符的位置,即下标 
        gets(s);
        int k,i,l;
        int sum=0;        //sum=sum+(i-pre[i])*(next[i]-i)  
        l=strlen(s);    //字符串长度
        for(i=0; i<26; i++)    //由于下标从0开始,所有字符在没出现第一次前都是 -1 
            last[i]=-1;
        for(i=0; i<l; i++)
        {
            k=s[i]-'a';
            pre[i]=last[k];    //前面与第i个字符相同的字符的位置
            last[k]=i;    //更新字符的位置 
        }
        for(i=0; i<26; i++)    //由于下标从0开始,从后面到前面,所有字符在没出现第一次前都是 l
            last[i]=l;
        for(i=l-1; i>=0; i--)
        {
            k=s[i]-'a';
            next[i]=last[k];    //后面与第i个字符相同的字符的位置
            last[k]=i;    //更新字符的位置 
        }
        for(i=0; i<l; i++)
        {
            sum+=(i-pre[i])*(next[i]-i);
            //(i-pre[i])为前面与第i个字符相同的字符与s[i]的距离
            //(next[i]-i)为后面与第i个字符相同的字符与s[i]的距离
        }
        printf("%d",sum);
        return 0;
    }

    image.gif

    Python解法:

    import os
    import sys
    # 请在此输入您的代码
    # 接收键盘输入
    s = input()
    # 初始化变量储存总分值
    sum_point = 0
    # 进行循环遍历字符串,求每个字符的分值
    for i in range(0, len(s)):
        # 初始化左长度
        left_len = 0
        # 初始化右长度
        right_len = 0
        # 初始化参考字符
        target = s[i]
        # 进行左循环
        flag = i - 1
        while flag >= 0 and s[flag] != target:
            left_len += 1
            flag -= 1
        # 进行右循环
        flag = i + 1
        while flag < len(s) and s[flag] != target:
            right_len += 1
            flag += 1
        # 对总分值进行累加
        sum_point += (left_len + 1) * (right_len + 1)
    # 打印输出
    print(sum_point)

    image.gif

    相关文章
    |
    6月前
    |
    算法 Java C++
    试题 算法训练 最长字符串
    试题 算法训练 最长字符串
    24 0
    |
    6月前
    【错题集-编程题】数组中的最长连续子序列(排序 + 模拟)
    【错题集-编程题】数组中的最长连续子序列(排序 + 模拟)
    |
    6月前
    |
    算法
    代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
    代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结
    52 1
    |
    6月前
    除夕日的每日一题(字符个数统计,多数元素)
    除夕日的每日一题(字符个数统计,多数元素)
    38 2
    |
    6月前
    leetcode-1688:比赛中的配对次数
    leetcode-1688:比赛中的配对次数
    40 0
    |
    6月前
    子串分值和(蓝桥杯C组)
    子串分值和(蓝桥杯C组)
    41 0
    |
    6月前
    【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
    【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
    45 0
    |
    算法 索引
    【算法挨揍日记】day08——30. 串联所有单词的子串、76. 最小覆盖子串
    给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words = [&quot;ab&quot;,&quot;cd&quot;,&quot;ef&quot;], 那么 &quot;abcdef&quot;, &quot;abefcd&quot;,&quot;cdabef&quot;, &quot;cdefab&quot;,&quot;efabcd&quot;, 和 &quot;efcdab&quot; 都是串联子串。 &quot;acdbef&quot; 不是串联子串,因为他不是任何 words 排列的连接。
    386 0
    |
    算法
    【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
    【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
    51 0
    |
    算法
    【力扣】第354场周赛 (最长合法子字符串的长度)
    【力扣】第354场周赛 (最长合法子字符串的长度)
    93 0