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

数据结构与算法之[把数字翻译成字符串]动态规划

前言:最近在刷动态规划的算法题目,感觉这一类题目还是有一点难度的,但是不放弃也还是能学好的,今天给大家分享的是牛客网中的编程题目[把数字翻译成字符串],这是一道经典的面试题目,快手,字节跳动等大厂出国这道题目。题目有点绕,需要进行分类讨论最好配合画图工具进行理解,这样能更好理解这道题目。

一.题目

二.进一步剖析题目

1.关于动态规划思想

动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

2.分析题目

①分析题目:能够译码的数字不会大于26,即有效的译码范围为 [1,26]。

②确定状态:以数组 "12345" 为例,首先要明确两点:

  • 依题意可知,数组中所有的数字都必须参与译码,比如数组 "1234" 的某一种译码方式为 “1,2,3,4",那么当数组尾再添加一个元素 "5" 时,刚才的译码方式就会变为 "1,2,3,4,5",即 "1,2,3,4" 和 "1,2,3,4,5" 是同一种译码方式。

由于所有数字都要参与译码,所以只要译码方式中存在个位数 "0",那么就都是无效的。

  • 当新加入一个数字"5" 时,其除了可以单独作为一个数字参与译码外,也可以与其左边的数字组成数字组合后再参与译码,即 "45" ,然后此时有多少种译码方式就取决于剩余的数字 即 "123" 了,这和前面所说的是同一个道理,只是此时把 "4"和"5" 看作是一个整体,可以理解为:原本数组 "123" 存在某种译码方式为 "1,2,3",现在加入 "45",译码方式就变成了 "1,2,3,45"。

由于有效的译码范围为 [1,26],所以新加入的数字 "5" 只需要考虑与其左边的数字组成两位数组合,无需再考虑组成更大的组合了,比如三位数 "345" 等等。

数字组合必须是十位数,比如 "0"和"2" 组成的 "02" 也是不符合译码要求的。

理解了上面两点后,现在我们从数组 "12345" 的子串"1"开始分析,然后逐步往后添加元素,设数组 x 有 f(x) 种有效的译码方式:

  • 当数组为 "1" 时,有以下译码方式:

①1

f("1")=1

  • 接着加入数字"2",数组为 "12" 时,有以下译码方式:

①1,2

②12

f("12")=2

其中第①种是从 数组 "1" 的译码方式 演变过来的,就是在其基础上再加上单个数字 "2"。

  • 接着加入数字"3",数组为 "123" 时,有以下译码方式:

①1,2,3

②12,3

③1,23

f("123")=3

其中第①、②种是从 数组 "12" 的译码方式 演变过来的,就是在其基础上再加上单个数字 "3";

而第③种是从 数组 "1" 的译码方式 演变过来的,就是在其基础上再加上数字组合 "23"。

  • 接着加入数字"4",数组为 "1234" 时,有以下译码方式:

①1,2,3,4
②12,3,4
③1,23,4
④1,2,34
⑤12,34

其中第①、②、③种是从 数组 "123" 的译码方式 演变过来的,就是在其基础上再加上单个数字 "4";

而第④、⑤种是从 数组 "12" 的译码方式 演变过来的,就是在其基础上再加上数字组合 "34";

由于 "45" 不在有效译码的范围内,所以这两种译码方式会被抛弃掉。

f("1234")=3

可见,数组 "1234" 的译码方式 是由 数组 "123"的译码方式数组 "12"的译码方式 组成的。

  • 根据上面的分析,当数组继续扩张到 "12345" 时,那么其译码方式就为:

当新加入的数字 "5" 单独作为个位数参与译码时,此时的译码方式 就等同于 数组 "1234" 的译码方式,这组译码方式是有效的,因为个位数 "5" 在有效的译码范围内;

而 "5" 与其前一位数字组成十位数 "45" 时,此时的译码方式 就等同于 数组 "123" 的译码方式,而这组译码是否有效则取决于 "45" 是否在有效的译码范围内。

即 f("12345") = f("12345" - "5") + f("12345" - "45") = f("1234") + f("123") = 3+3 = 6,但是由于 "45" 不在有效的译码范围内,所以 f("123") 的结果不能算在内,所以最终结果应该为3。

  • 可见,枚举到某位数字时,此时有多少种译码方式,可以由之前的译码方式相加得出,即当前的状态可以利用之前的状态,这是典型的动态规划。

③状态转移方程:f(x)=f(x-1)+f(x-2)(其中 x 表示数组长度,f(x) 表示有多少种有效的译码方式;是否加上 f(x-1) 取决于 nums[x] 是否在 [1,9] 内,即 nums[x] 需要满足不为0;是否加上 f(x-2) 则取决于 nums[i-1] 与 nums[i] 的数字组合是否在 [10,26] 内)

