Wednesday, September 7, 2016

LeetCode 394 - Decode String


https://leetcode.com/problems/decode-string/
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that kis guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

X.DFS
http://blog.csdn.net/qq508618087/article/details/52439114
思路: 一个DFS的题目, 给定的字符串可能会有嵌套很多层, 在每一层我们只要在碰到正常的字符就保存到当前层的结果中, 如果碰到数字就另外保存起来作为倍数, 碰到'[' 就进入下层递归, 碰到']' 就将当前层结果返回, 这样在返回给上层之后就可以用倍数加入到上层结果字符串中. 最终当所有层都完成之后就可以得到结果. 在不同层次的递归中, 我们可以维护一个共同的位置索引, 这样在下层递归完成之后上层可以知道已经运算到哪里了.
  1.     string DFS(string s, int &k)  
  2.     {  
  3.         string ans;  
  4.         int cnt = 0;  
  5.         while(k < s.size())  
  6.         {  
  7.             if(isdigit(s[k])) cnt = cnt*10 + (s[k++]-'0');  
  8.             else if(s[k]=='[')  
  9.             {  
  10.                 string tem = DFS(s, ++k);  
  11.                 for(int i = 0; i < cnt; i++) ans += tem;  
  12.                 cnt = 0;  
  13.             }  
  14.             else if(s[k]==']')  
  15.             {  
  16.                 k++;  
  17.                 return ans;  
  18.             }  
  19.             else ans += s[k++];  
  20.         }  
  21.         return ans;  
  22.     }  
  23.       
  24.     string decodeString(string s) {  
  25.         int k = 0;  
  26.         return DFS(s, k);  
  27.     }  
https://discuss.leetcode.com/topic/57318/java-simple-recursive-solution/3
    StringBuilder cur = new StringBuilder();
    int num = 0;
    for (int i = 0; i < s.length(); i++) {
        if (Character.isDigit(s.charAt(i))) {
            num = num * 10 + (s.charAt(i) - '0');
        } else if (s.charAt(i) == '[') {
            //find the matching ]
            int begin = i;
            i++;
            int count = 1; 
            while (count != 0) {
                if (s.charAt(i) == '[') {
                    count++;
                } else if (s.charAt(i) == ']') {
                    count--;
                }
                i++;
            }
            i--;
            
            String substr = decodeString(s.substring(begin + 1, i));
            for (int k = 0; k < num; k++) {
                cur.append(substr);
            }
            num = 0;
        } else { 
            cur.append(s.charAt(i));
        }
    }
    return cur.toString();
X. Iterative
https://all4win78.wordpress.com/2016/09/07/leetcode-394-decode-string/
http://www.guoting.org/leetcode/leetcode-394-decode-string/
    public String decodeString(String s) {
        if (s == null) {
            return null;
        }
         
        Stack<StringBuilder> sbStack = new Stack<>();
        Stack<Integer> intStack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int repeat = 0;
         
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                sbStack.push(sb);
                intStack.push(repeat);
                sb = new StringBuilder();
                repeat = 0;
            } else if (c == ']') {
                StringBuilder temp = sb;
                sb = sbStack.pop();
                repeat = intStack.pop();
                while (repeat > 0) {
                    sb.append(temp);
                    repeat -= 1;
                }
            } else if (c >= '0' && c <= '9') {
                repeat *= 10;
                repeat += c - '0';
            } else {
                sb.append(c);
            }
        }
         
        return sb.toString();
    }

