第03课丨01数组、链表、跳表的基本实现和特性
一、数组（Array）
java,C++: int a[100];
Python: list = []
JavaScript: let x = [1,2,3]
-
可以直接进行初始化
-
高级语言，对于数组中的元素类型没有限制--->泛型
-
内存管理器：每当申请数组时，计算机在内存中开辟了一段连续的地址，每一个地址直接可以通过内存管理器进行访问
-
无论访问哪个元素，时间复杂度是一样的，常数O(1)的
-
数组的问题，关键在于要增加、删除数组元素的时候，会进行相应的操作，如下图: 要在index=3的位置插入“D”，则需要移动“E”“F”“G”,此时源码中会涉及非常多的arraycopy操作，时间复杂度由常数级的复杂度--->O(n)，删除同理，将最后的元素设置为空，调用垃圾回收size-1。
image.png
二、链表（Linked List）
image
- 为了弥补数组的插入、删除带来的复杂度上升的缺点
- 每个元素有Value、Next，next指向下一个元素，一般用class来定义，
- 只有一个next指针叫单链表，
有时候往前一个指叫它的先前指针(previous)，是双向链表 - 头指针用head表示，尾指针用tail表示，
- 最后一个元素next指向空。
- 如果tail指针可以指向head指针，就叫循环链表。
增加节点前
增加操作（复杂度O(1)）
删除操作
- 增加或删除节点的话，没有引起整个链表的群移操作，也不需要复制元素，挪动元素到新的位置，所以它移动的效率和修改的操作效率非常高，复杂度为O(1)
- 这个结构导致了访问链表中的任何一个位置，操作就不再简单了，复杂度为O(n)
重点！！！
链表操作复杂度：
prepend ---> O(1)
append ---> O(1)
lookup ---> O(n)
insert ---> O(1)
delete ---> O(1)
Array操作复杂度：
prepend ---> O(1)
append ---> O(1)
lookup ---> O(1)
insert ---> O(n)
delete ---> O(n)
Linked list的实现（cpp）：
class LinkedList{
Node head; //head of list
/* Linked list Node */
class Node {
int data;
Node next;
// Constructor to create new node
// Next is by default initialized
// as null
Node(int d) { data = d;}
}
}
三、跳表（Skip List）--->以理解为主
工程中，主要在Redis中进行运用，理解其工作原理为主，对于链表的查询缺陷，访问复杂度为O(n)，做了优化。
image.png
1、优化的中心思想：
- 升维，将一维结构变为二维结构，不仅仅增加一个头指针和尾指针，再增加一个中指针，可以在中间的中间增加指针... ...
- 空间换时间，贯穿于整个数据结构和算法，也贯穿于整个数学和物理世界里面进行分析。
2、跳表的思想：（提高链表线性查找的效率）
可以认为next的每次速度为1，一级索引的每次速度为2
在一级索引的基础上，再乘以2
对于几千个元素可以增加log(2n)个级索引
3、跳表查询的时间复杂度分析
n/2、n/4、n/8、第k级索引结点的个数就是n/(2^k)
假设索引有h级，最高级的索引有2个结点。n/(2^h)=2，从而求得h=log2(n)-1
image.png
索引的高度：logn，每层索引遍历的结点个数：3
在跳表中查询任意数据的时间复杂度就是O(logn)，也就是从最朴素的原始链表的O(n)的时间复杂度降到了log2n的时间复杂度。
现实中跳表的形态：
image.png
由于增加或删除，导致索引跨度不一，而且维护成本相对较高，每增加或删除一个元素的时候，需要把它的索引都更新一遍。（时间复杂度为logn）
4、跳表的空间复杂度分析（收敛的）
image
5、工程中的应用
示例1：
leetcode 283 移动零leetcode-cn.com
快慢指针
class Solution(object):
def moveZeroes(self, nums):
j=0
for i in range(len(nums)):
if nums[i] != 0 :
nums[j] = nums[i]
if i != j:
nums[i]=0
j+=1
示例2：
leetcode 11 盛最多水的容器leetcode-cn.com
双指针，短的柱子移动
class Solution:
def maxArea(self, height:[]):
res, l, r = 0, 0, len(height) - 1
while l < r:
h = min(height[l], height[r])
print('=====')
print (h)
print (res, l, r)
# 先执行max(res, h * (r - l))，在执行l + (height[l] == h)，在执行r - (height[r] == h
res, l, r = max(res, h * (r - l)), l + (height[l] == h), r - (height[r] == h)
print (res, l, r)
return res
示例3：（典型的斐波垃圾数列）
leetcode 70 爬楼梯leetcode-cn.com
class Solution:
def climbStairs(self, n: int) -> int:
if (n <= 2): return n
f1, f2, f3 = 1, 2, 3
for i in range(3, n+1):
f3 = f1 + f2
f1 = f2
f2 = f3
return f3
示例4：（练习双指针的用法）
leetcode 15 三数之和leetcode-cn.com
class Solution(object):
def threeSum(self, nums):
res = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
l , r = i + 1,len(nums)-1
while l < r:
s = nums[i] + nums [l] +nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append((nums[i],nums[l],nums[r]))
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
示例5：(练习怎么操作链表)
leetcode 206 反转链表leetcode-cn.com
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表，while循环里面的内容其实可以写成一行
# 这里只做演示，就不搞那么骚气的写法了
while cur:
# 记录当前节点的下一个节点
tmp = cur.next
# 然后将当前节点指向pre
cur.next = pre
# pre和cur节点都前进一位
pre = cur
cur = tmp
return pre
示例6：(采用快慢指针--->实用性不强，当作思维训练即可)
leetcode 141 环形链表leetcode-cn.com
class Solution(object):
def hasCycle(self, head):
if(head == None or head.next == None):
return False
node1 = head
node2 = head.next
while(node1 != node2):
if(node2 == None or node2.next == None):
return False
node1 = node1.next
node2 = node2.next.next
return True
解题思路小结：
-
特别懵的时候，看看是否能暴力解？
-
想基本情况是什么，能不能化繁为简的思考？
-
数学归纳法的思想 ---> 递推
-
解决各种问题关键是找最近重复子问题：
-
if - else
-
for while , recursion(递归)
