Monday, May 30, 2016

Princeton Programming Assignment 3: Pattern Recognition


http://coursera.cs.princeton.edu/algs4/assignments/collinear.html
https://www.cs.princeton.edu/courses/archive/fall12/cos226/checklist/collinear.html
Computer vision involves analyzing patterns in visual images and reconstructing the real-world objects that produced them. The process is often broken up into two phases: feature detection and pattern recognition. Feature detection involves selecting important features of the image; pattern recognition involves discovering patterns in the features. We will investigate a particularly clean pattern recognition problem involving points and line segments. This kind of pattern recognition arises in many other applications such as statistical data analysis.
The problem. Given a set of N distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.

Points and lines
Brute force. Write a program BruteCollinearPoints.java that examines 4 points at a time and checks whether they all lie on the same line segment, returning all such line segments. To check whether the 4 points pqr, and s are collinear, check whether the three slopes between p and q, between p and r, and between p and s are all equal.
public class BruteCollinearPoints {
   public BruteCollinearPoints(Point[] points)    // finds all line segments containing 4 points
   public           int numberOfSegments()        // the number of line segments
   public LineSegment[] segments()                // the line segments
}
The method segments() should include each line segment containing 4 points exactly once. If 4 points appear on a line segment in the order pqrs, then you should include either the line segment ps or sp (but not both) and you should not include subsegments such as pr or qr. For simplicity, we will not supply any input to BruteCollinearPoints that has 5 or more collinear points.
Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N4 in the worst case and it should use space proportional to N plus the number of line segments returned.
A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.
  • Think of p as the origin.
  • For each other point q, determine the slope it makes with p.
  • Sort the points according to the slopes they makes with p.
  • Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p. If so, these points, together with p, are collinear.
Applying this method for each of the N points in turn yields an efficient algorithm to the problem. The algorithm solves the problem because points that have equal slopes with respect to p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Points and slopes
Write a program FastCollinearPoints.java that implements this algorithm.
public class FastCollinearPoints {
   public FastCollinearPoints(Point[] points)     // finds all line segments containing 4 or more points
   public           int numberOfSegments()        // the number of line segments
   public LineSegment[] segments()                // the line segments
}
The method segments() should include each maximal line segment containing 4 (or more) points exactly once. For example, if 5 points appear on a line segment in the order pqrst, then do not include the subsegments ps or qt.
Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N2 log N in the worst case and it should use space proportional to N plus the number of line segments returned.FastCollinearPoints should work properly even if the input has 5 or more collinear points.
public static void main(String[] args) throws IOException {
  String fileName = args[0];
  List<Point> points = readList(fileName); 
  Collections.sort(points);
  StdDraw.setXscale(0, 32768);
  StdDraw.setYscale(0, 32768);
  for(int i=0;i<points.size();i++) points.get(i).draw();
      Map<String, Boolean> printedMap = new HashMap<String, Boolean>();
      for(int i=0;i<points.size();i++) {
        List<Point> tmpPoints = new ArrayList<Point>();
        for(int j=i+1;j<points.size();j++) tmpPoints.add(points.get(j));
      Collections.sort(tmpPoints, points.get(i).SLOPE_ORDER);
      for(int j=0;j<tmpPoints.size();){
          double slote = points.get(i).slopeTo(tmpPoints.get(j));
        List<Point> nList = new ArrayList<Point>(); 
        nList.add(points.get(i)); nList.add(tmpPoints.get(j));
        j++;
        while(j<tmpPoints.size() && points.get(i).slopeTo(tmpPoints.get(j))==slote) {
          nList.add(tmpPoints.get(j));
          j ++;
          } 
          if(nList.size()>=4) {
            boolean printedFlag = false;
            for(int k=0;k<nList.size()-1;k++) {
              String seg = nList.get(k).toString()+","+nList.get(k+1).toString();
              if(!printedMap.containsKey(seg)) {
                printedMap.put(seg, true);
                printedFlag = true;
              }
            }
            if(printedFlag){
          Collections.sort(nList);
          for(int k=0;k<nList.size()-1;k++) System.out.print(nList.get(k)+" -> ");
          System.out.print(nList.get(nList.size()-1)+"\n");
          points.get(i).drawTo(nList.get(nList.size()-1));
            }
          }
        }
      }
}
public static void main(String[] args) {
    // Rescale the coordinate system.
    StdDraw.setXscale(0, 32768);
    StdDraw.setYscale(0, 32768);
    // Read points from the input file.
    In in = new In(args[0]);
    int pointsCount = in.readInt();
    Point[] points = new Point[pointsCount];
    for (int i = 0; i < pointsCount; i++) {
        int x = in.readInt();
        int y = in.readInt();
        points[i] = new Point(x, y);
        points[i].draw();
    }
    // Go each point p.
    for (int p = 0; p < pointsCount; p++) {
        // Sort the points according to the slopes they makes with p.
        sort(points, points[p].SLOPE_ORDER);
        // Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p
        ArrayList<Point> collinearPoints = new ArrayList<Point>(pointsCount);
        for (int q = 0; q < pointsCount - 1; q++) {
            if (p == q) {
                continue;
            }
            if (collinearPoints.isEmpty()) {
                collinearPoints.add(points[q]);
            } else if (points[p].slopeTo(points[q - 1]) == points[p].slopeTo(points[q])) {
                collinearPoints.add(points[q]);
            } else if (collinearPoints.size() > 2) {
                // Draw collinear points.
                collinearPoints.add(points[p]);
                Collections.sort(collinearPoints);
                // Display collinear points.
                for (int i = 0; i < 3; i++) {
                    StdOut.print(collinearPoints.get(i));
                    StdOut.print(" -> ");
                }
                StdOut.println(Collections.max(collinearPoints));
                Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));
                break;
            } else {
                collinearPoints.clear();
                collinearPoints.add(points[q]);
            }
        }
    }
}

