当前位置: 首页 > news >正文

每日一题——把数字翻译成字符串

把数字翻译成字符串

    • 题目描述
    • 示例
      • 示例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 个数字可以翻译成多少种不同的字符串。状态转移方程如下:

  1. 如果当前数字 nums[i] 不为 0,则 dp[i] += dp[i-1]
  2. 如果当前数字 nums[i-1]nums[i] 组成的两位数在 1026 之间,则 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 题解动态规划代码实现复杂度分析 总结 题目描述 有一种将字母编码成数字的方式&#xff1a;‘a’->1, ‘b’->2, … , ‘z’->26。 现在给一串数字&#xff0c;返回有多少种可能的译码结果。 数据范围&#xff1a;字符串…...

我们来学HTTP/TCP -- 三次握手?

三次握手 题记三次呼叫结语 题记 来&#xff0c;我们来演示下川普王和普京帝会面了 哎呦&#xff01;你好你好&#xff0c;握手…哎嗨&#xff01;侬好侬好&#xff0c;握手…欧嘿呦玛斯&#xff0c;握手… 抓狂啊&#xff01;作孽啊!!! 不说人话啊! 关键的是&#xff0c;“三…...

多媒体软件安全与授权新范例,用 CodeMeter 实现安全、高效的软件许可管理

背景概述 Reason Studios 成立于 1994 年&#xff0c;总部位于瑞典斯德哥尔摩&#xff0c;是全球领先的音乐制作软件开发商。凭借创新的软件产品和行业标准技术&#xff0c;如 ReWire 和 REX 文件格式&#xff0c;Reason Studios 为全球专业音乐人和业余爱好者提供了一系列高质…...

SQL复习

SQL复习 MySQL MySQL MySQL有什么特点&#xff1f; MySQL 不支持全外连接。 安装 数据类型 MySQL中的数据类型分为哪些&#xff1f; MySQL中的数据类型主要分为三大类&#xff1a;数值类型、字符串类型、日期时间类型。 其中&#xff0c; 数值类型又分为七种&#xff1a;T…...

红队视角出发的k8s敏感信息收集——日志与监控系统

针对 Kubernetes 日志与监控系统 的详细攻击视角分析&#xff0c;聚焦 集群审计日志 和 Prometheus/Grafana 暴露 的潜在风险及利用方法 攻击链示例 1. 攻击者通过容器逃逸进入 Pod → 2. 发现未认证的 Prometheus 服务 → 3. 查询环境变量标签获取数据库密码 → 4. 通过审…...

Flask中获取请求参数的一些方式总结

在 Flask 中&#xff0c;可以从 request 对象中获取各种类型的参数。以下是全面整理的获取参数的方式及示例代码。 1. 获取 URL 查询参数&#xff08;Query String Parameters&#xff09; URL 中的查询参数通过 ?keyvalue&key2value2 的形式传递&#xff0c;使用 reques…...

架构——LVS负载均衡主要模式及其原理、服务水平、优缺点

LVS&#xff08;Linux Virtual Server&#xff09;是一款高性能的开源负载均衡软件&#xff0c;支持多种负载均衡模式。以下是其主要模式及其原理、服务水平、优缺点&#xff1a; 1. NAT 模式&#xff08;Network Address Translation&#xff09; 原理&#xff1a; 请求流程…...

【漫话机器学习系列】093.代价函数和损失函数(Cost and Loss Functions)

代价函数和损失函数&#xff08;Cost and Loss Functions&#xff09;详解 1. 引言 在机器学习和深度学习领域&#xff0c;代价函数&#xff08;Cost Function&#xff09;和损失函数&#xff08;Loss Function&#xff09;是核心概念&#xff0c;它们决定了模型的优化方向。…...

Android 13 上通过修改 AOSP 拦截 SystemUI 音量调节事件

定位关键代码SystemUI 的音量调节逻辑主要集中在以下类中: VolumeDialogController.java:负责与 AudioService 交互。 VolumeDialogImpl.java:处理 UI 交互事件(如按钮点击)。 PhoneWindowManager.java:处理物理按键事件(如音量键)。 拦截音量调节事件 以 VolumeDialog…...

SQL与数据库程序设计

1.1986年&#xff0c;10月美国国家标准局颁布了SQL语言的美国标准&#xff0c;称为SQL86 2.SQL(Structured Query Language)又称为结构化查询语言 3.建立索引的主要目的是加快查找的速度 4.在基本表上建立一个或者多个索引 5. 一个基本表是最多只能建立一个聚簇索引 6.CAL…...

大模型Deepseek的使用_基于阿里云百炼和Chatbox

目录 前言1. 云服务商2. ChatBox参考 前言 上篇博文中探索了&#xff08;本地&#xff09;部署大语言模型&#xff0c;适合微调、数据高隐私性等场景。随着Deepseek-R1的发布&#xff0c;大语言模型的可及性得到极大提升&#xff0c;应用场景不断增加&#xff0c;对高可用的方…...

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…...

二〇二四年终总结

写在前面 简单总结一下告诉自己&#xff0c;曾经活着 不必太纠结于当下&#xff0c;也不必太忧虑未来&#xff0c;当你经历过一些事情的时候&#xff0c;眼前的风景已经和从前不一样了。——村上春树 原本应该 24 年年中的时候写 23 年年终的总结&#xff0c;但是一直拖着&…...

学习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&#xff1a;区别、场景与互补使用指南 eepseek回答宝塔和docker的区别 好的&#xff0c;我现在需要回答用户关于宝塔面板和Docker之间的区别的问题。首先&#xff0c;我需要明确这两个工具各自的定义、功能以及它们适用的场景&#xff0c;这样才能准确比较…...

