Tuesday, December 1, 2015

第三十二章、最小操作数 - 程序员编程艺术


https://github.com/tdoly/The-Art-Of-Programming-by-July/blob/master/ebook/zh/32.0.md
http://blog.csdn.net/v_july_v/article/details/9921437

题目详情如下:

给定一个单词集合Dict,其中每个单词的长度都相同。现从此单词集合Dict中抽取两个单词A、B,我们希望通过若干次操作把单词A变成单词B,每次操作可以改变单词的一个字母,同时,新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。
举个例子如下:
Given:
   A = "hit"
   B = "cog"
   Dict = ["hot","dot","dog","lot","log"]
Return
 [
   ["hit","hot","dot","dog","cog"],
   ["hit","hot","lot","log","cog"]
 ]
即把字符串A = "hit"转变成字符串B = "cog",有以下两种可能:
"hit" -> "hot" -> "dot" -> "dog" -> "cog";
"hit" -> "hot" -> "lot" -> "log" ->"cog"。
详解:本题是一个典型的图搜索算法问题。此题看似跟本系列的第29章的字符串编辑距离相似,但其实区别特别大,原因是最短编辑距离是让某个单词增加一个字符或减少一个字符或修改一个字符达到目标单词,来求变换的最少次数,但此最小操作数问题就只是改变一个字符。
通过此文:http://blog.csdn.net/v_JULY_v/article/details/6111353,我们知道,在图搜索算法中,有深度优先遍历DFS和广度优先遍历BFS,而题目中并没有给定图,所以需要我们自己建立图。
涉及到图就有这么几个问题要思考,节点是什么?边如何建立?图是有方向的还是无方向的?包括建好图之后,如何记录单词序列等等都是我们要考虑的问题。

解法一、单向BFS法

1、建图
对于本题,我们的图的节点就是字典里的单词,两个节点有连边,对应着我们可以把一个单词按照规则变为另外一个单词。比如我们有单词hat,它应该与单词cat有一条连边,因为我们可以把h变为c,反过来我们也可以把c变为h,所以我们建立的连边应该是无向的。
如何建图?有两种办法,
  • 第一种方法是:我们可以把字典里的任意两个单词,通过循环判断一下这两个单词是否只有一个位置上的字母不同。即假设字典里有n个单词,我们遍历任意两个单词的复杂度是O(n2),如果每个单词长度为length,我们判断两个单词是否连边的复杂度是O(length),所以这个建图的总复杂度是O(n2*length)。但当n比较大时,这个复杂度非常高,有没有更好的方法呢?
  • 第二种方法是:我们把字典里地每个单词的每个位置的字母修改一下,从字典里查找一下(若用基于red-black tree的map查找,其查找复杂度为O(logn),若用基于hashmap的unordered_map,则查找复杂度为O(1)),修改后的单词是否在字典里出现过。即我们需要遍历字典里地每一个单词O(n),尝试修改每个位置的每个字母,对每个位置我们需要尝试26个字母(其实是25个,因为要改得和原来不同),因此这部分复杂度是O(26*length),总复杂度是O(26 * n * length) (第二种方法优化版:这第二种方法能否更优?在第二种方法中,我们对每个单词每个位置尝试了26次修改,事实上我们可以利用图是无向的这一特点,我们对每个位置试图把该位置的字母变到字典序更大的字母。例如,我们只考虑cat变成hat,而不考虑hat变成cat,因为再之前已经把无向边建立了。这样,只进行一半的修改次数,从而减少程序的运行时间。当然这个优化从复杂度上来讲是常数的,因此称为常数优化,此虽算是一种改进,但不足以成为第三种方法,原因是我们经常忽略O背后隐藏的常数)。
