Leetcode JAVA刷刷站(91)解码方法

2024-08-24 05:52

本文主要是介绍Leetcode JAVA刷刷站(91)解码方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目概述

二、思路方向 

       这个问题是一个典型的动态规划问题,其中我们可以使用一个数组来存储到达每个位置时的解码方法的总数。

       我们定义一个数组 dp,其中 dp[i] 表示字符串 s 的前 i 个字符(从索引 0 到 i-1)的解码方法总数。

初始化:

  • dp[0] 的值取决于字符串的第一个字符。如果第一个字符是 '0',则没有解码方法,dp[0] = 0;否则,至少有一种解码方法(即第一个字符单独解码),dp[0] = 1

状态转移:
对于每个位置 i(从 1 开始到字符串长度减一),我们考虑两种情况:

  1. 如果 s[i-1](即当前字符)不是 '0',那么它可以单独解码为一个字母,此时 dp[i] 至少等于 dp[i-1](即,在 dp[i-1] 的基础上,加上当前字符的解码方式)。
  2. 如果 s[i-2] 和 s[i-1](即前两个字符)组成的两位数在 10 到 26 之间(包含10和26),那么这两个字符也可以一起解码为一个字母,此时 dp[i] 还需要加上 dp[i-2](即,在 dp[i-2] 的基础上,加上这两个字符一起解码的方式)。

注意

  • 如果 s[i-1] 是 '0',它不能单独解码,只能与前一个字符一起解码(如果可能的话)。
  • 如果 s[i-2] 是 '0',那么它不可能与 s[i-1] 组成有效的两位数解码,因此不需要考虑这种情况。
  • 如果 s 的前两个字符组成的两位数不在 10 到 26 之间,那么 dp[2] 只能根据 s[1] 是否为 '0' 来决定是否为 1 或 0,且 dp[1] 的值仅由 s[0] 决定。

三、代码实现 

public class Solution {  public int numDecodings(String s) {  if (s == null || s.length() == 0 || s.charAt(0) == '0') {  return 0;  }  int n = s.length();  int[] dp = new int[n + 1];  dp[0] = 1;  // 空字符串有一种解码方式  dp[1] = 1;  // 第一个字符不为 '0' 时,至少有一种解码方式  for (int i = 2; i <= n; i++) {  // 当前字符可以单独解码  if (s.charAt(i - 1) != '0') {  dp[i] += dp[i - 1];  }  // 前两个字符可以组合解码  int twoDigit = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');  if (twoDigit >= 10 && twoDigit <= 26) {  dp[i] += dp[i - 2];  }  }  return dp[n];  }  public static void main(String[] args) {  Solution solution = new Solution();  System.out.println(solution.numDecodings("11106"));  // 应输出 2  System.out.println(solution.numDecodings("226"));    // 应输出 3  System.out.println(solution.numDecodings("0"));      // 应输出 0  }  
}

执行结果: 

四、小结 

       这段代码首先检查了几种特殊情况,然后使用了动态规划的思想来解决问题。通过迭代地构建 dp 数组,我们得到了最终的结果。

 结语  

人生最重要的不是所站的位置

而是所朝的方向

!!!

这篇关于Leetcode JAVA刷刷站(91)解码方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4