Question

算法与数据结构-数组/链表

Answer 1

数组是指有序的元素序列。如果将有限个类型相同的变量的集合命名，那么这个名称就是数组名，而组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。

1.数组是相同数据类型的元素的集合。
2.数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。
3.数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

1.下标从0开始
2.随机访问

插入删除操作效率低：插入新元素时，新申请空间，移动元素再插入、使用尾插法效率高，但不一定能满足实际业务需求；删除操作类似。

1.注意下标越界问题。
2.扩容/缩容问题

链表通过指针将一组零散的内存块串联在一起，我们把内存块称为链表的节点，为了将所有的节点串起来，每个链表的节点除了存储数据之外，还需要记录链上的下一个节点的地址

(1)不需要连续的内存空间；
(2)有指针引用；
(3)三种常见的链表结构：单链表、双向链表和循环链表

1.设计一个LRU缓存淘汰算法——最近最少使用
解法：维护一个有序的单链表，加入时间排序。将链表遍历，如果找到了，删掉，然后插入头部，头部就是最新的；如果不存在，如果有空间，就插入头部，LRU有内存限制，如果空间没有了，删除最后一个，完成了算法。
2.约瑟夫问题：类似丢手绢；所有人围成一圈，开始点数，点到谁，谁退出；
解法：待更新