Sunday, October 16, 2016

LeetCode 424 - Longest Repeating Character Replacement


https://leetcode.com/problems/longest-repeating-character-replacement/
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

https://discuss.leetcode.com/topic/63471/java-sliding-window-easy-to-understand
The problem is similar to longest substring with most K distinct characte. But this time, the constraint is we can only have most K characters that is different with the most frequent character in the substring. For example in the sliding window:
"ABBBAC" most frequent character is B with count 3, all other character is count as different to B, 
    which is A and C, and the result is 2 + 1 = 3. 
Each time we count the different characters. If it is not bigger than k we extend the sliding window.
Since we only have 26 characters, keep the count in a integer array is good enough.
    public int characterReplacement(String s, int k) {
        if(s == null || s.length() == 0){
            return 0;
        }
        int max = 0;
        int[] ch = new int[26];
        char[] str = s.toCharArray();
        for(int i=0, j=0; i<s.length(); i++){
            while(j < s.length()){
                ch[str[j] - 'A']++;
                if(count(ch) > k){  //If exceed k, break
                    ch[str[j] - 'A']--;
                    break;
                }
                j++;
            }
            max = Math.max(max, j-i);
            ch[str[i] - 'A']--;
        }
        return max;
    }
    //Count the number of character that is different to the longest character
    public int count(int[] ch){
        int max = 0;
        int sum = 0;
        for(int val:ch){
            sum += val;
            max = Math.max(max, val);
        }
        return sum - max;
    }
https://discuss.leetcode.com/topic/63456/7-lines-c
The true meaning of his max_same is the window_size. (i.e. windows_size = max_same + k).
So it is all right that window_size never decreases since we are only interested in finding the biggest window.

https://discuss.leetcode.com/topic/63416/sliding-window-similar-to-finding-longest-substring-with-k-distinct-characters/5
The problem says that we can make at most k changes to the string (any character can be replaced with any other character). So, let's say there were no constraints like the k. Given a string convert it to a string with all same characters with minimal changes. The answer to this is
length of the entire string - number of times of the maximum occurring character in the string
Given this, we can apply the at most k changes constraint and maintain a sliding window such that
(length of substring - number of times of the maximum occurring character in the substring) <= k
    int characterReplacement(string s, int k) {
        vector<int> counts(26, 0);
        int start = 0;
        int maxCharCount = 0;
        int n = s.length();
        int result = 0;
        for(int end = 0; end < n; end++){
            counts[s[end]-'A']++;
            if(maxCharCount < counts[s[end]-'A']){
                maxCharCount = counts[s[end]-'A'];
            }
            while(end-start-maxCharCount+1 > k){
                counts[s[start]-'A']--;
                start++;
                for(int i = 0; i < 26; i++){
                    if(maxCharCount < counts[i]){
                        maxCharCount = counts[i];
                    }
                }
            }
            result = max(result, end-start+1);
        }
        return result;
    }

X.
http://bookshadow.com/weblog/2016/10/16/leetcode-longest-repeating-character-replacement/
定义一段区间内出现次数最多的字符为“优势字符”
维护有效区间[p1, p2],使得区间内除“优势字符”外的其余字符个数不大于k
时间复杂度O(m * n),其中m为字母个数, n为字符串长度
https://scottduan.gitbooks.io/leetcode-review/content/longest_repeating_character_replacement.html
Since we are only interested in the longest valid substring, our sliding windows need not shrink, even if a window may cover an invalid substring. We either grow the window by appending one char on the right, or shift the whole window to the right by one. And we only grow the window when the count of the new char exceeds the historical max count (from a previous window that covers a valid substring).
That is, we do not need the accurate max count of the current window; we only care if the max count exceeds the historical max count; and that can only happen because of the new char.
https://discuss.leetcode.com/topic/63494/java-12-lines-o-n-sliding-window-solution-with-explanation
There's no edge case for this question. The initial step is to extend the window to its limit, that is, the longest we can get to with maximum number of modifications. Until then the variable start will remain at 0.
Then as end increase, the whole substring from 0 to end will violate the rule, so we need to update start accordingly (slide the window). We move start to the right until the whole string satisfy the constraint again. Then each time we reach such situation, we update our max length.
The solution is great, but I have a small question here :
when you move the start pointer, why we the max count may change:
for example :
s = "bbcdef", k = 2.
when move end to 'e', we need to remove first 'b' so that maxcount will change to 1.
But for s = "bbcdd", it wont change when we move end to second 'd' and remove first 'b'.
In this question we may don't need to worry about that because we just need to get maxlength of substring. But what if the question is to find all the strategy, can we try to use similar method ?

when move the left begin of bmaxcount will not be change to 1.It will always the biggest one unless another one is more than it. That is why explain that
our sliding windows need not shrink, even if a window may cover an invalid substring
this situation it will shift the whole window to the right by one

  • We use a window.
  • The window starts at the left side of the string and the length of the window is initialized to zero.
  • The window only stays the same or grows in length as the algorithm proceeds.
  • The algorithm grows the window to the maximum valid length according to the rules of the game.
  • The algorithm returns the length of the window upon completion.
Setup:
  • The length of the window is defined by the following equation: end - start + 1.
  • The values of both start and end are subject to change during the execution of the algorithm.
  • The value of end starts at 0 and gets incremented by 1 with each execution of the loop.
  • But unless a certain condition is met, the value of start will also gets incremented with each execution of the loop, keeping the length of the window unchanged.
  • That condition is met when the number of the most commonly occuring character in the window + k is at least as large as the length of the window (the value of k determines how many of the less commonly occurring characters there can be). This condition would be required to create a string containing all the same characters from the characters contained within the window.
Execution:
  • Right in the beginning, the length of the window is going to be able to grow to at least the value of k.
  • After that initial growth, the algorithm becomes a search to find the window that contains the greatest number of reoccurring characters.
  • Whenever including the character at end results in an increase in the greatest number of reoccurring characters ever encountered in a window tested so far, the window grows by one (by not incrementing start).
  • When determining whether or not including another character at the end of the window results in the increase described above, only the occurrence of the newly included character in the window and the running all-time max need to be taken into account (after all, only the frequency of the newly included character is increasing).
  • Even if/when the value of start is incremented (i.e. the left side of the window is moved to the right), the all-time max doesn't need to be reset to reflect what's currently in the window because 1) at this point in the algorithm, the all-time maximum number of reoccurring characters in a window is what we're using to determine the all-time longest window; 

  • 2) we only care about positive developments in our search (i.e. we find a window that contains an even greater number of reoccurring characters than any other window we have tested so far and therefore is longer than any window we have tested so far). The algorithm becomes a search for the max and we only need to set the max when we have a new max.
