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

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

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

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