第一次考虑到的方法:
import java.util.*; public class Main { public static void main(String arg[]) { Scanner sc=new Scanner(System.in); String str=sc.next(); int sum=0; for(int i=0;i<str.length();i++) { for(int j=i;j<str.length();j++) { String s=str.substring(i,j+1); int count=0; int[] zimu=new int[26]; for(int k=0;k<s.length();k++) { zimu[((int)s.charAt(k))-97]+=1; } for(int k=0;k<zimu.length;k++) { if(zimu[k]==1) { count++; } } sum+=count; } } System.out.print(sum); sc.close(); } }
分析:
时间复杂度为O(n^2),超时了,时间超限55
暴力解决不了问题只能分析找规律
假设输入值为:befababc
下标:0 1 2 3 4 5 6 7
元素:b e f a b a b c
子串:befaba
下标:0 1 2 3 4 5
元素:b e f a b a
假如我们要求下标为3的元素a,在其可能包含a的子串中,出现一次的子串有多少个。出现一次,那么就碰到前后为a的时候停止,直到结束。如下:
往左找
a
fa
efa
befa
往右找
ab
左右两边并起来
fab
efab
befab
总共8个子串符合要求,我们可以发现总子串数=左子串数*(右子串数+1)
再结合下标来求公式,上面例子:(3- (-1))(5-3),下标为i推出公式为(i - left)(right - i)
left和right分别是左右碰到a或者结束的时候的下标
通过上面找规律,是不是发现可以用一个循环把字符串都遍历完,我们只需要将每一个元素含有多少个符合包含该元素且只出现一次的子串,然后将所有元素的符合子串个数相加,就可以了。
代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.next(); int len=str.length(); int right,left,sum=0; for(int i=0;i<len;i++){ for(right=i+1;right<len;right++){ if(str.charAt(right)==str.charAt(i)){ break; } } for(left=i-1;left>=0;left--){ if(str.charAt(left)==str.charAt(i)){ break; } } sum += (i-left)*(right-i); } System.out.print(sum); sc.close(); } }
0.0分
9 人评分
点我有惊喜!你懂得!浏览:2072 |
不知道哪里错了浏览:1146 |
程序员的表白 (C语言代码)浏览:1328 |
2005年春浙江省计算机等级考试二级C 编程题(3) (C语言代码)浏览:390 |
C语言程序设计教程(第三版)课后习题9.1 (Java代码)浏览:471 |
c primer plus 第十二章 12.1小节浏览:377 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1318 |
wu-淘淘的名单 (C++代码)浏览:1339 |
WU-输入输出格式练习 (C++代码)浏览:1082 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:550 |