(B卷,200分)- 字符串划分（Java & JS & Python & C）

题目描述

给定一个小写字母组成的字符串 s，请找出字符串中两个不同位置的字符作为分割点，使得字符串分成三个连续子串且子串权重相等，注意子串不包含分割点。

若能找到满足条件的两个分割点，请输出这两个分割点在字符串中的位置下标，若不能找到满足条件的分割点请返回0,0。

子串权重计算方式为:子串所有字符的ASCII码数值之和。

输入描述

输入为一个字符串，字符串由a~z，26个小写字母组成，5 ≤ 字符串长度 ≤ 200。

输出描述

输出为两个分割点在字符串中的位置下标，以逗号分隔

备注

只考虑唯一解，不存在一个输入多种输出解的情况

用例

题目解析

本题数量级不大，可以考虑暴力求解。即定义两个指针i, j，去模拟两个分割点，其中 i < j，且 j – i > 1，因为被分割的子串至少有1个字母。

另外，为了避免重复求解某范围内的子串权重，我们可以使用前缀和，实现O(1)时间计算出任意区间内的子串权重。

关于前缀和知识，可以看：

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const s = await readline();
  const chars = [...s].map((c) => c.charCodeAt());
  const n = chars.length;

  // 前缀和
  const preSum = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    preSum[i] = preSum[i - 1] + chars[i - 1];
  }

  // i,j是分割点
  for (let i = 1; i < n; i++) {
    // sum1 是 0 ~ i-1 范围的ASCII码之和
    const sum1 = preSum[i] - preSum[0];

    for (let j = i + 2; j < n; j++) {
      // sum2 是 i + 1 ~ j - 1 范围的ASCII码之和
      const sum2 = preSum[j] - preSum[i + 1];

      // 剪枝
      if (sum1 < sum2) break;

      if (sum1 == sum2) {
        // sum3 是 j + 1 ~ n - 1 范围的ASCII码之和
        const sum3 = preSum[n] - preSum[j + 1];

        if (sum2 == sum3) {
          return console.log(`${i},${j}`);
        }
      }
    }
  }

  console.log("0,0");
})();

Java算法源码

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLine()));
  }

  public static String getResult(String s) {
    char[] chars = s.toCharArray();
    int n = chars.length;

    // 前缀和
    int[] preSum = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      preSum[i] = preSum[i - 1] + chars[i - 1];
    }

    // i,j是分割点
    for (int i = 1; i < n; i++) {
      // sum1 是 0 ~ i-1 范围的ASCII码之和
      int sum1 = preSum[i] - preSum[0];
      for (int j = i + 2; j < n; j++) {
        // sum2 是 i + 1 ~ j - 1 范围的ASCII码之和
        int sum2 = preSum[j] - preSum[i + 1];

        // 剪枝
        if (sum1 < sum2) break;

        if (sum1 == sum2) {
          // sum3 是 j + 1 ~ n - 1 范围的ASCII码之和
          int sum3 = preSum[n] - preSum[j + 1];

          if (sum2 == sum3) {
            return i + "," + j;
          }
        }
      }
    }

    return "0,0";
  }
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    chars = list(map(ord, s))
    n = len(chars)

    # 前缀和
    preSum = [0] * (n+1)
    for i in range(1, n + 1):
        preSum[i] = preSum[i - 1] + chars[i - 1]

    # i,j是分割点
    for i in range(1, n):
        # sum1 是 0 ~ i-1 范围的ASCII码之和
        sum1 = preSum[i] - preSum[0]

        for j in range(i + 2, n):
            # sum2 是 i + 1 ~ j - 1 范围的ASCII码之和
            sum2 = preSum[j] - preSum[i + 1]

            # 剪枝
            if sum1 < sum2:
                break

            if sum1 == sum2:
                # sum3 是 j + 1 ~ n - 1 范围的ASCII码之和
                sum3 = preSum[n] - preSum[j + 1]

                if sum2 == sum3:
                    return f"{i},{j}"

    return "0,0"


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX_SIZE 200

int main()
{
char str[MAX_SIZE];
scanf("%s", str);

int n = strlen(str);

// 前缀和
int preSum[MAX_SIZE + 1] = {0};
for(int i=1; i<=n; i++) {
preSum[i] = preSum[i-1] + str[i-1];
}

// i,j是分割点
for(int i=1; i<n; i++) {
// sum1 是 0 ~ i-1 范围的ASCII码之和
int sum1 = preSum[i] - preSum[0];

for(int j=i+2; j<n; j++) {
// sum2 是 i + 1 ~ j - 1 范围的ASCII码之和
int sum2 = preSum[j] - preSum[i+1];

// 剪枝
if(sum1 < sum2) break;

if(sum1 == sum2) {
// sum3 是 j + 1 ~ n - 1 范围的ASCII码之和
int sum3 = preSum[n] - preSum[j+1];

if(sum2 == sum3) {
printf("%d,%d", i, j);
return 0;
}
}
}
}

printf("0,0");

return 0;
}