X. Use stack
http://blog.csdn.net/mebiuw/article/details/52448807
http://blog.csdn.net/yeqiuzs/article/details/52435359
http://www.guoting.org/leetcode/leetcode-394-decode-string/
意思是在字符串当中,有一个特殊的格式 — k[S],遇到这种状况,需要把S重复k次,注意是可以嵌套的
在这次解题当中,我是使用了栈的方式,去解决这个问题。分别使用了一个全局的已解码的字符串Builder,另外对于为解码的,使用栈来暂存。
符号’[‘控制进栈,分别进入计数数字和之前尚未解码的字符串
符号’]’控制出站,出栈当前计数,并且将未解码的字符串进行重复,再链接上一个未解码的字符串
注意栈空的时候证明当前嵌套解码完毕,需要添加到全局当中,反之基于暂存。
public String decodeString(String s) { int n = s.length(); char[] ss = s.toCharArray(); Stack<Integer> counts = new Stack<Integer>(); Stack<String> strings = new Stack<String>(); StringBuilder result = new StringBuilder(); int count = 0; //当前需要解码,但是还没有遇到]暂存的 String currentString = ""; for(int i=0;i<n;i++){ if(ss[i]>='0' && ss[i]<='9'){ count = count * 10; count = count + ss[i] -'0'; } else if(ss[i] == '['){ counts.push(count); count = 0; strings.push(currentString); currentString = ""; }else if(ss[i] >='a' && ss[i]<='z'){ //注意栈空与否很重要 if(!counts.isEmpty()) currentString += ss[i]; else result.append(ss[i]); } else if(ss[i] == ']'){ int times = counts.pop(); if(counts.isEmpty()){ for(int j=0;j<times;j++) result.append(currentString); currentString=strings.pop(); } else { String tmp = ""; for(int j=0;j<times;j++) tmp+=currentString; currentString = strings.pop()+tmp; } } } return result.toString(); }
https://discuss.leetcode.com/topic/57121/share-my-python-stack-simple-solution-easy-to-understand
https://discuss.leetcode.com/topic/57159/simple-java-solution-using-stack/2
-- Use StringBuilder
    public String decodeString(String s) {
        String res = "";
        Stack<Integer> countStack = new Stack<>();
        Stack<String> resStack = new Stack<>();
        int idx = 0;
        while (idx < s.length()) {
            if (Character.isDigit(s.charAt(idx))) {
                int count = 0;
                while (Character.isDigit(s.charAt(idx))) {
                    count = 10 * count + (s.charAt(idx) - '0');
                    idx++;
                }
                countStack.push(count);
            }
            else if (s.charAt(idx) == '[') {
                resStack.push(res);
                res = "";
                idx++;
            }
            else if (s.charAt(idx) == ']') {
                StringBuilder temp = new StringBuilder (resStack.pop());
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(res);
                }
                res = temp.toString();
                idx++;
            }
            else {
                res += s.charAt(idx++);
            }
        }
        return res;
    }
https://discuss.leetcode.com/topic/57356/java-2-stacks-solution-reference-basic-calculator
public String decodeString(String s) {
        if (s.length() == 0) return "";
        Stack<String> letter = new Stack<>();
        Stack<Integer> times = new Stack<>();
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetter(s.charAt(i))) {
                sb.append(s.charAt(i));
            }
            else if (Character.isDigit(s.charAt(i))) {
                int time = s.charAt(i) - '0';
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    time = time * 10 + s.charAt(i + 1) - '0';
                    i++;
                } 
                times.push(time);
                letter.push(sb.toString());
                sb = new StringBuilder();
            }
            else if (s.charAt(i) == ']') {
                sb = constructStringBuidler(sb, letter, times);
            }
        }
        
        return sb.toString();
    }
    
    private StringBuilder constructStringBuidler(StringBuilder sb, Stack<String> letter, Stack<Integer> times) {
        StringBuilder res = new StringBuilder();
        int time = times.pop();
        String prev = letter.pop(), curr = sb.toString();
        res.append(prev);
        
        for (int i = 0; i < time; i++) {
            res.append(sb);
        }
        
        return res;
    }
https://discuss.leetcode.com/topic/57250/java-short-and-easy-understanding-solution-using-stack
    public String decodeString(String s) {
        Stack<Integer> count = new Stack<>();
        Stack<String> result = new Stack<>();
        int i = 0;
        result.push("");
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int start = i;
                while (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') i++;
                count.push(Integer.parseInt(s.substring(start, i + 1)));
            } else if (ch == '[') {
                result.push("");//\\??
            } else if (ch == ']') {
                String str = result.pop();
                StringBuilder sb = new StringBuilder();
                int times = count.pop();
                for (int j = 0; j < times; j += 1) {
                    sb.append(str);
                }
                result.push(result.pop() + sb.toString());
            } else {
                result.push(result.pop() + ch);//\\
            }
            i += 1;
        }
        return result.pop();
    }

X. Use Recursion
https://discuss.leetcode.com/topic/57612/java-one-pass-recursive-solution
    int idx;
    public String decodeString(String s) {
        idx = 0;
        return helper(s);
    }
    String helper(String s) {
        StringBuilder ans = new StringBuilder();
        for (int k = 0; idx < s.length(); ++idx) {
            char ch = s.charAt(idx);
            if (ch == '[') {
                ++idx;
                String str = helper(s);
                while (k > 0) {
                    ans.append(str);
                    --k;
                }
            } else if (ch == ']') {
                break;
            } else if (Character.isDigit(ch)) {
                k = k * 10 + ch - '0';
            } else ans.append(ch);
        }
        return ans.toString();
    }