机器学习--实现多元线性回归

机器学习—实现多元线性回归 本节顺延机器学习--线性回归中的内容&#xff0c;进一步讨论多元函数的回归问题 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&#xff1a;可选。表示应该立即开始下载脚本&#xff0c;但不能阻止其他页面动作&#xff0c;比如下载资源或等待其他脚本加载。只对外部…...

【人工智能】释放数据潜能:使用Featuretools进行自动化特征工程

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门! 解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 特征工程是机器学习流程中至关重要的一步,它直接影响模型的性能。然而,手动特征工程既耗时又需要领域专业知识。Featuretools是一个强大的…...

算法——对比A*算法与IDA*算法

A*算法与IDA*算法详细解析 1. A*算法 核心思想&#xff1a; A*算法是一种启发式搜索算法&#xff0c;结合了Dijkstra算法的最短路径保证和贪心最佳优先搜索的高效导向性。其核心是评估函数 ( f(n) g(n) h(n) )&#xff0c;其中&#xff1a; ( g(n) ): 从起点到当前节点 ( …...

GitLab CI/CD 的配置详解:从零开始使用 .gitlab-ci.yml 文件

在现代软件开发中&#xff0c;CI/CD&#xff08;持续集成与持续部署&#xff09;已成为提高开发效率和代码质量的核心实践。GitLab CI/CD 提供了强大的功能&#xff0c;帮助开发者自动化构建、测试和部署应用程序。而 .gitlab-ci.yml 文件是 GitLab CI/CD 配置的关键所在&#…...

BilibiliDown:一站式B站视频下载与管理解决方案

BilibiliDown&#xff1a;一站式B站视频下载与管理解决方案 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors/bi/Bili…...

深蓝词库转换:3分钟解决你的输入法迁移难题

深蓝词库转换&#xff1a;3分钟解决你的输入法迁移难题 【免费下载链接】imewlconverter ”深蓝词库转换“ 一款开源免费的输入法词库转换程序 项目地址: https://gitcode.com/gh_mirrors/im/imewlconverter 你是否曾经因为更换输入法而不得不放弃多年积累的个人词库&am…...

【Docker跨架构实战权威指南】:ARM、x86、RISC-V一键互通的7大核心配置与3类高频报错根因诊断

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Docker跨架构兼容性原理与演进全景 Docker 跨架构兼容性并非天然存在&#xff0c;而是通过多层抽象与运行时协同实现的系统性工程。其核心依赖于 Linux 内核的体系结构无关性、容器镜像的分层元数据描述…...

2026年阿里云Hermes Agent/OpenClaw环境配置教程,百炼token Plan配置详解

2026年阿里云Hermes Agent/OpenClaw环境配置教程&#xff0c;百炼token Plan配置详解。OpenClaw作为阿里云生态下新一代的开源AI自动化代理平台&#xff0c;曾用名Moltbot/Clawdbot&#xff0c;凭借“自然语言交互自动化任务执行大模型智能决策”的核心能力&#xff0c;正在重构…...

快速上手tchMaterial-parser:国家中小学智慧教育平台电子课本下载终极指南

快速上手tchMaterial-parser&#xff1a;国家中小学智慧教育平台电子课本下载终极指南 【免费下载链接】tchMaterial-parser 国家中小学智慧教育平台 电子课本下载工具&#xff0c;帮助您从智慧教育平台中获取电子课本的 PDF 文件网址并进行下载&#xff0c;让您更方便地获取课…...

别再只改_Surface了!完整梳理URP材质Blend Mode、Render Queue与透明渲染的正确姿势

URP材质系统深度解析&#xff1a;Blend Mode、Render Queue与透明渲染的协同艺术 在Unity的通用渲染管线(URP)中&#xff0c;材质系统的配置远比表面看起来复杂。许多开发者习惯性地只修改_Surface属性来切换透明效果&#xff0c;却忽略了背后一整套相互关联的渲染机制。这种片…...

瑞芯微RKNN开发板连不上?手把手教你排查rknn_server启动问题(附日志调试技巧)

瑞芯微RKNN开发板连接故障全攻略&#xff1a;从日志分析到稳定运行的深度解决方案 当你在瑞芯微RKNN开发板上部署AI模型时&#xff0c;是否遇到过这样的场景&#xff1a;所有步骤都按官方文档操作&#xff0c;却在最后一步收到冰冷的server connect fail错误提示&#xff1f;这…...

Taotoken 模型广场如何辅助开发者进行模型选型

Taotoken 模型广场如何辅助开发者进行模型选型 1. 模型广场的核心功能 Taotoken 模型广场为开发者提供了一个集中展示各类大模型的平台。在这里&#xff0c;开发者可以浏览到平台支持的所有模型&#xff0c;包括它们的名称、版本、基础能力描述等关键信息。模型按照自然语言处…...

中兴光猫破解终极指南:使用zteOnu工具轻松获取工厂模式权限

中兴光猫破解终极指南&#xff1a;使用zteOnu工具轻松获取工厂模式权限 【免费下载链接】zteOnu A tool that can open ZTE onu device factory mode 项目地址: https://gitcode.com/gh_mirrors/zt/zteOnu 在当今网络环境中&#xff0c;中兴光猫作为广泛部署的家庭网关设…...

Docker容器化金融核心系统:3类高频故障(交易超时/证书吊销/审计断点)的秒级定位与修复手册

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Docker容器化金融核心系统的合规性基石与架构约束 金融行业对系统稳定性、数据隔离性与审计可追溯性有严苛要求&#xff0c;Docker 容器化部署必须在满足《GB/T 35273—2020 信息安全技术 个人信息安全…...