[LeetCode] Maximum Product Subarray

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:O(n)

public class Solution {

    public int maxProduct(int[] A) {
        if(A.length == 1)
            return A[0];
            
        int max = A[0];
        int premax = Math.max(A[0],0);
        int premin = Math.min(A[0],0);
        for(int i=1; i=0){
              premax = (premax ==0?A[i]: A[i]*premax);
              premin = (premin ==0?0: A[i]*premin);
            }
            else{
              int tmp = (premin ==0? 0 : A[i]*premin);
              premin = (premax > 0? A[i]*premax: A[i]);
              premax = tmp;
            }
            max = Math.max(max,premax);
        }
        return max;
    }
}

[LeetCode] Reverse Words in a String

Problem:

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

For example,
Given s = "the sky is blue",
return "blue is sky the".

Solution:O(n)

[LeetCode] Evaluate Reverse Polish Notation

Problem:

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

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

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:O(n)

[LeetCode] Max Points on a Line

Problem:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:O(n*n)

[LeetCode] Sort List

Problem:
Sort a linked list in O(n log n) time using constant space complexity.
Solution:O(nlogn)

[LeetCode] Insertion Sort List

Problem:
Sort a linked list using insertion sort.
Solution:O(n*n)

[LeetCode] LRU Cache

Problem:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:O(1)