每日一题——把数字翻译成字符串
把数字翻译成字符串
- 题目描述
- 示例
- 示例1
- 示例2
- 题解
- 动态规划
- 代码实现
- 复杂度分析
- 总结
题目描述
有一种将字母编码成数字的方式:‘a’->1, ‘b’->2, … , ‘z’->26。
现在给一串数字,返回有多少种可能的译码结果。
数据范围:字符串长度满足 (0 < n \leq 90)
进阶:空间复杂度 (O(n)),时间复杂度 (O(n))
示例
示例1
输入:
"12"
返回值:
2
说明:
2种可能的译码结果(“ab” 或 “l”)
示例2
输入:
"31717126241541717"
返回值:
192
说明:
192种可能的译码结果
题解
动态规划
我们可以使用动态规划来解决这个问题。设 dp[i] 表示前 i 个数字可以翻译成多少种不同的字符串。状态转移方程如下:
- 如果当前数字
nums[i]不为0,则dp[i] += dp[i-1]。 - 如果当前数字
nums[i-1]和nums[i]组成的两位数在10到26之间,则dp[i] += dp[i-2]。
边界条件:
dp[0] = 1,表示空字符串有一种翻译方式。dp[1] = 1,如果第一个字符不为0,则有一种翻译方式。
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 解码函数
int solve(char* nums) {int length = strlen(nums); // 获取输入字符串的长度if (length == 0) return 0; // 如果字符串为空,返回0// 分配动态规划数组,dp[i] 表示前 i 个字符的解码方法数int* dp = (int*)calloc(length + 1, sizeof(int));dp[0] = 1; // 空字符串有一种解码方式// 初始化第一个字符的解码方法数if (nums[0] > '0' && nums[0] <= '9') {dp[1] = 1; // 如果第一个字符是有效的数字(1-9),有一种解码方式} else {return 0; // 如果第一个字符无效(如 '0'),直接返回0}// 遍历字符串,计算每个位置的解码方法数for (int i = 1; i < length; i++) {// 将当前字符和前一个字符组合成一个两位数int two = (nums[i-1] - '0') * 10 + (nums[i] - '0');// 如果当前字符是 '0'if (nums[i] == '0') {// 如果两位数无效(如 '00' 或大于 '26'),返回0if (two == 0 || two >= 30) {return 0;}// 当前位置的解码方法数等于前两个字符的解码方法数dp[i+1] = dp[i-1];} // 如果两位数在 11 到 26 之间,可以解码为一个字母else if (two >= 11 && two <= 26) {// 当前位置的解码方法数等于前一个字符和前两个字符的解码方法数之和dp[i+1] = dp[i] + dp[i-1];} // 其他情况,当前字符单独解码else {dp[i+1] = dp[i];}}// 获取最终结果int result = dp[length];free(dp); // 释放动态规划数组return result;
}int main() {char nums[] = "226"; // 示例输入int result = solve(nums); // 调用解码函数printf("Number of ways to decode: %d\n", result); // 打印结果return 0;
}
复杂度分析
- 时间复杂度:(O(n)),其中 (n) 是字符串的长度。我们只需要遍历一次字符串即可。
- 空间复杂度:(O(n)),用于存储动态规划数组
dp。
总结
本题通过动态规划的方法,将问题分解为子问题,逐步求解。通过状态转移方程,我们可以有效地计算出所有可能的译码结果。这题最傻逼的就是如何处理0,还好只要考虑“00”到“99”一百种情况。所以不需要考虑太多。
相关文章:
每日一题——把数字翻译成字符串
把数字翻译成字符串 题目描述示例示例1示例2 题解动态规划代码实现复杂度分析 总结 题目描述 有一种将字母编码成数字的方式:‘a’->1, ‘b’->2, … , ‘z’->26。 现在给一串数字,返回有多少种可能的译码结果。 数据范围:字符串…...
我们来学HTTP/TCP -- 三次握手?
三次握手 题记三次呼叫结语 题记 来,我们来演示下川普王和普京帝会面了 哎呦!你好你好,握手…哎嗨!侬好侬好,握手…欧嘿呦玛斯,握手… 抓狂啊!作孽啊!!! 不说人话啊! 关键的是,“三…...
多媒体软件安全与授权新范例,用 CodeMeter 实现安全、高效的软件许可管理
背景概述 Reason Studios 成立于 1994 年,总部位于瑞典斯德哥尔摩,是全球领先的音乐制作软件开发商。凭借创新的软件产品和行业标准技术,如 ReWire 和 REX 文件格式,Reason Studios 为全球专业音乐人和业余爱好者提供了一系列高质…...
SQL复习
SQL复习 MySQL MySQL MySQL有什么特点? MySQL 不支持全外连接。 安装 数据类型 MySQL中的数据类型分为哪些? MySQL中的数据类型主要分为三大类:数值类型、字符串类型、日期时间类型。 其中, 数值类型又分为七种:T…...
红队视角出发的k8s敏感信息收集——日志与监控系统
针对 Kubernetes 日志与监控系统 的详细攻击视角分析,聚焦 集群审计日志 和 Prometheus/Grafana 暴露 的潜在风险及利用方法 攻击链示例 1. 攻击者通过容器逃逸进入 Pod → 2. 发现未认证的 Prometheus 服务 → 3. 查询环境变量标签获取数据库密码 → 4. 通过审…...
Flask中获取请求参数的一些方式总结
在 Flask 中,可以从 request 对象中获取各种类型的参数。以下是全面整理的获取参数的方式及示例代码。 1. 获取 URL 查询参数(Query String Parameters) URL 中的查询参数通过 ?keyvalue&key2value2 的形式传递,使用 reques…...
架构——LVS负载均衡主要模式及其原理、服务水平、优缺点
LVS(Linux Virtual Server)是一款高性能的开源负载均衡软件,支持多种负载均衡模式。以下是其主要模式及其原理、服务水平、优缺点: 1. NAT 模式(Network Address Translation) 原理: 请求流程…...
【漫话机器学习系列】093.代价函数和损失函数(Cost and Loss Functions)
代价函数和损失函数(Cost and Loss Functions)详解 1. 引言 在机器学习和深度学习领域,代价函数(Cost Function)和损失函数(Loss Function)是核心概念,它们决定了模型的优化方向。…...
Android 13 上通过修改 AOSP 拦截 SystemUI 音量调节事件
定位关键代码SystemUI 的音量调节逻辑主要集中在以下类中: VolumeDialogController.java:负责与 AudioService 交互。 VolumeDialogImpl.java:处理 UI 交互事件(如按钮点击)。 PhoneWindowManager.java:处理物理按键事件(如音量键)。 拦截音量调节事件 以 VolumeDialog…...
SQL与数据库程序设计
1.1986年,10月美国国家标准局颁布了SQL语言的美国标准,称为SQL86 2.SQL(Structured Query Language)又称为结构化查询语言 3.建立索引的主要目的是加快查找的速度 4.在基本表上建立一个或者多个索引 5. 一个基本表是最多只能建立一个聚簇索引 6.CAL…...
大模型Deepseek的使用_基于阿里云百炼和Chatbox
目录 前言1. 云服务商2. ChatBox参考 前言 上篇博文中探索了(本地)部署大语言模型,适合微调、数据高隐私性等场景。随着Deepseek-R1的发布,大语言模型的可及性得到极大提升,应用场景不断增加,对高可用的方…...
AlmaLinux9.5安装samba实现与Windows文件共享 笔记250214
Fedora41安装samba实现与Windows文件共享 笔记241202 步骤: 安装samba, 并启用 smb , nmb 服务 切换阿里源(可选) ### 备份 /etc/yum.repos.d 文件夹 tempUri/etc/yum.repos.d ; sudo cp -a $tempUri $tempUri.$(date %0y%0m%0d%0H%0M%0Sns%0N).bak sed -e s|^mirrorli…...
二〇二四年终总结
写在前面 简单总结一下告诉自己,曾经活着 不必太纠结于当下,也不必太忧虑未来,当你经历过一些事情的时候,眼前的风景已经和从前不一样了。——村上春树 原本应该 24 年年中的时候写 23 年年终的总结,但是一直拖着&…...
学习sql的资源:sql练习平台;在线编辑器,免费sql教程,免费sql书籍
sql练习平台 LeetCode力扣(部分免费) 题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台 HackerRank 解决 SQL |黑客排名 SQLPad SQL、Python 和 R 面试问题 StrataScratch StrataScratch - Analytical Questions 数据雷mur Free SQL Tutorial for Data Analysts …...
宝塔和docker的区别
宝塔面板 vs Docker:区别、场景与互补使用指南 eepseek回答宝塔和docker的区别 好的,我现在需要回答用户关于宝塔面板和Docker之间的区别的问题。首先,我需要明确这两个工具各自的定义、功能以及它们适用的场景,这样才能准确比较…...
机器学习--实现多元线性回归
机器学习—实现多元线性回归 本节顺延机器学习--线性回归中的内容,进一步讨论多元函数的回归问题 y ′ h ( x ) w ⊤ ∙ x b y^{\prime}h(x)w^\top\bullet xb y′h(x)w⊤∙xb 其中, w T ⋅ x 就是 W 1 X 1 w 2 X 2 w 3 X 3 ⋯ w N X N \text{其中,}w^\math…...
【JavaScript】《JavaScript高级程序设计 (第4版) 》笔记-Chapter2-HTML 中的 JavaScript
二、HTML 中的 JavaScript 将 JavaScript 插入 HTML 的主要方法是使用<script>元素。 <script>元素有下列 8 个属性。 async:可选。表示应该立即开始下载脚本,但不能阻止其他页面动作,比如下载资源或等待其他脚本加载。只对外部…...
【人工智能】释放数据潜能:使用Featuretools进行自动化特征工程
《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门! 解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 特征工程是机器学习流程中至关重要的一步,它直接影响模型的性能。然而,手动特征工程既耗时又需要领域专业知识。Featuretools是一个强大的…...
算法——对比A*算法与IDA*算法
A*算法与IDA*算法详细解析 1. A*算法 核心思想: A*算法是一种启发式搜索算法,结合了Dijkstra算法的最短路径保证和贪心最佳优先搜索的高效导向性。其核心是评估函数 ( f(n) g(n) h(n) ),其中: ( g(n) ): 从起点到当前节点 ( …...
GitLab CI/CD 的配置详解:从零开始使用 .gitlab-ci.yml 文件
在现代软件开发中,CI/CD(持续集成与持续部署)已成为提高开发效率和代码质量的核心实践。GitLab CI/CD 提供了强大的功能,帮助开发者自动化构建、测试和部署应用程序。而 .gitlab-ci.yml 文件是 GitLab CI/CD 配置的关键所在&#…...
B站缓存视频永久保存指南:m4s-converter让你的珍贵内容不再消失
B站缓存视频永久保存指南:m4s-converter让你的珍贵内容不再消失 【免费下载链接】m4s-converter 一个跨平台小工具,将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter 你是否曾有过这样的经…...
基于NapCat的QQ机器人框架openclaw-NapCatQQ部署与开发指南
1. 项目概述:一个为QQ协议打造的现代化机器人框架最近在折腾机器人项目,发现一个挺有意思的开源项目叫openclaw-NapCatQQ。乍一看这个名字,可能有点摸不着头脑,但如果你对QQ机器人生态有所了解,就会知道这背后代表着一…...
5大架构优势:i茅台智能预约系统的实战解决方案与高效部署指南
5大架构优势:i茅台智能预约系统的实战解决方案与高效部署指南 【免费下载链接】campus-imaotai i茅台app自动预约,每日自动预约,支持docker一键部署(本项目不提供成品,使用的是已淘汰的算法) 项目地址: h…...
智能解放双手:阴阳师自动化脚本SmartOnmyoji完整实战指南
智能解放双手:阴阳师自动化脚本SmartOnmyoji完整实战指南 【免费下载链接】SmartOnmyoji 阴阳师后台代肝脚本,支持所有类似阴阳师的卡牌游戏(点点点游戏)自动找图-点击…(支持后台运行、支持多开、支持模拟器ÿ…...
43-Android系统源码-ExoPlayer 实战 - Android 应用级媒体播放器核心技术
ExoPlayer 实战 - Android 应用级媒体播放器核心技术 源码: external/exoplayer (两个 tree 版本, ~1000 个 Java 文件) 版本: commit 8e57d371 (2022-04-11 更新) 协议: Apache License 2.0 用途: Google 开源的应用级媒体播放器,支持 DASH、HLS、SmoothStreaming 自适应流媒…...
Docker 与 Kubernetes 中的 Java 应用监控:确保应用健康运行
Docker 与 Kubernetes 中的 Java 应用监控:确保应用健康运行 核心概念 在容器化和云原生环境中,监控 Java 应用是确保应用健康运行的关键。通过监控,可以及时发现和解决问题,提高应用的可靠性和可用性。Docker 和 Kubernetes 提供…...
嵌入式系统行为建模:原子化需求与UML状态机实践
1. 嵌入式系统行为建模的核心挑战在嵌入式系统开发领域,我们经常面临一个根本性矛盾:系统功能日益复杂,但市场窗口期却越来越短。以智能家居网关开发为例,十年前可能只需要处理简单的协议转换,而现在要同时支持语音交互…...
在Windows 7上折腾YOLOv3?用Cygwin编译Darknet的保姆级避坑实录
在Windows 7上折腾YOLOv3?用Cygwin编译Darknet的保姆级避坑实录 十年前的老旧笔记本突然被征用,要求跑一个目标检测demo——甲方坚持用Windows 7系统,而项目依赖的YOLOv3需要Linux环境。当Cygwin遇上停止维护的Windows 7,这场跨越…...
通达信缠论插件:3步实现自动化技术分析,告别手工画线烦恼
通达信缠论插件:3步实现自动化技术分析,告别手工画线烦恼 【免费下载链接】ChanlunX 缠中说禅炒股缠论可视化插件 项目地址: https://gitcode.com/gh_mirrors/ch/ChanlunX 你是否还在为缠论分析中繁琐的笔段划分而头疼?面对复杂的K线走…...
通过审计日志功能追踪和管理团队的 API Key 使用情况
通过审计日志功能追踪和管理团队的 API Key 使用情况 1. 审计日志的核心价值 在团队协作使用大模型 API 的场景中,管理员需要清晰掌握每个成员或项目的资源消耗情况。Taotoken 提供的审计日志功能能够记录每一次 API 调用的关键信息,包括调用时间、使用…...
