数据结构

数组与链表

数组存储相同的数据类型，在内存中占用一块连续的内存空间。

链表可以使用零散的空间存储数据，各个元素通过指针连接，没有元素包括指向下一个元素的内存地址。

从存储的方式可以看出。数据可以迅速查找，给定下标，查找的时间复杂度O(1)。但是，由于需要用连续的存储空间，数组的插入时间复杂度为O(N)，需要将插入元素的后面的元素整体后移，如果空间不够，还需要开辟新的内存空间存储。

链表查找需要逐个遍历，因此查找的时间复杂度为O(N)，但是插入，删除元素，不用移动后面的元素，时间复杂度O(N)。

因此，可以根据数据操作的特点，选择合适的数据结构。

Hash表

Hash表可以看作数组和链表结合，可以实现快速增删。访问数据和增删数据，都是O(1)。

Hash表由一个固定大小的数组加一个链表组成。

查找元素时，先计算出元素对应hash值，然后根据hash值从数组中快速获取数据。插入数据，也通过hash值，找到应该插入的位置，如果两个元素的hash值相同，通过链接，解决碰撞问题。

栈

数组和链表都是线性表。栈就是在线性表，添加上“后进先出”的限制的数据结构。

栈的一个典型应用是函数调用栈。在操作系统中，函数调用产生和局部变量都存储在栈中。

队列

和栈相对的是队列，队列也是添加限制的线性表，和栈不同，队列需要“先进先出”

典型的应用场景是生产者消费者，生产者将任务放入队列，多个消费者从队列中去任务处理。

树

树是由n（n>0）个有限节点组成一个具有层次关系的集合。

典型的一种树是二叉排序树。其左子树上的所有节点的值都小于根节点，右子树上所有的节点都大于根节点。且左右子树也为二叉排序树。

平衡二叉（排序）树：如果从任何一个节点出发，左右子树的深度之差的绝对值不超过1。平衡二叉树的左右子树也为平衡二叉树。

红黑（排序）树：每个节点有两种颜色——红色和黑色。根节点都是黑色。每个叶子节点都是黑色的空节点。从根节点到叶子节点不会出现连续的红色节点。从任何一个节点出发到叶子节点，这条路径上都有相同数目的黑色节点。

增删节点时，红黑树通过染色和旋转满足定义。

红黑数 vs. 平衡二叉树

红黑树增删的时间复杂度O(1)，比平衡二叉树性能好。在大量增删的情况下，红黑树的效率高。但是，由于红黑树平衡性不如二叉树，因此，查找效率要差一些。

跳表

所有的数据构建为一个有序链表，时间复杂度为O(N)。

跳表：在原来的链表的基础上，在构建一个更系数的链表。

缺点：空间复杂度高，多出1倍的空间。

算法

常用算法有：穷举算法、递归算法、贪心算法、动态规划

1. 穷举算法

暴力遍历，时间复杂度一般为 2^n，数字很大时，无法计算。

1. 递归算法

典型的如快速排序算法。

特点：递归函数要写写退出条件，如果没有退出条件会导致栈溢出错误。

死循环，不会导致栈溢出。

1. 贪心算法

不从总体上考虑最优，总是作出当前看起来最好的选择。算法得到的是某种意义上的局部最优。

例如，背包问题，背包容量为4磅，需要装最优价值的东西。用贪心算法的思路，如果选用最大价值的原则，先放入最值钱的，即音箱。则最终获得3000。而实际最优是，放入笔记本和吉他 3500。

可见，贪心算法，通常不能得到令人满意的结果。

1. 动态规划算法

动态规划将问题分解为相似的子问题，试图解决每个子问题一次，并存储解，下次用到相同子问题直接查询。

动态规划在查找有很多重叠子问题的情况的最优解时有效。动态规划只能应用于有最优子结构的问题。

比如上面的（0-1）背包问题。

建立网格，网格中填写的值为c[i][j],i为可以选择的商品，j为背包容量。

v[i]为i的价值，w[i]为i的重量。

决定是否选择商品i的方案，比较选与不选的获得的价值

即，c[i][j] = max(c[i-1][j] ,v[i]+c[i-1][j-w[i]])



• 第一行，由于只有吉他可选，且吉他重量为1，因此，c[1][j]都为1500。

• 第二行，可选的有吉他和音响，由于音响4磅，因此，当容量小于4时，c[2][j] = 1500（只能放下吉他），当容量为4时，c[2][4]=3000。

• 第三行，笔记本为3磅，当j<=2时，还是只能选吉他，1500。

• 当j为3时，有两种选择，

1)不放笔记本，值为c[2][3]=1500

2)放笔记本，值为v[3]+c[2][3-w[3]]=2000

因此，最大价值的c[3][3] = 2000

• 当j为4时，也是2种选择，

1)不放笔记本，值为c[2][4]=3000

2)放笔记本，值为v[3]+c[2][4-w[3]]=2000 + 1500 = 3500

因此，c[3][4] = 3500。

由此，得到最优解，背包为4时，放吉他和笔记本，价值3500。