/***********************************************************************
 *  Bottom-Up merge sorting functions
 ***********************************************************************/

// stably merge a[lo..m] with a[m+1..hi] using aux[lo..hi]
private static void merge(Point[] a, Point[] aux, int lo, int m, int hi, Comparator<Point> comparator) {
    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }
    // merge back to a[]
    int i = lo, j = m+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > m)                a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(comparator, aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

// bottom-up mergesort
public static void sort(Point[] a, Comparator<Point> comparator) {
    int N = a.length;
    Point[] aux = new Point[N];
    for (int n = 1; n < N; n = n+n) {
        for (int i = 0; i < N-n; i += n+n) {
            int lo = i;
            int m  = i+n-1;
            int hi = Math.min(i+n+n-1, N-1);
            merge(a, aux, lo, m, hi, comparator);
        }
    }
}
// is v < w ?
private static boolean less(Comparator<Point> comparator, Point v, Point w) {
    return comparator.compare(v, w) < 0;
}


Brute Force
public static void main(String[] args) {
    // Rescale the coordinate system.
    StdDraw.setXscale(0, 32768);
    StdDraw.setYscale(0, 32768);
    // Read points from the input file.
    In in = new In(args[0]);
    int pointsCount = in.readInt();
    Point[] points = new Point[pointsCount];
    for (int i = 0; i < pointsCount; i++) {
        int x = in.readInt();
        int y = in.readInt();
        points[i] = new Point(x, y);
        points[i].draw();
    }
    // Go each 4 points and check whether they all lie on the same line segment.
    for (int p = 0; p < pointsCount; p++) {
        for (int q = p + 1; q < pointsCount; q++) {
            double slopeToQ = points[p].slopeTo(points[q]);
            for (int r = q + 1; r < pointsCount; r++) {
                double slopeToR = points[p].slopeTo(points[r]);
                if (slopeToQ == slopeToR) {
                    for (int s = r + 1; s < pointsCount; s++) {
                        double slopeToS = points[p].slopeTo(points[s]);
                        if (slopeToQ == slopeToS) {
                            // Create the list of collinear points and sort them.
                            List<Point> collinearPoints = new ArrayList<Point>(4);
                            collinearPoints.add(points[p]);
                            collinearPoints.add(points[q]);
                            collinearPoints.add(points[r]);
                            collinearPoints.add(points[s]);
                            Collections.sort(collinearPoints);
                            // Display collinear points.
                            for (int i = 0; i < 3; i++) {
                                StdOut.print(collinearPoints.get(i));
                                StdOut.print(" -> ");
                            }
                            StdOut.println(Collections.max(collinearPoints));
                            Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));
                        }
                    }
                }
            }
        }
    }
}