https://discuss.leetcode.com/topic/57527/3ms-simple-java-recursive-solution
The idea is to use DFS to find the solution. Each time we find a '[' we solve it recursively and when we encounter ']' the call is end.
So to make sure that we're gonna encounter '[' and ']' both one time in each recursion, I have do the following thing:
  1. Create a global variable strIndex;
  2. Adjust the input, surround it with '1[' and ']'.
    private int strIndex;
    
    public String decodeString(String s) {
        // Adapt the input to my algorithm
        return dfs("1[" + s + "]").toString(); //no need to add 1[]
    }
    
    private StringBuilder dfs(String s) {
        StringBuilder cur = new StringBuilder();

        for (int k = 0; strIndex < s.length(); ++strIndex) {
            char c = s.charAt(strIndex);
            if (c >= '0' && c <= '9') { // Calculate the number K
                k = k * 10 + c - '0';
            } else if (c == '[') { // Recursive step
                ++strIndex;
                StringBuilder sb = dfs(s);

                for (; k > 0; k--) cur.append(sb);
            } else if (c == ']') { // Exit the loop and return the result.
                break;
            } else {
                cur.append(c);
            }
        }
        
        return cur;
    }
X.
http://xiadong.info/2016/09/leetcode-394-decode-string/
对一个字符串进行解码, 该字符串的编码规则是这样的重复次数[重复内容], 由于有可能出现嵌套, 所以我使用递归来处理这个字符串.
对于括号匹配来说, 使用栈来确定与相应左括号匹配的右括号. 要注意可能会出现不重复的串, 这时要直接把它加到返回串的后面而不处理重复次数.
    string decodeString(string str) {
        s = str;
        return decodeStringImpl(0, s.length());
    }
    string decodeStringImpl(int start, int end) {
        string ret;
        int index = start;
        while(index < end && !isDigit(s[index]) && s[index] != ']'){
            index++;
        }
        ret += s.substr(start, index - start);
        while (index < end) {
            if(!isDigit(s[index])){
                int j = index;
                while(j < end && !isDigit(s[j])) j++;
                ret += s.substr(index, j - index);
                index = j;
            }
            else{
                int leftBracket = getInt(index);
                int repeat = stoi(s.substr(index, leftBracket - index));
                int rightBracket = findRightBracket(leftBracket);
                string s = decodeStringImpl(leftBracket + 1, rightBracket);
                for (int i = 0; i < repeat; i++) {
                    ret += s;
                }
                index = rightBracket + 1;
            }
        }
        return ret;
    }
    int findRightBracket(int index) {
        vector<int> st;
        st.push_back(index);
        int i = index;
        while (!st.empty() && i < s.length() - 1) {
            i++;
            if (s[i] == '[') st.push_back(i);
            else if (s[i] == ']') st.pop_back();
        }
        return i;
    }
    int getInt(int index) {
        while (index < s.length() && isDigit(s[index])) {
            index++;
        }
        return index;
    }
    
    bool isDigit(char ch){
        return ch <= '9' && ch >= '0';
    }
