(其他) 剑指 Offer 46. 把数字翻译成字符串 ——【Leetcode每日一题】

news/2024/3/3 13:35:03

❓ 剑指 Offer 46. 把数字翻译成字符串

难度:中等

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a”1 翻译成 “b”……11 翻译成 “l”……25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

提示

  • 0 < = n u m < 2 31 0 <= num < 2^{31} 0<=num<231

💡思路:动态规划

定义 dp 数组,dp[i] 表示以第 i 个字符结尾的子串的 总 翻译方法;

如果 若 x i x_i xi x i − 1 x_{i-1} xi1 组成的两位数字可以被翻译,则 dp[i]=dp[i−1]+dp[i−2];否则 dp[i]=dp[i−1]

  • 可被翻译的两位数区间:当 x i − 1 = 0 x_{i-1} = 0 xi1=0 时,组成的两位数是无法被翻译的(例如 00, 01, 02, ),因此区间为 [10,25]
  • 所以状态转移方程为: d p [ i ] = { d p [ i − 1 ] + d p [ i − 2 ] , 10 x i − 1 + x i ∈ [ 10 , 25 ] d p [ i − 1 ] , 10 x i − 1 + x i ∈ [ 0 , 10 ) ∪ ( 25 , 99 ] dp[i]=\begin{cases}dp[i-1]+dp[i-2]&,10x_{i-1}+x_i\in[10,25]\\dp[i-1]&,10x_{i-1}+x_i\in[0,10)\cup(25,99]\end{cases} dp[i]={dp[i1]+dp[i2]dp[i1],10xi1+xi[10,25],10xi1+xi[0,10)(25,99]

观察上面的 状态转移方程,发现 dp[i] 只与 前两位 dp[i - 1]dp[i - 2] 有关,所以可以进行空间优化,我们使用 pre1 代替 dp[i - 1]pre2 代替 dp[i - 2]cur 代替 dp[i]
c u r = { p r e 1 + p r e 2 , 10 x i − 1 + x i ∈ [ 10 , 25 ] p r e 1 , 10 x i − 1 + x i ∈ [ 0 , 10 ) ∪ ( 25 , 99 ] cur=\begin{cases}pre1+pre2&,10x_{i-1}+x_i\in[10,25]\\pre1&,10x_{i-1}+x_i\in[0,10)\cup(25,99]\end{cases} cur={pre1+pre2pre1,10xi1+xi[10,25],10xi1+xi[0,10)(25,99]

  • 当前 状态 cur 处理完, prepre2 共同前移一位,进而可以表示为:
    p r e 1 = { p r e 1 + p r e 2 , 10 x i − 1 + x i ∈ [ 10 , 25 ] p r e 1 , 10 x i − 1 + x i ∈ [ 0 , 10 ) ∪ ( 25 , 99 ] pre1=\begin{cases}pre1+pre2&,10x_{i-1}+x_i\in[10,25]\\pre1&,10x_{i-1}+x_i\in[0,10)\cup(25,99]\end{cases} pre1={pre1+pre2pre1,10xi1+xi[10,25],10xi1+xi[0,10)(25,99]
    p r e 2 = { p r e 1 − p r e 2 , 10 x i − 1 + x i ∈ [ 10 , 25 ] p r e 1 , 10 x i − 1 + x i ∈ [ 0 , 10 ) ∪ ( 25 , 99 ] pre2=\begin{cases}pre1-pre2&,10x_{i-1}+x_i\in[10,25]\\pre1&,10x_{i-1}+x_i\in[0,10)\cup(25,99]\end{cases} pre2={pre1pre2pre1,10xi1+xi[10,25],10xi1+xi[0,10)(25,99]

  • 按位遍历该数字,从 左到右右到左 是相同的,本方法使用 右到左

  • 初始化:pre1 = pre2 = 1,即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1

🍁代码:(C++、Java)

C++

class Solution {
public:int translateNum(int num) {if(num < 10) return 1;int pre1 = 1, pre2 = 1;while(num >= 10){int tmp = num % 100;if(tmp / 10 > 0 && tmp <= 25) {pre1 += pre2;pre2 = pre1 - pre2;}else{pre2 = pre1;}num /= 10;}return pre1;}
};

Java

class Solution {public int translateNum(int num) {if(num < 10) return 1;int pre1 = 1, pre2 = 1;while(num >= 10){int tmp = num % 100;if(tmp / 10 > 0 && tmp <= 25) {pre1 += pre2;pre2 = pre1 - pre2;}else{pre2 = pre1;}num /= 10;}return pre1;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为字符串 s 的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),使用常数大小的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/1095901.html

相关文章

2023年7月京东奶粉行业品牌销售排行榜(京东数据产品)

鲸参谋监测的京东平台7月份奶粉市场销售数据已出炉&#xff01; 根据鲸参谋平台的数据显示&#xff0c;今年7月份&#xff0c;京东奶粉市场的销量为600万&#xff0c;同比去年同期有所下滑&#xff0c;整体下降约21%&#xff1b;销售额为22亿&#xff0c;同比增长约9%。由此也…

索尼 toio™应用创意开发征文|toio俄罗斯方块游戏

目录 引言 摘要 创意简述 准备工作&#xff5c;手工开始 代码编写&#xff5c;合理集成 使用体验&#xff5c;近乎奇妙 引言 索尼toio™编程机器人是一款引领技术创新的产品&#xff0c;为开发者提供了一个全新的编程和创造平台。toio™的设计旨在将技术、塑性和乐趣融为…

05-JVM内存分配机制深度剖析

上一篇&#xff1a;04-JVM对象创建深度剖析 1.对象栈上分配 我们通过JVM内存分配可以知道JAVA中的对象都是在堆上进行分配&#xff0c;当对象没有被引用的时候&#xff0c;需要依靠GC进行回收内存&#xff0c;如果对象数量较多的时候&#xff0c;会给GC带来较大压力&#xff…

crontab的配置参数和基础使用教程

crontab基本格式 crontab文件的基本格式如下: * * * * * command 这5个*代表: 第一个* :分钟(0-59)第二个* :小时(0-23)第三个* :一个月中的第几天(1-31)第四个* :月份(1-12)第五个* :一周中的第几天(0-6,其中0代表星期天) command代表要执行的命令。 crontab常用时间设置…

Linux系统编程--IO

文章目录 一、系统调用1.open()1.1 所需基础知识1.2. open() 详解1.3 示例代码 二、标准IO三、高级IO 一、系统调用 1.open() 1.1 所需基础知识 Linux遵循一切皆是文件的理念&#xff0c;因此&#xff0c;很多的交互工作都是通过读取和写入文件来完成。 文件必须被打开才能被…

Kubernetes入门 十四、存储管理

目录 临时存储hostPathEmptyDir NFS 挂载安装NFS配置文件 PV和PVC概述PV 的回收策略PV 的访问模式PV 的状态使用PV和PVC生命周期 动态供应StorageClass动态供应流程NFS 动态供应案例 临时存储 Kubernetes 支持很多类型的卷。 Pod可以同时使用任意数目的卷类型。 临时卷类型的…

【LeetCode-中等题】17. 电话号码的字母组合

文章目录 题目方法一&#xff1a;递归回溯 题目 方法一&#xff1a;递归回溯 参考讲解&#xff1a;还得用回溯算法&#xff01;| LeetCode&#xff1a;17.电话号码的字母组合 首先可以画出树图&#xff1a; 先将数字对应的字符集合 加入到一个map集合 这里需要一个index来控…

Chrome 108版(64-bit 108.0.5359.125)网盘下载

还在用Selenium的朋友们注意了&#xff0c;目前Chrome的最新版是116&#xff0c;而官方的Chromedriver只支持到115版。 可惜Google不提供旧版Chrome的下载方式&#xff0c;需要旧版的很难回去了。如果真的想要旧版的Chrome&#xff0c;只能民间自救。 我在2022年12月备份了C盘…

ClickHouse 存算分离改造:小红书自研云原生数据仓库实践

ClickHouse 作为业界性能最强大的 OLAP 系统&#xff0c;在小红书内部被广泛应用于广告、社区、直播和电商等多个业务领域。然而&#xff0c;原生 ClickHouse 的 MPP 架构在运维成本、弹性扩展和故障恢复方面存在较大局限性。为应对挑战&#xff0c;小红书数据流团队基于开源 C…

matlab求解方程组-求解过程中限制解的取值范围

文章目录 问题背景代码my_fun.mmain.m 结果展示:不加入F(4)加入F(4) 问题背景 求解方程组的时候&#xff0c;对某些未知数的求解结果的取值范围有要求。例如在某些物理问题求解中&#xff0c;要求待求解量大于0。 代码 一共两个文件: my_fun.m main.mmy_fun.m function Fm…

concrt140.dll怎么下载,concrt140.dll修复工具(修复精灵下载)一键修复问题

今天&#xff0c;我将为大家介绍一个非常常见的问题&#xff1a;由于找不到concrt140.dll,无法继续执行代码怎么办。这个问题可能会让很多网友感到头疼&#xff0c;但是别担心&#xff0c;我会为大家提供5种最全详细的恢复方法。在接下来我将详细介绍这些问题及其解决方法。希望…

未来之路:数字孪生在车联网中的关键作用

随着车联网技术的快速发展&#xff0c;共享车辆出现在城市各个角落&#xff0c;数字孪生作为一种虚拟仿真技术&#xff0c;正在物联网行业内迅速崭露头角。数字孪生不仅提供了对车辆的实时监测&#xff0c;还为汽车制造商和车主带来了多方面的优势和应用&#xff0c;下面简单从…

高通DSP架构和HVX指令介绍

1. Qualcomm Snapdragon™处理器 Qualcomm Snapdragon™是高通的移动平台处理器,是一种系统级芯片(SoC),包含了CPU、GPU、DSP、调制解调器、无线电、摄像头处理器、安全处理器等多种功能。Snapdragon处理器广泛应用于智能手机、平板电脑、智能手表、智能音箱等移动设备中。…

【2023年11月第四版教材】第11章《成本管理》(第1部分)

第11章《成本管理》&#xff08;第1部分&#xff09; 1 章节说明2 管理基础3 管理过程3.1 管理ITTO汇总★★★ 1 章节说明 【本章分值预测】大部分内容不变&#xff0c;细节有一些变化&#xff0c;预计选择题考3-4分&#xff0c;案例和论文都有可能考&#xff1b;是需要重点学…

什么是SpringMVC以及SpringMVC框架的优点

它是基于MVC开发模式的框架,用来优化控制器.它是Spring家族的一员.它也具备IOC和AOP. 什么是MVC? 它是一种开发模式,它是模型视图控制器的简称.所有的web应用都是基于MVC开发. M:模型层,包含实体类,业务逻辑层,数据访问层 模型 模型(Model)&#xff1a;就是业务流程/状态…

Android 10.0 禁用adb shell input输入功能

1.前言 在10.0的产品开发中,在进行一些定制开发中,对于一些adb shell功能需要通过属性来控制禁止使用input 等输入功能,比如adb shell input keyevent 响应输入事件等,所以就需要 熟悉adb shell input的输入事件流程,然后来禁用adb shell input的输入事件功能,接下来分…

情侣头像微信小程序源码 朋友圈背景小程序源码 动态壁纸微信小程序源码

壁纸和情侣头像&#xff0c;朋友圈素材都可以做&#xff0c;带视频教程。 搭建也不难&#xff0c;纯前端无后台。直接开发者工具调试前端&#xff0c;绑定合法域名&#xff0c;流量主功能也是在前端替换。 无需服务器域名直接上手&#xff01;&#xff01;&#xff01;

[虚幻引擎插件介绍] DTGlobalEvent 蓝图全局事件, Actor, UMG 相互回调,自由回调通知事件函数,支持自定义参数。

本插件可以在虚幻的蓝图 Actor&#xff0c; Obiect&#xff0c;UMG 里面指定绑定和执行消息&#xff0c;可带自定义参数。 参数支持 Bool&#xff0c;Byte&#xff0c;Int&#xff0c;Int64&#xff0c;Float&#xff0c;Name&#xff0c;String&#xff0c;Text&#xff0c;Ve…

c++通过tensorRT调用模型进行推理

模型来源&#xff1a; 算法工程师训练得到的onnx模型 c对模型的转换&#xff1a; 拿到onnx模型后&#xff0c;通过tensorRT将onnx模型转换为对应的engine模型&#xff0c;注意&#xff1a;训练用的tensorRT版本和c调用的tensorRT版本必须一致。 如何转换&#xff1a; 算法工…

WMS仓储管理系统的功能与WCS系统有什么区别

在物流行业的现代化管理中&#xff0c;WMS仓储管理系统和WCS仓库控制系统是两个重要的组成部分。虽然它们都是用于仓库管理的软件系统&#xff0c;但是它们的功能和应用场景有很大的区别。本文我们将详细阐述这两者的功能和区别。 一、WMS仓储管理系统 WMS是一种软件系统&…
最新文章