Tuesday, May 7, 2013

Algorithm and Data Structure Review

常用总结。

1、常见数据结构

线性:
          数组:Merge Sorted Array
          链表:Merge k Sorted ListsPartition List
          队列,
          堆栈,
          块状数组(数组+链表)
          hash表,
          双端队列
        位图(bitmap)

树:
   二叉树: Minimum Depth of Binary Tree, Path Sum II, Inorder Travel
        堆(大顶堆、小顶堆)
          trie树(字母树or字典树)
          后缀树,
        后缀树组
          二叉排序/查找树,
          B+/B-,
        AVL树
        Treap
          红黑树
          splay树
        线段树
          树状数组

图:图

其它:并查集

2、常见算法

(1)       基本思想:枚举,
               递归: 
Flatten Binary Tree to Linked ListGenerate ParenthesesLetter Combinations of a Phone Number
               分治,
               模拟&贪心: Gray CodeInsert IntervalJump Game II, Multiply Strings, Next PermutationPalindrome NumberPascal's Triangle II
贪心,动态规划,剪枝,回溯
               二分查找:Median of Two Sorted ArraysSearch in Rotated Sorted Array

(2)       图算法:深度优先遍历与广度优先遍历, 最短路径,最小生成树,拓扑排序

(3)       字符串算法:
                   字符串查找: Implement strStrLength Of Last WordLongest Common Prefix, 
                                     Longest Palindromic SubstringLongest Non-Repeating SubString
                   双指针: Minimum Window Substring
                   hash算法,KMP算法

(4)       排序算法:冒泡,插入,选择,快排,归并排序,堆排序,
               桶排序: First Missing Positive

(5)       动态规划:Distinct SubsequencesEdit DistanceInterleaving StringJump GameLargest Rectangle in Histogram
  背包问题,最长公共子序列,最优二分检索树

(6)       数论问题:素数问题,整数问题,进制转换,同余模运算,
                     进制转换:Integer To Roman
                     乘除法:Divide Two Integers 

(7)       排列组合:排列和组合算法

(8)       其它:LCA与RMQ问题
               
 (9) 水箱问题:Trapping Rain WaterContainer With Most Water

3. 常见设计题
(1)海量数据处理



No comments: