华为OD机试 - 水仙花数Ⅱ - 动态规划（Python/JS/C/C++ 2024 E卷 200分）

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/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、输出

0

3、说明

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

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

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

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

返回 0。

五、解题思路

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

解题步骤：

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

六、Python算法源码

def generate_narcissistic_numbers():# 生成所有的水仙花数narcissistic_numbers = set()for i in range(100, 1000):hundred = i // 100ten = (i // 10) % 10one = i % 10if i == hundred ** 3 + ten ** 3 + one ** 3:narcissistic_numbers.add(i)return narcissistic_numbersdef get_ascii_sum(s, start, end):# 计算子串的ASCII和return sum(ord(s[i]) for i in range(start, end))def partition_string(s):n = len(s)narcissistic_numbers = generate_narcissistic_numbers()  # 获取所有水仙花数dp = [0] * (n + 1)ways = [0] * (n + 1)  # 记录不同的划分方案数dp[0] = 1  # 空字符串可以被划分ways[0] = 1  # 初始只有一种划分方式for i in range(1, n + 1):dp[i] = 0  # 初始化不可划分状态for j in range(i):sum_ascii = get_ascii_sum(s, j, i)  # 计算从j到i的子串的ASCII和if sum_ascii in narcissistic_numbers:  # 如果子串的ASCII和是水仙花数if dp[j] == 1:dp[i] = 1ways[i] += ways[j]  # 更新到i位置的划分方式数量if dp[n] == 0:return 0  # 如果无法划分，返回0elif ways[n] > 1:return -1  # 如果有多种划分方式，返回-1else:return dp[n]  # 返回唯一划分方案的子串数量def main():# 从控制台读取输入input_string = input("请输入字符串: ")  # 从控制台读取输入的字符串# 调用partition_string方法计算结果result = partition_string(input_string)# 输出结果print(result)if __name__ == "__main__":main()

七、JavaScript算法源码

// 生成所有水仙花数
function generateNarcissisticNumbers() {const narcissisticNumbers = new Set();for (let i = 100; i <= 999; i++) {const hundred = Math.floor(i / 100);const ten = Math.floor((i / 10) % 10);const one = i % 10;if (i === hundred ** 3 + ten ** 3 + one ** 3) {narcissisticNumbers.add(i);}}return narcissisticNumbers;
}// 计算子串的ASCII和
function getASCIISum(s, start, end) {let sum = 0;for (let i = start; i < end; i++) {sum += s.charCodeAt(i);}return sum;
}function partitionString(s) {const n = s.length;const narcissisticNumbers = generateNarcissisticNumbers(); // 获取所有水仙花数const dp = new Array(n + 1).fill(0);const ways = new Array(n + 1).fill(0); // 记录不同的划分方案数dp[0] = 1;  // 空字符串可以被划分ways[0] = 1;  // 初始只有一种划分方式for (let i = 1; i <= n; i++) {dp[i] = 0;  // 初始化不可划分状态for (let j = 0; j < i; j++) {const sum = getASCIISum(s, j, i);  // 计算从j到i的子串的ASCII和if (narcissisticNumbers.has(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];  // 返回唯一划分方案的子串数量}
}function main() {// 从控制台读取输入const input = prompt("请输入字符串: ");  // 从控制台读取输入的字符串// 调用partitionString方法计算结果const result = partitionString(input);// 输出结果console.log(result);
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>// 生成所有水仙花数
void generateNarcissisticNumbers(bool narcissisticNumbers[1000]) {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[i] = true;}}
}// 计算子串的ASCII和
int getASCIISum(const char* s, int start, int end) {int sum = 0;for (int i = start; i < end; i++) {sum += (int)s[i];}return sum;
}int partitionString(const char* s) {int n = strlen(s);bool narcissisticNumbers[1000] = { false };  // 存储是否是水仙花数generateNarcissisticNumbers(narcissisticNumbers);int dp[n + 1];   // 记录字符串是否可以被划分int ways[n + 1]; // 记录不同的划分方案数dp[0] = 1;       // 空字符串可以被划分ways[0] = 1;     // 初始只有一种划分方式for (int i = 1; i <= n; i++) {dp[i] = 0;  // 初始化为不可划分状态ways[i] = 0;for (int j = 0; j < i; j++) {int sum = getASCIISum(s, j, i);  // 计算从j到i的子串的ASCII和if (sum < 1000 && narcissisticNumbers[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];  // 返回唯一划分方案的子串数量}
}int main() {char input[1000];  // 假设输入的字符串长度不会超过1000printf("请输入一个字符串: ");fgets(input, sizeof(input), stdin);  // 从控制台读取输入的字符串// 去除换行符input[strcspn(input, "\n")] = 0;int result = partitionString(input);// 输出结果printf("%d\n", result);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <string>
#include <set>using namespace std;// 生成所有水仙花数
set<int> generateNarcissisticNumbers() {set<int> narcissisticNumbers;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.insert(i);}}return narcissisticNumbers;
}// 计算子串的ASCII和
int getASCIISum(const string& s, int start, int end) {int sum = 0;for (int i = start; i < end; i++) {sum += static_cast<int>(s[i]);}return sum;
}int partitionString(const string& s) {int n = s.length();set<int> narcissisticNumbers = generateNarcissisticNumbers(); // 获取所有水仙花数vector<int> dp(n + 1, 0);   // 记录字符串是否可以被划分vector<int> ways(n + 1, 0); // 记录不同的划分方案数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.find(sum) != narcissisticNumbers.end()) {  // 如果子串的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];  // 返回唯一划分方案的子串数量}
}int main() {string input;cout << "请输入一个字符串: ";getline(cin, input);  // 从控制台读取输入的字符串int result = partitionString(input);// 输出结果cout << result << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

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

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/146582.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

JavaWeb--纯小白笔记03：servlet入门---动态网页的创建

JavaWeb--纯小白笔记03：servlet入门---动态网页的创建

笔记&#xff1a;index.html在tomcat中为默认的名字&#xff0c;html里面的语法不严谨。改配置文件要小心&#xff0c;不然容易删掉其他 Servlet&#xff1a;服务器端小程序&#xff0c;写动态网页需要用Servlet&#xff0c;普通的java类通过继承HttpServlet&#xff0c;可以响…
阅读更多...
抖音如何改ip地址到另外城市

抖音如何改ip地址到另外城市

在数字化时代&#xff0c;抖音作为广受欢迎的社交媒体平台&#xff0c;不仅连接了亿万用户&#xff0c;也成为了展示个人生活、分享创意内容的重要舞台。然而&#xff0c;有时候出于隐私保护等需求&#xff0c;用户可能希望更改抖音账号显示的IP地址&#xff0c;使其看起来像是…
阅读更多...
超过1000篇文献？Mem)oRAG,下一代 RAG 技术，轻松让AI记住这些海量信息？

超过1000篇文献？Mem)oRAG,下一代 RAG 技术，轻松让AI记住这些海量信息？

想象一下，你每天要阅读几十篇文献，整理上千页的笔记，再将这些信息整合到自己的研究中，是不是有点头大？不光是你，很多人都有这样的困扰，尤其是在处理大量信息时。我们总是渴望一种更智能的方式，能帮我们高效地找到、理解并且运用这些知识。而这正是 MemoRAG 的用武之地。…
阅读更多...
会声会影2025视频剪辑教学

会声会影2025视频剪辑教学

会声会影2025是一款超级受欢迎的视频播放软件&#xff0c;用于剪辑和编辑各种类型的视频素材。软件具有直观的用户界面&#xff0c;使得即使对于初学者来说也能轻松上手。该软件提供了各种创意工具&#xff0c;可以帮助用户实现他们的创意想法。用户可以裁剪、合并和重新排列视…
阅读更多...
基于误差状态的卡尔曼滤波

基于误差状态的卡尔曼滤波

基于误差状态的卡尔曼滤波ESKF 注意这里的观测方程&#xff0c;是IMU的误差状态和激光定位的差值得到的。
阅读更多...
已解决sublime text 3 注册激活

已解决sublime text 3 注册激活

问题&#xff1a;未激活 解决方法&#xff1a; 安装sublime3后&#xff0c;将Patch.exe文件放入sublime 安装文件下 运行Patch.exe&#xff0c;复制粘贴注册码到 preference->enter license&#xff1b;操作如下 点击“Use license”,提示如下图表示激活成功&#xff1a; 重…
阅读更多...
学习笔记——EfficientNet

学习笔记——EfficientNet

EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks EfficientNet&#xff1a;重新思考卷积神经网络的模型扩展 论文下载地址&#xff1a; https://arxiv.org/abs/1905.11946 学习笔记参考了这位大佬&#xff1a;https://blog.csdn.net/qq_37541097/ar…
阅读更多...
【吊打面试官系列-MySQL面试题】列对比运算符是什么？

【吊打面试官系列-MySQL面试题】列对比运算符是什么？

大家好&#xff0c;我是锋哥。今天分享关于【列对比运算符是什么&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; 列对比运算符是什么&#xff1f; 在 SELECT 语句的列比较中使用&#xff0c;<>&#xff0c;<&#xff0c;<&#xff0c;> &#x…
阅读更多...
高校心理辅导：Spring Boot技术实现

高校心理辅导：Spring Boot技术实现

2 相关技术简介 2.1Java技术 Java是一种非常常用的编程语言&#xff0c;在全球编程语言排行版上总是前三。在方兴未艾的计算机技术发展历程中&#xff0c;Java的身影无处不在&#xff0c;并且拥有旺盛的生命力。Java的跨平台能力十分强大&#xff0c;只需一次编译&#xff0c;任…
阅读更多...
Spring Boot赋能高校心理健康教育

Spring Boot赋能高校心理健康教育

1绪 论 1.1研究背景 随着计算机和网络技术的不断发展&#xff0c;计算机网络已经逐渐深入人们的生活&#xff0c;网络已经能够覆盖我们生活的每一个角落&#xff0c;给用户的网上交流和学习提供了巨大的方便。 当今社会处在一个高速发展的信息时代&#xff0c;计算机网络的发展…
阅读更多...
做短剧申请微信小程序备案整体的操作流程！

