预习课重要知识点回顾
1.刷题方法: 五毒神掌+切题四件套
2.如何找解题思路?暴力法+找最小最近重复子问题
3.Leetcode解题思路?国内站的讨论区+国际站投票数高的讨论区
4.算法最终优化中心思想:升维,也就是以空间换时间
第一周学习总结
【1】数组、链表、跳表
1.1 数组 Array
1.1.1 java:常用写法
// 初始化空数组
int[] a = new int[];
// 初始化值
int[] b = new int[]{1,2,3};
// 初始化固定长度的数组
int[] c = new int[5];
1.1.2 数组的插入、删除、查找的原理及源码分析
数组的插入、删除 都会意味着数组的大小要重新扩容
插入,会将后面的元素往后进行重新移动
删除,会将后面的元素往前移动,并删除最后的元素
源码分析
/**
330: * Appends the supplied element to the end of this list.
331: * The element, e, can be an object of any type or null.
332: *
333: * @param e the element to be appended to this list
334: * @return true, the add will always succeed
335: */
336: public boolean add(E e)
337: {
338: modCount++;
339: if (size == data.length)
340: ensureCapacity(size + 1);
341: data[size++] = e;
342: return true;
343: }
ensureCapacity(size + 1)
是数组扩容函数。
1.1.3 时间复杂度分析
prepend O(1)
append O(1)
lookup O(1)
insert O(n)
delete O(n)
1.2 链表 LinkedList
1.2.1 java:常用写法
List linkedList = new LinkedList<T>();
java自身实现的LinkedList 是一个双向链表,里面包含往前的first节点,往后的last节点.
1.2.2 链表LinkedList
的插入、删除、查找的原理及源码分析
Java LinkedList源码
插入和删除 不会影响到其他节点的群移操作,也不涉及复制元素。
查找的话,需要一个一个节点的去找,时间复杂度是线性时间复杂O(n)
1.2.3 时间复杂度分析
prepend O(1)
append O(1)
lookup O(n)
insert O(1)
delete O(1)
1.3 跳表 SkipList
是基于链表 进行优化的一种数据结构。其中redis中有运用skipList。
那主要优化什么地方?从链表的时间复杂度可以看到,只有lookup 随机访问查找的时间复杂度是O(n),其余都是O(1)。那么想到查找,我们就联想到数据库的查找,数据库查找慢,我们可以优化sql,还可以通过建索引来优化。
缺点:索引难以维护
1.4 工程中的应用
LinkedList的应用:
LeetCode: LRU缓存 最近最少使用
skipList的应用
Redis - Skip List:跳跃表、为啥 Redis 使用跳表(Skip List)而不是使用 Red-Black?
1.5 常用算法解题思路及算法思想
解题思路:
1.想所有可能得解法,并记录下来, 比较得出最好的解法思路。
2.五遍刷题,反馈,看国内和国际讨论区
3.懵逼的时候?1.能不能暴力求解 2. 枚举基本情况 3. 找最近最小的重复子问题
算法思想:
- 双指针(左右下标)移动法(同向,反向):前提是 数组有序
【2】栈、队列、优先队列、双端队列
基本特性
栈 stack: 先入后出;添加、删除皆为O(1), 查询 O(n)
队列 queue: 先入先出; 添加、删除皆为O(1), 查询 O(n)
双端队列 Deque:
作业: 新API改写Deque
package leetcode.editor.cn;
import java.util.Deque;
import java.util.LinkedList;
public class DueueDemo {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
deque.addLast("d");
System.out.println(deque); // [c, b, a, d]
String str = deque.peekFirst();
System.out.println(str); // c
System.out.println(deque); // [c, b, a, d]
str = deque.peekLast();
System.out.println(str); // d
System.out.println(deque); // [c, b, a, d]
str = deque.pollFirst();
System.out.println(str); // c
System.out.println(deque); // [b, a, d]
str = deque.pollFirst();
System.out.println(str); // d
System.out.println(deque); // [b, a]
while (deque.size() > 0) {
System.out.println(deque.pollFirst());
}
System.out.println(deque);
}
}
优先队列 Priority Deque:
优点:取数,不再是先入先出或先入后出,而是按照元素的优先级取出。
场景: VIP权限优先级高,取最大值或最小值
Heap堆:实现有多种,不一定是二叉树实现的堆,也可以是斐波那契heap,或红黑树heap, treap
时间复杂度对比
参考链接
- Java 的 PriorityQueue 文档
- Java 的 Stack 源码
- Java 的 Queue 源码
- Python 的 heapq
- 高性能的 库