substring,subsequence,charAt执行效率的不同
程序员文章站
2022-03-12 10:15:00
以上写了一个返回最长回文子串的程序（1000个a，回文字串就是如abcddcba、bcb，左右两边相同，当然a一个字符也是），之前使用的test1总是500以上的执行时间，时间总是无法降低，最后问题落到了两个截取字串位置上，经过修改，test2成功降低执行时间。 test1 使用 sub 截取字符串 ......
1 package com.java.tencent;
2
3 public class t_2_longestpalindrome {
4
5 public string test1(string s){
6 long starttime=system.currenttimemillis();
7 int len = s.length();
8 int tmp = 0;
9 string result = "";
10 for(int i=0;i<len;i++){
11 if(tmp+i-len>0){
12 break;
13 }
14 int lenj = len-1;
15 for(int j=lenj;j>=i;j--){
16 if(tmp>j-i+1){
17 break;
18 }
19 string ch = s.substring(i,i+1);
20 string chj = s.substring(j,j+1);
21 if(ch.equals(chj)){
22 string str = s.substring(i,j+1);
23 if(tmp>str.length()){
24 continue;
25 }
26 boolean bl = true;
27 int ln = str.length();
28 int lenm = ln/2+1;
29 for(int m=0;m<lenm;m++){
30 charsequence start = str.subsequence(m, m+1);
31 charsequence end = str.subsequence(ln-m-1,ln-m);
32 if(!start.equals(end)){
33 bl = false;
34 break;
35 }
36 }
37 if(bl && ln>tmp){
38 result = str;
39 tmp = ln;
40 }
41 }
42 }
43 }
44 system.out.println(result);
45 long endtime=system.currenttimemillis();
46 system.out.println("程序运行时间： "+(endtime-starttime)+"ms");
47 return result;
48 }
49
50 public string test2(string s){
51 long starttime=system.currenttimemillis();
52 int len = s.length();
53 int tmp = 0;
54 string result = "";
55 for(int i=0;i<len;i++){
56 if(tmp+i-len>0){
57 break;
58 }
59 for(int j=len-1;j>=i;j--){
60 if(tmp>j-i+1){
61 break;
62 }
63 string str = s.substring(i,j+1);
64 boolean bl = true;
65 for(int m=0;m<(str.length()/2+1);m++){
66 character start = str.charat(m);
67 character end = str.charat(str.length()-m-1);
68 if(!start.equals(end)){
69 bl = false;
70 break;
71 }
72 }
73 if(bl && str.length()>tmp){
74 result = str;
75 tmp = str.length();
76 break;
77 }
78 }
79 }
80 system.out.println(result);
81 long endtime=system.currenttimemillis();
82 system.out.println("程序运行时间： "+(endtime-starttime)+"ms");
83 return result;
84 }
85
86
87 public static void main(string[] args) {
88 t_2_longestpalindrome lp = new t_2_longestpalindrome();
89 string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
90 lp.test2(s);
91 }
92
93 }
以上写了一个返回最长回文子串的程序（1000个a，回文字串就是如abcddcba、bcb，左右两边相同，当然a一个字符也是），之前使用的test1总是500以上的执行时间，时间总是无法降低，最后问题落到了两个截取字串位置上，经过修改，test2成功降低执行时间。
test1 使用 sub 截取字符串，执行时间500+ms
test2 使用 charat，执行时间180ms
以上可以明显看出执行效率的不同。