Thursday, May 17, 2018

LeetCode 751 - IP to CIDR


http://bookshadow.com/weblog/2017/12/24/leetcode-ip-to-cidr/
Given a start IP address ip and a number of ips we need to cover n, return a representation of the range as a list (of smallest possible length) of CIDR blocks.
A CIDR block is a string consisting of an IP, followed by a slash, and then the prefix length. For example: "123.45.67.89/20". That prefix length "20" represents the number of common prefix bits in the specified range.
Example 1:
Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
Explanation:
The initial ip address, when converted to binary, looks like this (spaces added for clarity):
255.0.0.7 -> 11111111 00000000 00000000 00000111
The address "255.0.0.7/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just this one address.

The address "255.0.0.8/29" specifies all addresses with a common prefix of 29 bits to the given address:
255.0.0.8 -> 11111111 00000000 00000000 00001000
Addresses with common prefix of 29 bits are:
11111111 00000000 00000000 00001000
11111111 00000000 00000000 00001001
11111111 00000000 00000000 00001010
11111111 00000000 00000000 00001011
11111111 00000000 00000000 00001100
11111111 00000000 00000000 00001101
11111111 00000000 00000000 00001110
11111111 00000000 00000000 00001111

The address "255.0.0.16/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just 11111111 00000000 00000000 00010000.

In total, the answer specifies the range of 10 ips starting with the address 255.0.0.7 .

There were other representations, such as:
["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"],
but our answer was the shortest possible.

Also note that a representation beginning with say, "255.0.0.7/30" would be incorrect,
because it includes addresses like 255.0.0.4 = 11111111 00000000 00000000 00000100 
that are outside the specified range.
Note:
  1. ip will be a valid IPv4 address.
  2. Every implied address ip + x (for x < n) will be a valid IPv4 address.
  3. n will be an integer in the range [1, 1000].

将起始ip转为int,遍历[ipInt, ipInt + range)
假设当前遍历到了第x个ip地址,记cIpInt = ipInt + x
计算cIpInt末尾0的个数,记为zeros,重复将zeros-1,直到x + 1<<zeros不大于range为止
将ipInt复原为IP地址 / 32 - zeros加入结果列表
https://felon03.github.io/2017/12/29/LeetCode-751-IP-to-CIDR/
这个问题是在给定的起始IP地址,求最少的CIDR正好覆盖n个IP地址。所求的地址要求是连续的,并且要在起始IP的后面。
先说明一下255.255.0.8/29中29的含义:
一个IPv4的地址总共有32位,可以表示29表示的是IP的前29为是固定的,后三位可以改变,因此可以覆盖23(8)个IP。那么要使CIDR尽量的少,就让固定的IP的位数尽量少,同时要保证IP是连续的。
比如我们以255.0.0.7开始,覆盖30个地址,那么就有:
255.0.0.7/32
只有一个IP地址 剩余30 - 1 = 29
接下来的IP地址是 255.0.0.8,最后8位是: 00001000,还有3位可以更改
则有255.0.0.8/29 可以覆盖8个IP,剩余29 - 8 = 21
8个地址后的IP是255.0.0.16,最后8位是: 00010000,还有4位可以更改
则有255.0.0.16/28 可以覆盖16个IP,剩余21 - 16 = 5
接下来的IP地址是255.0.0.32,最后8位是: 00100000,还有5位可以更改,而剩余的要覆盖的IP只有5个,因此要小于5,否则覆盖的IP范围就会超过给定的个数,因此是4个,即对最后两位进行更改
则有255.0.0.32/30 可以覆盖4个IP,剩余5 - 4 = 1
那么最后一个要覆盖的就是255.0.0.36/32,剩余0个要覆盖
至此可以得到最少的CIDR。
http://www.cnblogs.com/grandyang/p/8440087.html
此题给了我们一个用字符串表示的ip地址,还有一个整数n,让我们以给定的ip地址为起点,需要覆盖n个ip地址。而这n个ip地址的写法使用无类别域间路由CIDR块来写,所谓的CIDR块,是由一个正常的ip地址,加上斜杠数字,斜杠后面的数字表示这些ip地址具有相同的前缀的个数,比如"255.0.0.7/32",如果有32个相同的前缀,说明只有唯一的一个ip地址,因为IPv4总共就只有32位。再比如"255.0.0.8/29",表示有29个相同的前缀,那么最后3位可以自由发挥,2的3次方为8,所以就共有8个ip地址。同理,"255.0.0.16/32"只表示一个地址,那么这三个CIDR块总共覆盖了10个地址,就是我们要求的结果。
由于题目中要求尽可能少的使用CIDR块,那么在n确定的情况下,CIDR块能覆盖的越多越好。根据我们前面的分析,当CIDR块斜杠后面的数字越小,该块覆盖的ip地址越多。那么就是说相同前缀的个数越少越好,但是我们的ip地址又不能小于给定的ip地址,所以我们只能将0变为1,而不能将1变为0。所以我们的选择就是有将最低位1后面的0进行变换,比如"255.0.0.8"末尾有3个0,可以变换出8个不同的地址。那么我们只要找出末尾1的位置,就知道能覆盖多少个地址了。找末尾1有个trick,就是利用 x & -x 来快速找到,这个trick在之前做的题中也有应用。知道了最多能覆盖地址的数量,还要考虑到n的大小,不能超过n,因为题目只要求覆盖n个。确定了覆盖的个数,我们就可以进行生成CIDR块的操作了,之前我们为了求 x & -x,将ip地址转为了一个十进制的数,现在我们要把每一块拆分出来,直接按对应位数量进行右移并与上255即可,斜杠后的数字计算通过覆盖的个数进行log2运算,再被32减去即可
https://zhuanlan.zhihu.com/p/35541808
 public static void main(String[] args) {
  IP2CIDR i2 = new IP2CIDR();
  System.out.println(i2.IC("255.0.0.7", 10));
 }
 
 public String IC(String ip,int n){
  //思路,找到这些IPs中从右往左第一位相同的二进制位
  // x & -x ;-x是x的补码,返回x与2^64的最大公约数,
  //即x最多能被n个2整除就返回2^n,如果x是奇数返回1;返回值为0 ,说明x=0;为其他数,表示x为x与2^64的最大公约数
  //一言以蔽之就是获取32位二进制表示中从右往左首次出现1的位置
  long x = 0;
  //以"."划分每个IP
  String[] ipsegment = ip.split("\\.");
  for(int i=0;i<ipsegment .length;i++){
   x = Integer.parseInt(ipsegment [i])+x*256;
  }
  String res = "";
  while(n>0){
   long temp = x & -x;//求得该IP用32位二进制表示中从右往左首次出现1的位置
   //-x才是x的补码,~x为反码
   //temp如果为奇数,则该IP为第一个CIDR块
   //如果偶数,则该IP用二进制表示下的最低有效位的位数能表示的地址的数量
   while(temp>n) {
    temp = temp/2;
   }
                        //到这里temp肯定是小于n的,这告诉我们包括此IP在内的temp个IPs可以用一个ICDR来表示
   //接下来求出这些IPs所处的CIDR
   res+=longToIP(x, (int)temp)+"  ";
   //x加上temp;
   x+=temp;//temp个ips考虑好了,接下来考虑从x+temp考虑
   n-=temp;//还有几个IPs要求ICDR的
  }
  return  res;
 }
 
 public String longToIP(long x,int temp){
  int netID = 32;
  while(temp>0){
   temp/=2;
   netID--;
  }
  
  int[] ans = new int[4];
  for(int i=0;i<ans.length-1;i++){
   ans[i] = (int)(x & 255);
           x>>=8;
  }
  ans[ans.length-1] = (int)x;
  netID++; //加1:比如说某些IPs有m位相同,是指0-m-1位相同
  return ans[3]+"."+ans[2]+"."+ans[1]+"."+ans[0]+"/"+netID;
 }
https://blog.csdn.net/qq_32832023/article/details/78891298
  1.     public  List<String> ipToCIDR(java.lang.String ip, int range) {  
  2.         long x = 0;  
  3.         //获得一个ip地址每一部分  
  4.         String[] ips = ip.split("\\.");  
  5.         //将整ip地址看为一个整体,求出整体的int表示  
  6.         for (int i = 0; i < ips.length; ++i) {  
  7.             x = Integer.parseInt(ips[i]) + x * 256;  
  8.         }  
  9.         List<String> ans = new ArrayList<>();  
  10.         while (range > 0) {  
  11.             //求出二进制表示下的最低有效位的位数能表示的地址的数量  
  12.             //如果为奇数,则=1,即以原单个起始ip地址为第一块  
  13.             //如果为偶数,则二进制表示下的最低有效位的位数能表示的地址的数量  
  14.             long step = x & -x;  
  15.             //如果大于range,则需要缩小范围  
  16.             while (step > range) step /= 2;  
  17.             //不大于需要的range,开始处理  
  18.             //求出现在能表示的step个地址的地址块  
  19.             ans.add(longToIP(x, (int)step));  
  20.             //x加上以求出的地址块  
  21.             x += step;  
  22.             //range减去以表示的地址块  
  23.             range -= step;  
  24.         }//直到range<0  
  25.         return ans;  
  26.     }  
  27.     static String longToIP(long x, int step) {  
  28.         int[] ans = new int[4];  
  29.         //&255操作求出后8位十进制表示  
  30.         ans[0] = (int) (x & 255);  
  31.         //右移8位,即求下一个块  
  32.         x >>= 8;  
  33.         ans[1] = (int) (x & 255);  
  34.         x >>= 8;  
  35.         ans[2] = (int) (x & 255);  
  36.         x >>= 8;  
  37.         ans[3] = (int) x;  
  38.         int len = 33;  
  39.         //每一位就可以表示2个  
  40.         while (step > 0) {  
  41.             len --;  
  42.             step /= 2;  
  43.         }  
  44.         return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;  
  45.     }  



No comments:

Post a Comment

Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (634) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) LeetCode - Extended (62) Interview Corner (61) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (49) Trie (49) Binary Search Tree (47) USACO (46) Interval (45) LeetCode Hard (42) Mathematical Algorithm (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) Matrix (39) Recursive Algorithm (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) Data Structure Design (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (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) Graph (27) Random (27) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Post-Order Traverse (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Binary Indexed Trees (22) Bisection Method (22) Hash (22) DFS + Review (21) Lintcode - Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (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) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Long Increasing Sequence(LIS) (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (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) Miscs (11) Princeton (11) Proof (11) Rolling Hash (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) SPOJ (10) Theory (10) TreeMap (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) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) Interval Tree (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) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) TreeSet (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) 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) LeetCode - TODO (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) 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) Parser (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Skyline (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) Hard Algorithm (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) 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) 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) Clean Code (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) Concise (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) 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 - Construction (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode - Thinking (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) Two-End-BFS (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