Sunday, October 9, 2016

LeetCode 416 - Partition Equal Subset Sum


https://leetcode.com/problems/partition-equal-subset-sum/
Related: Partition of a set into K subsets with equal sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Both the array size and each of the array element will not exceed 100.
Example 1:
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

X. DP
http://www.cnblogs.com/grandyang/p/5951422.html
这道题给了我们一个数组,问我们这个数组能不能分成两个非空子集合,使得两个子集合的元素之和相同。那么我们想,原数组所有数字和一定是偶数,不然根本无法拆成两个和相同的子集合,那么我们只需要算出原数组的数字之和,然后除以2,就是我们的target,那么问题就转换为能不能找到一个非空子集合,使得其数字之和为target。开始我想的是遍历所有子集合,算和,但是这种方法无法通过OJ的大数据集合。于是乎,动态规划DP就是我们的不二之选。我们定义一个一维的dp数组,其中dp[i]表示数字i是否是原数组的任意个子集合之和,那么我们我们最后只需要返回dp[target]就行了。我们初始化dp[0]为true,由于题目中限制了所有数字为正数,那么我们就不用担心会出现和为0或者负数的情况。那么关键问题就是要找出递归公式了,我们需要遍历原数组中的数字,对于遍历到的每个数字nums[i],我们需要更新我们的dp数组,要更新[nums[i], target]之间的值,那么对于这个区间中的任意一个数字j,如果dp[j - nums[j]]为true的话,那么dp[j]就一定为true,于是地推公式如下:
dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)

https://discuss.leetcode.com/topic/62307/java-short-dp-solution-with-explanation
If sum of all the numbers is odd, the surely we cannot reach equal partition.
Using a boolean dp array (limit its max index to sum/2) whose ith entry indicates there is a way to reach the value i using certain subset of the numbers. SO if at any time we can find a subset to reach sum/2 index, we are able to equally partition.
https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

Since the problem is a 0-1 backpack problem, we only have two choices which are take or not. Thus in this problem, by using the sum value as the index of DP array, we transfer the problem to "whether should we take the currently visited number into the sum or not".
To construct the DP recurrence, when we are visiting nums[i] and to find partition of sum j: if we do not take the nums[i], then the current iteration does not make any difference on current DP value; if we take the nums[i], then we need to find whether the (new_sum = j - nums[i]) can be constructed. If any of this two construction can work, the partition of sum == j can be reached.

You can check for success within your elements loop (outer loop) to possibly terminate early.
Second, you can start your dp loop (inner loop) from a "max" position which is the lesser of the current sum of all elements used so far or the dp length.

    public bool CanPartition(int[] nums) 
    {
        int sum = 0;
        for (int i = 0; i < nums.Length; i++) sum += nums[i];
        int target = sum / 2;
        if (target * 2 != sum) return false;
        
        bool[] dp = new bool[target + 1];
        dp[0] = true;

        int currSum = 0;        
        foreach (int x in nums)
        {
            int max = Math.Min(currSum + x, target);
            for (int j = max; j >= x; j--)
            {
                dp[j] = dp[j] || dp[j-x];
            }
            
            if (dp[target] == true) return true;
            currSum += x;
        }
        
        return dp[target];
    }

    public boolean canPartition(int[] nums) {
        // check edge case
        if (nums == null || nums.length == 0) {
            return true;
        }
        // preprocess
        int volumn = 0;
        for (int num : nums) {
            volumn += num;
        }
        if (volumn % 2 != 0) {
            return false;
        }
        volumn /= 2;
        // dp def
        boolean[] dp = new boolean[volumn + 1];
        // dp init
        dp[0] = true;
        // dp transition
        for (int i = 1; i <= nums.length; i++) { // if(nums[i-1] > volumn/2) retu
            for (int j = volumn; j >= nums[i-1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
        return dp[volumn];
    }
https://discuss.leetcode.com/topic/67539/0-1-knapsack-detailed-explanation
This problem is essentially let us to find whether there are several numbers in a set which are able to sum to a specific value (in this problem, the value is sum/2).
Actually, this is a 0/1 knapsack problem, for each number, we can pick it or not. Let us assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true, otherwise it is false.
Base case: dp[0][0] is true; (zero number consists of sum 0 is true)
Transition function: For each number, if we don't pick it, dp[i][j] = dp[i-1][j], which means if the first i-1 elements has made it to j, dp[i][j] would also make it to j (we can just ignore nums[i]). If we pick nums[i]. dp[i][j] = dp[i-1][j-nums[i]], which represents that j is composed of the current value nums[i] and the remaining composed of other previous numbers. Thus, the transition function is dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
https://discuss.leetcode.com/topic/64499/java-solution-similar-to-subset-sum-problem
http://leetcodesolution.blogspot.com/2016/10/leetcode-partition-equal-subset-sum.html
https://discuss.leetcode.com/topic/62913/38ms-dp-java-solution
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n == 0) 
            return true;
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if (sum % 2 == 1)
            return false;
        Arrays.sort(nums);
        int target = sum / 2;
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (nums[i-1] == target)
                return true;
            if (nums[i-1] > target)
                return false;
            System.arraycopy(dp[i-1], 0, dp[i], 0, Math.min(target + 1, nums[i-1]));
            for (int j = nums[i-1]; j <= target; j++) {
                dp[i][j] = dp[i-1][j - nums[i-1]];
            }
            if (dp[i][target])
                return true;
        }
        return false;
    }
https://discuss.leetcode.com/topic/64499/java-solution-similar-to-subset-sum-problem
It's similar to Subset Sum Problemwhich asks us to find if there is a subset whose sum equals to target value. For this problem, the target value is exactly the half of sum of array.
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num: nums) sum += num;
        if(sum % 2 == 1) return false;
        
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        // deal with the first row
        if(nums[0] <= target) dp[0][nums[0]] = true;
        
        // deal with the first col
        for(int i = 0; i < nums.length; i++) dp[i][0] = true;
        
        // deal with the rest
        for(int i = 1; i < dp.length; i++) {
            for(int j = 1; j < dp[0].length; j++) {
                if(j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

http://bookshadow.com/weblog/2016/10/09/leetcode-partition-equal-subset-sum/
动态规划(Dynamic Programming)
利用数组dp[i]记录和为i的子数组是否存在,初始令dp[0] = 1
for num in nums:
    for i in range(sum(nums) - num + 1):
        if dp[i]: dp[i + num] = 1
def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ sums = sum(nums) if sums & 1: return False nset = set([0]) for n in nums: for m in nset.copy(): nset.add(m + n) return sums / 2 in nset

X. DP2
http://www.cnblogs.com/wangxiaobao/p/5943978.html
用01背包的思路,bool值 dp[i][j] 表示从0,1,2...i选重量为j是否可能。
则有递推关系:
dp[i][j] = dp[i - 1][j] || dp[i][j - nums[i]]; (i位置取或者不取)
结果返回值为dp[nums.size() - 1][sum]; (sum为和的一半)
 3     bool canPartition(vector<int>& nums) {
 4         int sum = 0;
 5         for (int i = 0; i < nums.size(); ++i) {
 6             sum += nums[i];
 7         }
 8         if (sum % 2 == 1) {
 9             return false;
10         } 
11         sum /= 2;
12         int dp[nums.size()][sum] = {false};
13         if (nums.size() == 1) {
14             return false;
15         }
16         for (int i = 0; i <= sum; ++i) {
17             if (nums[0] == i) {
18                 dp[0][i] = true;
19             }
20         }
21         for (int i = 1; i < nums.size(); ++i) {
22             for (int j = 1; j <= sum; ++j) {
23                 dp[i][j] = dp[i - 1][j] || dp[i][j - nums[i]];
24             }
25         }
26         return dp[nums.size() - 1][sum];
27     }

X. DFS+Cache - TLE
https://discuss.leetcode.com/topic/62267/java-solution-with-commets-using-dfs
    public boolean canPartition(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int sum = 0;
        for(int i : nums){
            if(map.containsKey(i)){
                map.put(i, map.get(i) + 1);
            }else{
                map.put(i, 1);
            }
            sum += i;
        }
        if(sum % 2 == 1) return false;
        return helper(map, sum / 2);
    }
    
    private boolean helper(Map<Integer, Integer> map, int target){
        /*target is achieveable*/
        if(map.containsKey(target) && map.get(target) > 0) return true;
        /*dfs*/
        for(int key : map.keySet()){
            if(key < target && map.get(key) > 0){
                map.put(key, map.get(key) - 1);
                if(helper(map, target - key)) return true;
                map.put(key, map.get(key) + 1);
            }
        }
        return false;
    }
}
https://discuss.leetcode.com/topic/62342/why-dp-is-slower-than-dfs-even-with-no-memoization/
The N in DFS is the length of the input array, while in DP it is the half of the summation of all elements in the input array. It might be possible that the length of the input array is short, however, the summation is pretty large, in which case DP performs worse than DFS.
Could be. But then again: both size and elements have the same bound in the problem description (100). That means the maximum possible sum is O(N^2). That makes DP O(N^3), and backtracking is still O(2^N). Even when N is around 20 they should be on about the same level, for larger N backtracking should be prohibitively slow! And there are test cases as large as 50 elements.

X. DFS - Brute Force
http://blog.csdn.net/mebiuw/article/details/52765840
老旧的暴力法 仅供参考 不可AC
/** * 首先和为奇数的过滤 * 其次使用DFS * 排序后可以剪枝很多情况 * */ public boolean canPartition(int[] nums) { Arrays.sort(nums); int sum=0; for (int num:nums) sum+= num; if(sum % 2 == 1) return false; sum/=2; return dfs(0,sum,nums); } // 一一尝试 public boolean dfs(int index,int sum,int[] nums){ sum -= nums[index] ; if(sum == 0) return true; for(int i=index+1;i<nums.length;i++){ if(sum<nums[i]) break; if(dfs(i,sum,nums)) return true; } return false; }
http://www.hihuyue.com/hihuyue/codepractise/leetcode/leetcode416-partition-equal-subset-sum

X. BitSet
https://discuss.leetcode.com/topic/62334/simple-c-4-line-solution-using-a-bitset
the question description has changed (max array size 100 ==> 200). I have modified my code below according to the new description, and also made it a bit easier to understand.
Time complexity O(n), size of the bitset is 1256 bytes
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        const int MAX_NUM = 100;
        const int MAX_ARRAY_SIZE = 200;
        bitset<MAX_NUM * MAX_ARRAY_SIZE / 2 + 1> bits(1);
        int sum = 0;
        for (auto n : nums) {
            sum += n;
            bits |= bits << n;
        }
        return !(sum % 2) && bits[sum / 2];
    }
};
It's possible to shorten the solution to 4 lines, by using std::accumulate(), but that doesn't really make you type less or make it run faster though...
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> bits(1);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        for (auto n : nums) bits |= bits << n;
        return !(sum & 1) && bits[sum >> 1];
    }
};
http://www.cnblogs.com/grandyang/p/5951422.html
这道题还可以用bitset来做,感觉也十分的巧妙,bisets的大小设为5001,为啥呢,因为题目中说了数组的长度和每个数字的大小都不会超过100,那么最大的和为10000,那么一半就是5000,前面再加上个0,就是5001了。我们初始化把最低位赋值为1,然后我们算出数组之和,然后我们遍历数字,对于遍历到的数字num,我们把bits向左平移num位,然后再或上原来的bits,这样所有的可能出现的和位置上都为1。举个例子来说吧,比如对于数组[2,3]来说,初始化bits为1,然后对于数字2,bits变为101,我们可以看出来bits[2]标记为了1,然后遍历到3,bits变为了101101,我们看到bits[5],bits[3],bits[2]都分别为1了,正好代表了可能的和2,3,5,这样我们遍历玩整个数组后,去看bits[sum >> 1]是否为1即可
    bool canPartition(vector<int>& nums) {
        bitset<5001> bits(1);
        int sum = 0;
        for (auto n : nums) {
            sum += n;
            bits |= bits << n;
        }
        return !(sum & 1) && bits[sum >> 1]; // !(sum % 2) && bits[sum / 2];
    }
http://love-oriented.com/pack/P01.html

No comments:

Post a Comment

Labels

GeeksforGeeks (1038) Algorithm (811) LeetCode (733) to-do (605) Review (438) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (270) LeetCode - Review (265) Google Interview (234) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (114) Cracking Coding Interview (110) Smart Algorithm (110) Math (97) HackerRank (88) Lintcode (83) Binary Search (75) Graph Algorithm (75) Greedy Algorithm (61) Interview Corner (61) Binary Tree (59) DFS (59) List (58) Codility (54) Algorithm Interview (53) Advanced Data Structure (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Stack (41) Binary Search Tree (39) Jobdu (39) Knapsack (39) Interval (38) Recursive Algorithm (38) String Algorithm (38) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Space Optimization (36) Beauty of Programming (35) Sort (35) Trie (35) Backtracking (34) Array (33) prismoskills (33) Segment Tree (32) Union-Find (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) Sliding Window (28) to-do-must (28) Random (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) Graph (23) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Hash (22) Queue (22) Binary Indexed Trees (21) DFS + Review (21) Pre-Sort (21) TopCoder (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Company-Facebook (19) Merge Sort (19) UVA (19) Follow Up (18) Probabilities (18) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Post-Order Traverse (16) Priority Quieue (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Bisection Method (15) Difficult (15) Iterator (15) O(N) (15) Ordered Stack (15) Number (14) Number Theory (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Binary Search - Bisection (12) 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) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Company - Microsoft (10) Company-Airbnb (10) Facebook Hacker Cup (10) HackerRank Easy (10) Lintcode - Review (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Time Complexity (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) O(1) Space (8) Prefix Sum (8) Prime (8) Quick Sort (8) Suffix Tree (8) System Design (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) Level Order Traversal (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Minimum Spanning Tree (7) Miscs (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+Cache (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Inversion (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) 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) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) 单调栈 (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) Maze (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) 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) 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) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) 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) Stream (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) 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) 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 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) 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) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts