题解 | #把数字翻译成字符串#
把数字翻译成字符串
https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668
从下标0开始,计算当前字符及该字符之前字符串中一共有多少种解码方式;
同理斐波那契,由于每个状态只与前两个状态相关,用两个变量记录,pre记录上一轮结果,cur为当前轮结果;
状态转移有三种情况:
当 当前字符和上一个字符组成两位数时不满足数值在10-26之间时,我们只能把这个数当做单独的数来解码,如3,6组合36比26大了,6只能当做单独的6来解码,0,9组合比10小了,9只能当做单独的数字9来看;
即该轮结果应与上一轮结果一致,cur可不变,pre转为上轮结果:pre =cur
当 当前字符和上一个字符组成两位数满足数值在10-26之间时,就出现两种选择——与前一个字符相组合 | 不组合 ,将两种选择相加即可;
即该轮结果等于上一轮结果与上上轮结果相加:cur = cur + pre;
pre转为上轮结果:pre = cur - pre;
值得注意,当一位数时不能是0,所以在处理一位数时,得把0给搞掉:nums.charAt(i) == '0'?0:cur
import java.util.*; public class Solution { /** * 解码 * @param nums string字符串 数字串 * @return int整型 */ public int solve (String nums) { int pre = 0;//上一轮的结果 int cur = 1;//当前i下标及之前的字符串的可能组合数 for (int i = 0; i < nums.length(); i++) { if (i == 0 || (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0') > 26 || (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0') < 10) {//如果没有构成两位数的条件,则只能将当前数字单独相加 pre = cur; cur = nums.charAt(i) == '0'?0:cur;//若当前单独相加的数字是0,说明根本没有选择 } else {//可以选择组一位数->cur也可以选择组两位数->pre,将两种情况相加 cur = (nums.charAt(i) == '0'?0:cur) + pre;//相加时同样要处理一位数是0的情况 pre = cur - pre; } } return cur; } }