LeetCode(91) -- 91, 89,

P91. Decode Ways (Medium)

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

My Solution

首先应该从后往前走，因为从前往后走的话，0的问题比较麻烦，如果第三位是0，第二位就必须要跟那个0进行组合，也就是说我必须要往后看两位甚至以上。从后往前走就不会有这个问题。

其次这道题显然是一道动态规划，要用一个数据记录下来每个位置可以组合的个数，逐个推进。

从右往左每新加一个数字，就可能出现两种情况，新一种情况是新加的数字单独分开，组合的个数就等于当前的。第二种情况是新加的数字跟当前最左边的数字组合成一组，那么组合的个数就等于第二位保存的个数。

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int[] memo = new int[n + 1];
        memo[n] = 1;
        memo[n - 1] = s.charAt(n - 1) == '0' ? 0 : 1;
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') continue;
            int parseInt = Integer.parseInt(s.substring(i, i + 2));
            memo[i] = parseInt <= 26 ? memo[i + 1] + memo[i + 2] : memo[i + 1];
        }
        return memo[0];
    }
}

97%

P89. Gray Code (Medium)

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

My Solution

The Best Solution

P. (Medium)

My Solution

The Best Solution

P. (Medium)

My Solution

The Best Solution

P. (Medium)

My Solution

The Best Solution