数组、链表、跳表
数组 ArrayList
高级编程语言，对于数组里的元素的类型没有严格的要求，相对来说比较多样化。
在语言上，有一个标准的叫法叫做泛型。也就是说任何一个单元类型，都可以放进数组。
数组底层的硬件存在一个内存管理器，每当你申请数组，计算机实际上是在内存中开辟一段连续的地址。
每一个地址可以直接通过内存管理器进行访问。数组访问任何元素，都是常数时间 O(1)。
数组可以随机访问任何一个元素，它的访问速度非常快。
数组增加、删除数组元素都是 O(n) 的时间复杂度。最好的情况为 O(1)，最坏的情况为 O(n)。
修改、添加、删除比较频繁的情况下，数组其实并不好用。
ArrayList 的时间复杂度
prepend O(1)
append O(1)
lookup O(1)
insert O(n)
delete O(n)
正常情况下数组的 prepend 操作的时间复杂度是 O(n)，但是可以进行特殊优化到 O(1)。采用的方式是申请稍大一些的内存空间，然后在数组最开始预留一部分空间，然后 prepend 的操作则是把头下标前移一个位置即可。
盛最多水的容器（腾讯、百度、字节跳动在近半年内面试常考）
移动零（华为、字节跳动在近半年内面试常考）
爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）
三数之和（国内、国际大厂历年面试高频老题）
// 移动零，一维数组的坐标变换
// 思路1：循环遍历数组，每次走的时候统计 0 的个数，非 0 元素前移，0 元素后移
// 思路2：重新开一个新数组，遇到 0 往后放，非 0 前面放，内存空间多。新开了数组，不符合必须原数组操作
// 思路3：操作数组中 index 操作
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let j = 0; // 记录下一个非 0 元素
for (let i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[j] = nums[i];
if (i !== j) {
nums[i] = 0;
}
j++;
}
}
};
// 盛最多水的容器
// 思路1：枚举，left bar、right bar，(x - y) * height_diff、O(n^2)
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
const _getArea = (i, j) => {
return (j - i) * Math.min(height[i], height[j]);
}
let max = 0;
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
max = Math.max(_getArea(i, j), max);
}
}
return max;
};
// 思路2：双指针（左右夹逼），左右边界向中间收敛，只需要关心下标比它高的，计算最大面积、O(n)
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let max = 0;
for (let i = 0, j = height.length - 1; i < j; ) {
const minHeight = height[i] < height[j] ? height[i++] : height[j--];
const area = (j - i + 1) * minHeight;
max = Math.max(max, area);
}
return max;
};
// 爬楼梯问题
// 思路1：寻找最近重复子问题
// 1: 1
// 2: 2
// 3: f(1) + f(2)
// 4: f(3) + f(2)
// n: f(n - 1) + f(n - 2)
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n <= 2) return n;
let f1 = 1,
f2 = 2;
for (let i = 3; i <= n; i++) {
const temp = f1 + f2;
f1 = f2;
f2 = temp;
}
return f2;
};
// 两数之和 https://leetcode-cn.com/problems/two-sum/
// a + b == target
// 思路1：两层循环，枚举下标
// 思路2：hash 表处理
// 思路3：一次 hash 表
// 三数之和（高频老题）
// a + b = -c
// 思路1：暴力求解 三层循环
// 思路2：两重暴力 + hash，O(n^2)、仍然需要判重
// 思路3：排序之后，双指针（夹逼），结果可能重复
链表 LinkedList
如果只存在一个 next 指针，叫做单链表。
如果还存在先前指针叫做 prev 或者是 previous，这个链表就叫做双向链表。
头指针一般用 head 来表示，尾指针用 tail 来表示。最后一个元素，它的 next 指针指向空。
如果 tail 指针的 next 指回到 head，那么这个链表就叫做循环链表。
// 最简单 LinkedList 实现
class LinkedList {
Node Head;
class Node {
int data;
Node next;
Node (int d) {
data = d;
}
}
}
[Linked List 示例代码](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/code/LinkedList.java)
Java 中的 LinkedList 是一个很标准的双向链表结构。
链表增加和删除任何节点，不会引起整个链表的群移操作，也不需要复制元素、挪动一半的元素、挪动多个元素到新的位置。
链表的移动和修改的效率非常高，都为 O(1)。
但是也因为这样的结构，访问链表中任何一个位置，操作其实并不简单。
如果访问头节点和尾节点，都是 O(1)。但是如果想访问中间节点，必须从头节点一步一步往后移动。线性 n 的，O(n) 的算法。
LinkedList 的时间复杂度
prepend O(1)
append O(1)
lookup O(n)
insert O(1)
delete O(1)
反转链表（字节跳动、亚马逊在半年内面试常考）
两两交换链表中的节点（阿里巴巴、字节跳动在半年内面试常考）
环形链表（阿里巴巴、字节跳动、腾讯在半年内面试常考）
K 个一组翻转链表（字节跳动、猿辅导在半年内面试常考）
// 环形链表
// 思路1：遍历链表，set 记录所有访问的结点，看后续元素是否出现再 set 中
// 思路2：快慢指针 O(1) 内存，也是双指针解法
跳表 Skip List
数组中有序的时候，二分查找可以很快的查到目标元素位置。
链表元素有序的时候，如何快速的查询到目标位置？
跳表的使用只能用于链表里的元素有序的情况。跳表里的元素始终必须是有序的，不然没办法使用。
跳表（skip list）对标的是平衡二叉树（AVL Tree）和二分查找，是一种插入、删除、搜索都是 O(log n) 的数据结构。1989 年出现。
其他的 “树” 都是在 1960、196 几年出现，跳表比它们晚了接近 30 年，最后才出现。
它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 Redis、LevelDB 等。
LevelDB 是 Goole 用来取代 BigTable 的，同时是 Google 的工程师 Jeff Dean 这个人发明的。
如何给有序的链表加速？
时间复杂度：查询 O(n)
简单优化：添加头尾指针
一维数据结构加速，经常采用的方式就是升维。这样就会存在更加的附加信息，空间换时间。
可以为链表增加一级索引，指向 next + 1。还可以增加多级索引。
跳表查询的时间复杂度分析
n/2、n/4、n/8，第 k 级索引结点的个数就是 n/(2^k)。
假设索引有 h 级，最高级的索引有 2 个结点。n/(2^h) = 2，从而可以求得 h = log2(n) - 1。
在跳表中查询任意数据的时间复杂度就是 O(logn)。
现实中使用跳表时，会由于元素的增加和删除，导致它的索引并不是完全工整的。
经过多次改动之后，有些地方会少跨或者只跨两步。
维护成本相对比较高。增加元素时，要把索引更新一遍，删除元素时，也需要把索引更新一遍。
增加和删除的时候的时间复杂度就变成 logn。
跳表的空间复杂度分析
原始链表大小为 n，每 2 个结点抽一个，每层索引的节点数：
n/2，n/4，n/8，…，8，4，2
原始链表大小为 n，没 3 个结点抽一个，每层索引的节点数：
n/3，n/9，n/27，…，9，3，1
空间复杂度是 O(n)。
不管是 java，还是现在的 c++，Go，js 中，都提供了很多封装好的数据结构。
LRU Cache - Linked list： LRU 缓存机制
Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？