(新卷,100分)- 字符串分割（Java JS Python）-平芜编程栈

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

题目描述

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

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

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

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

输入描述

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

输出描述

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

备注

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

用例

输入	abc
输出	0
说明	分割不成功

输入	f3@d5a8
输出	-1
说明	分割成功但分割结果不唯一，可以分割为两组，一组’f3’和’@d5a8’，另外一组’f3@d5’和’a8’

输入	AXdddF
输出	2
说明	分割成功且分割结果唯一，可以分割’AX’(153)和’dddF’(370)成两个子串

题目解析

我的解题思路如下：

首先将输入字符串变为一个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)时间求解任意区间的元素之和。

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

ASCII码值的和均为水仙花数

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

对于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())