leetcode-91解码方法(动态规划|记忆化搜索)[通俗易懂]

leetcode-91解码方法(动态规划|记忆化搜索)[通俗易懂]一条包含字母 A-Z 的消息通过以下映射进行了 编码 :‘A’ -> 1‘B’ -> 2…‘Z’ -> 26要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“111” 可以将 “1” 中的每个 “1” 映射为 “A” ,从而得到 “AAA” ,或者可以将 “11” 和 “1”(分别为 “K” 和 “A” )映射为 “KA” 。注意,“06” 不能映射为 “F” ,因为 “6” 和 “06” 不同。给你一个只含数字的 非空 字符串

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“111” 可以将 “1” 中的每个 “1” 映射为 “A” ,从而得到 “AAA” ,或者可以将 “11” 和 “1”(分别为 “K” 和 “A” )映射为 “KA” 。注意,“06” 不能映射为 “F” ,因为 “6” 和 “06” 不同。

给你一个只含数字的 非空 字符串 num ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:

输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3:

输入:s = "0"
输出:0
解释:没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10"'T'-> "20" 。由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。
示例 4:

输入:s = "06"
输出:0
解释:"06" 不能映射到 "F" ,因为字符串开头的 0 无法指向一个有效的字符。 
 

提示:

1 <= s.length <= 100
s 只包含数字,并且可能包含前导零。

题解

  1. 动态划归
    设置f[i]代表[1,i]一共有多少方案,f[i]和f[i-1]和f[i-2]都有联系
class Solution { 
   
public:
    int numDecodings(string s) { 
   
        int n = s.size(),num;
        vector<int> f(n + 1);
        f[0] = 1;
        stringstream ss;
        for(int i = 1;i <= n;i ++){ 
   
            if(s[i - 1] != '0')f[i] = f[i - 1];
            if(i - 2 >= 0){ 
   
                ss.clear();
                ss << s.substr(i - 2,2);
                ss >> num;
                if(num >= 10 && num < 27){ 
   
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
};
  1. 记忆化搜索
    记忆化搜索,f[i]代表陈[i,n]中有多少方案
class Solution { 
   
public:
    int f[101];
    int dfs(int u,string t){ 
   
        if(t == "")return 1;
        if(t[0] == '0')return 0;
        int res = 0,num;
        if(t[0] >= '1' && t[0] <= '9'){ 
   
            if(f[u + 1] == 0){ 
   
                f[u + 1] = dfs(u + 1,t.substr(1));
                if(f[u + 1] == 0)f[u + 1] = -1;
            }
            if(f[u + 1] != -1)res += f[u + 1];
        }
        stringstream ss;
        if(t.size() >= 2){ 
   
            ss << t.substr(0,2);
            ss >> num;
            if(num >= 10 && num <= 26)
            { 
   
                if(f[u + 2] == 0){ 
   
                    f[u + 2] = dfs(u + 2,t.substr(2));
                    if(f[u + 2] == 0)f[u + 2] = -1;
                }
                if(f[u + 2] != -1)res += f[u + 2];
            }
        }
        cout<<t<<" "<<res<<endl;
        return res;
    }
    int numDecodings(string s) { 
   
        return dfs(0,s);
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168707.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java语言_java好学吗?java是不是最难学的语言?

    java语言_java好学吗?java是不是最难学的语言?java好学吗?java是不是最难学的语言?对于一些刚接触java的朋友来说,可能会有这样的疑问,下面就来一起了解下吧。1、java好学吗?  从某些方面来说,java比较容易学,如果是大学毕业,大学计算机专业里大多开设了java基础课程,或者学过一点编程,学起java来也会轻松不少。即使是零基础也不用担心,java可以零基础授课,入门比较简单,难的是学深入,这不是一件容易的事。学习java…

  • django动态路由_网线无线转换器怎么用

    django动态路由_网线无线转换器怎么用自定义路径转换器有时候上面的内置的url转换器并不能满足我们的需求,因此django给我们提供了一个接口可以让我们自己定义自己的url转换器django内置的路径转换器源码解析在我们自定义路由转

  • LAMP配置-php-fpm.conf

    LAMP配置-php-fpm.confphp-fpm.conf默认包含/usr/local/php72/etc/php-fpm.d/*.confphp-fpm.conf文件内容比较简单;;;;;;;;;;;;;;;;;;;;;;FPMConfiguration;;;;;;;;;;;;;;;;;;;;;;include=/usr/local/php72/etc/php-fpm.d/*.confwww.conf内容才是真正的配置项user=nobodygroup=nobodylisten=127.

  • 安利一款Python开发的仿Linux树形显示目录tree命令「建议收藏」

    安利一款Python开发的仿Linux树形显示目录tree命令「建议收藏」大家好,我是小小明,今天要带大家通过python来实现仿Linux的tree命令。文章目录Linux与Windows的tree命令Linux的tree命令演示Windows的tree命令Python自制tree命令os模块基础代码Rich库关于tree模块的官方示例调用Tree模块实现仿Linux树形显示目录效果安装自定义tree模块首先看看Linux下的tree命令效果如何:Linux与Windows的tree命令Linux的tree命令演示在CentOS的Linux系统下,我们可以再使用yum

  • Vue和Springboot实现SM4加密和解密(前端可加密,后端可加解密,MD5同理)

    Vue和Springboot实现SM4加密和解密(前端可加密,后端可加解密,MD5同理)Vue和Springboot实现SM4加密和解密(前端可加密,后端可加解密,MD5同理)前言一、前端加密输入的密码前置检测粘贴我的SM4.js代码在组件中调用加密结果二、Springboot后端进行SM4的解密和加密引入库复制我的SM4加解密代码调用方法总结前言网站配置https比较麻烦,所以为了我们的用户账户安全,密码在从前端传输到后端的过程中,最好加密一下,选用SM4有两个原因,一是国产加密算法,二是这个国密算法是对称的,只要加密和解密的key和vi相同,可以很容易的

  • Python快速入门教程【转】「建议收藏」

    Python快速入门教程【转】「建议收藏」第一章Python基础知识1.1介绍1.1.1特点Python是一种面向对象、解释型计算机程序设计语言。语法简洁清晰,强制用空白符作为语句缩进。Python具有丰富和强大的库,又被称为胶

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号