Verbose Java solution, LinkedList


  • 8
    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

    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


  • 1

    @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

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

  • 0
    T

    If the ops[0]="C" then the application will throw java.util.NoSuchElementException.
    So we may need add the special logic to handle this situation.

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

    This may work better.


  • -1
    M
    This post is deleted!

  • 0

    @Midgar77 said in Verbose Java solution, LinkedList:

    list.get(list.size() - 2));

    This call right here is exactly why LinkedList is one of the worst choices of data structures to store the points. Since it is a LinkedList, calling .get() is O(N) and you are calling .size() within that get which is also O(N).

    Consider at least storing (and updating appropriately) the size of your LinkedList as a variable :-)

    What part of

    public int size() {
        return size;
    }
    

    makes you say O(N)?

    http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/LinkedList.java#l325

    And that get call is O(1) as well. As you can see elsewhere in the code if you just bother to look. And as you should expect after reading the first two paragraphs of the documentation.


  • 0
    Z

    @ManuelP For + you can remove the last element from LinkedList (O(1)) and then add it back after calculating sum. LinkedList/Deque is a great data structure to solve this problem cleanly.


  • 0

    @zeebo Hmm, but why would you do that? That's two unnecessary modifications. Is that supposed to be somehow better than what shawngao does? And please show the code, would be good to have for comparison.

    @shawngao Why do you use peekLast instead of getLast? As far as I can tell, the difference is that peekLast returns null if the list is empty, but it's not like you can actually handle a null value, so I find this rather misleading.


  • 0
    Z

    @ManuelP I think the get(list.size() - 2) is O(n) operation, but removing 1 element from Deque is O(1) operation. This is my code:

    class Solution {
    public int calPoints(String[] ops) {
    Deque<Integer> points = new LinkedList<>();
    int sum = 0;
    for (String s : ops) {
    if (s.equals("C") && !points.isEmpty()) {
    sum -= points.removeLast();
    } else if (s.equals("D") && !points.isEmpty()) {
    int val = points.peekLast() * 2;
    points.addLast(val);
    sum += val;
    } else if (s.equals("+") && points.size() >= 2) {
    int last = points.removeLast();
    int plus = last + points.peekLast();
    points.addLast(last);
    points.addLast(plus);
    sum += plus;
    } else {
    int val = Integer.parseInt(s);
    points.addLast(val);
    sum += val;
    }
    }
    return sum;
    }
    }


  • 0

    @zeebo said in Verbose Java solution, LinkedList:

    @ManuelP I think the get(list.size() - 2) is O(n) operation

    As I already said, it's O(1).

    And please format your code, it's rather hard to read without indentation.


Log in to reply
 

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