问题描述
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.
输入
输入第一行是测试用例的个数，后面每一行表示一个数字组成的字符串，例如："123123"
输出
输出找到的满足要求的最长子串的长度。例如，给定的例子长度应该是 6。每行对应一个用例的结果。
示例输入
1
1538023
示例输出
4
1.递归解法
（1）若输入的数字字符串长度length为0或1，则结果为0
（2）若输入的数字字符串长度length为偶数：
a. 若前length/2位之和等于后length/2之和===>返回结果length
b. 若前length/2位之和不等于后length/2之和：===>寻找长度为length-2的子字符串：
（3）若输入的数字字符串长度length为奇数===>寻找长度为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.动态规划
上述递归解法存在大量重复计算，会超时。使用动态规划求解：
（1）构建DP[i]，长度为length，初始化全为0。i表示关注的字符串长度-1（-1方便编程）
（2）由于字串长度必为偶数，则DP[i]=DP[i-1]，i-1为奇数（即偶数位与上一奇数位相同）
（3）对于DP[j]，j为偶数，其取值范围为DP[i-1]~i+1（上限为字符串长度：i+1，下限为上一轮结果）:
a.整个字符串是否满足条件，满足则返回字符串长度：L=i+1，否则观察长度为L=L-2的子串是否满足
b.对于每个L<i+1，只需观察两种情况是否满足：
输入为1538023时构建DP的例子：
代码（将调用find改为调用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{
//判断整个字符串是否满足
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{
//不满足时，若上一轮的结果是整个字符串的长度，则可以不用计算。因为i-1是此时的下限
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;
}
}
//若未能在到达下限之前找到答案，则答案为下限
if(dp[i] == 0)
dp[i] = dp[i-2];
}
}
}
}
return dp[input.length-1];
}
}
网友评论