华为OD机试 - 水仙花数Ⅱ - 动态规划（Java 2024 E卷 200分）

时间:2025/7/10 9:09:32来源：https://blog.csdn.net/guorui_java/article/details/142117933 浏览次数:0次

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

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

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

二、输入描述

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

三、输出描述

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

四、测试用例

测试用例1：

1、输入

f3@d5a8

2、输出

-1

3、说明

分割成功但分割结果不唯一，可以分割为两组，一组f3和@d5a8，另外一组f3@d5和a8。

测试用例2：

1、输入

AXY

2、输出

3、说明

字符串 AXY 可以有两种划分方式：

方案1：AX 和 Y，其ASCII和分别为153和89。153 是水仙花数，但89不是。

方案2：AXY 整体的ASCII和为 234，不是水仙花数。

无法划分为符合要求的子串，因此不能分割成功。

返回 0。

五、解题思路

这道题要求将字符串分割成若干子串，并且每个子串的ASCII码值的和必须是水仙花数。水仙花数是指一个三位数，每一位的立方和等于该数本身。

解题步骤：

水仙花数的判定：首先生成所有水仙花数(100到999之间的数字)，并存入一个集合中以便后续快速查找。
ASCII值和计算：遍历字符串，尝试将字符串划分为多个子串，计算每个子串的ASCII值之和，判断这些和是否为水仙花数。
动态规划求解：
- 使用动态规划的思想来解决这个问题。定义一个数组dp[i]，表示到索引i为止的字符串是否可以被划分，并且记录不同划分方案的数量。
- 初始化dp[0] = 1，表示空字符串可以被划分。
- 遍历字符串并尝试从每个位置开始到下一个位置，判断该子串的ASCII值之和是否为水仙花数，如果是，则更新dp数组。
结果判断：根据最终的dp值来判断结果：
- 若字符串不能被划分为符合条件的子串，则返回0。
- 若存在多个划分方案，则返回-1。
- 若唯一划分方案成功，则返回子串的数量。

六、Java算法源码

public class OdTest01 {// 生成所有水仙花数public static Set<Integer> generateNarcissisticNumbers() {Set<Integer> narcissisticNumbers = new HashSet<>();for (int i = 100; i <= 999; i++) {int hundred = i / 100;int ten = (i / 10) % 10;int one = i % 10;if (i == hundred * hundred * hundred + ten * ten * ten + one * one * one) {narcissisticNumbers.add(i);}}return narcissisticNumbers;}// 计算子串的ASCII和public static int getASCIISum(String s, int start, int end) {int sum = 0;for (int i = start; i < end; i++) {sum += (int) s.charAt(i);}return sum;}public static int partitionString(String s) {int n = s.length();Set<Integer> narcissisticNumbers = generateNarcissisticNumbers(); // 获取所有水仙花数int[] dp = new int[n + 1];int[] ways = new int[n + 1]; // 记录不同的划分方案数dp[0] = 1;  // 空字符串可以被划分ways[0] = 1;  // 初始只有一种划分方式for (int i = 1; i <= n; i++) {dp[i] = 0;  // 初始化不可划分状态for (int j = 0; j < i; j++) {int sum = getASCIISum(s, j, i);  // 计算从j到i的子串的ASCII和if (narcissisticNumbers.contains(sum)) {  // 如果子串的ASCII和是水仙花数if (dp[j] == 1) {dp[i] = 1;ways[i] += ways[j];  // 更新到i位置的划分方式数量}}}}if (dp[n] == 0) {return 0;  // 如果无法划分，返回0} else if (ways[n] > 1) {return -1;  // 如果有多种划分方式，返回-1} else {return dp[n];  // 返回唯一划分方案的子串数量}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 从控制台读取输入String input = scanner.nextLine();  // 从控制台读取输入的字符串// 调用partitionString方法计算结果int result = partitionString(input);// 输出结果System.out.println(result);}
}