牛客-小乐乐与字符串

忘是亡心i 2023-06-12 08:51 30阅读 0赞

**题目：**

在庆祝祖国母亲70华诞之际，老师给小乐乐出了一个问题。大家都知道China的英文缩写是CHN，那么给你一个字符串s，你需要做的是统计s中子串“CHN”的个数。

子串的定义：存在任意下标a < b < c，那么“s\[a\]s\[b\]s\[c\]”就构成s的一个子串。如“ABC”的子串有“A”、“B”、“C”、“AB”、“AC”、“BC”、“ABC”。

链接：[https://ac.nowcoder.com/acm/contest/1877/S][https_ac.nowcoder.com_acm_contest_1877_S]

## 输入描述: ##

输入只包含大写字母的字符串s。(1 ≤ length ≤ 8000)

## 输出描述: ##

输出一个整数，为字符串s中字串“CHN”的数量。

示例1

## 输入 ##

复制

CCHNCHN

## 输出 ##

复制

示例2

## 输入 ##

复制

CCHNCHNCHNCHN

## 输出 ##

复制

import java.util.Scanner;
    
    /*8000*8000*8000 =10的11次方复杂度*/
    public class S {
    	public static void main(String[] args) {
    		Scanner cin=new Scanner(System.in);
    		String str=cin.next();
    		char[] a=str.toCharArray();
    		//System.out.println(violence(a));
    		System.out.println(get3(a));
    	}
    	//只能过百分之40
    	public static int violence(char[] a) {
    		int num=0;
    		int index_c=0;
    		int index_h=0;
    		int index_n=0;
    		int[] c=new int[8000];
    		int[] h=new int[8000];
    		int[] n=new int[8000];	
    		for(int i=0;i<a.length;i++) {
    			if(a[i]=='C') c[index_c++]=i;
    			if(a[i]=='H') h[index_h++]=i;
    			if(a[i]=='N') n[index_n++]=i;
    		}
    		for(int i=0;i<index_c;i++) {
    			for(int j=0;j<index_h;j++) {
    				for(int k=0;k<index_n;k++) {
    					if(c[i]<h[j]&&h[j]<n[k]) {
    						num++;
    					}
    				}
    			}
    		}
    		
    		return num;
    	}
    	//只能过百分之70 问题是超出了int的表示范围
    	public static int get2(char[] a) {
    		int c=0;
    		int h=0;
    		int n=0;
    		for(int i=0;i<a.length;i++) {
    			if(a[i]=='C') c++;
    			if(a[i]=='H') h+=c;
    			if(a[i]=='N') n+=h;
    		}
    		return n;
    	}
    	//能过
    		public static long  get3(char[] a) {
    			long c=0;
    			long h=0;
    			long n=0;
    			for(int i=0;i<a.length;i++) {
    				if(a[i]=='C') c++;
    				if(a[i]=='H') h+=c;
    				if(a[i]=='N') n+=h;
    			}
    			return n;
    		}
    }

因为时间复杂度超过了10的9次方 所以暴力是会超时的

[https_ac.nowcoder.com_acm_contest_1877_S]: https://ac.nowcoder.com/acm/contest/1877/S