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

暴力递归转动态规划(四)

题目
规定1对应A、2对应B、3对应C…26对应Z,那么一个数字字符串比如"111",就可以转化为:“AAA”、“KA"或"AK”,给定一个数字字符组成的字符串str,返回有多少种转化结果。

解释一下,字符串"111",可以拆分成"1"-“1”-“1"或者字符串"11”-“1"或者字符串"1”-“11”,所以有3种转化结果。

暴力递归
依然首先是暴力递归的思路,将str转换成char[],共有两种转换方式。

  1. 自己单独转换,不过有一点注意,如果我当前字符是’0’的时候是不支持转化的,因为没有对应字母支撑。
  2. 两个字符拼接后转换,同样也有一点主要注意,因为是只有26个英文字母, 所以两个字符拼接后,不能以’0’字符开头,并且相加后 < 27。

代码
代码中index == chars.length时 return 1 是当 char[] 走完,下面没字符之后,返回的1代表是一种转换结果,对当前转换结果的承认,如果转换不成功,中间过程中有0 或者 拼接完之后是 "01"或者拼接玩之后"28"这种没有字母对应的字符,直接就会在过程中进行 return 0

 public static int number(String str){if (str == null || str.length() == 0){return 0;}char[] chars = str.toCharArray();//process()方法返回方法返回字符串转化结果return process(chars,0);}//从index位置开始转化,index之前的不在意public static int process(char[] chars,int index){//如果走到了chars.length的位置,说明走完了,if (index == chars.length){return 1;}//如果当前字符是'0',直接return 不往下走了。if (chars[index] == '0'){return 0;}//单独自己转换int ans = process(chars,index +1);//拼接后面的转化,先判断当前是不是最后一个字符,并且满足转化条件if (index + 1 < chars.length &&(( chars[index] - '0') * 10 + (chars[index + 1] - '0') ) < 27){ans += process(chars,index +2);}return ans;}

动态规划
根据可变参数index改动态规划,因为只有一个可变参数,所以是一个一维数组,调用过程process是index + 1 和 index + 2,所以是依赖后面,根据暴力递归代码中base case index == chars.length return 1,可确定数组最后一个位置的值,由后向前推导。

dp表组成根据暴力递归代码进行修改即可。

public static int dp(String str) {if (str == null || str.length() == 0) {return 0;}char[] strs = str.toCharArray();int N = strs.length;int[] dp = new int[N + 1];dp[N] = 1;for (int i = N - 1; i >= 0; i--) {if (strs[i] != '0'){int ans =  dp[i + 1];if (i + 1 < N && (dp[i] - '0') * 10 + (dp[i + 1] - '0') < 27) {ans += dp[i + 2];}dp[i] = ans;}}return dp[0];}

相关文章:

暴力递归转动态规划(四)

题目 规定1对应A、2对应B、3对应C…26对应Z&#xff0c;那么一个数字字符串比如"111"&#xff0c;就可以转化为&#xff1a;“AAA”、“KA"或"AK”&#xff0c;给定一个数字字符组成的字符串str&#xff0c;返回有多少种转化结果。 解释一下&#xff0c;字…...

大数据项目实战(Sqoop安装)

一&#xff0c;搭建大数据集群环境 1.4 Sqoop安装 1.sqoop安装 &#xff08;1&#xff09;上传安装包 &#xff08;2&#xff09;解压安装包 tar -zxvf sqoop-1.4.6.bin__hadoop-2.0.4-alpha.tar.gz -C /export/servers &#xff08;3&#xff09;重命名 mv sqoop-1.4.6.b…...

android——spinner下拉弹窗、popupwindow下拉弹窗列表

一、spinner下拉弹窗 效果图如下&#xff1a; adapter的代码&#xff1a; package com.yaona.spinnerimport android.R import android.content.Context import android.graphics.Color import android.view.LayoutInflater import android.view.View import android.view.Vie…...

【阿里淘天】淘天20230824真题一、二 <模拟、双指针>

一、 题目描述&#xff1a; 小红有一个01字符串&#xff0c;她可以进行最多k次提作&#xff0c;每次操作可以交换相邻的两个字符&#xff0c;问可以得到的字典序最小的字符串是什么 输入描述&#xff1a; 一行两个整数 n 和 k&#xff0c;表示字符串的长度和可以进行的操作…...

Java注解和反射

注解(Java.Annotation) 什么是注解&#xff08;Annotation&#xff09;&#xff1f; Annotation是从JDK5.0开始引入的新技术 Annotation的作用: 不是程序本身&#xff0c;可以对程序作出解释(这一点和注释(comment)没什么区别)可以被其他程序(比如:编译器等)读取Annotation的…...

【Docker】01-Centos安装、简单使用

参考教程&#xff1a; https://www.bilibili.com/video/BV1Qa4y1t7YH/?p5&spm_id_frompageDriver&vd_source4964ba5015a16eb57d0ac13401b0fe77 什么是Docker&#xff1f; Docker是一种开源的容器化平台&#xff0c;用于构建、打包、部署和运行应用程序。它通过使用容…...

k8s之存储篇---数据卷Volume

数据卷概述 Kubernetes Volume&#xff08;数据卷&#xff09;主要解决了如下两方面问题&#xff1a; 数据持久性&#xff1a;通常情况下&#xff0c;容器运行起来之后&#xff0c;写入到其文件系统的文件暂时性的。当容器崩溃后&#xff0c;kubelet 将会重启该容器&#xff…...

博流RISC-V芯片JTAG debug配置与运行

文章目录 1、Windows下安装与配置2、Linux下安装与配置3、芯片默认 JTAG PIN 列表4、命令行运行JTAG5、Eclipse下使用JTAG 1、Windows下安装与配置 CKLink 驱动安装 Windows版驱动下载地址&#xff1a; https://occ-oss-prod.oss-cn-hangzhou.aliyuncs.com/resource//1666331…...

[国产MCU]-W801开发实例-UART控制器

UART控制器 文章目录 UART控制器1、UART控制器介绍2、UART驱动API介绍3、UART使用示例本文将详细如何使用W801的UART模块。 1、UART控制器介绍 UART是一种通用串行 数据总线 ,用于 异步通信 。该总线支持双向通信,可以实现 全双工传输 和接收。 W801 共 6组普通 UART口,通…...

OpenCV(九):LUT查找表

LUT&#xff08;Look-Up Table&#xff09;查找表是OpenCV中一种常用的图像处理方法&#xff0c;用于对图像进行像素级别的颜色映射或图像增强操作。LUT查找表可以实现快速、高效的颜色转换和像素操作&#xff0c;尤其在处理大量像素的情况下具有优势。以下是关于OpenCV LUT查找…...

2023年 Java 面试八股文(25w字)

0.Java八股文上&#xff08;25w字&#xff09;2.3w 1.集合容器 2.Java基础链接 目录 一.Java 基础面试题1.Java概述Java语言有哪些特点&#xff1f;Java和C有什么关系&#xff0c;它们有什么区别&#xff1f;JVM、JRE和JDK的关系是什么&#xff1f;**什么是字节码?**采用字…...

STM32f103入门(7)pwm驱动led驱动舵机驱动直流电机

PWM驱动 PWM介绍TIM_OC1Init 配置通道TIM_OCStructInit 输出比较参数默认值输出比较模式 TIM_OCInitstructure输出比较极性 TIM_OCInitstructure设置输出使能以下三个决定了PWM的频率 占空比初始化通道 TIM_OC1Init(TIM2, &TIM_OCInitstructure);GPIO复用 PWM通道 驱动LED复…...

Linux centos7 bash编程——-求质数和

训练项目&#xff1a;使用函数求质数和。 定义一个函数IsPrime()&#xff0c;据此判断一个数是否为质数 由用户输入一个整数&#xff0c;求出比此数大的两个最小质数之和。 一、解决思路: 1.先在键盘上输入一个整数 2.求出比此数大的最小质数 3.再求出比此质数大的另一个…...

给Hexo添加说说功能

首发博客地址 官网地址 效果 &#x1f440; 前言 GitHub 仓库&#xff1a;Artitalk.js &#x1f389; 特性 增删查改全方面支持 支持针对每条说说的评论 支持 Markdown/html 语法 支持图片上传 &#x1f680; 快速使用 下列主题已将本项目整合进去&#xff0c;可以直接使用。 感…...

Tensorflow调用训练好的yolov5模型进行推理

文章目录 1、安装TensorFlow-GPU版本1.2、验证是否安装正常 2、将训练好的pt文件转换成onnx文件2.2、什么是Onnx模型和Tensorflow模型2.1、将onnx文件转换成pb文件 1、安装TensorFlow-GPU版本 1、创建虚拟环境python3.8 conda create -n TF2.4 python3.82、进入虚拟环境 conda…...

【场景方案】我所积累的一些跨页面的数据传递方式,持续更新,欢迎补充~

文章目录 Iframe内嵌相互传递BroadcastChannel同标签页数据传递localStorage中间人传递未完待续... Iframe内嵌相互传递 使用window.postMessage()的这个html5特性去跨域传递数据&#xff0c;不受跨域限制。 父层&#xff1a; sendMes(){ // 向iframe发送let iframdom this…...

ASP.NET Core 的错误页面

异常处理 Developer 环境的异常页面 ASP.NET Core App 会可以在开发阶段用UseDeveloperExceptionPage启用 Developer 异常页面&#xff1a; app.UseDeveloperExceptionPage();当遇到Unhandled 异常信息时&#xff0c;可以输出异常信息页面&#xff1a; 异常信息包括&#xf…...

Android静态ip设置的坑

Android静态ip设置的坑 Android静态ip设置&#xff0c;对于这个功能&#xff0c;如果没有接触过&#xff0c;会给人感觉是个特别简单的功能&#xff0c;直接调用系统的接口即可&#xff0c;其实这个功能还是有许多坑的&#xff0c;因为谷歌在Android SDK中对相关的API进行非系…...

电源管理(PMIC)TPS63070RNMR、TPS650942A0RSKR、LM5175RHFR器件介绍、应用及特点。

一、TPS63070RNMR&#xff0c;降压升压 开关稳压器 IC 正 可调式 2.5V 1 输出 3.6A&#xff08;开关&#xff09; 15-PowerVFQFN 1、概述 TPS63070高输入电压降压-升压转换器是一款高效的低静态电流降压-升压转换器。这些器件适用于输入电压高于或低于输出电压的应用。升压模式…...

k8s(kubernetes)介绍篇

一、Kubernetes 是什么 Kubernetes 是一个全新的基于容器技术的分布式架构解决方案&#xff0c;是 Google 开源的一个容器集群管理系统&#xff0c;Kubernetes 简称 K8S。 Kubernetes 是一个一站式的完备的分布式系统开发和支撑平台&#xff0c;更是一个开放平台&#xff0c;对…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...