[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)

[LeetCode] Binary Tree Postorder Traversal

Problem:

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:O(n)