Saturday, June 4, 2016

Seam Carving - Princeton Part II - Programming Assignment 2


http://coursera.cs.princeton.edu/algs4/assignments/seamCarving.html
Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row. (A horizontal seam is a path of pixels connected from the left to the right with one pixel in each column.) Below left is the original 505-by-287 pixel image; below right is the result after removing 150 vertical seams, resulting in a 30% narrower image. Unlike standard content-agnostic resizing techniques (e.g. cropping and scaling), the most interesting features (aspect ratio, set of objects present, etc.) of the image are preserved.
As you'll soon see, the underlying algorithm is quite simple and elegant. Despite this fact, this technique was not discovered until 2007 by Shai Avidan and Ariel Shamir. It is now a feature in Adobe Photoshop (thanks to a Princeton graduate student), as well as other popular computer graphics applications.

 
In this assignment, you will create a data type that resizes a W-by-H image using the seam-carving technique.
  1. Energy calculation. The first step is to calculate the energy of each pixel, which is a measure of the importance of each pixel—the higher the energy, the less likely that the pixel will be included as part of a seam (as we'll see in the next step). In this assignment, you will implement the dual-gradient energy function, which is described below. Here is the dual-gradient energy function of the surfing image above:
    Dr. Hug as energy
    The energy is high (white) for pixels in the image where there is a rapid color gradient (such as the boundary between the sea and sky and the boundary between the surfing Josh Hug on the left and the ocean behind him). The seam-carving technique avoids removing such high-energy pixels.

  2. Seam identification. The next step is to find a vertical seam of minimum total energy. This is similar to the classic shortest path problem in an edge-weighted digraph except for the following:

    • The weights are on the vertices instead of the edges.
    • We want to find the shortest path from any of the W pixels in the top row to any of the W pixels in the bottom row.
    • The digraph is acyclic, where there is a downward edge from pixel (xy) to pixels (x − 1, y + 1), (xy + 1), and (x + 1, y + 1), assuming that the coordinates are in the prescribed range.

    Vertical Seam

  3. Seam removal. The final step is to remove from the image all of the pixels along the seam.
The SeamCarver API. Your task is to implement the following mutable data type:
public class SeamCarver {
   public SeamCarver(Picture picture)                // create a seam carver object based on the given picture
   public Picture picture()                          // current picture
   public     int width()                            // width of current picture
   public     int height()                           // height of current picture
   public  double energy(int x, int y)               // energy of pixel at column x and row y
   public   int[] findHorizontalSeam()               // sequence of indices for horizontal seam
   public   int[] findVerticalSeam()                 // sequence of indices for vertical seam
   public    void removeHorizontalSeam(int[] seam)   // remove horizontal seam from current picture
   public    void removeVerticalSeam(int[] seam)     // remove vertical seam from current picture
}
  • Computing the energy of a pixel. You will use the dual-gradient energy function: The energy of pixel (x,y) is Δx2(x,y)+Δy2(x,y), where the square of the x-gradient Δx2(x,y)=Rx(x,y)2+Gx(x,y)2+Bx(x,y)2, and where the central differences Rx(x,y)Gx(x,y), and Bx(x,y) are the differences in the red, green, and blue components between pixel (x + 1, y) and pixel (x − 1, y), respectively. The square of the y-gradient Δy2(x,y) is defined in an analogous manner. We define the energy of a pixel at the border of the image to be 1000, so that it is strictly larger than the energy of any interior pixel.As an example, consider the 3-by-4 image (supplied as 3x4.png) with RGB values—each component is an integer between 0 and 255—as shown in the table below:

    RGB values and dual-gradient energies of a 3-by-4 image
    The ten border pixels have energy 1000. Only the pixels (1, 1) and (1, 2) are nontrivial. We calculate the energy of pixel (1, 2) in detail:
    Rx(1, 2) = 255 − 255 = 0,
    Gx(1, 2) = 205 − 203 = 2,
    Bx(1, 2) = 255 − 51 = 204,
    yielding Δx2(1, 2) = 22 + 2042 = 41620.
    Ry(1, 2) = 255 − 255 = 0,
    Gy(1, 2) = 255 − 153 = 102,
    By(1, 2) = 153 − 153 = 0,
    yielding Δy2(1, 2) = 1022 = 10404.

    Thus, the energy of pixel (1, 2) is 41620+10404=52024. Similarly, the energy of pixel (1, 1) is 2042+1032=52225
  • Finding a vertical seam. The findVerticalSeam() method returns an array of length H such that entry y is the column number of the pixel to be removed from row y of the image. For example, the dual-gradient energies of a 6-by-5 image (supplied as 6x5.png).
    dual-gradient energies and a minimum vertical seam for a 6-by-5 image
    The minimum energy vertical seam is highlighted in blue. In this case, the method findVerticalSeam() returns the array { 3, 4, 3, 2, 2 } because the pixels in a minimum energy vertical seam are (3, 0), (4, 1), (3, 2), (2, 3), and (2, 4). When there are multiple vertical seams with minimal total energy, your method can return any such seam.
  • Finding a horizontal seam. The behavior of findHorizontalSeam() is analogous to that of findVerticalSeam() except that it returns an array of length W such that entry x is the row number of the pixel to be removed from column x of the image. For the 6-by-5 image, the method findHorizontalSeam() returns the array { 2, 2, 1, 2, 1, 2 } because the pixels in a minimum energy horizontal seam are (0, 2), (1, 2), (2, 1), (3, 2), (4, 1), and (5, 2).

    dual-gradient energies and a minimum horizontal seam for a 6-by-5 image
  • Performance requirements. The width()height(), and energy() methods should take constant time in the worst case. All other methods should run in time at most proportional to W H in the worst case. For faster performance, do not construct explicit DirectedEdge and EdgeWeightedDigraph objects.
https://github.com/nastra/AlgorithmsPartII-Princeton/tree/master/seamCarving
http://nifty.stanford.edu/2015/hug-seam-carving/
https://segmentfault.com/a/1190000005345079
作业中值得提到的点其实不多,大部分功能的实现都非常直接,中间加入了一点图像处理的入门知识,同样也非常好理解,重点是最短路径的BFS:
  • 对于固定值边界的处理比较繁琐,需要仔细处理;
  • 对很多图像处理问题,虽处理对象大体上还符合“图”的定义,但因为很多图像固有的因素,会将问题简化得多,不必再使用重量级的Digraph类,就事论事地解决问题即可;
  • 要找到能量最小的seam需要对整个图像计算路径距离,我的做法是维护distTo(最近距离)和edgeTo(最近距离对应“父节点”)两个数组,遍历全图后在最后一行(列)找到distTo的最小值即为所求seam的尾元素,通过追踪edgeTo即可得到所求seam。
  • energy的复用是一个小难点,需要认真考虑每移除一列或一行seam后,哪些情况下的点应该被重新计算,参考作业说明的vertical-seam.png、horizontal-seam.png或下图去分析,可能会有帮助:
  • 我想到的转置的目的是为了在纵横两个方向都能利用System.arraycopy()的高效,开始时我没有做这项优化,是手写了removeHorizontalSeam()的这个过程,因已达到了满分要求便没有再优化。
https://blog.niallconnaughton.com/2015/11/21/image-resizing-with-seam-carving/
Seam carving achieves this by identifying the “energy” of each pixel, which is a measurement of the how important to the image the detail of each pixel is. It then identifies horizontal or vertical seams through the image and removes the seam with the least total energy. The seams don’t have to be straight lines, allowing the algorithm to remove paths of low detail pixels that follow the shape of the image.

Colour gradients – a simple measurement of pixel energy

The energy function used will determine the results of the resize. It’s easy to imagine customised energy functions to suit certain types of images. A general purpose approach is to use the rate of colour change around a pixel, and this is the one used in the Algorithms II assignment. The idea is that areas of an image with very little variation in colour have less detail and so are better candidates for removal when resizing.
Below is an example showing the energy of a photo and the lowest energy vertical seam that would be removed from the image. The highest energy parts of the photo are the edges between the rocks and water, and the hills and skyline. The detail in the water and rocks does have some energy, but on the whole I was surprised that so much of the photo has low energy, given the level of detail we perceive with our eyes. Presumably this is what allows Jpeg compression to be so effective.
The implementation can be seen as a graph algorithm on a weighted directed acyclic graph. Each pixel contributes energy to the three pixels immediately below it. As pixels only contribute energy downwards, there are no cycles in the graph. By finding the shortest weighted path from the top row to the bottom row, you find the vertical seam with the least energy. This is the topological order approach to shortest paths in a weighted DAG. After identifying the minimal seam, its pixels are removed and the process is repeated.
There are some improvements that could be made to the approach. In their videos and papers, the original creators refer to this approach as “backwards energy”, meaning looking at the image as it was and then removing a seam. This can lead to bringing together two sharp edges that end up having significantly increased energy, which you see in the image as artefacts in lines and edges. They propose using “forwards energy” which takes into account the impact on the image if this seam were to be removed. From my examples, I think this would reduce the artefacts significantly, but I haven’t had time to try it.
Another possibility that occurred to me was anti-aliasing high detail sections along seams that were removed. This may help smooth/soften harsh changes visible when the seam crosses edges in the image, like a horizon line. Although possibly it could cause more trouble than it solves if it results in large areas of the image being blurred over – I haven’t had time to test this either.

https://github.com/zhichaoh/Coursera-Algorithms/blob/master/src/SeamCarver.java
public class SeamCarver {

private Picture pic;

private double[][] energy;

public SeamCarver(Picture picture) {
pic = new Picture(picture);
energy = new double[pic.height()][pic.width()];
}

public Picture picture() {
// current picture
return pic;
}

public int width() {
// width of current picture
return pic.width();
}

public int height() {
// height of current picture
return pic.height();
}

public double energy(int x, int y) throws IndexOutOfBoundsException {
// energy of pixel at column x and row y
if (x < 0 || y < 0 || x >= pic.width() || y >= pic.height())
throw new IndexOutOfBoundsException();
else if (x == 0 || y == 0 || x == pic.width() - 1
|| y == pic.height() - 1)
return 195075.0;
else {
Color xp1y = pic.get(x + 1, y);
Color xn1y = pic.get(x - 1, y);
Color xyp1 = pic.get(x, y + 1);
Color xyn1 = pic.get(x, y - 1);
double detX = (xn1y.getRed() - xp1y.getRed())
* (xn1y.getRed() - xp1y.getRed())
+ (xn1y.getBlue() - xp1y.getBlue())
* (xn1y.getBlue() - xp1y.getBlue())
+ (xn1y.getGreen() - xp1y.getGreen())
* (xn1y.getGreen() - xp1y.getGreen());
double detY = (xyn1.getRed() - xyp1.getRed())
* (xyn1.getRed() - xyp1.getRed())
+ (xyn1.getBlue() - xyp1.getBlue())
* (xyn1.getBlue() - xyp1.getBlue())
+ (xyn1.getGreen() - xyp1.getGreen())
* (xyn1.getGreen() - xyp1.getGreen());
return detX + detY;
}
}

private void dfsMinPath(int x, int y, double[][] sumEnergy,
double[][] energy, int[][] steps, boolean horizontal) {
if ((horizontal && x == pic.width() - 1)
|| (!horizontal && y == pic.height() - 1)) {
sumEnergy[y][x] = energy[y][x];
steps[y][x] = -1;
return;
}
double minPath = Double.MAX_VALUE;
int bestMv = 0;
for (int mv = -1; mv <= 1; mv++) {
if (horizontal) {
int py = y + mv;
if (py >= pic.height() || py < 0)
continue;
if (steps[py][x + 1] == 0)
dfsMinPath(x + 1, py, sumEnergy, energy, steps, horizontal);
if (sumEnergy[py][x + 1] < minPath) {
minPath = sumEnergy[py][x + 1];
bestMv = py;
}
} else {
int px = x + mv;
if (px >= pic.width() || px < 0)
continue;
if (steps[y + 1][px] == 0)
dfsMinPath(px, y + 1, sumEnergy, energy, steps, horizontal);
if (sumEnergy[y + 1][px] < minPath) {
minPath = sumEnergy[y + 1][px];
bestMv = px;
}
}
}
steps[y][x] = bestMv;
sumEnergy[y][x] = energy[y][x] + minPath;
}

private void calSumEnergy() {
for (int j = 0; j < pic.height(); j++)
for (int i = 0; i < pic.width(); i++) {
energy[j][i] = this.energy(i, j);
}
}

public int[] findHorizontalSeam() {
// sequence of indices for horizontal seam
int[][] steps = new int[pic.height()][pic.width()];
double[][] sumEnergy = new double[pic.height()][pic.width()];
this.calSumEnergy();
for (int y = 0; y < this.height(); y++)
this.dfsMinPath(0, y, sumEnergy, energy, steps, true);
int[] ht = new int[pic.width()];
double bestEnergy = Double.MAX_VALUE;
for (int y = 0; y < this.height(); y++) {
if (sumEnergy[y][0] < bestEnergy) {
bestEnergy = sumEnergy[y][0];
ht[0] = y;
}
}
for (int x = 1; x < this.width(); x++) {
ht[x] = steps[ht[x - 1]][x - 1];
}
return ht;
}

public int[] findVerticalSeam() {
// sequence of indices for vertical seam
int[][] steps = new int[pic.height()][pic.width()];
double[][] sumEnergy = new double[pic.height()][pic.width()];
this.calSumEnergy();
for (int x = 0; x < this.width(); x++)
this.dfsMinPath(x, 0, sumEnergy, energy, steps, false);
int[] ht = new int[pic.height()];
double bestEnergy = Double.MAX_VALUE;
for (int x = 0; x < this.width(); x++) {
if (sumEnergy[0][x] < bestEnergy) {
bestEnergy = sumEnergy[0][x];
ht[0] = x;
}
}
for (int y = 1; y < this.height(); y++)
ht[y] = steps[y - 1][ht[y - 1]];
return ht;
}

public void removeHorizontalSeam(int[] a) throws IllegalArgumentException {
// remove horizontal seam from picture
if (a.length != pic.width())
throw new IllegalArgumentException();
Picture cPic = new Picture(pic.width(), pic.height() - 1);
for (int i = 0; i < pic.width(); i++) {
for (int j = 0; j < pic.height(); j++) {
if (j == a[i])
continue;
int pt = j;
if (pt > a[i])
pt--;
cPic.set(i, pt, this.pic.get(i, j));
}
}
this.pic = cPic;
}

public void removeVerticalSeam(int[] a) throws IllegalArgumentException {
// remove vertical seam from picture
if (a.length != pic.height())
throw new IllegalArgumentException();
Picture cPic = new Picture(pic.width() - 1, pic.height());
for (int j = 0; j < pic.height(); j++) {
for (int i = 0; i < pic.width(); i++) {
if (i == a[j])
continue;
int pt = i;
if (pt > a[j])
pt--;
cPic.set(pt, j, pic.get(i, j));
}
}
this.pic = cPic;
}
}

No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (632) to-do (596) Classic Algorithm (334) Review (330) Classic Interview (299) Dynamic Programming (263) Google Interview (229) LeetCode - Review (224) 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) Interview Corner (61) Greedy Algorithm (60) List (58) Binary Tree (56) DFS (54) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (44) 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) prismoskills (33) Segment Tree (32) Space Optimization (32) Trie (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) 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) Time Complexity (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) 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) Sweep Line (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) 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) Master Theorem (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