leetcode面试题46把数字翻译成字符串

标签: 每日一题  动态规划贪心

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

示例 1:

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

题目分析:和之前的打家劫舍有些相似。由于题目最大数字为25,是一个两位数,那么将数字进行拆分求解组合时“
如果是一位数,没有任何限制,但是如果是一个两位数,就需要判断是否是一个合法的数字,合法才能算为一个方案,不难看出,合法的范围为[10-25],此外,0X的形式也是不合法的。
我们用dp[i]表示到数字i为止的方案数目,如果i与i-1的组成的两位数是合法的,方案累加,否则仍旧继承i-1的方案数
在这里插入图片描述

代码:

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0]=dp[1] = 1;
        for(int i = 2;i <= n;i++){
          String te = s.substring(i-2,i);
          if(te.compareTo("10")>=0&&te.compareTo("25")<=0) dp[i] = dp[i-1]+dp[i-2];
          else dp[i] = dp[i-1];
        }
        return dp[n];
    }
}

优化:一维的递推数组我们可以使用临时变量的方法来进行空间优化

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int n = s.length();
        int a = 1,b = 1,c = 0;
        for(int i = 2;i <= n;i++){
          String te = s.substring(i-2,i);
            c = te.compareTo("10") >= 0 && te.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;

        }
        return a;
    }
}

更进一步,我们还可以把字符串s去掉,直接在num上进行处理,对某个数值要取得特定位数的数字,一般通过
对10的幂做整除与取余运算

版权声明:本文为JingleLiA原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/JingleLiA/article/details/106640177

智能推荐

PoolThreadCache

缓存构成   PoolThreadCache的缓存由三部分构成:tiny、small 和 normal。 tiny   缓存数据大小区间为[16B, 496B]数据,数组长度为32,根据数据大小计算索引的办法:数据大小除以16,如下代码所示: small   缓存数据大小区间为[512B, 4KB]数据,数组长度为4,根据数据大小计算索引的办法:数据大小除以512,然后log2得到指数,如下代码所...

Intellij IDEA 搭建Spring Boot项目(一)

Intellij IDEA 搭建Spring Boot项目 标签(空格分隔): SpringBoot JAVA后台 第一步 选择File –> New –> Project –>Spring Initialer –> 点击Next  第二步 自己修改 Group 和 Artif...

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

猜你喜欢

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...