时间复杂度:O(N) ,需要遍历一次数组

空间复杂度:O(N) ,需要声明一个状态数组记录f(x)

3.C++代码

class Solution {public:int solve(string nums) {// write code hereif(nums[0]=='0')return 0;vector<int>dp(nums.size(),0);dp[0]=1;for(int i=1;i<dp.size();i++){if(nums[i]!='0'){if(nums[i-1]=='1'){dp[i]=dp[i-1]+(i-2>=0?dp[i-2]:1);continue;}if(nums[i-1]=='2'&&(nums[i]-'0'>0&&nums[i]-'0'<7)){dp[i]=dp[i-1]+(i-2>=0?dp[i-2]:1);continue;}    dp[i]=dp[i-1];            }else {if(nums[i-1]-'0'==1||nums[i-1]-'0'==2){dp[i]=dp[i-1];continue;}return 0;           }}return dp[nums.size()-1];
}
};

相关文章:

数据结构与算法之[把数字翻译成字符串]动态规划

前言&#xff1a;最近在刷动态规划的算法题目&#xff0c;感觉这一类题目还是有一点难度的&#xff0c;但是不放弃也还是能学好的&#xff0c;今天给大家分享的是牛客网中的编程题目[把数字翻译成字符串]&#xff0c;这是一道经典的面试题目&#xff0c;快手&#xff0c;字节跳…...

java 面向对象三大特性之多态 万字详解(超详细)

目录 前言 : 一、为什么需要多态 : 1.白璧微瑕 : 2.举栗&#xff08;请甘雨,刻晴,钟离吃饭&#xff09;: 3.代码 : 4.问题 : 二、什么是多态 : 1.定义 : 2.多态的实现步骤&#xff08;重要&#xff09; : 三、多态的使用 : 1.多态中成员方法的使用&#xff08;重要…...

git push origin master 情况

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3;哈喽&#xff01;大家好&#xff0c;我是「奇点」&#xff0c;江湖人称 singularity。刚工作几年&#xff0c;想和大家一同进步&#x1f91d;&#x1f91d;一位上进心十足的【Java ToB端大厂领…...

ElasticSearch查询优化routing

如果一个索引分片多达一百,再加上每个分片数据量大的情况下ES查询速度会慢,这种情况可以根据业务情况考虑使用_routing优化。 _routing 路由 当索引一个文档的时候,文档会被存储在一个主分片上。在存储时一般都会有多个主分片。Elasticsearch 如何知道一个文档应该放置在哪…...

【HashMap 1.7和1.8】

Java中的HashMap是一种常用的数据结构&#xff0c;用于存储键值对。在Java 1.7和1.8中&#xff0c;HashMap的实现有一些不同。 Java 1.7中的HashMap实现是基于“拉链法”的哈希表。每个哈希桶(bucket)是一个链表&#xff0c;存储了散列值相同的键值对。当键值对数量过多时&…...

【Zabbix实战之故障处理篇】Zabbix监控中文乱码问题解决方法

【Zabbix实战之故障处理篇】Zabbix监控中文乱码问题解决方法 一、问题展现1.查看Zabbix仪表盘2.问题分析二、检查Zabbix环境1.检查Zabbix监控主机2.检查Zabbix各组件状态三、在宿主机安装中文字体库1.安装中文字体2.查看字体文件四、安装中文字库1.查看Zabbix所有组件容器2.拷贝…...

学习(mianshi)必备-ClickHouse高性能查询/写入和常见注意事项(五)

目录 一、ClickHouse高性能查询原因-稀疏索引 二、ClickHouse高性能写入-LSM-Tree存储结构 什么是LSM-Tree 三、ClickHouse的常见注意事项和异常问题排查 一、ClickHouse高性能查询原因-稀疏索引 密集索引: 在密集索引中&#xff0c;数据库中的每个键值都有一个索引记录&…...

在Kotlin中探索 Activity Results API 极简的解决方案

Activity Results APIActivity Result API提供了用于注册结果、启动结果以及在系统分派结果后对其进行处理的组件。—Google官方文档https://developer.android.google.cn/training/basics/intents/result?hlzh-cn一句话解释&#xff1a;官方Jetpack组件用于代替startActivity…...

样式冲突太多,记一次前端CSS升级

目前平台前端使用的是原生CSSBEM命名&#xff0c;在多人协作的模式下&#xff0c;容易出现样式冲突。为了减少这一类的问题&#xff0c;提升研效&#xff0c;我调研了业界上主流的7种CSS解决方案&#xff0c;并将最终升级方案落地到了工程中。 样式冲突的原因 目前遇到的样式…...

如何解决报考PMP的那些问题?

