Wednesday 25 June 2014

How to find a Solution?

Source: How To Find a Solution http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=findSolution

1)
Straight-forward problems that don't require any special technique (e.g. simulation, searching, sorting, BST etc.)

2) 
Breadth First Search (BFS)
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one. & all of edges having the same cost of 1.

Example Leetcode:
1: Word Ladder

3)
Flood Fill
Sometimes you may encounter problems that are solved by the help of Flood Fill, a technique that uses BFS to find all reachable points. 

Example Leetcode:
1: Surrounded Regions
2: Binary Tree Level Order Traversal

4)
Brute Force
How does a brute force algorithm work? Actually, it tries all possible situations and selects the best one. It's simple to construct and usually simple to implement. If there is a problem that asks to enumerate or find all possible ways (situations) of doing a certain thing, and that doesn't have high limits - then it's most probably a brute force problem.

5)
Dynamic Programming
1: Optimal Subproblem
2: Repeated Computing

AND both the search space and the target are integers!!

Example Leetcode:
1: Unique Paths I & II
2: Climbing Stairs
3: Decode Ways

6) 
Greedy Algorithm
1: Optimal Subproblem
2: Repeated Computing
3: Greedy Property

7)
Recursion Method
Tree, String, Array

Example Leetcode:
1: Scramble String

8)
N-Scan Method

  1. 2-round Scan
  2. Fast-Slow Scan
  3. Reversed Scan

9) 
Linear Programming
1: Objective Function
2: Constraints


No comments:

Post a Comment