温馨提示: 豌豆仅提供国内节点,不提供境外节点,不能用于任何非法用途,不能访问境外网站及跨境联网。

免费领取1万IP!

LeetCode--栈专题

发布时间:

385. Mini Parser

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) 
    {
        if(s==null || s.length()==0)
            return null;
        NestedInteger cur=null;
        Stack<NestedInteger> st=new Stack<>();
        int sign=1,num=0;
        for(int i=0;i<s.length();i++)
        {
            char c=s.charAt(i);
            if(c=='[')
                st.push(new NestedInteger());
            else if(c=='-')
                sign=-1;
            else if(Character.isDigit(c))
            {
                int j=i;
                while(j<s.length() && Character.isDigit(s.charAt(j)))
                {
                    num=num*10+s.charAt(j)-'0';
                    j++;
                }
                i=j-1;
                if (st.isEmpty()) {
                    cur = new NestedInteger(sign*num);
                    break;
                }
                st.peek().add(new NestedInteger(sign*num));
                sign=1;
            }
            else if(c==']')
            {
                cur=st.pop();
                if(st.isEmpty())
                    break;
                st.peek().add(cur);
            }
            else
                num=0;
        }
        return cur;
    }
}

241. Different Ways to Add Parentheses
算法一

class Solution {
    
    public List<Integer> diffWaysToCompute(String input) {
        
        
        return recursive(input);
    }
    
    public List<Integer> recursive(String input){
        LinkedList<Integer> res=new LinkedList<>();
        if(input.equals(""))
            return res;
        for(int i=0;i<input.length();i++)
        {
            char c=input.charAt(i);
            if(c=='+'|| c=='-'|| c=='*'){
                List<Integer> left=recursive(input.substring(0,i));
                List<Integer> right=recursive(input.substring(i+1));
                for(int a:left){
                    for(int b:right){
                        if(c=='+')
                            res.add(a+b);
                        if(c=='-')
                            res.add(a-b);
                        if(c=='*')
                            res.add(a*b);
                    }
                }
            }
        }
        if(res.size()==0)
            res.add(Integer.valueOf(input));
        return res;
    }
}

算法二:

class Solution {
    List<Integer>[][] dp = null;
    public List<Integer> diffWaysToCompute(String input) {
        int n = input.length();
        dp = new ArrayList[n][n];
        eval(input, 0, n-1);
        return dp[0][n-1];
    }
    private void eval(String s, int i, int j){
        if(dp[i][j] != null) return;
        dp[i][j] = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        for(int k=i; k <= j; k++){
            char op = s.charAt(k);
            if( op == '+' || op == '-' || op == '*'){
                eval(s, 0, k-1);
                eval(s, k+1, j);
                for(int val1 : dp[i][k-1])
                    for(int val2 : dp[k+1][j])
                        res.add(calc(val1, op, val2));
            }
        }
        if(res.isEmpty()){
            dp[i][j].add(Integer.valueOf(s.substring(i,j+1)));
            return;
        }
        dp[i][j] = res;
    }
    private int calc(int n1, char op, int n2){
        if(op == '+')
            return n1+n2;
        else if(op == '-')
            return n1-n2;
        else if(op == '*')
            return n1*n2;
        return 0;
    }
}

282. Expression Add Operators

class Solution {
    
    public static List<String> ret;
    public List<String> addOperators(String num, int target) {
        
        ret=new LinkedList<>();
        backtrace(num,new StringBuilder(),target,0,0,0);
        return ret;
    }
    
    
    public static void backtrace(String num,StringBuilder sb,int target,int start,long pre,long sum){
        
        if(start==num.length())
        {
            if(sum==target)
                ret.add(sb.toString());
            return;
        }
        
        for(int i=start;i<num.length();i++){
            
            if(num.charAt(start)=='0' && i>start)
                break;
            long val=Long.valueOf(num.substring(start,i+1));
            int len=sb.length();
            if(start==0){
                backtrace(num,sb.append(val),target,i+1,val,sum+val);
                sb.setLength(len);
            }else{
                backtrace(num,sb.append('+').append(val),target,i+1,val,sum+val);
                sb.setLength(len);
                backtrace(num,sb.append('-').append(val),target,i+1,-val,sum-val);
                sb.setLength(len);
                backtrace(num,sb.append('*').append(val),target,i+1,pre*val,sum-pre+pre*val);
                sb.setLength(len);
            }
        }
    }
}

227. Basic Calculator II

class Solution {
    public int calculate(String s) {
        int num=0;
        char sign='+';
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            
            char c=s.charAt(i);
            if(Character.isDigit(c))
                num=num*10+c-'0';
            if((!Character.isDigit(c) && c!=' ') || i==s.length()-1){
                    if(sign=='+')
                        stack.push(num);
                    if(sign=='-')
                        stack.push(-num);
                    if(sign=='*')
                        stack.push(stack.pop()*num);
                    if(sign=='/')
                        stack.push(stack.pop()/num);
                    num=0;
                    sign=c;
            }
        }
        int sum=0;
        while(!stack.isEmpty())
            sum+=stack.pop();
        return sum;
    }
}
以上内容来自于网络,如有侵权联系即删除

相关文章


RLP C#设计模式学习(沙盒模式) Bone Collector HDU - 2602(裸01背包dp) 李宏毅机器学习2(P4-P7) React( mobx的使用以及配置 ) numpy矩阵与与图像像素排布对应关系 共享网络打印机连接 MySQL 里 视图,触发器,事物,存储过程,内置函数,流程控制,索引

上一篇:转换流、文件拷贝案例和字符编码
下一篇:函数重载、函数指针、函数默认参数
注册
联系我们
渠道合作
16522444463
大客户合作
16522444463
QQ群
qq