http://www.cnblogs.com/dongling/p/5843795.html
public String decodeString(String s) { if(s==null||s.length()==0) return s; char ch; int index=0; int repeat=0; StringBuilder head=new StringBuilder(""),body=new StringBuilder(""); while(index<s.length()&&!Character.isDigit(ch=s.charAt(index))){ head.append(ch); index++; } if(index<s.length()){ //indicating that next character is Digit while(index<s.length()&&Character.isDigit(ch=s.charAt(index))){ repeat=repeat*10+ch-'0'; index++; }//got the leading num //now index is pointing to '['; //next, to get the index of ']'; int rightBracket=index+1; int leftBracketNum=1; while(leftBracketNum>0){ ch=s.charAt(rightBracket); if(ch==']'){ leftBracketNum--; } else if(ch=='['){ leftBracketNum++; } else{ } rightBracket++; } rightBracket--;//now rightBracket is pointing to the right position of the ']'; String res1=decodeString(s.substring(index+1,rightBracket)); String tail=decodeString(s.substring(rightBracket+1)); for(int i=1;i<=repeat;i++){ body.append(res1); } body.append(tail); } return head.toString()+body.toString(); }
X. Follow up
http://www.1point3acres.com/bbs/thread-211139-1-1.html
第三轮:LC394,剩十分钟follow up是反过来encode,求最短encode(跟我说前面那个是warm up,这才是真题)。
懵逼,给了个贪心+memory的算法(代码非常乱),也不知道能不能得到最优解。没做出来。。。
最后结束的时候她说这题很难很难,让我don't worry,用DP做(分析题目的时候我试了一下,她没有hint所以我没继续下去),
然后我才想到用dp[k][i][j]做应该可以。。。但也没时间写了。。

https://discuss.leetcode.com/topic/68275/can-we-do-the-encode-way-i-post-one-the-return-is-the-shortest-length-of-encoded-string
Suppose we have a string with only lowercase letters and the problem asked us to encode it and return the shortest one.
How can we do that? Does anyone have the idea?
update: I write a solution for the problem. Does anyone have some suggestion?
11/18 update: This solution return the shortest encode string, this means if the string is "aaa", it will return "aaa".
if the string is "aaaaa", it will return "5[a]"
Today I saw some people were asked the encoding as a follow up for leetcode #394 decode string. Most of the them only gave a brief direction during the interview and didn't write any code. But I would like to ask for more thoughts.
I may think about using dynamic programming. For string s, the shortest encoding from the ith character to the jth character is denoted by dp[i][j], then we have:
  • If i+2 > j, dp[i][j] = s[i-1:j ], i.e. just keep those characters.
  • else If s[i-1:j ] can be represented as repeating patterns, then encode it as repeating_times[repeating_pattern], using the finest repeating pattern.
  • otherwise dp[i][j] = min_length(dp[i][k] + dp[k+1][j]) where i < k < j
It runs in O(n3) time however, where n is the length of the string to be encoded.
case- aaaabb public static boolean checkRepeating(String s, int l, int r, int start, int end){
  if( (end-start) % (r-l) != 0 ){
   return false;
  }
  int len = r-l;
  String pattern = s.substring(l, r);
  for(int i = start; i +len <= end; i+=len){
   if(!pattern.equals(s.substring(i, i+len))){
    return false;
   }
  }
  return true;
 }

 public static int getLength(int plen, int slen){
  return (int)(Math.log10(slen/plen)+1);
 }

 public static String sortestEncodeString(String s){
  int len = s.length();
  int[][] dp = new int[len+1][len+1];
  for(int i = 1; i <= len; ++i){
   for(int j = 0; j < i; ++j){
    dp[j][i] = i-j;
   }
  }

  Map<String, String> dpMap = new HashMap<>();

  for(int i = 1; i <= len; ++i){
   for(int j = i-1; j >= 0; --j){
    String temp = s.substring(j, i);
    if(dpMap.containsKey(temp)){
     dp[j][i] = dpMap.get(temp).length();
     continue;
    }
    String ans = temp;
    for(int k = j+1; k <= i; ++k){
     String leftStr = s.substring(j, k);
     String rightStr = s.substring(k, i);
     if(dp[j][i] > dp[j][k] + dp[k][i]){
      dp[j][i] = dp[j][k] + dp[k][i];
      ans = dpMap.get(leftStr) + dpMap.get(rightStr);
     }
     if( checkRepeating(s, j, k, k, i) 
      && ( 2 + getLength(k-j, i-j) + dp[j][k] < dp[j][i]) ){
      dp[j][i] = 2 + getLength(k-j, i-j) + dp[j][k];
      ans = String.valueOf((i-j)/(k-j)) +"["+ dpMap.get(leftStr) +"]";
     }
    }
    dpMap.put(temp,ans);
   }
  }
  return dpMap.get(s);
 }
I wrote a similar top-down approach combining KMP.
    def check_repeating(s):
        sz = len(s)
        lps = [0] * sz
        for i in range(1, sz):
            l = lps[i-1]
            while l and s[l] != s[i]:
                l = lps[l-1]
            lps[i] = l + (s[l] == s[i])
        if lps[-1] and sz % (sz-lps[-1]) == 0:
            p = sz - lps[-1]
            return sz/p, s[:p]
        return 1, s

    memo = {}

    def _encode(s):
        if s not in memo:
            if len(s) <= 2:
                return s
            can = s
            for m in range(1, len(s)-1):
                l_cnt, l_str = check_repeating(s[:m])
                r_cnt, r_str = check_repeating(s[m:])
                if l_str == r_str:
                    comb = '{}[{}]'.format(l_cnt+r_cnt, _encode(l_str))
                else:
                    comb = _encode(s[:m])+_encode(s[m:])
                can = min(can, comb, key=len)
            memo[s] = can
        return memo[s]

    return _encode(s)
http://blog.gainlo.co/index.php/2016/09/30/uber-interview-question-delimiter-matching/
Write an algorithm to determine if all of the delimiters in an expression are matched and closed.
For example, “{ac[bb]}”, “[dklf(df(kl))d]{}” and “{[[[]]]}” are matched. But “{3234[fd” and {df][d} are not. The question has been asked by Uber recently and is expected to be solved quickly.
When I was working on this problem for the first time, what I thought first is to keep separate counters for each delimiter and if all of them are 0 after processing the string, all of the delimiters are balanced. However, this doesn’t work. Consider the case “([)]”, we have an equal number of left and right delimiters but they are incorrectly matched.
Therefore, only keeping the number of unmatched delimiters is not enough, we also need to keep track of all the previous delimiters. Since each time when we see a new delimiter, we need to compare this one with the last unmatched delimiter, stack is the data structure we should consider.
Let’s finalize the solution as follows:
  • Start with an empty stack to store any delimiter we are processing
  • Go over the string, for each delimiter we find:
    • If it’s a left parenthesis, push it to the stack
    • If it’s a right parenthesis, pop the top element of the stack and compare with the right parenthesis. If they are matched, keep processing the string. Otherwise, delimiters are not balanced.




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