(B卷,100分)- 字符串分割（Java & JS & Python）

题目描述

给定非空字符串s，将该字符串分割成一些子串，使每个子串的ASCII码值的和均为水仙花数。

1、若分割不成功，则返回0；

2、若分割成功且分割结果不唯一，则返回-1；

3、若分割成功且分割结果唯一，则返回分割后子串的数目。

输入描述

输入字符串的最大长度为200

输出描述

根据题目描述中情况，返回相应的结果。

备注

"水仙花数"是指一个三位数，每位上数字的立方和等于该数字本身，如 371 是’水仙花数’，因为 371=3^3+7^3+1^3

用例

题目解析

我的解题思路如下：

首先将输入字符串变为一个ascii码值数组arr，比如f3@d5a8，就变为了 [102,51,64,100,53,97,56]

然后处理逻辑如下

let sum = 0
for(let i=0; i<arr.length; i++) {
sum += arr[i]
if(isSxh(sum)) { // 如果sum是水仙花数，则0~i子串可以组成水仙花数，下一个子串从i+1开始
let sum2 = 0
for(let j=i+1; j<arr.length; j++) {
sum2 += arr[j]
if(isSxh(sum2)) {// 如果sum2是水仙花数，则i+1~j子串可以组成水仙花数，下一个子串从j+1开始
let sum3 = 0
for(let k=j+1; k<arr.length; k++) {
sum3 += arr[k]
if(isSxh(sum3)) {// 如果sum3是水仙花数，则j+1~k子串可以组成水仙花数，下一个子串从k+1开始
// 重复以上逻辑
}
}
}
}
}
}

可以发现，上面逻辑可以使用递归来实现，当递归到子串长度为0时结束，或者无法没有下一次递归时结束。

在递归过程中，我们可以统计到一共有多少种分割方式，每种分割方式将字符串分为几段。

如果有0种分割方式，则打印0

如果有1种分割方式，则打印该分割方式可以将字符串分为几段

如果有2种或以上分割方式，则打印-1

本题还有一个优化点，就是基于前缀和，实现O(1)时间求解任意区间的元素之和。关于前缀和的应用请看：

2023.08.09

OJ用例库为了产生这样的子串：

ASCII码值的和均为水仙花数

因此，输入的字符串中会存在一些不常用的字符，这些字符可能会对输入获取逻辑产生影响，比如Java语言按照Scanner获取的话，则会以空白字符作为输入获取截止符，因此我们需要通过useDelimiter指定只有换行符才能截止输入获取。具体请看下面Java代码的输入获取逻辑。

更多输入获取知识可以看：华为OD机试ACM输入输出_伏城之外的博客-CSDN博客

对于JS和Python没有此类问题。

Java算法源码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in).useDelimiter("[n]");
    System.out.println(getResult(sc.next()));
  }

  public static int getResult(String s) {
    // 将字符串转化为ASCII数组
    char[] cArr = s.toCharArray();

    int n = cArr.length;

    // 前缀和，实现O(1)时间求解某区间内元素之和
    int[] preSum = new int[n + 1];
    for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + cArr[i - 1];

    // res记录成功分割的情况
    ArrayList<Integer> res = new ArrayList<>();
    // 递归
    recursive(preSum, n, 0, 0, res);

    if (res.size() == 0) return 0;
    else if (res.size() == 1) return res.get(0);
    else return -1;
  }

  public static void recursive(int[] preSum, int n, int start, int count, ArrayList<Integer> res) {
    if (start == n) {
      res.add(count);
      return;
    }

    for (int end = start + 1; end <= n; end++) {
      // 基于前缀和快速求解任意区间内的元素和
      if (isSxh(preSum[end] - preSum[start])) {
        recursive(preSum, n, end, count + 1, res);
      }
    }
  }

  // 判断num是否为水仙花数
  public static boolean isSxh(int num) {
    if (num <= 99 || num >= 1000) return false;

    int x = num / 100 % 10;
    int y = num / 10 % 10;
    int z = num % 10;

    return num == x * x * x + y * y * y + z * z * z;
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
rl.on("line", (line) => {
  console.log(getResult(line));
});
 
function getResult(str) {
  // 将字符串转化为ASCII数组
  const cArr = [...str].map((ele) => ele.charCodeAt());
 
  const n = cArr.length;
 
  // 前缀和，实现O(1)时间求解某区间内元素之和
  const preSum = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + cArr[i - 1];
 
  // res记录成功分割的情况
  const res = [];
  // 递归
  recursive(preSum, n, 0, 0, res);
 
  if (res.length === 0) return 0;
  else if (res.length === 1) return res[0];
  else return -1;
}
 
function recursive(preSum, n, start, count, res) {
  if (start === n) {
    res.push(count);
    return;
  }
 
  for (let end = start + 1; end <= n; end++) {
    // 基于前缀和快速求解任意区间内的元素和
    if (isSxh(preSum[end] - preSum[start])) {
      recursive(preSum, n, end, count + 1, res);
    }
  }
}
 
/* 判断入参是否为水仙花数 */
function isSxh(num) {
  if (num <= 99 || num >= 1000) return false;
  
  const x = parseInt(num / 100) % 10;
  const y = parseInt(num / 10) % 10;
  const z = num % 10;
  
  return num == x * x * x + y * y * y + z * z * z;
}

Python算法源码

# 输入获取
s = input()


# 判断num是否未水仙花数
def isSxh(num):
    if num <= 99 or num >= 1000:
        return False

    x, y, z = [int(c) for c in str(num)]

    return num == x ** 3 + y ** 3 + z ** 3


# 递归分割
def recursive(preSum, n, start, count, res):
    if start == n:
        res.append(count)
        return

    for end in range(start + 1, n + 1):
        if isSxh(preSum[end] - preSum[start]):
            recursive(preSum, n, end, count + 1, res)


# 算法入口
def getResult():
    # 将字符串转化为ASCII数组
    cArr = [ord(c) for c in s]

    n = len(cArr)

    # 前缀和，实现O(1)时间求解某区间内元素之和
    preSum = [0] * (n + 1)
    for i in range(1, n + 1):
        preSum[i] = preSum[i - 1] + cArr[i - 1]

    # res记录成功分割的情况
    res = []

    # 递归分割
    recursive(preSum, n, 0, 0, res)

    if len(res) == 0:
        return 0
    elif len(res) == 1:
        return res[0]
    else:
        return -1


# 算法调用
print(getResult())