OK,上面两种方法孰优孰劣呢?直接比较n2*length 与 26 * n * length的大小。很明显,通常情况下,字典里的单词个数非常多,也就是n比较大,因此第二种方法效果会好一些,稍后的参考代码也会选择上述第二种方法的优化。
2、记录单词序列
对于最简单的bfs,我们是如何记录路径的?如果只需要记录一条最短路径的话,我们可以对每个走到的位置,记录走到它的前一个位置。这样到终点后,我们可以不断找到它的前一个位置。我们利用了最短路径的一个特点:即第二次经过一个节点的时候,路径长度不比第一次经过它时短。因此这样的路径是没有圈的。
但是本题需要记录全部的路径,我们第二次经过一个节点时,路径长度可能会和第一次经过一个节点时路径长度一样。这是因为,我们可能在第i层中有多个节点可以到达第(i + 1)层的同一个位置,这样那个位置有多条路径都是最短路径。
如何解决呢?——我们记录经过这个位置的前面所有位置的集合。这样一个节点的前驱不是一个节点,而是一个节点的集合。如此,当我们第二次经过一个第(i+ 1)层的位置时,我们便保留前面那第i层位置的集合作为前驱。
3、遍历
解决了以上两个问题,我们最终得到的是什么?如果有解的话,我们最终得到的是从终点开始的前一个可能单词的集合,对每个单词,我们都有能得到它的上一个单词的集合,直到起点。这就是bfs分层之后的图,我们从终点开始遍历这个图的到起点的所有路径,就得到了所有的解,这个遍历我们可以采用之前介绍的dfs方法(路径的数目可能非常多)。
其实,为了简单起见,我们可以从终点开始bfs,因为记录路径记录的是之前的节点,也就是反向的。这样最终可以按顺序从起点遍历到终点的所有路径。
参考代码如下:
//copyright@caopengcs     
//updated@July 08/12/2013    
class Solution    
{    
public:    
    // help 函数负责找到所有的路径    
    void help(intx,vector<int> &d, vector<string> &word,vector<vector<int> > &next,vector<string> &path,vector<vector<string> > &answer) {    
        path.push_back(word[x]);    
        if (d[x] == 0) {   //已经达到终点了    
            answer.push_back(path);    
        }    
        else {    
            int i;    
            for (i = 0; i <next[x].size(); ++i) {    
                help(next[x][i],d, word, next,path,answer);    
            }    
        }    
        path.pop_back();   //回溯    
    }    

    vector<vector<string>> findLadders(string start, string end, set<string>& dict)    
    {    

        vector<vector<string> > answer;    
        if (start == end) {   //起点终点恰好相等    
            return answer;    
        }    
        //把起点终点加入字典的map    
        dict.insert(start);    
        dict.insert(end);    
        set<string>::iterator dt;    
        vector<string> word;    
        map<string,int>allword;    
        //把set转换为map,这样每个单词都有编号了。    
        for (dt = dict.begin(); dt!= dict.end(); ++dt) {    
            word.push_back(*dt);    
            allword.insert(make_pair(*dt, allword.size()));    
        }    

        //建立连边 邻接表    
        vector<vector<int> > con;    
        int i,j,n =word.size(),temp,len = word[0].length();    
        con.resize(n);    
        for (i = 0; i < n; ++i){    
            for (j = 0; j <len; ++j) {    
                char c;    
                for (c =word[i][j] + 1; c <= 'z'; ++c) {  //根据上面第二种方法的优化版的思路,让每个单词每个位置变更大    
                    char last =word[i][j];    
                    word[i][j] =c;    
                    map<string,int>::iterator t = allword.find(word[i]);    
                    if (t !=allword.end()) {    
                        con[i].push_back(t->second);    
                        con[t->second].push_back(i);    
                    }    
                    word[i][j] =last;    
                }    
            }    

        }    

        //以下是标准bfs过程    
        queue<int> q;    
        vector<int> d;    
        d.resize(n, -1);    
        int from = allword[start],to = allword[end];    
        d[to] = 0;  //d记录的是路径长度,-1表示没经过    
        q.push(to);    
        vector<vector<int> > next;    
        next.resize(n);    
        while (!q.empty()) {    
            int x = q.front(), now= d[x] + 1;    
            //now相当于路径长度  
            //当now > d[from]时,则表示所有解都找到了  
            if ((d[from] >= 0)&& (now > d[from])) {    
                break;    
            }    
            q.pop();    
            for (i = 0; i <con[x].size(); ++i) {    
                int y = con[x][i];    
                //第一次经过y  
                if (d[y] < 0) {      
                    d[y] = now;    
                    q.push(y);    
                    next[y].push_back(x);    
                }    
                //非第一次经过y  
                else if (d[y] ==now) {  //是从上一层经过的,所以要保存    
                    next[y].push_back(x);    
                }    

            }    
        }    
        if (d[from] >= 0) {  //有解    
            vector<string>path;    
            help(from, d,word,next, path,answer);    
        }    
        return answer;    
    }    
};

解法二、双向BFS法

