藍橋杯 Java試題 I: 子串分值和

大家關注微信公衆号 罡罡同學 回複藍橋杯

可免費獲得曆年真題和C語言版的真題源代碼

Java試題 I: 子串分值和

【問題描述】

對于一個字元串 S，我們定義 S 的分值 f(S ) 為 S 中出現的不同的字元個

數。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。

現在給定一個字元串 S [0…n − 1]（長度為 n），請你計算對于所有 S 的非空

子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是多少。

【輸入格式】

輸入一行包含一個由小寫字母組成的字元串 S。

【輸出格式】

輸出一個整數表示答案。

【樣例輸入】

ababc

【樣例輸出】

28

【樣例說明】

子串 f值

a 1

ab 2

aba 2

abab 2

ababc 3

b 1

ba 2

bab 2

babc 3

a 1

ab 2

abc 3

b 1

bc 2

c 1

思路：利用好HashSet

将字元串從i,到j位進行分割，分割後的字串在進行去重，所有去重後字串的長度相加輸出即可。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String a[] = new String[40000000];
		int k = 0;
		int count = 0;
		for(int i = 0;i<s.length();i++){
			for(int j = i+1;j<=s.length();j++){
				a[k] = (s.substring(i,j));
				k++;
			}		
		}
		for(int i = 0;i<k;i++){
			Set<String> set = new HashSet<String>();
			for(int j = 0;j<a[i].length();j++){
				set.add(a[i].charAt(j)+"");	
			}
			count = count+set.size();		
		}	
	System.out.print(count);	
	}
}
           

謝謝大家的支援，您的一鍵三連是 罡罡同學前進的最大動力！

一鍵三連 一鍵三連 一鍵三連 一鍵三連 一鍵三連 一鍵三連