学习笔记
- 视频：1.5～2.0倍数播放、难点（暂停+反复）
- 实践尝试：2倍速看完，难点或者觉得重要的点结合PPT做笔记，如果思考后又不理解的地方再回看视频对应位置直到弄懂。
- Chunk it up 切碎知识点
- Delibrerate Practicing 刻意练习
- Feedback 反馈
- Clarification 理解题目
- Possible solution 列出所有的解法
- compare(time/space) 根据时间和空间复杂度对比算法
- optimal(加强)
- Coding(多写)
- Test Cases 设计测试用例检验
- 第一遍
- 5分钟～10分钟读题+思考
- 无思路后，直接看解法：注意！多解法，比较解法优劣
- 背诵、默写好的解法
- 第二遍
- 马上自己写，LeetCode提交
- 多种解法比较、体会，再优化！
- 第三遍
- 过了一天后，再重复做题
- 不同解法的熟练程度->专项练习
- 第四遍
- 过了一周：反复回来练习相同题目
- 第五周
- 面试前一周恢复性训练
至少刷五遍，可以根据自己的感觉增加次数
- Java: IntelliJ （学习Top tips）
- Leetode plugin
- O(1)：Constant Complexity 常数复杂度
- O(log n): Logarithmic Complexity 对数复杂度
- O(n): Linear Complexity 线性时间复杂度
- O(n^2): N square Complexity 平方
- O(n^3): N cubic Complexity 立方
- O(2^n):Exponential Growth 指数
- O(n!): Factorial 阶乘
注意：只看最高复杂度的运算
时间复杂度
- prepend O(1)
- append O(1)
- lookup O(1)
- insert O(n)
- delete O(n)
时间复杂度
- prepend O(1)
- append O(1)
- lookup O(n)
- insert O(1)
- delete O(1)
- 限制：只能用于元素有序的情况
- 特点：原理简单、容易实现、方便扩展、效率更高
- 用途：替代平衡树，如：Redis、LevelDB等
- 实现方法：添加多级索引
时间复杂度
- prepend O(logn)
- append O(logn)
- lookup O(logn)
- insert O(logn)
- delete O(logn)
- Stack：先入后出；添加、删除皆为O(1)，查找O(n)
- Queue: 先入先出；添加、删除皆为O(1)，查找O(n)
- Deque（Double-End Queue）：添加、删除皆为O(1)
- Priority Queue:
- 插入O(1), 取出O(logN):按元素的优先级取出
- 底层具体实现的数据结构较为多样和复杂：heap、bst、treap
用add first或add last这套新的API改写Deque的代码
原代码
Deque<String> deque = new LinkedList<String>();
deque.push("a");
deque.push("b");
deque.push("c");
System.out.println(deque);
String str = deque.peek();
System.out.println(str);
System.out.println(deque);
while (deque.size() > 0) {
System.out.println(deque.pop()); }
System.out.println(deque);Comparison of Stack and Deque methods
| Stack Method | Equivalent Deque Method |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
用add first或add last这套新的API改写Deque的代码
Deque<String> deque = new LinkedList<String>();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);
String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);
while (deque.size() > 0) {
System.out.println(deque.removeFirst()); }
System.out.println(deque);分析Queue和Priority Queue的源码
Queue是接口，提供了插入，提取和检查操作。这些方法中的每一种都以两种形式存在：一种在操作失败时引发异常，另一种返回一个特殊值（根据操作而为null或false）
| Method | Throws exception | Returns special value |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
Priority Queue是Queue接口的一种实现，是基于优先级堆的无界优先级队列。
** 以下分析基于jdk8源码 **
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private static final int MAX_ARRAY_SIZE = 2147483639;- 队列保存在无序列化的数组中，设置了默认容量和最大容量
public boolean add(E e) {
// 调用offer(e)
return this.offer(e);
}
public boolean offer(E e) {
if (e == null) {
throw new NullPointerException();
} else {
++this.modCount;
int i = this.size;
if (i >= this.queue.length) {
this.grow(i + 1);
}
this.size = i + 1;
if (i == 0) {
this.queue[0] = e;
} else {
this.siftUp(i, e);
}
return true;
}
}- add和offer方法实现一致，都不允许null元素并抛出空指针异常
- 队列容量不足时，将调用grow方法进行扩容
- 添加元素时调用siftUp方法加入元素并调整堆
private void grow(int minCapacity) {
int oldCapacity = this.queue.length;
int newCapacity = oldCapacity + (oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);
if (newCapacity - 2147483639 > 0) {
newCapacity = hugeCapacity(minCapacity);
}
this.queue = Arrays.copyOf(this.queue, newCapacity);
}
- 根据当前容量大小进行2倍或者1.5倍扩容
- 扩容操作执行为建立新容量的数组
public boolean remove(Object o) {
int i = this.indexOf(o);
if (i == -1) {
return false;
} else {
this.removeAt(i);
return true;
}
}
private E removeAt(int i) {
++this.modCount;
int s = --this.size;
if (s == i) {
this.queue[i] = null;
} else {
E moved = this.queue[s];
this.queue[s] = null;
this.siftDown(i, moved);
if (this.queue[i] == moved) {
this.siftUp(i, moved);
if (this.queue[i] != moved) {
return moved;
}
}
}
return null;
}
public E poll() {
if (this.size == 0) {
return null;
} else {
int s = --this.size;
++this.modCount;
E result = this.queue[0];
E x = this.queue[s];
this.queue[s] = null;
if (s != 0) {
this.siftDown(0, x);
}
return result;
}
}- remove删除指定的元素
- poll删除队首元素并返回
- remove和poll方法的思想类似，都是取出要删除的queue[i]元素，然后调用siftDown方法将最后一个元素插入到queue[i]下沉调整堆结构。removeAt方法中下沉失败时，执行上浮操作
public E peek() {
return this.size == 0 ? null : this.queue[0];
}- 直接返回队首元素，不改变队列本身
- 无element方法实现，被废弃
老师提供的刷题方法颠覆了我原来的思想，之前做题都是就算用暴力法也要自己想办法做出来，证明自己至少是有能力做这些题的。好不容易AC了以后已经精疲力尽了，然后去看别人的高票答案只是感慨一下别人的想法真厉害，然后没有精力再去深究了。 使用了五毒神掌以后，从一开始就能学到好的解法，然后把精力放到研究这些好的算法上来提升自我，并在做题的过程中觉得一直都有进步。
第一周坚持下来，开始的时候算了下总题量，同时考虑到第二天和一周后需要复刷题目，相当于从第二周开始每天的题量就是每天新题的三倍，所以我控制每天的题目在4题。每天学习新题需要花费的时间比较长，平均1题可能需要1个小时，同时如果遇到hard题， 时间会更长一点。所以难度高的题我会分散在不同的日子里。
希望自己继续加油！
| 题目编号 | 题目名称 | 难度 | 类型 | #1[实现/高票] | #2[优化] | #3[一天后] | #4[一周后] | #5[面试前一周] |
|---|---|---|---|---|---|---|---|---|
| 11 | container-with-most-water | Medium | Array | 0810/0810 | 0810/0810 | 0811/0811 | 0818/0818 | |
| 283 | move-zeroes | Easy | Array | 0810/0810 | 0810/0810 | 0811/0811 | 0818/0818 | |
| 70 | climbing-stairs | Easy | Array | 0810/0810 | 0810/0810 | 0811/0811 | 0818/0818 | |
| 15 | 3sum | Medium | Array | 0810/0810 | 0810/0810 | 0811/0811 | 0818/0818 |
时间标注为：计划时间/实际执行时间
| 题目编号 | 题目名称 | 难度 | 类型 | #1 | #2 | #3 | #4 | #5 |
|---|---|---|---|---|---|---|---|---|
| 206 | reverse-linked-list | Easy | Linked List | 0811/0811 | 0811/0811 | 0812/0812 | 0819/0819 | |
| 24 | swap-nodes-in-pairs | Medium | Linked List | 0811/0811 | 0811/0811 | 0812/0812 | 0819/0819 | |
| 141 | linked-list-cycle | Easy | Linked List | 0811/0811 | 0811/0811 | 0812/0812 | 0819/0819 | |
| 142 | linked-list-cycle-ii | Medium | Linked List | 0811/0811 | 0811/0811 | 0812/0812 | 0819/0819 |
| 题目编号 | 题目名称 | 难度 | 类型 | #1 | #2 | #3 | #4 | #5 |
|---|---|---|---|---|---|---|---|---|
| / | 用add first或add last这套新的API改写Deque的代码 | / | Queue | 0812/0811 | ||||
| / | 分析Queue和Priority Queue的源码 | / | Queue | 0812/0812 | ||||
| 25 | reverse-nodes-in-k-group | Hard | Linked List | 0812/0812 | 0812/0812 | 0813/0813 | 0820/0820 | |
| 20 | valid-parentheses | Easy | Stack | 0812/0812 | 0812/0812 | 0813/0813 | 0820/0820 | |
| 155 | min-stack | Easy | Stack | 0812/0812 | 0812/0812 | 0813/0813 | 0820/0820 |
| 题目编号 | 题目名称 | 难度 | 类型 | #1 | #2 | #3 | #4 | #5 |
|---|---|---|---|---|---|---|---|---|
| 84 | largest-rectangle-in-histogram | Hard | Stack | 0813/0813 | 0813/0813 | 0814/0814 | 0821/0822 | |
| 239 | sliding-window-maximum | Hard | Queue | 0813/0813 | 0813/0813 | 0814/0814 | 0821/0822 | |
| 26 | remove-duplicates-from-sorted-array | Easy | Array | 0813/0813 | 0813/0813 | 0814/0814 | 0821/0822 | |
| 189 | rotate-array | Easy | Array | 0813/0813 | 0813/0813 | 0814/0814 | 0821/0822 |
| 题目编号 | 题目名称 | 难度 | 类型 | #1 | #2 | #3 | #4 | #5 |
|---|---|---|---|---|---|---|---|---|
| 21 | merge-two-sorted-lists | Easy | Linked List | 0814/0814 | 0814/0814 | 0815/0815 | 0822/0823 | |
| 88 | merge-sorted-array | Easy | Array | 0814/0814 | 0814/0814 | 0815/0815 | 0822/0823 | |
| 1 | two-sum | Easy | Array | 0814/0814 | 0814/0814 | 0815/0815 | 0822/0823 | |
| 66 | plus-one | Easy | Array | 0814/0814 | 0814/0814 | 0815/0815 | 0822/0823 |
| 题目编号 | 题目名称 | 难度 | 类型 | #1 | #2 | #3 | #4 | #5 |
|---|---|---|---|---|---|---|---|---|
| 641 | design-circular-deque | Medium | Queue、Array | 0815/0815 | 0815/0815 | 0816/0816 | 0823/0823 | |
| 42 | trapping-rain-water | Hard | Array、Stack | 0815/0815 | 0815/0815 | 0816/0816 | 0823/0823 | |
| 146 | lru-cache | Medium | Linked List | 0815/0815 | 0815/0815 | 0816/0816 | 0823/0823 | |
| 299 | bulls-and-cows | Easy | Array | 0815/0815 | 0815/0815 | 0816/0816 | 0823/0823 |