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
https://discuss.leetcode.com/topic/71392/simple-java-dfs-solution
    private int pos = 0;
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        String num = "";
        for (int i = pos; i < s.length(); i++) {
            if (s.charAt(i) != '[' && s.charAt(i) != ']' && !Character.isDigit(s.charAt(i))) {
                sb.append(s.charAt(i));
            } else if (Character.isDigit(s.charAt(i))) {
                num += s.charAt(i);
            } else if (s.charAt(i) == '[') {
                pos = i + 1;
                String next = decodeString(s);
                for (int n = Integer.valueOf(num); n > 0; n--) sb.append(next);
                num = "";
                i = pos;
            } else if (s.charAt(i) == ']') {
                pos = i;
                return sb.toString();
            }
        }
        return sb.toString();
    }
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
And the method is really straight-forward: every time when you meet a number, it must be followed by [...], we just need to recursively call our method to decode "...", then repeat the result "num" times.
    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();
http://www.cnblogs.com/lishiblog/p/5874147.html
    public String decodeString(String s) {
        StringBuilder builder = new StringBuilder();
        decodeStringRecur(s.toCharArray(),builder,0);
        return builder.toString();
    }
    
    public int decodeStringRecur(char[] sArr, StringBuilder builder, int start){
        if (start>=sArr.length){
            return start;
        }
        
        int p1 = start;
        while (p1<sArr.length && sArr[p1]!=']'){
            if (sArr[p1]<'0' || sArr[p1]>'9'){
                builder.append(sArr[p1++]);
            } else {
                // get the following encoded string.
                // get the number first.
                int val = 0;
                while (p1<sArr.length && sArr[p1]!='['){
                    val = val*10 + (int)(sArr[p1++]-'0');
                }
                
                // get the string.
                StringBuilder subBuilder = new StringBuilder();
                p1 = decodeStringRecur(sArr,subBuilder,p1+1);
                
                // add into decoded string.
                for (int i=0;i<val;i++){
                    builder.append(subBuilder);
                }
            }
        }
        
        return (p1<sArr.length) ? p1+1 : p1;
    }
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
There will be many temporary String object there. So I used a Stack with StringBuilder.
-- 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;
    }

class StrItem {
    int num = 0;
    StringBuilder sb = new StringBuilder();
    
    StrItem(int n) {this.num = n;}
}
    public String decodeString(String s) {
        int num = 0;
        Stack<StrItem> stack = new Stack<>();
        stack.push(new StrItem(1));
        for (char c: s.toCharArray())
            switch (c) {
                case '0': case '1': case '2': case '3': case '4':
                case '5': case '6': case '7': case '8': case '9':
                    num = num * 10 + c - '0';
                    break;
                case '[':
                    stack.push(new StrItem(num));
                    num = 0;
                    break;
                case ']':
                    String curStr = stack.peek().sb.toString();
                    int n = stack.pop().num;
                    for (int i = 0; i < n; i++)
                        stack.peek().sb.append(curStr);
                    break;
                default:
                    stack.peek().sb.append(c);
            }
        return stack.pop().sb.toString();
    }
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 (1107) LeetCode (993) Algorithm (795) Review (766) to-do (633) LeetCode - Review (514) Classic Algorithm (324) Dynamic Programming (293) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Different Solutions (120) Bit Algorithms (118) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (107) HackerRank (89) Binary Tree (82) Binary Search (81) Graph Algorithm (74) Greedy Algorithm (72) DFS (67) LeetCode - Extended (62) Interview Corner (61) Stack (60) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (48) Binary Search Tree (46) USACO (46) Trie (45) Mathematical Algorithm (42) ACM-ICPC (41) Interval (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) LeetCode Hard (39) Recursive Algorithm (39) Matrix (38) String Algorithm (38) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) Data Structure Design (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Priority Queue (27) Random (27) Graph (26) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) Post-Order Traverse (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) Binary Indexed Trees (21) DFS + Review (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) O(N) (20) Follow Up (19) Time Complexity (19) Two Pointers (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) Reverse Thinking (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Miscs (11) Princeton (11) Proof (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) TreeMap (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) LeetCode - DP (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) TreeSet (6) Xpost (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) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (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 - Recursive (4) LeetCode - TODO (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (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) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (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) O(N) Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (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) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (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) Company-Snapchat (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) Edit Distance (2) Factor (2) Forward && Backward Scan (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) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (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) Tree Without Tree Predefined (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) Augmented BST (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 Sarch Tree (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) Cloest (1) Clone (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-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 - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (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) Maintain State (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) 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 Element (1) Next Successor (1) Offline Algorithm (1) PAT (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) 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) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (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) Test Cases (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 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) Virtual Matrix (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