Monday, June 13, 2016

LeetCode 356 - Line Reflection


[LeetCode] Line Reflection 直线对称 - Grandyang - 博客园
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given set of points.
Example 1:

Given points = [[1,1],[-1,1]], return true.
Example 2:

Given points = [[1,1],[-1,-1]], return false.
Follow up:
Could you do better than O(n2)?
Hint:
  1. Find the smallest and largest x-value for all points.
  2. If there is a line then it should be at y = (minX + maxX) / 2.
  3. For each point, make sure that it has a reflected point in the opposite side.
http://blog.csdn.net/jmspan/article/details/51688862

http://dartmooryao.blogspot.com/2016/06/leetcode-356-line-reflection.html
https://leetcode.com/discuss/108319/simple-java-hashset-solution
The idea is that all symmetry pair of number's x value will add to the same number.
So we want to find out this number by finding the min and max, then add them

In addition, we use a string to represent the points.
For each point, we calculate the counter part of this point, and check whether this string exists in the set. If not, return false. If all points pass the check, return true.

My idea is similar to it. However, in my solution, I have to either add or subtract the number. Also, I have to deal with double value because I use average of the two value. Which is more difficult to handle.

Very important:
(1) Use sum over average!
(2) Consider using min/max value when I need to find a particular value from a group of numbers.
(3) String matching is magic!
public boolean isReflected(int[][] points) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; HashSet<String> set = new HashSet<>(); for(int[] p:points){ max = Math.max(max,p[0]); min = Math.min(min,p[0]); String str = p[0] + "a" + p[1]; set.add(str); } int sum = max+min; for(int[] p:points){ //int[] arr = {sum-p[0],p[1]}; String str = (sum-p[0]) + "a" + p[1]; if( !set.contains(str)) return false; } return true; }  

https://discuss.leetcode.com/topic/48172/simple-java-hashset-solution/5
    public boolean isReflected(int[][] points) {
        int max, min, sum;
        HashSet<Point> set = new HashSet<>();
        if(points.length == 0) return true;
        max = points[0][0]; min = max;
        for(int[] point: points) {
            int x = point[0];
            if(x > max) max = x;
            if(x < min) min = x;
            set.add(new Point(point[0], point[1]));
        }
        sum = (max + min);
        for(int[] point: points) {
            Point ref = new Point(sum - point[0], point[1]);
            if(set.contains(ref)) set.remove(ref);
        }
        return set.isEmpty();
        
    }
    private class Point {
        int x;
        int y;
        Point(int xx, int yy) {x = xx; y = yy;}
        @Override
        public boolean equals(Object obj){
            Point p = (Point) obj;
            return (this.x == p.x && this.y == p.y);
        }
        @Override
        public int hashCode(){
            return x * 31 + y * 17;
        }
    }

方法:使用哈希映射来快速查找反射点。
https://leetcode.com/discuss/107725/8ms-java-no-hash-just-sort-o-1-space
Thanks for StefanPochmann's test case. I found that average solution does not work for odd points. As the example StefanPochmann provided [[0,0],[1,0],[3,0]]. There is no reflection line. With average code, it returns true.
So after read the hint and StefanPochmann's solution, I made it with Java.
Just sort the points with x. Then "reflect" it by assume there is a x-axis formed by minx and maxx. Then resorted the array. All the points should be same as the first sort.
public boolean isReflected(int[][] points) { if (points == null) { return false; } Arrays.sort(points, new ArrComparator()); int[][] reflectedPoints = new int[points.length][2]; for (int i = 0; i < reflectedPoints.length; i++) { reflectedPoints[i][0] = points[0][0] + points[reflectedPoints.length-1][0] - points[i][0]; reflectedPoints[i][1] = points[i][1]; } Arrays.sort(reflectedPoints, new ArrComparator()); for (int i = 0; i < reflectedPoints.length; i++) { if (reflectedPoints[i][0] != points[i][0] || reflectedPoints[i][1] != points[i][1]) { return false; } } return true; } public class ArrComparator implements Comparator<int[]>{ @Override public int compare(int[] a, int b[]) { if (a[0] == b[0]) { return Integer.compare(a[1], b[1]); } return Integer.compare(a[0], b[0]); } }
My first approach to solve this problem was to sort all points by its x-coordinates, find the mid point of all points and then use 2-pointer to iterate through the sorted points from both side, and check if they are symmetric.
It turn out this approach is a pain in the neck. Because sorting all points is not easy. The compare function used in sorting depends on where the middle line is. If you are not convinced, please think about how to compare 2 points that have the same x-coordinate.

这道题给了我们一堆点,问我们存不存在一条平行于y轴的直线,使得所有的点关于该直线对称。题目中的提示给的相当充分,我们只要按照提示的步骤来做就可以解题了。首先我们找到所有点的横坐标的最大值和最小值,那么二者的平均值就是中间直线的横坐标,然后我们遍历每个点,如果都能找到直线对称的另一个点,则返回true,反之返回false.
    bool isReflected(vector<pair<int, int>>& points) {
        unordered_map<int, set<int>> m;
        int mx = INT_MIN, mn = INT_MAX;
        for (auto a : points) {
            mx = max(mx, a.first);
            mn = min(mn, a.first);
            m[a.first].insert(a.second);
        }
        double y = (double)(mx + mn) / 2;
        for (auto a : points) {
            int t = 2 * y - a.first;
            if (!m.count(t) || !m[t].count(a.second)) {
                return false;
            }
        }
        return true;
    }
下面这种解法没有求最大值和最小值,而是把所有的横坐标累加起来,然后求平均数,基本思路都相同
    bool isReflected(vector<pair<int, int>>& points) {
        if (points.empty()) return true;
        set<pair<int, int>> pts;
        double y = 0;
        for (auto a : points) {
            pts.insert(a);
            y += a.first;
        }
        y /= points.size();
        for (auto a : pts) {
            if (!pts.count({y * 2 - a.first, a.second})) {
                return false;
            }
        }
        return true;
    }
http://blog.csdn.net/github_34333284/article/details/51697208
Think that, if all points are reflect each other. We need to first find the line. The line should be in the middle of (min, max). For other points, if two point reflect, the y-ith should be same, (min, max) / 2 - x1 = (min, max) / 2 - x2. */ bool isReflected(vector< pair<int, int> >& points) { unordered_map< int, set<int> > m; int minX = INT_MAX, maxX = INT_MIN; for(int i = 0; i < points.size(); ++i) { minX = min(points[i].first, minX); maxX = max(points[i].first, maxX); m[points[i].first].insert(points[i].second); } double y = double(maxX + minX) / 2; for(int i = 0; i < points.size(); ++i) { int t = 2*y - points[i].first; if(!m.count(t) || !m[t].count(points[i].second)) return false; } return true; } // second method bool isReflectedII(vector<pair<int, int> >& points) { if(point.size() == 0) return true; set< pair<int, int> > res; double y = 0; for(auto a : points) { res.insert(a); y += a.first; } y = y / points.size(); for(auto a : res) { if(!res.count((2 * y - a.first), a.second)) return false; } return true; }
https://reeestart.wordpress.com/2016/06/06/google-vertical-symmetric-line/

[Solution]
如果存在,这条线肯定是所有x的平均值或者中值(Avg or Median).
先算出所有x的平均值作为candidate,然后对于所有在同一条y上的点,算对称轴,只要有一条对称轴和candidate不同,就返回false, 否则返回true.
[Mistake]
上面的Solution,如果input的点都在同一条水平线上,比如[-2, 1], [-1, 1], [1, 1], [3, 1]这4个点,很明显没有对称轴,但还是会返回true。
[Solution]
无论是Average还是Median都是不靠谱的。因为就算对于两行点来说有相同的average或者median x coordinator,也没法保证每行内的点都关于这个x对称。
[Solution #1]
一种解决方法是仍然找Average, 只要有一行点的average和其他不同就返回false,但是除此之后,对于同一水平线上的点,仍然需要判断它们是否关于candidate对称,判断方法就是对每一个点,看对称轴另一边的点是否存在。
Cons: 由于ConcurrentModificationException, 使得实现起来稍微麻烦一点。
[Solution #2]
第二种解决方法是leetcode上给的hint,如果存在一条对称轴,那么对于所有对称点,两个x的和必然为一个固定值。
A.x + B.x === xMin + xMax, if A and B are symmetrical to each other.
那么和第一种方法一样,在first pass的时候一边 group y,一边找所有点的xMin和xMAX。最终如果存在对称轴,所有对称点的sum of x一定等于xMin + xMax。于是可以把问题简化为对于每一行的点,做two sum。
[Solution #3]
还有一种方法思路和solution #2一样,不过可以换种方法来解决。
idea就是把所有点表示成一个string, 比如x#y,然后把所有点的string加入到HashSet里,在找对称点的时候只要找set里是否存在(sum – x)#y这样的string就可以了。
[Time & Space]
O(n) time, O(n) space
Code is for Solution #2
  public boolean isReflected(int[][] points) {
    if (points.length == 0) {
      return true;
    }
    int xMin = Integer.MAX_VALUE;
    int xMax = Integer.MIN_VALUE;
    Map<Integer, Set<Integer>> yGroup = new HashMap<>();
    for (int i = 0; i < points.length; i++) {
      xMin = Math.min(xMin, points[i][0]);
      xMax = Math.max(xMax, points[i][0]);
      yGroup.putIfAbsent(points[i][1], new HashSet<>());
      yGroup.get(points[i][1]).add(points[i][0]);
    }
    int sum = xMax + xMin;
    for (int y : yGroup.keySet()) {
      Set<Integer> set = yGroup.get(y);
      for (int x : set) {
        if (!set.contains(sum - x)) {
          return false;
        }
      }
    }
    return true;
  }



Follow up: 如果对称轴是任意直线呢

2. LC 356, 但是直线可以是任意直线
http://www.1point3acres.com/bbs/thread-210040-1-1.html
Read full article from [LeetCode] Line Reflection 直线对称 - Grandyang - 博客园

No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) 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) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts