Verbose Java solution, LinkedList


  • 7
    class Solution {
        public int calPoints(String[] ops) {
            int sum = 0;
            LinkedList<Integer> list = new LinkedList<>();
            for (String op : ops) {
                if (op.equals("C")) {
                    sum -= list.removeLast();
                }
                else if (op.equals("D")) {
                    list.add(list.peekLast() * 2);
                    sum += list.peekLast();
                }
                else if (op.equals("+")) {
                    list.add(list.peekLast() + list.get(list.size() - 2));
                    sum += list.peekLast();
                }
                else {
                    list.add(Integer.parseInt(op));
                    sum += list.peekLast();
                }
            }
            return sum;
        }
    }
    

  • 0

    Awesome! Could you explain why using LinkedList instead of ArrayList(Advantages)? Thanks!


  • -1
    B

    @BryanBo.Cao yea pretty sure the add function on LinkedList is O(n) compared to an ArrayList's O(1)


  • 0
    V

    I did it with stack.

    class Solution {
        public int calPoints(String[] ops) {
            if(ops == null || ops.length == 0) return 0;   
            Stack<Integer> st = new Stack<Integer>();
            int len = ops.length;
            int total = 0,
                new_pts = 0,
                temp = 0;
            for(int i=0;i<len;++i){
                switch(ops[i]){
                    case "+":
                          if(st.size() > 1){
                            temp = st.pop();
                            new_pts = temp + st.peek(); 
                            st.push(temp);
                            st.push(new_pts);
                            total += new_pts;                        
                          }
                    break;
                    case "C":
                          if(!st.isEmpty()) total -= st.pop();
                    break;
                    case "D":
                          if(!st.isEmpty()){
                               total += st.peek() << 1;
                               st.push(st.peek()<<1);
                          }
                    break;
                    default:
                         temp = Integer.parseInt(ops[i]);
                         st.push(temp);
                         total += temp;
                }            
                
            }                
            
            return total;
        }
    }
    

  • 0

    @bleepbloopblop said in Verbose Java solution, LinkedList:

    @BryanBo.Cao yea pretty sure the add function on LinkedList is O(n) compared to an ArrayList's O(1)

    Thanks! But if the add function on LinkedList is O(n) greater than ArrayList's O(1) then why do we use LinkedList?
    nʕ-͏̶̶̶̯͡-ʔn


  • 0
    B

    @BryanBo.Cao that's the point. we dont want to use LinkedList


  • 0

    @bleepbloopblop said in Verbose Java solution, LinkedList:

    @BryanBo.Cao yea pretty sure the add function on LinkedList is O(n) compared to an ArrayList's O(1)

    LinkedList's is O(1). Why wouldn't it be?

    And ArrayList's isn't O(1) but only amortized O(1).


  • 0
    B
    This post is deleted!

  • 0
    R
        public int calPoints(String[] ops) {
            if(ops == null) return 0;
            Stack<Integer> s = new Stack<Integer>();
            int sum = 0;
            for(int i=0; i<ops.length; i++)
            {
                if(ops[i].equals("C"))
                {
                    if(s.isEmpty())
                        return -1;
                    int x = s.pop();
                    sum -= x;
                }
                else if(ops[i].equals("D"))
                {
                    int x = s.peek();
                    x = x * 2;
                    s.push(x);
                    sum += x;
                }
                else if(ops[i].equals("+"))
                {
                    if(s.size() < 2)
                        return -1;
                    int t1 = s.pop();
                    int t2 = s.pop();
                    s.push(t2);
                    s.push(t1);
                    s.push(t1 + t2);
                    sum += t1 + t2;
                }
                else
                {
                    int x = Integer.parseInt(ops[i]);
                    s.push(x);
                    sum += x;
                }
            }
            
            return sum;
        }
    }

  • 1

    @Vivek
    I did it with stack too, and here is my solution:

    public int calPoints(String[] ops) {
            int sum = 0;
            Stack<Integer> stack = new Stack<>();
            for (String s : ops) {
                if (s.equals("C")) sum -= stack.pop();
                else if (s.equals("D")) {
                    stack.push(stack.peek() * 2);
                    sum += stack.peek();
                }
                else if (s.equals("+")) {
                    int last = stack.pop();
                    int add = last + stack.peek();
                    stack.push(last);
                    stack.push(add);
                    sum += stack.peek();
                }
                else {
                    stack.push(Integer.parseInt(s));
                    sum += stack.peek();
                }
            }
            return sum;
    }
    

  • 1
    V

    @dilyar Yes, with stack it becomes pretty intuitive.


  • 0
    M
    import java.util.ArrayList;
    import java.util.regex.Pattern;
    class Solution {
        public int calPoints(String[] ops) {
            int sum = 0;
    	        ArrayList<Integer> list = new ArrayList<Integer>();
    	        Pattern pattern = Pattern.compile("^[-]?[\\d]*$");
    	        for (int i = 0; i < ops.length; i++) {
    				if (pattern.matcher(ops[i]).matches()) {
    					list.add(Integer.valueOf(ops[i]));
    				} else if(ops[i] == "C"){
                      list.remove(list.size() - 1);
    				}
    				else if(ops[i] == "D"){
    	              list.add(2 * list.get(list.size()-1));
    				}
    				else if (ops[i] == "+") {
    					list.add(list.get(list.size()-1) + list.get(list.size()-2));					
    				}
    			}
    	        
    	        for (int j = 0; j < list.size(); j++) {
    				sum += list.get(j);
    			}
    	        return sum;
        }
    }
    

    I don't know why I get the right values in my Eclipse, however when I run it on the LeetCode, it got the inconsistent value.


  • 0
    F

    I use stack

    class Solution {
        public int calPoints(String[] ops) {
            Stack<Integer> stack = new Stack<>();
            int sum = 0;
            for (String s: ops) {
                if (s.equals("D")) {
                    stack.push(stack.peek() * 2);
                    sum += stack.peek();
                } else if (s.equals("C")) {
                    sum -= stack.pop();
                } else if (s.equals("+")) {
                    int sec = stack.peek();
                    stack.pop();
                    int fir = stack.peek();
                    int cur = fir + sec;
                    stack.push(sec);
                    stack.push(cur);
                    sum += cur;
                } else {
                    stack.push(Integer.parseInt(s));
                    sum += stack.peek();
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.