LeetCode Day10 Stack&Queue Part 2
Tags: leetcode, java, algorithms, datastructures
Published: 2024-06-17 15:07:06

# LeetCode No.150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.
 

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 

Constraints:

1 <= tokens.length <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
[Original Page](https://leetcode.com/problems/evaluate-reverse-polish-notation/description/)



```
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new LinkedList<>();
        for(String s: tokens){
            char ch = s.charAt(s.length()-1);
            if(ch>='0' && ch<='9'){
                deque.push(Integer.valueOf(s));
            }
            else{
                int num2 = deque.pop();
                int num1 = deque.pop();
                deque.push(calculation(num1,num2,ch));
            }
        }
        return deque.pop();
    }

    public int calculation(int num1, int num2, char sign){
        return switch(sign){
            case '+' -> num1+num2;
            case '-' -> num1-num2;
            case '*' -> num1 * num2;
            case '/' -> num1 / num2;
            default -> Integer.MAX_VALUE;
        };
    }
```

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u7oyievuwm1t1gfv9r9u.png)
Be careful 
- String array's elements are only comprised by numbers or '+', '-', '*', and '/',so we divided them into number and non-number
- in Java we cannot directly evaluate a String whether is a number or not so we have to change it into char and to evaluate whether the ***last element*** of the String is number or not (the last element because the negative numbers are start from '-' as well)
- don't forget cast String to int (actually it will cast String to Integer and auto-boxing Integer to int)


# LeetCode 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:

Input: nums = [1], k = 1
Output: [1]
 

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
[Original Page](https://leetcode.com/problems/top-k-frequent-elements/description/)

1 statistic for elements
2 sorted 
3 return value

-----> From above three key points we can get 
we at least need 
1 Map
2 Sorted 

So here is a directly code about this method 

```
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for(int i: nums){
            map.put(i, map.getOrDefault(i,0)+1);
        }

        List<Map.Entry<Integer,Integer>> result = map.entrySet()
                                                    .stream()
                                                    .sorted(Map.Entry.<Integer,Integer>comparingByValue(Comparator.reverseOrder()))
                                             .collect(Collectors.toList());

        List<Integer> out = new ArrayList<>();
        for(int i=0; i<k;i++){
            Map.Entry<Integer,Integer> temp = result.get(i);
            out.add(temp.getKey());
        }

        return out.stream().mapToInt(Integer::valueOf).toArray();

    }
```


### Refine above code 
```
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for(int i: nums){
            map.put(i, map.getOrDefault(i,0)+1);
        }

        List<Integer> result = map.entrySet()
                                .stream()
                                .sorted(Map.Entry.<Integer,Integer>comparingByValue(Comparator.reverseOrder()))
                                .limit(k)
                                .map(Map.Entry::getKey)
                                .collect(Collectors.toList());


        return result.stream().mapToInt(Integer::valueOf).toArray();

    }
```
Time: O(nlogn) +n + k in detail but O(nlogn) in general 

### To Be Continue: PriorityQueue