每日一题——把数字翻译成字符串
把数字翻译成字符串
- 题目描述
- 示例
- 示例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。 现在给一串数字,返回有多少种可能的译码结果。 数据范围:字符串…...
基于状态观测器和物联网基础设施的智能电网高速孤岛检测
论文标题 中文标题: 基于状态观测器和物联网基础设施的智能电网高速孤岛检测 英文标题: High-Speed Islanding Detection in Smart Grids Using a State Observer and IoT Infrastructure 作者信息 Shahid Karim<sup>1,2, *</sup>, Prajo…...
FPGA的星辰大海
编者按 时下风头正盛的DeepSeek,正值喜好宏大叙事的米国大统领二次上岗就业,OpenAI、软银、甲骨文等宣布投资高达5000亿美元“星际之门”之际,对比尤为强烈。 某种程度上,,是低成本创新理念的直接落地。 包括来自开源社区的诸多赞誉是,并非体现技术有多“超越”,而是…...
【Black Mesa】黑山起源用服务器开服多人联机教程
1、登录服务器(百度莱卡云游戏面板) 进入控制面板后会出现正在安装的界面,安装大约10分钟(如长时间处于安装中请联系我们的客服人员) 2、修改端口 看到一下图片的界面时说明服务器已经安装完成,服务器需要…...
【学习笔记】深度学习网络-深度模型中的优化
作者选择了由 Ian Goodfellow、Yoshua Bengio 和 Aaron Courville 三位大佬撰写的《Deep Learning》(人工智能领域的经典教程,深度学习领域研究生必读教材),开始深度学习领域学习,深入全面的理解深度学习的理论知识。 在之前的文章中介绍了深度学习中…...
java八股文之Redis
1.Rdis常见的使用场景 缓存分布式锁(redision,setnx)计数器保存token消息队列延迟队列 2.说明一下缓存雪崩,缓存穿透和缓存击穿以及解决方式 1.缓存雪崩 定义: 缓存雪崩指的是当大量的缓存数据同时失效,…...
ubuntu系统下KVM设置桥接网络(失败)
20250216 - 概述 因实验需求,需要设置KVM下的虚拟机采用桥接模式进行通信,这种方式将使虚拟机与主机类似使用同一网段的IP。实际上,为了实现这个功能,我已经在自己mac上VMware使用过,虚拟机获得了自己独立的IP。 但…...
CentOS 7操作系统部署KVM软件和创建虚拟机
CentOS 7.9操作系统部署KVM软件和配置指南,包括如何创建一个虚拟机。 步骤 1: 检查硬件支持 首先,确认您的CPU支持虚拟化技术,并且已在BIOS中启用: egrep -c (vmx|svm) /proc/cpuinfo 如果输出大于0,则表示支持虚拟…...
驱动开发系列38 - Linux Graphics 3D 绘制流程(一)- 创建画布
一:概述 当应用程序创建 OpenGL 上下文时,它通常需要申请帧缓冲(Framebuffer,即画布)。在 X11 体系下,应用程序不会直接向内核的 DRM 模块请求创建帧缓冲,而是通过 X 服务器进行申请。 虽然从技术上讲,应用程序可以直接使用 DRM 接口创建帧缓冲对象(BO),但为了将其与…...
Spring Boot过滤器链:从入门到精通
文章目录 一、过滤器链是什么?二、为什么需要过滤器链?三、Spring Boot中的过滤器链是如何工作的?(一)过滤器的生命周期(二)过滤器链的执行流程 四、如何在Spring Boot中定义自己的过滤器&#…...
QT 读写锁
一、概述 1、读写锁是一种线程同步机制,用于解决多线程环境下的读写竞争问题。 2、读写锁允许多个线程同时获取读锁(共享访问),但只允许一个线程获取写锁(独占访问)。 3、这种机制可以提高并发性能&…...
C++中的智能指针
智能指针总结 智能指针其作⽤是管理⼀个指针,避免程序员申请的空间在函数结束时忘记释放,造成内存泄漏这种情况滴发⽣。使⽤智能指针可以很⼤程度上的避免这个问题,因为智能指针就是⼀个类,当超出了类的作⽤域是,类会…...
IntelliJ IDEA 接入 AI 编程助手(Copilot、DeepSeek、GPT-4o Mini)
IntelliJ IDEA 接入 AI 编程助手(Copilot、DeepSeek、GPT-4o Mini) 📊 引言 近年来,AI 编程助手已成为开发者的高效工具,它们可以加速代码编写、优化代码结构,并提供智能提示。本文介绍如何在 IntelliJ I…...
【R语言】非参数检验
一、Mann-Whitney检验 在R语言中,Mann-Whitney U检验(也称为Wilcoxon秩和检验)用于比较两个独立样本的中位数是否存在显著差异。它是一种非参数检验,适用于数据不满足正态分布假设的情况。 1、独立样本 # 创建两个独立样本数据…...
PyTorch 源码学习:阅读经验 代码结构
分享自己在学习 PyTorch 源码时阅读过的资料。本文重点关注阅读 PyTorch 源码的经验和 PyTorch 的代码结构。因为 PyTorch 不同版本的源码实现有所不同,所以笔者在整理资料时尽可能按版本号升序,版本号见标题前[]。最新版本的源码实现还请查看 PyTorch 仓…...
04运维实用篇(D4_日志)
目录 一、简介 二、代码中使用日志工具记录日志 1. 操作步骤 步骤1:添加日志记录操作 步骤2:设置日志输出级别 步骤3:设置日志组 2. 知识小结 三、优化日志对象创建代码 1. 实例 2. 总结 四、日志输出格式控制 1. 实例 2. 总结 …...
Linux文件管理:硬链接与软链接
文章目录 1. 硬链接的设计目的(1)节省存储空间(2)提高文件管理效率(3)数据持久性(4)文件系统的自然特性 2. 软链接的设计目的**(1)跨文件系统引用****&#x…...
【零基础学Mysql】常用函数讲解,提升数据操作效率的利器
以耳倾听世间繁华,以语表达心中所想 大家好,我是whisperrrr. 前言: 大家好,我是你们的朋友whisrrr。在日常工作中,MySQL作为一款广泛使用的开源关系型数据库,其强大的功能为我们提供了便捷的数据存储和管理手段。而在…...
小米平板怎么和电脑共享屏幕
最近尝试使用小米平板和电脑屏幕分屏互联 发现是需要做特殊处理的,需要下载一款电脑安装包:小米妙享 关于这个安装包,想吐槽的是: 没有找到官网渠道,是通过其他网络方式查到下载的 不附录链接,原因是因为地…...
宝藏软件系列 篇一:My APK(Android)
文章目录 系列文章官方网站特色功能同类软件 系列文章 官方网站 My APK 官方版本是在 谷歌商店 中上架的。 官方下载地址:Google Play 商店页面。(需要外网) 2025.2最新版本的CSDN本地下载地址(因为是Android App Bundle&…...
本地 Ollama 部署 Deepseek R1 并使用 Spring AI Alibaba 构建 Chat 应用示例
本地部署 Deepseek R1 并使用 Spring AI Alibaba 构建 Chat 应用示例 Ollama 部署 Deepseek R1 官网:https://www.deepseek.com/ Github:https://github.com/deepseek-ai Ollama:https://ollama.com/ Docker Compose 部署一个 Ollama 和…...
centos8.0 docker ngnix
问题1:镜像拉取不下来,用DAO云加速器 问题2:ngnix镜像不能运行, 无法检索OCI运行时错误 在CentOS上使用Docker来运行Nginx是一个常见的做法,因为它提供了快速、一致的环境配置方式,并且可以很容易地扩展。…...
位运算在数据库中的运用实践-以MySQL和PG为例
目录 前言 一、两种不同的数据库设计 1、状态字段存储JSON 2、使用位运算 二、数据库中的位运算实践 1、MySQL中的位运算实践 2、PostgreSQL中位运算实践 三、总结 前言 最近在解决某用户的一个业务需求时,遇到一个很有意思的场景。首先先跟大家分享一下需…...
IoTDB 常见问题 QA 第五期
关于 IoTDB 的 Q & A 情人节之际,让 IoTDB Q&A 陪您一起共度解惑!我们将定期汇总我们将定期汇总社区讨论频繁的问题,并展开进行详细回答,通过积累常见问题“小百科”,方便大家使用 IoTDB。 Q1:导入…...
【kafka系列】日志存储设计 消息写入、读取
目录 日志存储设计 1. 日志存储的目录结构 2. 日志内容格式设计 3. 日志索引设计 4. 设计优势 消息写入流程 示例 流程图 消息读取流程 示例 关键设计细节 流程图 日志存储设计 Kafka的日志存储是其高吞吐、持久化能力的核心设计,其结构包含目录组织、…...
Python实现语音识别详细教程【2025】最新教程
文章目录 前言一、环境搭建1. 下载 Python2. 安装 Python3 使用 pip 安装必要的库 二、使用 SpeechRecognition 库进行语音识别1.识别本地音频文件2.实时语音识别3. 使用其他语音识别引擎 注意事项 前言 以下是一份较为完整的 Python 语音识别教程,涵盖环境搭建、使…...
【一文读懂】HTTP与Websocket协议
HTTP协议 概述 HTTP (Hypertext Transfer Protocol),即超文本传输协议,是一种用于在客户端和服务器之间传输超文本(例如网页、图片、音频、视频等)的通信协议。它是万维网(WWW)的基础,负责在浏…...
SpringBoot+微信小程序+数据可视化的宠物到家喂宠服务(程序+论文+讲解+安装+调试+售后等)
感兴趣的可以先收藏起来,还有大家在毕设选题,项目以及论文编写等相关问题都可以给我留言咨询,我会一一回复,希望帮助更多的人。 系统介绍 在经济高速发展、物质生活极大丰富的当下,人们的精神需求愈发凸显࿰…...
Windows逆向工程入门之堆栈结构与信息获取
公开视频 -> 链接点击跳转公开课程博客首页 -> 链接点击跳转博客主页 目录 1. 堆栈结构基础 堆栈的主要操作: 2. 代码功能解析 2.1 加载 ntdll.dll 2.2 获取 NtQueryInformationThread 函数指针 2.3 调用 NtQueryInformationThread 获取线程信息…...
springboot项目如何部署到tomcat中
1、使用springboot内部嵌入的tomcat 可以改一些tomcat的参数 2、可以把springboot项目打包为war包,然后部署到tomcat中去 Spring Boot 默认使用嵌入式 Tomcat 作为其 Web 容器,这使得 Spring Boot 应用可以作为一个独立的 JAR 文件运行。这种嵌入式服务…...
C语言之easyX
目录 概要 easyX整体架构 图形绘制 画布宽高 圆形 图片的贴图 加载图像 游戏框架 概要 easyX是一个轻量级的图形库,用于在Windows平台上进行简单的2D图形绘制。它提供了一组简单易用的函数,可以方便地绘制基本的图形元素,如线条、矩形、圆形…...
es6箭头函数和普通函数的区别
在JavaScript中,函数是执行特定任务的代码块。函数可以被定义并且随后被调用。JavaScript中有两种主要的函数定义方式:普通函数声明和箭头函数表达式。下面是这两种函数的定义方式及其区别和使用场景: 普通函数声明 普通函数可以通过函数声明…...
DeepSeek R1 32B 本地部署实战
#DeepSeek# DeepSeek是一款基于人工智能的智能助手,专为提升工作效率和信息获取能力而设计。它结合了自然语言处理、机器学习和大数据技术,能够快速理解用户需求并提供精准的答案或解决方案。 DeepSeek的核心功能 智能问答 DeepSeek可以回答各种问题&…...
八、SPI读写XT25数据
8.1 SPI 简介 SPI(Serial Peripheral Interface,串行外设接口)是一种同步串行通信协议,广泛用于嵌入式系统中连接微控制器与外围设备,如传感器、存储器、显示屏等。 主要特点 1. 全双工通信:支持同时发送…...
AIP-145 范围
编号145原文链接AIP-145: Ranges状态批准创建日期2020-05-28更新日期2020-05-28 服务通常需要表示具体值或连续值的范围。这些范围的含义存在诸多差异,也存在许多数据类型:整数、浮点数、时间戳等(在此仅举几例)。根据所讨论范围…...
(学习总结24)Linux 基本命令2
Linux 基本命令2 操作文件或目录命令更改文件或目录访问权限命令 chmod修改文件的所有者和所属组命令 chown修改文件或目录的所属组命令 chgrp更改文件或目录的属性命令 chattr创建文件和目录时的默认权限掩码命令 umask判断文件类型命令 file显示文件或文件系统状态命令 stat树…...
WPF-数据转换器
一、单值转换器 1.不传参数 转换器 当Value值大于100时返回红色 public class DataConverter : IValueConverter{/// <summary>/// 表示从源到目标数据转换/// </summary>/// <param name"value">数据源的值</param>/// <param name&q…...
STM32 I2C通信协议说明
目录 背景 I2C协议 数据的有效性 I2C通信开始和停止条件 I2C数据传输 发送 响应 正常情况: 异常情况: 主机结束接收 写寄存器的标准流程 读寄存器的标准流程 仲裁机制 时钟同步 SDA线的仲裁 程序 背景 对单片机的三大通信中的I2C通信进…...
网络工程师 (42)IP地址
一、定义与功能 IP地址是IP协议提供的一种统一的地址格式,它为互联网上的每一个网络和每一台主机分配一个逻辑地址,以此来屏蔽物理地址的差异。这种地址分配方式确保了用户在连网的计算机上操作时,能够高效且方便地从众多计算机中选出自己所需…...
Deepseek实用万能提问模板
一,背景需求约束条件 背景:提供与问题相关的时间、地点、人物、事件等信息,帮助 DeepSeek 更好地理解问题的情境。 需求:清晰明确地阐述你希望 DeepSeek完成的任务或提供的信息。 约束条件:可根据具体情况,对回答的范围、格式、字数等进行…...
强化学习笔记7——DDPG到TD3
前提:基于TD 的方法多少都会有高估问题,即Q值偏大。原因两个:一、TD目标是真实动作的高估。 二:自举法高估。 DDPG 属于AC方法:异策略,适合连续动作空间,因为他的策略网络直接输出的动作&#…...
传统混合专家模型MoE架构详解以及python示例(DeepSeek-V3之基础)
我们已经了解到DeepSeek-V3的框架结构基于三大核心技术构建:多头潜在注意力(MLA)、DeepSeekMoE架构和多token预测(MTP)。而DeepSeekMoE架构的底层模型采用了混合专家模型(Mixture of Experts,MoE)架构。所以我们先了解一下传统混合专家模型MoE架构。 一、传统混合专家模…...
开源协议深度解析:理解MIT、GPL、Apache等常见许可证
目录 前言1. MIT协议:自由而宽松的开源许可1.1 MIT协议的主要特点1.2 MIT协议的适用场景 2. GPL协议:自由软件的捍卫者2.1 GPL协议的核心理念2.2 GPL协议的适用场景 3. Apache License 2.0:开源与专利保护的平衡3.1 Apache License 2.0的主要…...
三维重建(十二)——3D先验的使用
文章目录 零、最近感受和前言一、使用能够快速得到重建初始化的方法1.1 Colmap(多视角)1.2 深度估计(单视角)二、已知形状模板2.1 人脸2.2 人体2.3 动物三、刚性与非刚性约束(变形约束)3.1 刚性变形3.2 非刚性变形四、统计(深度学习)先验——从大量(3D)数据中提取信息…...
Java项目《苍穹外卖》BUG修复记录
一、订单详情地址显示为null 原因:查看订单详情接口中,未设置收货地址信息,故地址返回为null。 解决方案: 1、OrderServiceImpl中创建一个私有方法专门获取订单收货地址 /*** 获取订单收获地址* param addressBookId* return*/…...
DockerDesktop更改默认的磁盘镜像地存储位置
DockerDesktop更改默认的磁盘镜像地存储位置 文章目录 DockerDesktop更改默认的磁盘镜像地存储位置1. 默认存储位置2. 新建一个目录3. 将磁盘镜像存储位置改为新建的目录下 1. 默认存储位置 2. 新建一个目录 如:D:\DiskImagelocationData 3. 将磁盘镜像存储位置改为…...
阿里云视频点播,基于thinkphp8上传视频
前端参考官方示例(jQuery版) <!DOCTYPE html> <html> <head><meta charset"utf-8"><title>阿里云 JavaScript上传SDK Demo (使用jquery)</title><script src"__STATIC__/jquery.min.js"></script><sc…...
C# windowForms 的DataGridView控件的使用
C# Windows Forms DataGridView 控件使用详解 DataGridView 是 Windows Forms 中用于显示和编辑表格数据的核心控件。它支持高度自定义的列类型、数据绑定、事件处理和丰富的样式配置。以下是其详细使用方法。 目录 基础使用 数据绑定 列类型与自定义...
【NLP 22、语言模型 language model】
有时候我也想听听,我在你心里,是什么样子 —— 25.1.12 一、什么是语言模型 语言是灵活的,也是有规律的 了解一门语言的人可以判断一句话是否“合理” 通俗来讲,语言模型用来评价一句话(句子可以看作是字的组合)是否“合理”或…...
vtkCamera类的Dolly函数作用及相机拉近拉远
录 1. 预备知识 1.1.相机焦点 2. vtkCamera类的Dolly函数作用 3. 附加说明 1. 预备知识 要理解vtkCamera类的Dolly函数作用,就必须先了解vtkCamera类表示的相机的各种属性。 VTK是用vtkCamera类来表示三维渲染场景中的相机。vtkCamera负责把三维场景投影到二维平面,如…...