做短剧申请微信小程序备案整体的操作流程！

做国内短剧对接微信小程序&#xff0c;小程序备案是必不可少的&#xff0c;需要准备哪些资料&#xff0c;以及需要注意的事项&#xff0c;所需材料全部整理出来了&#xff0c;小程序从注册到类目和备案分为五个步骤来讲解&#xff0c;下面就由我来向大家介绍所有的操作流程。 …
阅读更多...
【Linux】解锁系统编程奥秘，高效文件IO的实战技巧

【Linux】解锁系统编程奥秘，高效文件IO的实战技巧

文件 1. 知识铺垫2. C文件I/O2.1. C文件接口2.2 fopen()与重定向2.3. 当前路径2.4. stdin、stdout、stderr 3. 系统文件I/O3.1. 前言3.2. open3.2.1. flags</h3>3.2.2. mode</h3>3.2.3. 返回值fd 3.3. write</h2>3.4. read3.5. close</h2>3.6. lseek&l…
阅读更多...
牛啊，GitHub 代理加速图文教程

牛啊，GitHub 代理加速图文教程

大家好&#xff0c;众所周知&#xff0c;GitHub 在国内访问速度堪忧&#xff0c;经常出现访问不了的情况&#xff0c;如果我们去 clone 代码&#xff0c;网速非常差。今天教大家如何给 GitHub 进行加速。 要用到我开发的开源项目 Cloudflare Workers Proxy&#xff0c;它是一个…
阅读更多...
腾讯大模型算法实习生面试题，大家秋招上岸

腾讯大模型算法实习生面试题，大家秋招上岸

本人情况 关于博主: 博主是过年某985研二&#xff0c;过完年打算找大厂实习offer&#xff0c;本次主要记录了本小菜研找实习的坎坷历程&#xff0c; 欢迎大佬们给建议!!! 应聘岗位: 腾讯大模型算法实习生 面试轮数: 第一轮 整体面试感觉:偏难 技术问题 分布式训练框架都了解…
阅读更多...
定时重启Windows服务

定时重启Windows服务

文章目录 引言I 定时重启Windows服务II Windows服务管理使用net/sc命令结合taskkill进行服务的重启【推荐】通过命令行杀掉进程使用程序自带脚本管理服务知识扩展Windows7显示文件扩展通过进行名称查看进程号引言 基于任务计划程序，实现定时重启Windows服务。 核心：编写重启…
阅读更多...
Java8的Optional简介

Java8的Optional简介

文章目录 环境背景方法1&#xff1a;直接获取方法2&#xff1a;防御式检查方法3&#xff1a;Java 8的Optional概述map()测试 flatMap()测试 总结参考 注&#xff1a;本文主要参考了《Java 8实战》这本书。 环境 Ubuntu 22.04jdk-17.0.3.1 &#xff08;兼容Java 8&#xff09; …
阅读更多...
2024/9/21 英语每日一段

2024/9/21 英语每日一段

“Girls mature earlier than boys,” she says. “They hit rapid growth at 11, 12, whereas boys hit it about 13. Once you hit ‘peak height velocity’, training should concentrate on the structural side, push strength and muscle development. Girls are missin…
阅读更多...
部标（JT/T1078）流媒体对接说明

部标（JT/T1078）流媒体对接说明

1.前言 最近在配合客户开发流媒体相关的服务的时候&#xff0c;整理了一些对接过程资料&#xff0c;这里做个分享与记录。流媒体的对接主要牵扯到4个方面&#xff1a; &#xff08;1&#xff09;平台端&#xff1a;业务端系统&#xff0c;包含前端呈现界面。 &#xff08;2&a…
阅读更多...
Transformer宝藏入门教程，五天肝疯了—Transformer最全面的入门指南

Transformer宝藏入门教程，五天肝疯了—Transformer最全面的入门指南

随着 BERT、GPT 等大规模语言模型的兴起&#xff0c;越来越多的公司和研究者采用 Transformers 库来构建 NLP 应用。本文档教程里包括了自然语言处理、Transformer模型、注意力机制、pytorch、微调预训练模型、翻译任务、序列标注任务、文本摘要等等模块 一、内容介绍 《Tran…
阅读更多...
【正点原子K210连载】第三十九章 YOLO2人脸检测实验 摘自【正点原子】DNK210使用指南-CanMV版指南

【正点原子K210连载】第三十九章 YOLO2人脸检测实验 摘自【正点原子】DNK210使用指南-CanMV版指南

第三十九章 YOLO2人脸检测实验 从本章开始&#xff0c;将通过几个实例介绍Kendryte K210上的KPU&#xff0c;以及CanMV下KPU的使用方法&#xff0c;本章将先介绍YOLO2网络的人脸检测应用在CanMV上的实现。通过本章的学习&#xff0c;读者将学习到YOLO2网络的人脸检测应用在Can…
阅读更多...
最新文章

Copyright @ 2022~2023