编码专题 2016-8-25

[wolfogre]

91. Decode Ways

89. Gray Code

[dayang]

/**
 * [AC] LeetCode 89 Gray Code
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
    if(n <= 0) return [0];
    var ans = ['0','1'], i, j;

    for(i = 1; i < n; i++){
        for(j = Math.pow(2,i) - 1; j >= 0 ; j--){
            ans.push('1' + ans[j]);
            ans[j] = '0' + ans[j];
        }
    }

    return ans.map(function(s){
        return parseInt(s,2);
    });
};

[zhaokuohaha]

91 - C

public class Solution
{
    public int NumDecodings(string s)
    {
        if (String.IsNullOrEmpty(s)) 
            return 0;
        if (s[0] == '0') 
            return 0;
        if (s.Length == 1) 
            return  1;
        if (Convert.ToInt32(s.Substring(0, 2)) > 21 && Convert.ToInt32(s.Substring(0, 2)) % 10 == 0) 
            return 0;
        if (s.Length == 2) 
            return Convert.ToInt32(s) > 26 || Convert.ToInt32(s)  < 11|| Convert.ToInt32(s) % 10 == 0 ? 1 : 2;
        int[] dp = new int[s.Length];
        dp[0] = 1;
        dp[1] = Convert.ToInt32(s.Substring(0,2)) > 26 ||  Convert.ToInt32(s.Substring(0, 2)) < 11 ? 1 : 2;
        for(int i=2; i<s.Length; i++)
        {
            int ele = Convert.ToInt32(s.Substring(i - 1, 2));
            if (s[i] == '0')
            {
                if (s[i - 1] == '0' || s[i-1] > '2') return 0;
                dp[i] = dp[i - 2];
            }
            else dp[i] = (ele > 26 || ele < 10) ? s[i-1] == '0' ? dp[i-2] : dp[i - 1] : dp[i - 1]+dp[i-2];
        }
        return dp[s.Length - 1];
    }
}

[zhaokuohaha]

89 - C

public class Solution
{
    public IList<int> GrayCode(int n)
    {
        List<int> res = new List<int>();
        res.Add(0);
        if (n > 0)
            res.Add(1);
        for(int i = 1; i<n; i++)
        {
            for(int j=res.Count-1; j>=0; j--)
            {
                res.Add((int)Math.Pow(2, i) + res[j]);
            }
        }
        return res;
    }
}