题目描述
给定一个小写字母组成的字符串s,请找出字符串中两个不同位置的字符作为分割点,使得字符串分成的三个连续子串且子串权重相等,注意子串不包含分割点。
若能找到满足条件的两个分割点,请输出这两个分割点在字符串中的位置下标,若不能找到满足条件的分割点请返回0,0。
子串权重计算方式为:子串所有字符的ASCII码数值之和。
输入描述:
输入为一个字符串,字符串由a~z,26个小写字符组成,5 <= 字符串长度 <= 200。
输出描述:
输出为两个分割点在字符串中的位置下标,以逗号分隔
补充说明:
只考虑唯一解,不存在一个输入多种输出解的情况
收起
示例1
输入:
acdbbbca
输出:
2,5
说明:
以位置2和5作为分割点,将字符串分割为ac,bb,ca三个子串,每一个的子串权重都为196,输出为:2,5
示例2
输入:
abcabc
输出:
0,0
说明:
找不到符合条件的分割点,输出为0,0
题目解析
解题思路
使用贪心算法,遍历不同的切分点,将数据切分成三块
注意切分点的位置即可:
切点i:从1开始,到length-4
切点j:从i+2开始,到length-2
java_53">java实现
java">package com.HW;
/**
* @ClassName : TstrCutWeight
* @Author : kele
* @Date: 2023/10/24 22:01
* @Description :字符串划分
*/
public class TstrCutWeight {
public static void main(String[] args) {
handle("acdbbbca");
}
public static void handle(String str) {
char[] chars = str.toCharArray();
for (int i = 1; i < chars.length - 3; i++) {
for (int j = i + 2; j < chars.length - 1; j++) {
String s1 = str.substring(0, i);
String s2 = str.substring(i + 1, j);
String s3 = str.substring(j + 1, chars.length);
if (Weight(s1) == Weight(s2) && Weight(s2) == Weight(s3)) {
System.out.println(i + "," + (j));
return;
}
}
}
System.out.println("0,0");
}
public static int Weight(String str) {
int sum = 0;
for (char c : str.toCharArray()) {
sum += (int) c;
}
return sum;
}
}