algorithm 简单讲讲刷题的感想

leetcode到现在已经刷了200题了，感触很深。以前没觉得算法这么有意思的，在刷题多了之后，竟然有点喜欢这种做题的感觉。对于一些题型也有了自己的理解和做法总结。1-4节讲述了基本的考察数据结构类型。

1 数组

数组是最常见的算法展开形式。如果数组是有序的或者部分有序的，那一般都有跟二分法相关的东西，例如旋转数组的查找。数组还经常有前后指针展开的，例如有序数组的2sum题。数组也经常作为DP的基本展开，例如求子数组的最大和最大乘积等。

2 字符串

字符串其实可以认为就是char数组，不过字符串也有自己独特的性质，比如更容易让人看懂题。字符串的操作，经常有用到通过128长度的数组存储每个字符的数目。回文字符串是很多题展开的基础，例如找出一个字符串中含有的最长回文。

3 链表

一般是单链表，单链表有很多题。例如求倒数k个元素，中间元素，反转，部分反转，合并有序链表，环问题，用链表进行排序等等。这里面常用的方法有：简历pre指针，快慢指针。

4 树

树也是经常考的内容。树的题目也有很多耳熟能详的，树高，是否平衡，对称树，路径和，是否相同树。有些题是图的概念展开的，例如有多个孩子，有互为邻居的节点等，其实都可以用树的思想去做题。也有些题目是针对BST展开的，利用BST的特性，有很多操作，例如基于BST的栈能每次pop出最小元素等等。

5 DFS

DFS经常用于列出所有情况的题，例如字码表、Ip字符串、切割回文、排列组合、子集合等都会用到DFS。这些题目有个特点，就是需要做出选择，并且每种选择会造成下一步的选择因为本次选择而有所不同--例如字符串的题上来选一个字符，则第二选择就必须从第二个字符开始，上来选俩，则第二个选择就要从第三开始。DFS和下面其他形式在之后的文章会单独展开介绍。

6 BFS

BFS比DFS的题目要少一些，但是也不算少。例如二叉树的有些题目要用BFS，最短路径的一些题会用到BFS，以及判断是否有这样一条路径的题目。当然后面这两种都是可以用DFS做的，但是对于路径题目BFS会有优化，例如已经用过的节点，之后的遍历中就不再用(因为之前已经走过).所以比DFS的复杂度要低。

7 DP

动态规划虽然放到了最后，但是他其实是最重要的，也是最难的。DP和DFS在很多题目上是前后题，一个题列出情况，另一个题求有多少种情况。前者用DFS后者用DP，例如回文切割、IP、字码表等等都是可以用DP求数目的。DP一般会抽象成一个到2个参数的函数，尤其是两个参数的较难，一般有f(m,n)和f(m-xxx,n-xxx)在某一特定条件下有一定的关系。