about // doc

# LeetCode Practice

## Array and List

## Binary Search

## Matrix

## Numerical Implementation

## Bit Manipulation

## Dynamic Programming

## Tree

## Graph

*Last updated: Feb, 2015*

The list below includes my practice on problems from Leetcode Online Judge. Various online resources are of great help in such as process, including Leetcode OJ forums and this blog. I mostly write them in Python but will add solutions in C++ or Java later.

Merge and sort:

K-sum problems:

When to use binary search: if the object is somewhat “sorted”, then it has potential to be applied with binary search.

- Search insert position
- Search for a range
- Sqrt(x)
- Search a 2D matrix
- Search in rotated sorted array I and II
- Find minimum in rotated sorted array
- Find peak element

Many matrix problems here do not involve fancy algorithms and data structures. However, index manipulation can be tedious and error prone.

In C++ or Java, one may need to worry about the int type overflow in some of those problem .

- Palindrome number
- Reverse integer
- Sqrt(x)
- Pow(x,n)
- Divide two integers
- Max points on a line
- Add binary
- Add two numbers
- Plus one
- Multiply strings (empty)

Dynamic programming problems exist in many forms. The first step is to tell if the problem can be solved by dynamic programming paradigm, and then try to find the recurrence relationship. Note that dynamic programming problems are not only solvable by recursive design: they can also be done by iterative programs, which may or may not be more efficient. For the recursive approach, one needs to design the API of the recursive call. Some API design is more elegant and efficient that others.

Prototype problems of using dynamic programming: counting/listing different ways of doing something, tree operations, some program using a stack, etc. A good article on this topic is “dynamic programming: from novice to advanced”.

- Climbing stairs
- Decode ways
- Maximum subarray
- Maximum product subarray
- Best time to buy and sell stock I, II and III

Basic tree traversal methods include preorder, postorder, inorder and level order. The preorder, postorder and inorder traversal can be realized recursively or interatively (using a stack). Level order traversal is realized iteratively using a queue. Zigzag level order traversal is a variant using stacks.

- Binary tree inorder, preorder and postorder traversal.
- Binary tree level order traversal I and II.
- Binary tree zigzag level order traversal

Binary tree properties:

- Maximum depth of binary tree
- Minimum depth of binary tree
- Balanced binary tree
- Same tree
- Symmetric tree

Path sum problems:

Binary search trees.

- Convert sorted array or list to binary search tree
- Construct binary tree from preorder and inorder traversal
- Construct binary tree from inorder and postorder traversal
- Validate binary search tree
- Recover binary search tree
- Unique binary search tree I and II

- Clone graph
- [Word ladder I and II]
- Longest consecutive sequence
- Word search
- Surrounded regions

comments powered by Disqus