public class Point implements Comparable<Point> {

    // compare points by slope
    public final Comparator<Point> SLOPE_ORDER = new Comparator<Point>() {
        public int compare(Point o1, Point o2) {
            double slope1 = slopeTo(o1);
            double slope2 = slopeTo(o2);
            if (slope1 == slope2) {
                return 0;
            }
            if (slope1 < slope2) {
                return -1;
            }
            return 1;
        }
    };

    private final int x;                              // x coordinate
    private final int y;                              // y coordinate

    // create the point (x, y)
    public Point(int x, int y) {
        /* DO NOT MODIFY */
        this.x = x;
        this.y = y;
    }

    // plot this point to standard drawing
    public void draw() {
        /* DO NOT MODIFY */
        StdDraw.point(x, y);
    }

    // draw line between this point and that point to standard drawing
    public void drawTo(Point that) {
        /* DO NOT MODIFY */
        StdDraw.line(this.x, this.y, that.x, that.y);
    }

    // slope between this point and that point
    public double slopeTo(Point that) {
        if (that == null) {
            throw new NullPointerException();
        }
        if (that.x == x) {
            if (that.y == y) {
                return Double.NEGATIVE_INFINITY;
            }
            return Double.POSITIVE_INFINITY;
        }
        if (that.y == y) {
            return 0.0;
        }
        return (double) (that.y - this.y) / (that.x - this.x);
    }

    // is this point lexicographically smaller than that one?
    // comparing y-coordinates and breaking ties by x-coordinates
    public int compareTo(Point that) {
        if (y == that.y && x == that.x) {
            return 0;
        }
        if (y < that.y || (y == that.y && x < that.x)) {
            return -1;
        }
        return 1;
    }

    // return string representation of this point
    public String toString() {
        /* DO NOT MODIFY */
        return "(" + x + ", " + y + ")";
    }
}
http://blog.csdn.net/liuweiran900217/article/details/19285111
slopeTo类相当于来计算两点间连线的斜率了。初中数学我们就知道,有如下几种情况。
(1)两个点的y坐标相同,即连线与x轴平行。这种情况的斜率为0。但是我们要注意一个问题,在Java中实际上有两种0,即+0和-0,并且Java内置的比较函数认为+0>-0。这是怎么来的呢?在题目的CheckList中已经给出了相关的介绍,我们放在这里供大家参考:
What does it mean for slopeTo() to return positive zero?Java (and the IEEE 754 floating-point standard) define two representations of zero: negative zero and positive zero.
double a = 1.0;
double x = (a - a) /  a;   // positive zero ( 0.0)
double y = (a - a) / -a;   // negative zero (-0.0)
Note that while (x == y) is guaranteed to be true,Arrays.sort() treatsnegative zero as strictly less than positive zero.Thus, to make the specification precise, we require you to return positive zero for horizontal line segments.Unless your program casts to the wrapper type Double (either explicitly or via autoboxing),you probably will not notice any difference in behavior;but, if your program does cast to the wrapper type and fails only on (some) horizontal line segments, this may bethe cause.
(2)两个点的x坐标相同,即连线与y轴平行。根据题目要求,我们要把这种斜率定义为正无穷大。在Java中,Double类给出了双精度浮点数正无穷大的表示,为Double.POSITIVE_INFINITY,因此用这个值代表正无穷大即可。
(3)两个点相同。这是一个极为特殊的情况,在CheckList中也有过说明,内容如下:
Can the same point appear more than once as input to Brute or Fast?You may assume the input to Bruteand Fast are N distinct points.Nevertheless, the methods implemented as part of the Point data typemust correctly handle the case when the points are not distinct:for the slopeTo() method, this requirement is explicitly stated in the API;for the comparison methods, this requirement is implict in the contracts for Comparable andComparator.
对于这种情况,我的处理方法是将其结果设置为负无穷大,即Double.NEGATIVE_INFINITY。
(4)其他一般情况。这种情况下,我们直接计算斜率即可,计算公式很简单,为:(y_1 - y_0) / (x_1 - x_0)。不过注意到点的坐标表示是int,斜率为double,因此我们还需要一个强制转换来保证计算的精度。

