栈&动态规划 2016-08-05

[SnackMen]

150. Evaluate Reverse Polish Notation 91. Decode Ways

[zhaokuohaha]

150 - C# - 使用C# Stack类型

public class Solution
{
    public int EvalRPN(string[] tokens)
    {
        Stack<int> st = new Stack<int>();
        foreach(string item in tokens)
        {
            if(item=="+"|| item == "-" || item == "*" || item == "/")
            {
                calculate(st,item);
            }else
            {
                st.Push(Convert.ToInt32(item));
            }
        }
        return st.Peek();
    }

    private void calculate(Stack<int> st,string opt)
    {
        int a = st.Pop();
        int b = st.Pop();
        switch (opt)
        {
            case "+":
                st.Push(b + a);
                break;
            case "-":
                st.Push(b - a);
                break;
            case "*":
                st.Push(b * a);
                break;
            case "/":
                st.Push(b / a);
                break;
        }
    }
}

[zhaokuohaha]

91 - C# - 斐波那契 :8ball:

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];
    }
}

还没过, 转移方程不会写

public class Solution
{
    public int NumDecodings(string s)
    {
        if (String.IsNullOrEmpty(s)) return 0;
        if (s[0] == '0') return 0;
        if (Convert.ToInt32(s.Substring(0, 2)) > 21 && Convert.ToInt32(s.Substring(0, 2)) % 10 == 0) return 0;
        if (s.Length == 1) return  1;
        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]+1;
        }
        return dp[s.Length - 1];
    }
}

[dayang]

/**
 * [AC] LeetCode 91  Decode Ways
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    if (s.length === 0) return 0;
    if (s[0] === '0') return 0;
    if (s.length === 1) return 1;
    let nums = [1, 1];
    let t;
    for (let i = 2; i <= s.length; i++) {
        if (s[i - 1] === '0' && (s[i - 2] === '0' || s[i - 2] > '2')) {
            return 0;
        } else {
            if (s[i - 1] === '0') {
                nums.push(nums[i - 2]);
            } else if (s[i - 2] === '0') {
                nums.push(nums[i - 1]);
            } else {
                let str = s[i - 2] + s[i - 1];
                t = str <= '26' ? nums[i - 2] : 0;
                nums.push(nums[i - 1] + t);
            }
        }
    }
    return nums[s.length];
};

[dayang]

/**
 * [AC] LeetCode 150 Evaluate Reverse Polish Notation
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    function compute(a,b,op){
        a = Number(a);
        b = Number(b);
        if(isNaN(a) || isNaN(b)){
            return null;
        }
        let res;
        switch(op){
            case '+':
                res = a + b;
                break;
            case '-':
                res = a - b;
                break;
            case '*':
                res = a * b;
                break;
            case '/':
                res = (a / b >= 0 ? Math.floor(a / b) : Math.ceil(a / b));
                break;
            default:
                return null;
        }
        return res;
    }

    function isOperator(op){
        return op === '+' || op === '-' || op === '*' || op === '/';
    }

    if(tokens.length === 0) return 0;
    let stack = [],a,b;
    stack.push(tokens[0]);
    if(tokens.length > 1)
        stack.push(tokens[1]);
    for(let i = 2; i < tokens.length; i++){
        if(isOperator(tokens[i])){
            b = stack.pop();
            a = stack.pop();
            let res = compute(a,b,tokens[i]);
            if(res !== null){
                stack.push(res);
            }else{
                return 0;
            }
        }else{
            stack.push(tokens[i]);
        }
    }
    return (stack.length === 1 && Number(stack[0]) ? Number(stack[0]) : 0);
};

[SnackMen]

/*
*[AC] LeetCode 150 Evaluate Reverse Polish Notation
*/
public class Solution {
    public Stack<String> stack;
    public int evalRPN(String[] tokens) {
        stack = new Stack();
        for(String str:tokens){
            stack.push(str);
            if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
                calculate();
            }
        }
        String string =stack.pop();
        return Integer.valueOf(string);
    }

    public void calculate(){
        String string = stack.pop();
        int num1 = Integer.valueOf(stack.pop());
        int num2 = Integer.valueOf(stack.pop());
        int num=0;
        if(string.equals("+")){
            num=num2+num1;
        }else if(string.equals("-")){
            num=num2-num1;
        }else if(string.equals("*")){
            num=num2*num1;
        }else if(string.equals("/")){
            num=num2/num1;
        }
        stack.push(String.valueOf(num));
    }
}

[SnackMen]

/*
*[AC] LeetCode 91  Decode Ways
*/
public class Solution {
    public int numDecodings(String s) {
        int length=s.length();
        if(length==0)
            return 0;
        int num[] = new int[length+1];
        num[length]=1;
        num[length-1]=s.charAt(length-1)=='0' ? 0:1;
        for(int i=length-2;i>=0;i--){
            if(s.charAt(i)=='0')
                continue;
            else{
                if(Integer.valueOf(s.substring(i,i+2))<27)
                    num[i]=num[i+1]+num[i+2];
                else
                    num[i]=num[i+1];
            }
        }
        return num[0];
    }

}