学习总结
这一周重温了下数组、链表、队列、栈这几个数据结构。最重要的是要做题，从做题中总结技巧、经验。老师说的生维让我印象深刻，比如三数之和，不就是两数之和的升维吗？从宏观方面看代码，更有助于举一反三。
代码review
阅读645同学的代码，学到了合并两个链表引入空节点的方法和简明的循环队列的实现，也建议一些题目尝试更优的解法。
735同学，代码实现很规范。
370同学，代码逻辑很清晰。
685同学，代码很简洁。
705同学，代码格式良好易读。
时间复杂度
| 数据结构 |
prepend |
append |
lookup |
insert |
delete |
| linkedlist |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
| array |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
| stack |
- |
- |
O(n) |
O(1) |
O(1) |
| queue |
- |
- |
O(n) |
O(1) |
O(1) |
| 跳表 |
O(1) |
O(1) |
O(logn) |
O(1) |
O(1) |
题目
| 数据结构 |
题目 |
解题关键 |
完成遍数 |
| 数组 |
11.最大盛水容器 |
双指针，因为容器越长越好，不用考虑中间遮挡，i从0开始，j从n-1开始，每次循环计算最大面积，循环条件i<j，需要移动端点时，往中间移动高度较小的那个，尽量多实用高度较高的那个，两端收缩 |
4 |
| 数组 |
283.移动零 |
快慢指针，快指针用于遍历，快指针记录不为0的元素下一个位置，当i,j<n时循环，先一个while循环找出下一个不为0的元素，然后nums[j++]=nums[i++]，将最后一个非零位置值改成这个非零只，同时两个指针都自增，循环结束后j指示第一个应该放零的位置，循环直到n将元素改成0。需要注意的点：1.外循环条件别忘j<n。2.循环内部循环别忘判断数组边界。 |
3 |
| 数组 |
70.爬楼梯 |
从后往前状态记忆，数学归纳，dp[0]=1，dp[1]=1，return dp[n]。 |
3 |
| 数组 |
15.三数之和 |
排序+双指针，将数组排序用来去重，第一层循环遍历第一个元素，终止条件是i<n-2。因为三数相加为0,最小的数小于等于0，如果nums[i]>0 就跳出循环，另第一个元素去重，当nums[i]等于nums[i-1]，则continue。l=i+1, r=n-1分别作为第二三个元素索引，排序更方便检索两个值得和。当l<r，将三叔相加，如果结果是0，加入结果列表，之后分别将i和j自增和自减，随后两个while循环去重，当nums[l]等于nums[l-1]，l自增，当nums[r] = nums[r+1]，r自减。如果结果小于0，l自增，否则r自减。需要注意的点：1.第一个元素大约0的提前break。2.第一个元素也要去重。3.去重要在获取的结果后进行，否则可能漏掉结果。4.内层循环去重方法需要注意。5.去重循环不要忘了判断数组越界。 |
3 |
| 链表 |
206.反转链表 |
三个变量，pre，cur，next，next在反转时缓存；引入pre作为尾可为null，从前往后prepend。需要注意的点：1.循环条件是cur!=null，不是cur.next!=null。2.循环内部不要少了pre = cur。3.返回pre而不是cur。 |
3 |
| 链表 |
24.两两交换节点 |
方法1：三个变量：pre,a,b,引入缺失的pre作为头，为空节点，且将该节点同head相连，pre从dummy开始，a、b分别为每次交换时的第一、二个元素，每次交换完两个节点都把尾节点与后面的节点连起来，将pre改成尾节点，可通过pre.next和pre.next.next找到后面两个节点。方法2：与方法1类似，多加交换函数，在交换后多加一个同后面节点连接的操作，注意连接时是head.next=cur，不是pre，pre是交换后的头节点。在外层循环中，先保存头节点cur = pre.next，将pre.next连上交换后的头节点，再更新尾节点pre = cur，因为连接操作，当只剩一个节点时不用多余操作，因为已与前面连接起来。方法3：递归，最简洁，假设后面已经交换完成，前面的元素要做的是第一个节点的next指向交换好的头，第二个元素指向第一个元素，返回第二个元素。递归出口是只有一个元素或0个元素，即head==null或head.next=null。 |
3 |
| 链表 |
141.环形链表 |
快慢指针，注意判断条件，p和q都从head开始，因为q要移动两次，索引要判断p，q和q.next。 |
3 |
| 链表 |
142.环形链表2 |
快慢指针求交点，从head和交点两个同速指针，相遇点即交点。需要注意的点：1.第一步寻找交点一定要引入新变量，因为进入不了循环和从循环跳出是两回事。2.可能存在交点为Null的情况，提前返回。3.二次寻找交点的时候，由于头节点也可能是交点，先判断ps是否等于q。 |
3 |
| 链表 |
25.K个一组交换节点 |
方法1：循环翻转，循环条件pre1=null，同上一题，关键点是翻转后的尾节点要和后面连接起来。每次循环先判断是否还有K个元素，不满足则直接返回dummy.next。满足，则先保存头节点next = pre.next,pre.next = 以pre.next为开头翻转的头节点，因为原头节点已变成尾节点所以更改pre = next。对于k个元素翻转，循环K次后，别忘了head.next = cur连接后面元素。方法2：递归，递归出口是元素个数少于k个，跳出循环不交换，直接返回Head。第一步先找到k个节点之后的第一个节点，对这个节点作为头节点进行递归处理得到反转后头节点h，之后从当前第一个节点开始进行k次反转，反转后的最后一个节点即为head，head指向n，返回头节点即反转前最后一个节点pre。需要注意的点：第一步中指针右移的条件是p != null而不是p.next != null |
3 |
| 栈 |
20.合法括号 |
左括号入栈，右括号匹配出栈，优化点是记录左括号可用数量，左括号没超量才允许放左括号，否则返回false，优化效果不大。使用数组代替map效率会更高。需要注意的点：1.从queue里poll出来的元素可能为null，不能直接和字符比较，要先和null比较。2.左右括号没匹配上直接return false，不要break。 |
3 |
| 栈 |
155.最小栈 |
辅助栈记录当前最小值，主栈压入弹出和辅助栈同步。为了不适用多余map，当当前压入栈的值小于等最小值栈顶的值，则压入最小栈。弹出值时，吐过值等于最小栈栈顶的值，把最小栈也弹出。 |
3 |
| 栈 |
84.直方图最大矩形 |
入栈index，构造高度递增栈，当前高度小于栈顶元素高度时，对高度大于等于当前元素高度的索引循环出栈，计算栈顶索引高度，宽度为(i-栈顶第二元素索引-1)的栈顶索引为右边界的最大面积，对于剩余的元素，计算宽度为(n-栈顶第二元素索引-1)的矩形面积最大值。为什么栈内存的是右边界？因为当前面高度大于等于时会被弹出压入新值，该索引直到下一个元素索引之前的高度都满足最小高度。需要注意的点：1.栈是递增站。2.计算最大值时，对poll出来的元素，别忘计算高度。 |
5 |
| 双向队列 |
239.滑动窗口最大值 |
双向队列，队首为最大元素下标，入队一个元素，相应下标的队首元素出队，队尾元素入队前值小于或等于的元素下标从后面出队。需要注意的点：1.j结果数组长度需要注意，为n-k+1。2.提前准备0-k窗口的初始值，提高效率。3.入队元素不需要判断条件，元素从后面入队。4，窗口最大值为队首不是队尾。4.结果数组下标同数据数组下标的对应要注意，为n-k+1。5.第一个窗口只有一个结果元素，下标为0。6.使用arrayDeque比LinkedList速度快。 |
3 |
| 数组 |
26.删除重复元素 |
双指针：一个指针用来循环所有元素，j放不循环元素的下一个位置，当j>=1 && nums[i]==nums[j-1]，则跳过这个i，否则nums[j++] = nums[i++]。注意到i一直需要自增，且判断条件可以优化成不重复则放，而且只有一个元素需要额外判断索引，事实上第一个元素一定不重复。因此优化：i和j都从1开始，默认第一个元素已经放好，i改成for循环，当nums[i]!=nums[j-1]，则nums[j++] = nums[i]。 |
4 |
| 数组 |
189. 旋转数组 |
方法1：环状替换，从0开始，k-1结束，从前往后移动元素，每次移动都将目标位置更新为pre的值，在此之前保存该新位置的值，替换后更新pre为该值，下一个元素坐标为新位置索引。循环直到下一个需移动的索引回到了i的初始值。在每个k都形成闭环的情况下，需要k次循环，但没有闭环的话可能一次就替换完，索引引入count值，每次移动count++，for循环最后count==n的情况下，跳出循环。需要注意的点：1.需要临时变量保存目标元素值。2.需要count计数和判断。3.内层while循环使用do-while。2.翻转数组：先将整个数组翻转，再先将前k%n个元素翻转，再将后面的元素翻转，这里k%n是因为k可能大于n。需要注意的点：1，翻转长度需要%n，k>n时不能直接返回，也要移动。2.第一个翻转终点是k%n-1，不是(k-1)%n。 |
4 |
| 链表 |
21. 合并两个有序链表 |
引入一个head节点，循环指针p=head,当l1和l2都不等于null时，p.next更新为其中的最小节点，l1或l2后移，p后移。循环结束后，p.next指向l2和l2中不为null的那个，最后返回head.next。需要注意的的点：1.第一步循环别忘后移p指针。2.循环结束后不需要对多余的节点进行遍历，直接更新p.next即可。 |
4 |
| 数组 |
88. 合并两个有序数组 |
l从m+n-1位置开始递减，从后往前在两个数组中找最大值放在l的位置，直到两个数组中有一个用完。如果用完的nums2，那么nums1一定从来没移动过，数组已排序完整，不需要额外操作，否则，则nums1全比剩余nums2大，空出前面的位置把nums2剩余元素复制过去即可。复制的起始索引时0，复制的长度是j+1或l+1。 |
4 |
| 数组 |
1. 两数之和 |
hash表，记录当前索引需要被加数，key为被加数，值为索引，如果当前元素值在map的key中存在，就返回map值和当前索引作为元素的数组。将每个数组元素在循环中提前算出能加快速度。注意这道题用排序+双指针不行，因为这道题需要的是索引，不同索引的元素可能相同。 |
3 |
| 数组 |
66. 加一 |
因为是加1，考虑进位的时候只考虑9，进位后结果只可能是0。有两种清空：进位，当前位变成0，且可连续进位，最终不需要进位的位加1，这里还需要考虑需要加一位的情况；不进位，当前位加一。所以先用个while循环从后往前，将为9d的位全部变成0，跳出循环结束的当前位索引，如果是-1，说明需要扩展高位，返回一个长度为n+1，首尾为0的数组。否则，当前位加1，因为当前位可能是没有进过位的最低位，到此程序完。需要注意的点：第一个while循环要不断减不是假。2.需要加高位的条件是当前位索引是-1，不是0。3.最后当前位加一包括无进位的情况，不要多加1。 |
3 |
| 队列 |
641. 设计循环双端队列 |
数组实现循环队列，可增加计数器记录size，也可在初始化数组时capacity增加1，这样队列为空和队列满将不是同一个条件，另数组下标直接引用赋值结果会让运行速度变快；也可设置队列数组时多余一个长度，用于判断队列空（tail在head相邻的后面），满的条件是(tail-head+capacity+1)%(capacity+1)==capacity-1，这样就不需要额外的长度变量 |
2 |
| 栈 |
42. 接雨水 |
构造高度递减栈，每个元素作为右边界，从栈中弹出高度小于当前高度的元素高度作为水坑底，下一栈顶元素作为左边界，（min(左边界，当前高度)-弹出高度)*(当前序号-左边界-1)加入和。当前序号（左边界或计算过的高度）入栈 |
2 |
Deque代码改写
Deque<String> deque = new LinkedList<String>();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);
String str = deque.getFirst();
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
参考文章：Java ArrayDeque源码剖析
Queue是队列的接口，其实现接口有Deque。Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Queue相对应的接口：
| Queue Method |
Equivalent Deque Method |
说明 |
add(e) |
addLast(e) |
向队尾插入元素，失败则抛出异常 |
offer(e) |
offerLast(e) |
向队尾插入元素，失败则返回false |
remove() |
removeFirst() |
获取并删除队首元素，失败则抛出异常 |
poll() |
pollFirst() |
获取并删除队首元素，失败则返回null |
element() |
getFirst() |
获取但不删除队首元素，失败则抛出异常 |
peek() |
peekFirst() |
获取但不删除队首元素，失败则返回null |
下表列出了Deque与Stack对应的接口：
| Stack Method |
Equivalent Deque Method |
说明 |
push(e) |
addFirst(e) |
向栈顶插入元素，失败则抛出异常 |
| 无 |
offerFirst(e) |
向栈顶插入元素，失败则返回false |
pop() |
removeFirst() |
获取并删除栈顶元素，失败则抛出异常 |
| 无 |
pollFirst() |
获取并删除栈顶元素，失败则返回null |
peek() |
getFirst() |
获取但不删除栈顶元素，失败则抛出异常 |
| 无 |
peekFirst() |
获取但不删除栈顶元素，失败则返回null |
上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（false或null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。
ArrayDeque和LinkedList是Deque的两个通用实现，官方更推荐使用AarryDeque用作栈和队列。
从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。
addFirst()
addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[--head] = e即可。
实际需要考虑：1.空间是否够用，以及2.下标是否越界的问题。上图中，如果head为0之后接着调用addFirst()，虽然空余空间还够用，但head为-1，下标越界了。下列代码很好的解决了这两个问题。
//addFirst(E e)
public void addFirst(E e) {
if (e == null)//不允许放入null
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
if (head == tail)//1.空间是否够用
doubleCapacity();//扩容
}上述代码我们看到，空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。
下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于取余，同时解决了head为负值的情况。因为elements.length必需是2的指数倍，elements - 1就是二进制低位全1，跟head - 1相与之后就起到了取模的作用，如果head - 1为负数（其实只可能是-1），则相当于对其取相对于elements.length的补码。
下面再说说扩容函数doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。
复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。
//doubleCapacity()
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边元素的个数
int newCapacity = n << 1;//原空间的2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
elements = (E[])a;
head = 0;
tail = n;
}addLast()
addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail总是指向下一个可以插入的空位，因此只需要elements[tail] = e;即可。插入完成后再检查空间，如果空间已经用光，则调用doubleCapacity()进行扩容。
public void addLast(E e) {
if (e == null)//不允许放入null
throw new NullPointerException();
elements[tail] = e;//赋值
if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
doubleCapacity();//扩容
}pollFirst()
pollFirst()的作用是删除并返回Deque首端元素，也即是head位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。
public E pollFirst() {
E result = elements[head];
if (result == null)//null值意味着deque为空
return null;
elements[h] = null;//let GC work
head = (head + 1) & (elements.length - 1);//下标越界处理
return result;
}pollLast()
pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
E result = elements[t];
if (result == null)//null值意味着deque为空
return null;
elements[t] = null;//let GC work
tail = t;
return result;
}peekFirst()
peekFirst()的作用是返回但不删除Deque首端元素，也即是head位置处的元素，直接返回elements[head]即可。
public E peekFirst() {
return elements[head]; // elements[head] is null if deque empty
}peekLast()
peekLast()的作用是返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。
public E peekLast() {
return elements[(tail - 1) & (elements.length - 1)];
}PriorityQueue
参考文章：深入理解Java PriorityQueue
优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。
add()和offer()
add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。
新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整。
//offer(E e)
public boolean offer(E e) {
if (e == null)//不允许放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自动扩容
size = i + 1;
if (i == 0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i, e);//调整
return true;
}上述代码中，扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(int k, E x)方法，该方法用于插入元素x并维持堆的特性。
//siftUp()
private void siftUp(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
element()和peek()
element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。
代码也就非常简洁：
//peek()
public E peek() {
if (size == 0)
return null;
return (E) queue[0];//0下标处的那个元素就是最小的那个
}remove()和poll()
remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
代码如下：
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];//0下标处的那个元素就是最小的那个
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);//调整
return result;
}上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）。重点是siftDown(int k, E x)方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
//siftDown()
private void siftDown(int k, E x) {
int half = size >>> 1;
while (k < half) {
//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
int child = (k << 1) + 1;//leftNo = parentNo*2+1
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;//然后用c取代原来的值
k = child;
}
queue[k] = x;
}remove(Object o)
remove(Object o)方法用于删除队列中跟o相等的某一个元素（如果有多个相等，只删除一个），该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。具体来说，remove(Object o)可以分为2种情况：1. 删除的是最后一个元素。直接删除即可，不需要调整。2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。
具体代码如下：
//remove(Object o)
public boolean remove(Object o) {
//通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
int i = indexOf(o);
if (i == -1)
return false;
int s = --size;
if (s == i) //情况1
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//情况2
......
}
return true;
}
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent