LeetCode(102) -- 150, 151, 152

P150. Evaluate Reverse Polish Notation (Medium)

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

My Solution

用stack就可以了

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                Integer second = stack.pop();
                Integer first = stack.pop();
                stack.push(first + second);
            } else if (token.equals("-")) {
                Integer second = stack.pop();
                Integer first = stack.pop();
                stack.push(first - second);
            } else if (token.equals("*")) {
                Integer second = stack.pop();
                Integer first = stack.pop();
                stack.push(first * second);
            } else if (token.equals("/")) {
                Integer second = stack.pop();
                Integer first = stack.pop();
                stack.push(first / second);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

94%

P151. Reverse Words in a String (Medium)

Given an input string, reverse the string word by word.

My Solution

class Solution {
    public String reverseWords(String s) {
        String[] split = s.trim().split("\\s+");
        int length = split.length;
        for (int i = 0; i < length / 2; i++) {
            String temp = split[i];
            split[i] = split[length - i - 1];
            split[length - i - 1] = temp;
        }
        StringBuilder sb = new StringBuilder();
        for (String s1 : split) {
            sb.append(s1).append(" ");
        }
        return sb.toString().trim();
    }
}

69%

Solution

class Solution {
  public String reverseWords(String s) {
    int left = 0, right = s.length() - 1;
    // remove leading spaces
    while (left <= right && s.charAt(left) == ' ') ++left;

    // remove trailing spaces
    while (left <= right && s.charAt(right) == ' ') --right;

    Deque<String> d = new ArrayDeque();
    StringBuilder word = new StringBuilder();
    // push word by word in front of deque
    while (left <= right) {
      char c = s.charAt(left);

      if ((word.length() != 0) && (c == ' ')) {
        d.offerFirst(word.toString());
        word.setLength(0);
      } else if (c != ' ') {
        word.append(c);
      }
      ++left;
    }
    d.offerFirst(word.toString());

    return String.join(" ", d);
  }
}

这答案算法没什么，但是可以学习一下ArrayDeque, Deque,以及stringbuilder其实可以通过setLength(0)这个方法清空。deque可以用offerFirst()这个方法把元素加到队列的最前面。String.join(“ “, deque)这个方法可以把deque变成string, 中间用空格隔开。

P152. Maximum Product Subarray (Medium)

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

My Solution

暴力求解了，把所有可能的乘积都算出来，找出最大的。

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = i; j < nums.length; j++) {
                product *= nums[j];
                max = Math.max(max, product);
            }
        }
        return max; 
    }
}

5%

The Best Solution

方法一：

class Solution {
    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];
        max[0] = nums[0];
        min[0] = nums[0];
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            max[i] = Math.max(nums[i], Math.max(max[i - 1] * nums[i], min[i - 1] * nums[i]));
            min[i] = Math.min(nums[i], Maht.min(max[i - 1] * nums[i], min[i - 1] * nums[i]));
        }
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res, max[i]);
        }
        return res;
    }
}

方法二：

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = nums[0];
        int curMin = nums[0];
        int curMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int min = Math.min(nums[i], Math.min(curMin * nums[i], curMax * nums[i]));
            int max = Math.max(nums[i], Math.max(curMin * nums[i], curMax * nums[i]));
            curMin = min;
            curMax = max;
            res = Math.max(res, curMax);
        }
        return res;
    }
}