BFS需要把每一步搜到的节点都存下来,很有可能每一步的搜到的节点个数越来越多,但最后的目的节点却只有一个。后半段的很多搜索都是白耗时间了。
上面给出了单向BFS的解法,但看过此前blog中的这篇文章“A*、Dijkstra、BFS算法性能比较演示”可知:http://blog.csdn.net/v_JULY_v/article/details/6238029,双向BFS性能优于单向BFS。
举个例子如下,第1步,是起点,1个节点,第2步,搜到2个节点,第3步,搜到4个节点,第4步搜到8个节点,第5步搜到16个节点,并且有一个是终点。那这里共出现了31个节点。从起点开始广搜的同时也从终点开始广搜,就有可能在两头各第3步,就相遇了,出现的节点数不超过(1+2+4)*2=14个,如此就节省了一半以上的搜索时间。
下面给出双向BFS的解法,参考代码如下:
//copyright@fuwutu 6/26/2013  
class Solution  
{  
public:  
    vector<vector<string>> findLadders(string start, string end, set<string>& dict)  
    {  
        vector<vector<string>> result, result_temp;  
        if (dict.erase(start) == 1 && dict.erase(end) == 1)   
        {  
            map<string, vector<string>> kids_from_start;  
            map<string, vector<string>> kids_from_end;  

            set<string> reach_start;  
            reach_start.insert(start);  
            set<string> reach_end;  
            reach_end.insert(end);  

            set<string> meet;  
            while (meet.empty() && !reach_start.empty() && !reach_end.empty())  
            {  
                if (reach_start.size() < reach_end.size())  
                {  
                    search_next_reach(reach_start, reach_end, meet, kids_from_start, dict);  
                }  
                else  
                {  
                    search_next_reach(reach_end, reach_start, meet, kids_from_end, dict);  
                }  
            }  

            if (!meet.empty())  
            {  
                for (set<string>::iterator it = meet.begin(); it != meet.end(); ++it)  
                {  
                    vector<string> words(1, *it);  
                    result.push_back(words);  
                }  

                walk(result, kids_from_start);  
                for (size_t i = 0; i < result.size(); ++i)  
                {  
                    reverse(result[i].begin(), result[i].end());  
                }  
                walk(result, kids_from_end);  
            }  
        }  

        return result;  
    }  

private:  
    void search_next_reach(set<string>& reach, const set<string>& other_reach, set<string>& meet, map<string, vector<string>>& path, set<string>& dict)  
    {  
        set<string> temp;  
        reach.swap(temp);  

        for (set<string>::iterator it = temp.begin(); it != temp.end(); ++it)  
        {  
            string s = *it;  
            for (size_t i = 0; i < s.length(); ++i)  
            {  
                char back = s[i];  
                for (s[i] = 'a'; s[i] <= 'z'; ++s[i])  
                {  
                    if (s[i] != back)  
                    {  
                        if (reach.count(s) == 1)  
                        {  
                            path[s].push_back(*it);  
                        }  
                        else if (dict.erase(s) == 1)  
                        {  
                            path[s].push_back(*it);  
                            reach.insert(s);  
                        }  
                        else if (other_reach.count(s) == 1)  
                        {  
                            path[s].push_back(*it);  
                            reach.insert(s);  
                            meet.insert(s);  
                        }  
                    }  
                }  
                s[i] = back;  
            }  
        }  
    }  

    void walk(vector<vector<string>>& all_path, map<string, vector<string>> kids)  
    {  
        vector<vector<string>> temp;  
        while (!kids[all_path.back().back()].empty())  
        {  
            all_path.swap(temp);  
            all_path.clear();  
            for (vector<vector<string>>::iterator it = temp.begin(); it != temp.end(); ++it)  
            {  
                vector<string>& one_path = *it;  
                vector<string>& p = kids[one_path.back()];  
                for (size_t i = 0; i < p.size(); ++i)  
                {  
                    all_path.push_back(one_path);  
                    all_path.back().push_back(p[i]);  
                }  
            }  
        }  
    }  
};  

参考链接及推荐阅读

  1. caopengcs,最小操作数:http://blog.csdn.net/caopengcs/article/details/9919341
  2. 编程艺术第29章字符串编辑距离:http://blog.csdn.net/v_july_v/article/details/8701148#t4
  3. matrix67,十个利用矩阵乘法解决的经典题目:http://www.matrix67.com/blog/archives/276
  4. leetcode上最小操作数一题:http://leetcode.com/onlinejudge#question_126
  5. 超然烟火,http://blog.csdn.net/sunnianzhong/article/details/9326289



No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (652) to-do (599) Review (360) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) 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) Binary Tree (58) List (58) 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) Jobdu (39) Interval (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) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Segment Tree (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 (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (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) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (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) Divide and Conquer (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) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (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) 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) Kadane’s Algorithm (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) 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) Parent-Only Tree (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