compareTo()

这个类的实现也很容易,直接按照题目要求来实现即可。当y_0 < y_1或者当y_0 = y_1且x_0 < x_1时,返回-1。

SLOPE_ORDER

这个类的实现也很容易,分别计算两个点对于第三个点的斜率(调用slopeTo()),然后返回两个结果的比较值即可。因为在slopeTo()中我们已经处理过了3种特殊的情况,因此直接返回比较值就是正确的结果。
 private static void FastMethod(Point[] pointArray){
  int N = pointArray.length;
  for (int i=0; i<N; i++){
   Point origPoint = pointArray[i];
   Point[] otherPoint = new Point[N-1];
   for (int j=0; j<pointArray.length; j++){
    if (j < i) otherPoint[j] = pointArray[j];
    if (j > i) otherPoint[j-1] = pointArray[j];
   }
   Arrays.sort(otherPoint, origPoint.SLOPE_ORDER);
   
   int count = 0;
   int index = 0;
   double tempSlope = origPoint.slopeTo(otherPoint[0]);
   for (int j=0; j<otherPoint.length;j++){
    if (Double.compare(origPoint.slopeTo(otherPoint[j]),  tempSlope) == 0){
     count++;
     continue;
    }else{
     if (count >=3){
      if (otherPoint[index].compareTo(origPoint) >=0){
       StdOut.print(origPoint + " -> ");
       for (int k=index; k<j-1; k++){
        StdOut.print(otherPoint[k] + " -> ");
       }
       StdOut.println(otherPoint[j-1]);
       origPoint.drawTo(otherPoint[j-1]);
      }
     }
     count = 1;
     index = j;
     tempSlope = origPoint.slopeTo(otherPoint[j]);
    }
   }
   if (count >= 3){
    if (otherPoint[index].compareTo(origPoint) >= 0){
     StdOut.print(origPoint + " -> ");
     for (int k=index; k<otherPoint.length - 1; k++){
      StdOut.print(otherPoint[k] + " -> ");
     }
     StdOut.println(otherPoint[otherPoint.length-1]);
     origPoint.drawTo(otherPoint[otherPoint.length-1]);
    }
   }
  }
  StdDraw.show(0);
 }
作业说明中对核心算法的描述非常清晰,应当特别小心的技术点(浮点误差、正负零等等)也都在checklist中予以强调,因而实现难度不算很大,其中使用了Java的Comparable与Comparator,排序过程调用Arrays.sort(),详细思考问题理清关系后,实现非常自然,前提是编程基本功必须扎实。
值得提到的点:
  • checklist鼓励初学者开始编写快速算法时先不要担心5个或以上的点共线的情况,而实际上对基本功扎实的同学,从开始便考虑这个问题更为合适;
  • checklist提到compare()和FastCollinearPoints类可以完全避免浮点数用整形运算实现,我想到的唯一符合要求(Point.java注释中规定不得依赖toString())的方法是,对Point类的compareTo()方法返回值增加意义(不单纯返回正负1),以获取两点的坐标之差(因题目给定坐标取值范围0-32767,可在返回值低两位字节存储x坐标差, 高两位字节存储y坐标差),再利用坐标差判断斜率是否相等。虽依然完全符合题目要求,但已有一点奇技淫巧之嫌,并且不一定能够通过autograder(评分时会替换Point类去测试FastCollinearPoints),不多讨论。(更新:此方法已确定违反FastCollinearPoints的API。)

No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (637) to-do (598) Review (340) Classic Algorithm (334) Classic Interview (299) Dynamic Programming (263) Google Interview (234) LeetCode - Review (229) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) List (58) Binary Tree (56) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Trie (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts