`
huntfor
  • 浏览: 201172 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetocde]Decode Ways

 
阅读更多

新博文地址:[leetcode]Decode Ways

Decode Ways

写道
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

 被这道题折磨的死去活来。。。递归超时,最后用的DP,但是对DP不是太熟,提交了3次才过

算法思想:

边界:当没有字符(可能为null或者长度为0两种情况),直接返回0即可。

当length == 1时,f(1) = 0(当s == 0时) f(1) = 1(s != 0 )

当length == 2时,f(2) = 2(当s在11~19 || 21 ~26之间) f(2) = 0 (当s < 10 或 s == 30,40,50...90)f(2) = 1(其他情况)

再来看f(n) 

字符串的第一个字母有四种情况,0,1,2,其他,

情况0 : 0 ,f(n) = 0即可

情况1 : 1 那么当第二个字母是0时,f(n) = f(n- 2)其他情况下 f(n) = f(n - 1) + f(n - 2)

情况2: 2 当第二个字母是0,7,8,9时, f(n) = f(n -2)其他情况 f(n) = f(n - 1) + f(n - 2)

情况3,其他情况,f(n) = f(n - 1)

最后返回f(n)

至于代码中,为了与字符串下标统一,我倒着求的,道理是安全一样的

public int numDecodings(String s) {
		if (s == null || s.length() == 0)
			return 0;
		int[] result = new int[s.length()];
		if(s.charAt(s.length() - 1) != '0'){
			result[s.length() - 1] = 1;
		}
		if (s.length() >= 2) {
			int subInt = Integer.valueOf(s.substring(s.length() - 2 ));
			if (subInt > 10 && subInt <= 26 && subInt != 20) {
				result[s.length() - 2] = 2;
			}else if((subInt % 10 == 0 && subInt / 10 > 2) || subInt < 10){
				result[s.length() - 2] = 0;
			}else{
				result[s.length() - 2] = 1;
			}
		}
		for(int i = s.length() - 3 ; i >= 0 ; i--){
			if ((s.charAt(i) == '1' && s.charAt(i + 1) == '0')
					|| (s.charAt(i) == '2' && (s.charAt(i+1) >= '7'
							&& s.charAt(i+1) <= '9' || s.charAt(i+1) == '0'))) {
				result[i] = result[i + 2];
			} else if (s.charAt(i) == '1' || s.charAt(i) == '2') {
				result[i] = result[i + 1]+result[i + 2];
			} else if(s.charAt(i) == '0'){
				result[i] = 0;
			}else{
				result[i] = result[i + 1];
			}
		}
		return result[0];		
	}

 

 

分享到:
评论

相关推荐

    java-leetcode题解之Decode Ways.java

    java java_leetcode题解之Decode Ways.java

    java-leetcode题解之Decode Ways II.java

    java java_leetcode题解之Decode Ways II.java

    java-91-decode-ways

    java java_91-decode-ways

    python-leetcode题解之091-Decode-Ways

    python python_leetcode题解之091_Decode_Ways

    js-leetcode题解之91-decode-ways.js

    javascript js_leetcode题解之91-decode-ways.js

    c语言-leetcode题解之0091-decode-ways.zip

    c语言基础 c语言_leetcode题解之0091_decode_ways.zip

    js代码-leetcode 91 DEcode Ways

    "DEcode Ways"是LeetCode中的第91题,它涉及到字符串处理和动态规划的算法知识。下面将详细讨论这个题目以及如何使用JavaScript来解决它。 解题思路: 问题描述:给定一个只包含大写字母的非空字符串s,已知每个...

    关于decode函数的使用

    ### 关于decode函数的使用详解 #### 函数概述 `decode()`函数在SQL语言中是一种常用的条件函数,它可以根据指定的表达式返回不同的值。这种功能对于数据转换、分类统计等场景非常有用。 #### 主要作用 `decode()`...

    关于oracle decode函数的用法

    Oracle的DECODE函数是一种条件表达式,用于在SQL语句中执行类似于IF...THEN...ELSE逻辑判断的功能。它根据一个指定的表达式的值,与一系列的条件进行比较,如果匹配到某个条件,则返回对应的值;如果没有匹配任何...

    hw_decode_linuxffmpeg_hw_decode_linuxffmpegmp4_vaapi硬件解码_源码

    编译hw_decode.c #gcc -o hw_decode hw_decode.c -I/.../include -L/.../lib -lavformat -lavfilter -lavcodec -lswscale -lavutil -lswresample -lpthread -lm -lz -lX11 -lva -lvdpau -lva-drm -lva-x114....

    Oracle中Decode()函数的有关用法

    ### Oracle中Decode()函数的有关用法 #### 一、Decode()函数简介 在Oracle数据库中,`DECODE()`函数是一种非常实用的功能,主要用于条件判断并返回特定的值。它提供了一种简单的方法来实现多分支逻辑判断,尤其是...

    decode函数.docx

    Decode 函数详解 Decode 函数是一个强大的 Oracle 函数,用于根据条件返回不同的值。它的语法结构为 `decode(条件,值 1,返回值 1,值 2,返回值 2,...值 n,返回值 n,缺省值)`。decode 函数的含义是,如果条件等于值 1...

    SQL语句的DECODE和NVL

    SQL 语句的 DECODE 和 NVL 函数 在 SQL 语句中,DECODE 和 NVL 函数是两个非常重要和常用的函数,它们可以帮助我们实现复杂的逻辑判断和数据处理。本文将详细介绍 DECODE 和 NVL 函数的使用方法和实践应用。 一、...

    python decode()和encode()函数详解

    decode和encode是他们之间的转化函数 大致的过程如下 decode encode str --&gt; str(Unicode) --&gt; str decode()方法语法: str.decode(encoding=‘UTF-8’,errors=‘strict’) 参数: encoding – 要使用的编码...

    ev1转换器ev1decode.zip

    "ev1转换器ev1decode.zip" 提供的工具显然专注于处理名为 "ev1" 的特定编码格式。让我们深入探讨一下这个话题,以及与之相关的知识点。 1. **EV1编码**:EV1(可能指的是Enhanced Video1或类似含义)是一种视频编码...

    decode 加入clickhouse库之后代码

    "decode"函数在数据库系统中通常用于解码或转换编码的数据。在ClickHouse中,`decode`函数可能被用来处理编码过的字符串,将其转化为原始格式。例如,如果你有一个用Base64或URL编码的数据字段,`decode`函数可以...

    decode函数[归类].pdf

    【DECODE函数详解】 DECODE函数是Oracle PL/SQL中的一个独特特性,它在软件开发,尤其是数据库查询中,提供了一种简洁而高效的方法来进行条件判断和数据转换。这个函数在Oracle SQL中扮演了if-then-else逻辑的角色...

Global site tag (gtag.js) - Google Analytics