【 剑指Offer 1 】数据结构 1. 数组
数据结构是技术面试中的重点，总结以下几种常见的必须熟练掌握数据结构。
- 数组
- 字符串
- 链表
- 树
- 栈和队列
数组和字符串是两种最基本的数据结构，连续内存；
链表和树是面试中出现频率最高的；
栈与递归密切相关，队列与广度优先遍历算法密切相关。
顺序存储数据。
预先分配内存：创建数组时，我们需要首先制定数组的容量大小，根据大小分配内存。
问题：空间效率不好，经常会有空闲的区域没有得到充分利用。
优点：内存连续，可根据下表在O(1) 时间读/写任何元素，时间效率高。
实现简单哈希表：数组下标设为哈希表的键值（key），数组中的数字位哈希表的值（value）。可以在O(1)时间内实现查找，快速、高效地解决问题。
动态数组：解决数组空间效率不高的问题。
例：C++的STL中的vector。可扩容。但这种额外操作影响时间性能。需要尽量减少改变数组容量大小的次数。
数组名也是一个指针，利用指针访问数组时，要防止越界。
举例说明数组和指针的区别：
面试题：数组中重复的数字