子串分值——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++
    试题 算法训练 最长字符串
    试题 算法训练 最长字符串
    25 0
    【Leetcode -575.分糖果 -594.最长和谐子序列】
    【Leetcode -575.分糖果 -594.最长和谐子序列】
    56 0
    |
    3月前
    |
    算法 C++
    第一周算法设计与分析 E : 构造回文串
    这篇文章介绍了解决算法问题"构造回文串"的方法,即判断给定的整数N(视为字符串)是否可以通过在前面添加任意个0(或不添加)来构造一个回文串,并给出了相应的C++代码实现。
    |
    6月前
    满足条件的01序列(大厂机考题)
    满足条件的01序列(大厂机考题)
    |
    6月前
    除夕日的每日一题(字符个数统计,多数元素)
    除夕日的每日一题(字符个数统计,多数元素)
    40 2
    |
    6月前
    每日一题来啦!请查收~(至少是其他数字两倍,两个数组的交集)
    每日一题来啦!请查收~(至少是其他数字两倍,两个数组的交集)
    31 0
    |
    6月前
    |
    算法 测试技术 C#
    C++前缀和算法:统计美丽子字符串
    C++前缀和算法:统计美丽子字符串
    |
    6月前
    子串分值和(蓝桥杯C组)
    子串分值和(蓝桥杯C组)
    44 0
    |
    6月前
    【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
    【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
    47 0
    |
    算法
    代码随想录算法训练营第二十五天 | LeetCode 216. 组合总和 III、17. 电话号码的字母组合
    代码随想录算法训练营第二十五天 | LeetCode 216. 组合总和 III、17. 电话号码的字母组合
    55 0