553. Optimal division [medium question] [daily question]

Idea: [mathematical method]

1. Let the optimal solution of dividing these n numbers be Fn=x/y. obviously, if the numerator is as large as possible and the denominator is as small as possible, the result will be the largest. Because nums are all positive integers greater than 1, the smaller the division is, it will be the largest only when the numerator takes nums[0], so now it becomes Fn=nums[0]/Fn-1, and Fn-1 represents the result of dividing the next n-1 numbers.
2. At this time, in order to maximize Fn, it is known from the above analysis that Fn-1 needs to be minimized, and Fn-1 can also be expressed in the form of fraction x/y. to minimize Fn-1, it is necessary to minimize the numerator x and maximize the denominator y. therefore, according to the rules of mathematical operation multiplication and division, in the combination of n-1 numbers after nums, only when nums[1] itself is the numerator and the numerator is the smallest, the denominator is the largest when the latter n-2 numbers are continuously multiplied, So the minimum value of Fn-1 is expressed as
   nums[1] / (multiply all the numbers behind).
3. Thus, Fn (max) = num [0] / Fn-1 (min) = num [0] / (Num [1] / num [2] /... / num [len-1]), that is, when the array length len is 1, Num [0] / num [1] is returned directly; when the array length len is 2, Num [0] / num [1] is returned; when the array length is greater than 2, Num [0] / (Num [1] / num [2] /... / num [len-1]) is returned.

code:

class Solution {
    public String optimalDivision(int[] nums) {
        int len = nums.length;
        if (len == 1){
            return nums[0]+"";
        }
        if (len == 2){
            return nums[0]+"/"+nums[1];
        }
        StringBuilder ans = new StringBuilder(nums[0] + "/(");
        for (int i = 1; i < len; i++) {
            ans.append(nums[i]).append("/");
        }
        ans.deleteCharAt(ans.length()-1);
        return ans+")";
    }
}

150. Evaluation of inverse Polish expression [medium question]

Idea:

1. This question has no technical content. The following tips are too obvious.
2. The title must give a valid inverse Polish expression, so if the length of tokens is 1, it must be a number. Just return this number. The length of tokens cannot be 2. If it is 2, it cannot constitute a valid inverse Polish expression, but the range of tokens is greater than or equal to 1. In fact, it is unnecessary to return - 1 if the length is 2, It can't all be in the code len=2.
3. When the length is greater than or equal to 3, the first two numbers must be numbers. Add them to the Linkedlist, and traverse from the third position of tokens. When encountering an operator, take out the last element of the current list, set it to n2, delete the last position element, and then take out the last element of the current list, set it to n1, and delete the last element of the list again, In short, the meaning of this operation is to set the penultimate element extraction of the list to n1 and the last element extraction to n2 when encountering an operator, delete the last two elements, and operate n1 and n2 according to the operator (n1)
   Operator n2), the result obtained is added to the last position of the list; If an array is encountered, the current number is directly stored in the last position of the list.
   4. After traversal, there is only one element left in the list. This element is the final operation result. Just return it.

code:

class Solution {
    public int evalRPN(String[] tokens) {
        int len = tokens.length;
        if (len == 1){
            return Integer.parseInt(tokens[0]);
        }
        if (len == 2){
            return -1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        list.addFirst(Integer.parseInt(tokens[0]));
        list.addLast(Integer.parseInt(tokens[1]));
        for (int i = 2; i < len; i++) {
            String cur = tokens[i];
            if ("+".equals(cur) || "-".equals(cur) || "*".equals(cur) || "/".equals(cur)){
                int n2 = list.getLast();
                list.removeLast();
                int n1 = list.getLast();
                list.removeLast();
                int n = 0;
                switch (cur){
                    case "+":n = n1+n2;break;
                    case "-":n = n1-n2;break;
                    case "*":n = n1*n2;break;
                    case "/":n = n1/n2;break;
                }
                list.addLast(n);
            }else {
                list.add(Integer.parseInt(cur));
            }
        }
        return list.getFirst();
    }
}