蓝桥杯（子串分值）Java

目录

• • 题目描述
  • 一、暴力（超时）
  • 二、dp（超时）
  • 三、计算贡献度（AC）

题目描述

一、暴力（超时）

最容易想到的暴力，两层for循环，再加一个判断f()个数的单层循环，利用长度为26的数组记录每个字母的出现次数。
时间复杂度直接O(n^3) 超时

import java.util.Scanner;public class Main {    public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); scanner.close(); int len = s.length(); int sum = 0; for (int i = 0; i < len; i++) {     for (int j = i+1; j <= len; j++) {  sum += f(s.substring(i,j));     } } System.out.println(sum);    }    static int f(String s){ int cnt = 0; int[] num = new int[26]; for (int i = 0; i < s.length(); i++) {     num[s.charAt(i)-'a']++; } for (int i = 0; i < 26; i++) {     if(num[i] == 1) cnt++; } return cnt;    }}

二、dp（超时）

利用dp数组记录从i到j子串的恰好出现一次的字母个数，状态转移方程为：

import java.util.Scanner;public class Main {    public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); scanner.close(); int len = s.length(); int sum = 0; int[] dp = new int[len + 1]; for (int i = 0; i < len; i++) { //起点     dp[i] = 0;     int[] nums = new int[26]; // 记录每个字母出现次数     for (int j = i; j < len; j++) {  int tmp = nums[s.charAt(j)-'a']++;  if(tmp == 1){  // 满足      dp[j+1] = dp[j] + 1;  }else if(tmp == 2){ // 之前只出现一次，需要减一      dp[j+1] = dp[j] - 1;  }else {  // 之前出现不止一次，不需要再减了      dp[j+1] = dp[j];  }  sum += dp[j+1];     } } System.out.println(sum);    }}

三、计算贡献度（AC）

只有当字母出现的次数为1才有贡献度，因此我们只需要计算出每个位置的贡献度累加求和即为答案
如何求解每个位置的贡献度呢
例如ababc，如果我们求第二个位置b的贡献度，则以b为中心，向两边扩散，找到只有一个b时的最长子串
向左步长为left=1，即ababc，向右步长为right=1，即ababc,所以我们找到的子串为aba，它一共有ab,aba,b,ba4种组合，从左到b做起点，从b到右做终点，即贡献度=(left+1)*(right+1)

import java.util.Scanner;public class Main {    public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); scanner.close(); int len = s.length(); int sum = 0; for (int i = 0; i < len; i++) {     int left = 0;     int right = 0;     char c = s.charAt(i);     while(i-left-1 >= 0 && s.charAt(i-left-1) != c) left++; // 求左步长     while(i+right+1 < len && s.charAt(i+right+1) != c) right++; // 求右步长     sum += (left+1)*(right+1); // 计算贡献度 } System.out.println(sum);    }}

全民K歌电脑版