public int characterReplacement(String s, int k)
{
    int[] count = new int[128];
    int max=0;
    int start=0;
    for(int end=0; end<s.length(); end++)
    {
        max = Math.max(max, ++count[s.charAt(end)]);
        if(max+k<=end-start)
            count[s.charAt(start++)]--;
    }
    return s.length()-start;//??
}
    public int characterReplacement(String s, int k) {
        int len = s.length();
        int[] count = new int[26];
        int start = 0, maxCount = 0, maxLength = 0;
        for (int end = 0; end < len; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
X.  https://discuss.leetcode.com/topic/63465/java-o-n-solution-using-sliding-window
http://blog.csdn.net/MebiuW/article/details/52830364
The idea is to find maximum valid substring with repeated character 'A' to 'Z' respectively. For each case, use sliding window to determine its maximum length, update the global maximum length if needed.
    public int characterReplacement(String s, int k) {
        int maxLen = 0;
        for(int l = 0 ; l<26;l++){
            char c = (char)('A' + l); //repeated char we are looking for
            int i = 0, j = 0, count = 0;
            while(j<s.length()){
                char cur = s.charAt(j);
                if(cur != c) count++;
                
                //make the substring valid again
                while(count > k){
                    if(s.charAt(i) != c) count--;
                    i++;
                }
                
                //update maximun len
                maxLen = Math.max(maxLen,j-i+1);
                j++;
            }
        }
        return maxLen;
    }
X. DFS http://brookebian.blogspot.com/2016/10/424-longest-repeating-character.html
   Set<Character> dict = new HashSet<>();  
   int max = 0;  
   public int characterReplacement(String s, int k) {  
     if(s.length() == 0) return 0;  
     for(int i = 0; i < s.length(); i++)  
       dict.add(s.charAt(i));  
     dfs(s.toCharArray(),k,new HashSet<>());  
     return max;  
   }  
   public void dfs(char[] chars,int k,Set<Integer> visited){  
     int[] count = count(String.valueOf(chars));  
     max = Math.max(count[count.length-1],max);  
     if(k == 0)  
       return;  
     for(int i = 0; i < chars.length; i++){  
       if(visited.contains(i))  
         continue;  
       char tmp = chars[i];  
       for(char c: dict){  
         if(c==tmp )  
           continue;  
         chars[i] = c;  
         visited.add(i);  
         dfs(chars,k-1,visited);  
         visited.remove(i);  
       }  
       chars[i] = tmp;  
     }  
     return ;  
   }  
   public int[] count(String s){  
     int[] count = new int[s.length()+1];  
     count[0]=1;  
     count[s.length()-1]=1;  
     int max = 1;  
     for(int i = 1; i < s.length(); i++){  
       count[i] = s.charAt(i) != s.charAt(i-1)? 1:count[i-1] + 1;  
       max = Math.max(max,count[i]);  
     }  
     for(int i = s.length()-2; i >= 0; i--){  
       if(s.charAt(i) == s.charAt(i+1))  
         count[i] = count[i+1];  
     }  
     count[s.length()]=max;  
     return count;  
   }  
   public int[] copy(int[] nums){  
     int n = nums.length;  
     int[] copy = new int[n];  
     for(int i = 0; i < n; i++){  
       copy[i] = nums[i];  
     }  
     return copy;  
   } 

http://bookshadow.com/weblog/2016/10/16/leetcode-longest-repeating-character-replacement/
解法II 统计单词连续区间 + 枚举字母 + 枚举区间起止点
时间复杂度O(m * n),其中m为字母个数, n为区间数
首先统计出字符串内各单词所在的连续区间,记为cdict,例如AABABBA得到的区间为{A : [(0, 1), (3, 3), (6, 6)], B : [(2, 2), (4, 5)]}
然后枚举需要保留的字母
尝试用k值填补区间之间的间隙,并更新最优答案。
def characterReplacement(self, s, k): """ :type s: str :type k: int :rtype: int """ sizes = len(s) letters = set(s) cdict = collections.defaultdict(list) li, lc = 0, (s[0] if s else None) for i, c in enumerate(s): if c != lc: cdict[lc].append( (li, i - 1) ) li, lc = i, c cdict[lc].append( (li, sizes - 1) ) ans = 0 for c in letters: invs = cdict[c] ans = max(ans, max(y - x + 1 + min(k, x + sizes - 1 - y) for x, y in invs)) sizec = len(invs) cnt = k sp = 0 ep = 1 while sp < sizec and ep < sizec: if cnt >= invs[ep][0] - invs[ep - 1][1] - 1: cnt -= invs[ep][0] - invs[ep - 1][1] - 1 lenc = invs[ep][1] - invs[sp][0] + 1 + min(cnt, invs[sp][0] + sizes - 1 - invs[ep][1]) ans = max(ans, lenc) ep += 1 else: sp += 1 cnt += invs[sp][0] - invs[sp - 1][1] - 1 return ans

http://www.cnblogs.com/EdwardLiu/p/6359777.html
give a string, all 1 or 0, we can flip a 0 to 1, find the longest 1 substring after the flipping
这是一个简单版本of LC 424 Longest Repeating Character Replacement
又是Window, 又是Two Pointers
Window还是采用每次都try to update left使得window valid, 每次都检查最大window
 5     public static int find2(String str) {
 6         if (str==null || str.length()==0) return 0;
 7         int l = 0, r = 0;
 8         int maxLen = 0;
 9         int countZero = 0;
10         for (r=0; r<str.length(); r++) {
11             if (str.charAt(r) == '0') countZero++;
12             while (countZero > 1 && l < str.length()) {
13                 if (str.charAt(l) == '0') countZero--;
14                 l++;
15             }
16             maxLen = Math.max(r-l+1, maxLen);
17         }
18         return maxLen;
19     }


No comments:

Post a Comment

Labels

GeeksforGeeks (1105) LeetCode (896) Algorithm (811) Review (634) to-do (616) LeetCode - Review (392) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (285) Google Interview (240) Tree (146) POJ (140) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (114) Lintcode (112) Cracking Coding Interview (110) Smart Algorithm (109) Math (103) HackerRank (89) Binary Search (78) Graph Algorithm (75) Greedy Algorithm (66) Binary Tree (65) Interview Corner (61) DFS (60) List (58) Codility (54) Algorithm Interview (53) Advanced Data Structure (52) BFS (52) ComProGuide (52) Geometry Algorithm (48) LeetCode - Extended (47) USACO (46) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Stack (41) Binary Search Tree (40) Interval (40) Jobdu (39) Knapsack (39) LeetCode - Phone (39) Recursive Algorithm (38) String Algorithm (38) Trie (38) Matrix (37) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Space Optimization (36) Backtracking (35) Beauty of Programming (35) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) 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) GeeksQuiz (25) Logic Thinking (25) Palindrome (25) hihocoder (25) Graph (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Company - LinkedIn (22) Hash (22) Queue (22) Binary Indexed Trees (21) DFS + Review (21) Pre-Sort (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) Follow Up (19) Lintcode - Review (19) Post-Order Traverse (19) UVA (19) Bisection Method (18) Probabilities (18) Company-Uber (17) Codercareer (16) Game Theory (16) Heap (16) Priority Quieue (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) O(N) (15) Ordered Stack (15) Number (14) Number Theory (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Binary Search - Bisection (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (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) Miscs (11) Princeton (11) Time Complexity (11) Tree DP (11) 挑战程序设计竞赛 (11) Coin Change (10) Company - Microsoft (10) Company-Airbnb (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) Two Pointers (10) X Sum (10) Divide and Conquer (9) LeetCode Hard (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Stack Overflow (9) Stock (9) System Design (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Bucket Sort (8) Company-Amazon (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) Longest Common Subsequence(LCS) (8) O(1) Space (8) Prime (8) Suffix Tree (8) Tech-Queries (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) Inversion (7) Level Order Traversal (7) Linked List (7) Math-Divisible (7) Minimum Spanning Tree (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+Cache (6) DFS+DP (6) DP - Tree (6) DP-Multiple Relation (6) Dutch Flag (6) How To (6) Interviewstreet (6) Kadane - Extended (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Manacher (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) TreeMap (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DP-Include vs Exclude (5) DP-Print Solution (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (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) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (4) Cycle (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) LeetCode - TODO (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) Spell Checker (4) Stock Maximize (4) Stream (4) Subset Sum (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (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) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (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) Sieve of Eratosthenes (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (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 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) Priority Queue (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (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) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (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 String (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) Cont Improvement (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) Diagonal (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) Machine Learning (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-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (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) ZOJ (1) ZigZag (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