新博文地址:[leetcode]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.
'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]; }
相关推荐
js代码-leetcode 91 DEcode Ways
DECODE
主要作用:将查询结果翻译成其他值(即以其他形式表现...Select decode(columnname,值1,翻译值1,值2,翻译值2,...值n,翻译值n,缺省值) From talbename Where … 其中columnname为要选择的table中所定义的column,
Oracle中Decode()函数的有关用法Oracle中Decode()函数的有关用法
关于oracle decode函数的用法
编译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....
decode和encode是他们之间的转化函数 大致的过程如下 decode encode str --> str(Unicode) --> str decode()方法语法: str.decode(encoding=‘UTF-8’,errors=‘strict’) 参数: encoding – 要使用的编码...
1 DECODE 中的if-then-else逻辑 在逻辑编程中,经常用到If – Then –Else 进行逻辑判断。在DECODE的语法中,实际上就是这样的逻辑处理过程。
base64decode 编码,解码。
avs_decode.rar
UrlDecode是我们天天要用的东西了,小的字符串,我们直接拷到在线网站上处理掉,大量数据呢?这个工具可以高效离线处理,亲测200GB日志,完全满足您的需求。
decode函数.docx
如果不想在url中看到有明文,比如http://localhost:8080/template_1/login.action?user=张三 可以使用js的encodeURI的URLDecoder.decode一起使用一起来把url加密下 (1)JS在页面上把数据var val = encodeURI...
js实现urlncode 和urldecode
decode 加入clickhouse库之前代码
PHP 获取JSON json_decode返回NULL解决办法,不小心在返回的json字符串中返回了BOM头的不可见字符,某些编辑器默认会加上BOM头,这样处理才能正确解析json数据
DECODE函数相当于一条件语句(IF).它将输入数值与函数中的参数列表相比较,根据输入值返回一个对应值。
jwt JS解密文件 var getUserjwt = function (token) { if (!token) { return; } } //解析jwt令牌 var jwtDecodeVal = jwt_decode(token);
Oracle中Decode()函数使用技巧Oracle中Decode()函数使用技巧Oracle中Decode()函数使用技巧