关于PMP的报考条件&#xff0c;报考PMP都需要什么条件呢&#xff1f;【学历条件】&#xff1a;需要满足23周岁/高中毕业5年以上/大专以上学历&#xff0c;三个满足一个即可&#xff1b;【PDU条件】&#xff1a;报考PMP需要PDU证明&#xff08;学习项目管理课程的学时证明&#…...

数据结构栈的经典OJ题【leetcode最小栈问题大剖析】【leetcode有效的括号问题大剖析】

目录 0.前言 1.最小栈 1.1 原题展示 1.2 思路分析 1.2.1 场景引入 1.2.2 思路 1.3 代码实现 1.3.1 最小栈的删除 1.3.2 最小栈的插入 1.3.3 获取栈顶元素 1.3.4 获取当前栈的最小值 2. 有效的括号 0.前言 本篇博客已经把两个关于栈的OJ题分块&#xff0c;可以根据目…...

数据结构与算法之打家劫舍(一)动态规划思想

动态规划里面一部题目打家劫舍是一类经典的算法题目之一&#xff0c;他有各种各样的变式&#xff0c;这一篇文章和大家分享一下打家劫舍最基础的一道题目&#xff0c;掌握这一道题目&#xff0c;为下一道题目打下基础。我们直接进入正题。一.题目大家如果刚接触这样的题目&…...

无人驾驶路径规划论文简要

A Review of Motion Planning Techniques for Automated Vehicles综述和分类0Motion Planning for Autonomous Driving with a Conformal Spatiotemporal Lattice从unstructured环境向structured环境的拓展&#xff0c;同时还从state lattice拓展到了spatiotemporal lattice从而…...

C++ sort()函数和priority_queue容器中比较函数的区别

普通的queue是一种先进先出的数据结构&#xff0c;元素在队列尾追加&#xff0c;而从队列头删除。priority_queue中元素被赋予优先级。在创建的时候根据优先级进行了按照从大到小或者从小到大进行了自动排列&#xff08;大顶堆or小顶堆&#xff09;。可以以O(log n) 的效率查找…...

STM32开发(14)----CubeMX配置ADC

CubeMX配置ADC前言一、什么是ADC&#xff1f;二、实验过程1.单通道ADC采集STM32CubeMX配置代码实现2.多通道ADC采样(非DMA)STM32CubeMX配置代码实现3.多通道ADC采样&#xff08;DMA&#xff09;STM32CubeMX配置代码实现总结前言 本章介绍使用STM32CubeMX对ADC进行配置的方法&a…...

Simple RNN、LSTM、GRU序列模型原理

一。循环神经网络RNN 用于处理序列数据的神经网络就叫循环神经网络。序列数据说直白点就是随时间变化的数据&#xff0c;循环神经网络它能够根据这种数据推出下文结果。RNN是通过嵌含前一时刻的状态信息实行训练的。 RNN神经网络有3个变种&#xff0c;分别为Simple RNN、LSTM、…...

【原创】java+swing+mysql生肖星座查询系统设计与实现

今天我们来开发一个比较有趣的系统&#xff0c;根据生日查询生肖星座&#xff0c;输入生日&#xff0c;系统根据这个日期自动计算出生肖和星座信息反馈到界面。我们还是使用javaswingmysql去实现这样的一个系统。 功能分析&#xff1a; 生肖星座查询系统&#xff0c;顾名思义…...

CentOS 环境 OpneSIPS 3.1 版本安装及使用

文章目录1. OpenSIPS 源码下载2. 工具准备3. 编译安装4. opensips-cli 工具安装5. 启动 OpenSIPS 实例1. OpenSIPS 源码下载 使用以下命令即可下载 OpenSIPS 的源码&#xff0c;笔者下载的是比较稳定的 3.1 版本&#xff0c;读者有兴趣也可前往 官方传送门 sudo git clone htt…...

SQL95 从 Products 表中检索所有的产品名称以及对应的销售总数

描述 Products 表中检索所有的产品名称&#xff1a;prod_name、产品id&#xff1a;prod_idprod_idprod_namea0001egga0002socketsa0013coffeea0003colaOrderItems代表订单商品表&#xff0c;订单产品&#xff1a;prod_id、售出数量&#xff1a;quantityprod_idquantitya0001105…...

平时技术积累很少,面试时又会问很多这个难题怎么破?别慌,没事看看这份Java面试指南,解决你的小烦恼!

前言技术面试是每个程序员都需要去经历的事情&#xff0c;随着行业的发展&#xff0c;新技术的不断迭代&#xff0c;技术面试的难度也越来越高&#xff0c;但是对于大多数程序员来说&#xff0c;工作的主要内容只是去实现各种业务逻辑&#xff0c;涉及的技术难度并不高&#xf…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...