問題描述
???????Given a string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits.
輸入
???????輸入第一行是測試用例的個(gè)數(shù)，后面每一行表示一個(gè)數(shù)字組成的字符串，例如："123123"
輸出
???????輸出找到的滿足要求的最長子串的長度。例如，給定的例子長度應(yīng)該是 6。每行對應(yīng)一個(gè)用例的結(jié)果。
示例輸入
1
1538023
示例輸出
4
1.遞歸解法
???????（1）若輸入的數(shù)字字符串長度length為0或1，則結(jié)果為0
???????（2）若輸入的數(shù)字字符串長度length為偶數(shù)：
??????????????a. 若前l(fā)ength/2位之和等于后length/2之和===>返回結(jié)果length
??????????????b. 若前l(fā)ength/2位之和不等于后length/2之和：===>尋找長度為length-2的子字符串：
???????（3）若輸入的數(shù)字字符串長度length為奇數(shù)===>尋找長度為length-1的子字符串：
???????代碼：
import java.util.Scanner;
public class SymSubstr {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int casesnum = sc.nextInt();
sc.nextLine();
while(casesnum>0){
String temp = sc.nextLine();
int[] input = new int[temp.length()];
for(int i=0;i<input.length;i++){
input[i] = Integer.parseInt(temp.charAt(i)+"");
}
int result = find(input);
System.out.println(result);
casesnum --;
}
}
public static int find(int[] input){
if(input.length==0)
return 0;
if(input.length%2 == 0){
int sum1 = 0;
int sum2 = 0;
for(int i=0;i<input.length/2;i++){
sum1 += input[i];
}
for(int i=input.length/2;i<input.length;i++){
sum2 += input[i];
}
if(sum1 == sum2)
return input.length;
else{
int[] new1 = new int[input.length-2];
int[] new2 = new int[input.length-2];
int[] new3 = new int[input.length-2];
for(int i=0;i<input.length-2;i++){
new1[i] = input[i];
}
for(int i=2;i<input.length;i++){
new2[i-2] = input[i];
}
for(int i=1;i<input.length-1;i++){
new3[i-1] = input[i];
}
return Math.max(Math.max(find(new1),find(new2)),find(new3));
}
}
else{
int[] new1 = new int[input.length-1];
int[] new2 = new int[input.length-1];
for(int i=0;i<input.length-1;i++){
new1[i] = input[i];
}
for(int i=1;i<input.length;i++){
new2[i-1] = input[i];
}
return Math.max(find(new1),find(new2));
}
}
}
2.動(dòng)態(tài)規(guī)劃
???????上述遞歸解法存在大量重復(fù)計(jì)算，會(huì)超時(shí)。使用動(dòng)態(tài)規(guī)劃求解：
（1）構(gòu)建DP[i]，長度為length，初始化全為0。i表示關(guān)注的字符串長度-1（-1方便編程）
（2）由于字串長度必為偶數(shù)，則DP[i]=DP[i-1]，i-1為奇數(shù)（即偶數(shù)位與上一奇數(shù)位相同）
（3）對于DP[j]，j為偶數(shù)，其取值范圍為DP[i-1]~i+1（上限為字符串長度：i+1，下限為上一輪結(jié)果）:
???????a.整個(gè)字符串是否滿足條件，滿足則返回字符串長度：L=i+1，否則觀察長度為L=L-2的子串是否滿足
???????b.對于每個(gè)L<i+1，只需觀察兩種情況是否滿足：
???????輸入為1538023時(shí)構(gòu)建DP的例子：
???????代碼（將調(diào)用find改為調(diào)用DP）：
import java.util.Scanner;
public class SymSubstr {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int casesnum = sc.nextInt();
sc.nextLine();
while(casesnum>0){
String temp = sc.nextLine();
int[] input = new int[temp.length()];
for(int i=0;i<input.length;i++){
input[i] = Integer.parseInt(temp.charAt(i)+"");
}
int result = DP(input);
System.out.println(result);
casesnum --;
}
}
public static int DP(int[] input){
int[] dp = new int[input.length];
for(int i=0;i<dp.length;i++)
dp[i] = 0;
for(int i=1;i<input.length;i++){
if(i%2 == 0)
dp[i] = dp[i-1];
else{
//判斷整個(gè)字符串是否滿足
int sum1 = 0;
int sum2 = 0;
for(int j=0;j<=i/2;j++)
sum1 += input[j];
for(int j=i/2+1;j<=i;j++)
sum2 += input[j];
if (sum1 == sum2)
dp[i] = i+1;
else{
//不滿足時(shí)，若上一輪的結(jié)果是整個(gè)字符串的長度，則可以不用計(jì)算。因?yàn)閕-1是此時(shí)的下限
if(dp[i-1] == i-1)
dp[i] = i-1;
else{
for (int j=i-1;j>dp[i-2];j-=2){
//從i-1開始，按照長度遞減判斷是否存在子字符串
//sum3，sum4用于判斷情況1，sum5，sum6用于判斷情況2
int sum3 = 0;
int sum4 = 0;
int sum5 = 0;
int sum6 = 0;
//情況1
for(int k=i-j+1;k<i-j+1+j/2;k++)
sum3 += input[k];
for(int k=i-j+1+j/2;k<i+1;k++)
sum4 += input[k];
//情況2
for(int k=i-j;k<i-j+j/2;k++)
sum5 += input[k];
for(int k=i-j+j/2;k<i;k++)
sum6 += input[k];
if(sum3 == sum4 || sum5 == sum6) {
dp[i] = j;
break;
}
}
//若未能在到達(dá)下限之前找到答案，則答案為下限
if(dp[i] == 0)
dp[i] = dp[i-2];
}
}
}
}
return dp[input.length-1];
}
}
