剑指offer-46.把数字翻译成字符串(动态规划)

2023-12-30 13:32

本文主要是介绍剑指offer-46.把数字翻译成字符串(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目来源:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

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

 

示例 1:

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

思路:

一开始想说建个哈希方便查找。。看了一下题解,其实是个一维的动归:

  • 状态:dp[i],表示i个数字最多有多少翻译方法。
  • 状态转移方程:考虑输入为1 2 2 8,那么有三种翻译方法,怎么来的呢?按顺序推:
    dp[1]:一个数字,当然是1种
    dp[2]:2的前序数字为num[0] = 1,所以2要么和1组合,要么不组合,所以有2种:dp[2] = dp[1] + dp[0]
    dp[3]:2的前序数字为2,如果组合的话,组成数字为22,在表示范围内,那么可以选择组合或者不组合,不组合时,2单独翻译,dp[3] = dp[2],组合时,22组合在一起了,那么dp[3] = dp[1],所以最终有dp[3] = dp[1] + dp[2]
    dp[4]:8的前序数字为2,如果组合的话,组成数字为28,不在表示范围内,所以8只能单独翻译,那么有dp[4] = dp[3]
  • 根据这个过程,可以有如下结论:
    dp[i] = dp[i-1] + dp[i-2]                     if (num[i-2:i] < '26' and num[i-2] == '2') or num[i-2] == '1'
    dp[i] = dp[i-1]                                   else
  • 初始化:dp[0]=1, dp[1]=1,所以全部初始化为1就行。
class Solution(object):def translateNum(self, num):""":type num: int:rtype: int"""num = str(num)n = len(num)dp = [1] * (n+1)for i in range(2, n+1):if num[i-2] == '1' or (num[i-2] == '2' and num[i-2:i] < '26'):dp[i] = dp[i-1] + dp[i-2]else:dp[i] = dp[i-1]return dp[-1]

参考:

https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/46-pythondong-tai-gui-hua-by-lullaby/

 

这篇关于剑指offer-46.把数字翻译成字符串(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/552991

相关文章

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

C#从XmlDocument提取完整字符串的方法

《C#从XmlDocument提取完整字符串的方法》文章介绍了两种生成格式化XML字符串的方法,方法一使用`XmlDocument`的`OuterXml`属性,但输出的XML字符串不带格式,可读性差,... 方法1:通过XMLDocument的OuterXml属性,见XmlDocument类该方法获得的xm

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程(AOP)是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

python修改字符串值的三种方法

《python修改字符串值的三种方法》本文主要介绍了python修改字符串值的三种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录第一种方法:第二种方法:第三种方法:在python中,字符串对象是不可变类型,所以我们没办法直接