Queue实现分为general-purpose（通用实现？中文该这么翻译？）和 concurrent implementation并发实现。

通用队列实现：
LinkedList实现了Queue接口，为add ， poll提供了先进先出（FIFO）队列操作。

PriorityQueue类是基于堆数据结构的优先级队列。 此队列根据构造时指定的顺序对元素进行排序，这些顺序可以是元素的自然顺序，也可以是 Explict Comparator施加的顺序。

队列检索操作（ poll ， remove ， peek和element ）访问队列开头的元素。 相对于指定的顺序，队列的开头是最小的元素。 如果多个元素的价值最小，那么head是这些元素之一。

PriorityQueue及其迭代器实现Collection和Iterator接口的所有可选方法。迭代器方法中提供的iterator不能保证以任何特定顺序遍历PriorityQueue的元素。 对于有序遍历，请考虑使用Arrays.sort(pq.toArray()) 。

并发队列实现：
java.util.concurrent包包含一组同步的Queue接口和类。 BlockingQueue扩展了Queue的操作，这些操作等待检索元素时队列变为非空，并等待存储元素时队列中的空间变为可用。 该接口由以下类实现：
LinkedBlockingQueue —由链接节点支持的可选有界FIFO阻止队列
ArrayBlockingQueue —由数组支持的有界FIFO阻塞队列
PriorityBlockingQueue —由堆支持的无界阻塞优先级队列
DelayQueue —由堆支持的基于时间的调度队列
SynchronousQueue —使用BlockingQueue接口的阻塞队列机制

新的认识

- 五遍法刷新了自己对算法学习的认识,需要多多实践验证

学习和解题

每道题的第一次完解控制在1h
1. 审题,理解题意
2. 先问自己,这个问题属于哪类算法问题?
1. 列出所有可能得算法,每种方法的时间复杂度
2. 要将不熟悉的题转换成熟悉的题(比如:三数求和—>2数求和—>双指针)
3. 再思考并写下所给条件中有哪些性质是可以利用的?
1. 比如题中有序数组的有序就是一个可以利用的条件)
2. 比如题中是否存在,就联想到哈希表的数据结构
4. 这类算法问题通常的解题思路?
1. “解决链表问题最好的办法是在脑中或者纸上把链表画出来”
2. 数组—>双指针
5. 以上4点需要在15min 内完成
6. 先用伪代码写出逻辑，再补全小段代码
7. 找重复性(重复单元)
8. notion记录自己的解题过程(这一点很重要,可以发现自己的缺陷,方便日后对景对情),和最优解做对比
9. 将不同的解法,制成anki 卡片记录
1. 搜索优质解题方法和思路(博客,leetcode 国际站)
2. 制作 gif 图片
10. 五遍刷题法,重写所有的解法

Queue 源码分析

1. Java 中的 Queue是一个接口,继承了 Collection 接口,支持泛型

2. 按Queue中元素的顺序特点分类

   1. FIFO (first-in-first-out) manner
   2. priority queues
   3. 其它(LIFO)

3. add 方法和 offer 方法的区别

   • 队列没有空间时,两个方法的表现不一样,add 会抛异常,add 适合有界队列,offer 可能会扩容(看具体实现)

4. remove 和 poll 的区别

   • 队列为空时 remove 方法抛出异常,poll 不抛异常

5. element 和 peek 的区别

   • 队列为空时 element 方法抛出异常,peek 不抛异常

6. Queue 的特点

   1. Queue接口没有定义阻塞队列方法(并发编程)
   2. Queue 中不推荐插入 null 元素

PriorityQueue源码分析

1. 使用改数据结构(容器)的限制

   1. 容器中的元素都是可比较的(Java 中实现 Comparable 接口)
   2. 不允许 null 元素

2. PriorityQueue优先队列特点

   1. A priority queue is unbounded(无界队列)—>自动扩容
   2. 线程不安全

3. 不同构造函数

   1. 基于优先堆
   2. 基于队列 queue

第 1 周 第 3 课 | 数组、链表、跳表
数组 Array
时间复杂度 prepend O(1) append O(1) lookup O(1) insert O(n) delete O(n)
LeetCode
https://leetcode-cn.com/problems/container-with-most-water/
https://leetcode-cn.com/problems/move-zeroes/
https://leetcode.com/problems/climbing-stairs/
https://leetcode-cn.com/problems/3sum/

链表 Linked list
链表不需要连续的内存空间，通过指针将零散的内存块串联起来使用​
时间复杂度 prepend O(1) append O(1) lookup O(n) insert O(1) delete O(1)

常见的链表结构
单链表
双向链表
循环链表
常见的缓存策略
先进先出 FIFO(First In, First out)
最少使用 LFU(Least Frequently Used)
最近最少使用 LRU(Least Recently Used)

LeetCode
https://leetcode.com/problems/reverse-linked-list/
https://leetcode.com/problems/swap-nodes-in-pairs
https://leetcode.com/problems/linked-list-cycle
https://leetcode.com/problems/linked-list-cycle-ii
https://leetcode.com/problems/reverse-nodes-in-k-group/

跳表 Skip list
升维**，空间换时间
把链表变成二维空间，使用了更多的索引节点
跳表的时间复杂度与红黑树一致，但是实现起来更简单
在并发环境下跳表有另一个优势，红黑树在插入和删除的时候可能需要做 rebalance 操作，可能会涉及到整个树的其他部分，而跳表的操作更局部一些，锁住的节点更少，这样性能会更好一些

第 1 周 第 4 课 | 栈、队列、优先队列、双端队列
栈 Stack
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许再一端插入和删除数据。栈主要包含连个操作，入栈和出站，也就是在栈顶插入一个数据和从栈顶删除一个数据
先进后出，后进先出
栈的实现
用链表实现的栈，叫链式栈
用数组实现的栈，叫顺序栈
时间复杂度
access O(n) search O(n) insert O(1) delete O(1)

队列 Queue
先进先出，后进后出
时间复杂度 search O(n) access O(n) insertion O(1) deletion O(1)

双端队列 Deque: Double-End Queue
双端队列可以在队首添加/删除元素，也可以在队尾添加/删除元素在实际应用中，一般使用双端队列替代普通队列​
Queue 和 Stack 的结合体
时间复杂度 access O(n) search O(n) insertion O(1) deletion O(1)

优先队列 PriorityQueue
时间复杂度
insert O(1)
pop O(logN) // 按照优先级取出

数组

一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据

• 线性表
• 连续的内存空间和相同类型的数据
  • 随机访问 O(1)
  • 插入、删除低效 O(n)
  • 查找 O(logn)

链表

• 单链表
  • 随机访问 O(n)
  • 插入、删除低效 O(1)
• 循环链表
• 双向链表
  • 用空间换时间
• 对比

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统肯呢个没有足够的连续内存空间分配给它，导致内存不足。如果声明的数组过大小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。

如果代码对内存使用非常苛刻，数组更适合。因为链表中每个节点都需要消耗额外的存储空间去存储一份指向下一个节点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片。

关于跳表的理解
本周对相对陌生的跳表进行总结，以掌握**为主，通过课上学习和查找相关材料，总结内容包括：
1、跳表的定义；
2、跳表的相关操作及实现思路；
3、跳表的应用；

第一部分：跳表的定义

跳跃表（Skip List）是1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除等操作
时的时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较
同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优
势。
1、跳跃表的结构
跳跃表由多条链构成（S0，S1，S2 ……，Sh），且满足如下三个条件：
（1）每条链必须包含两个特殊元素：+∞ 和 -∞；
（2）S0包含所有的元素，并且所有链中的元素按照升序排列；
（3）每条链中的元素集合必须包含于序数较小的链的元素集合。
2、跳跃表的时间及空间复杂度
空间复杂度： O(n)
时间复杂度：
(1)查找： O(logn)
(2)查找： O(logn)
(3)删除： O(logn)

第二部分：跳表的相关操作及实现思路

操作包括查找、插入、删除，各操作实现思路如下：
1、查找
在跳跃表中查找一个元素x，按照以下步骤进行：
从最上层的链（Sh）的开头开始
假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较
x=y 输出查询成功，输出相关信息
y<x 从p向右移动到q的位置
y>x 从p向下移动一格
如果当前位置在最底层的链中（S0），且还要往下移动的话，则输出查询失败。

2、插入
在跳跃表中插入一个元素x，按照以下步骤进行：
插入的位置和插入对应元素。
当我们往跳表中插入数据的时候，我们可以通过一个随机函数，来决定这个结点插入到哪几级索引层中，随机函数的选择是非常有讲究的，从概率上讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能的过度退化。
至于随机函数的选择，见下面的C++代码实现：
/***** 随机函数起始********/
private int randomLevel()
{
int level = 1;
for(int i = 1; i < MAX_LEVEL; ++i)//MAX_LEVEL为链条数
{
if(random.nextInt() % 2 == 1){
level++;
}
}
return level;
}
/****** 随机函数结束********/
3、删除
从跳跃表中删除一个元素x，按照以下步骤进行：
1）在跳跃表中查找到这个元素的位置，如果未找到，则退出
2）将该元素所在整列从表中删除
3）将多余的“空链”删除

第三部分：跳表的应用

使用跳跃表的产品：
1、Lucene, elasticSearch
2、Redis：
Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的 是所有的成员，排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。

写在最后

 1、要深刻理解跳表，需要自己动手用代码实现一遍，这个暂且搁置后续实现；
 2、leetcode涉及跳表题目：1206 设计跳表；

本周感想：算法学习方法的探索
覃超老师说过算法学习需要刻意练习，印象最深的就是“五毒神掌”，相同的题目要不断的刷。道理很简单，但真正做到有难度，因为工作较忙，结合实际情况，只能减少遍数，我的算法学习步骤大致计划如下：
1、覃超老师的在线课程先听一遍，在听的过程中，涉及算法例题讲解的部分，自己同步在纸上写思路，和手写源码；
注：第一遍主要是完成课程，了解知识点。
2、听完在线课程后，针对例题和练习题，学习leetcode上经典题解，每题在IDE里至少两种解法编写，提交leetcode；
注：第二遍主要是刻意练习，巩固知识点。
3、对于做过的题目，跳出自己认为难理解、容易忘的题目再次IDE里编写，提交leetcode；
注：第三遍主要是查漏补缺，掌握知识点。

标题格式：【学号后三位+week1】（如果是第二周就是week2，以此类推）+文章标题

正文部分，字数不限。

时间复杂度空间复杂度表

数据结构操作

数据结构|访问（平均）|搜索（平均）|插入（平均）|删除（平均）|访问（最差）|搜索（最差）|插入（最差）|删除（最差）|空间复杂度
:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
Array|O(1)|O(n)|O(n)|O(n)|O(1)|O(n)|O(n)|O(n)|O(n)
Singly-Linked List|O(n)|O(n)|O(1)|O(1)|O(n)|O(n)|O(1)|O(1)|O(n)
Doubly-Linked List|O(n)|O(n)|O(1)|O(1)|O(n)|O(n)|O(1)|O(1)|O(n)
Skip List|O(log(n))|O(log(n))|O(log(n))|O(log(n))|O(n)|O(n)|O(n)|O(n)|O(nlog(n))
Stack|O(n)|O(n)|O(1)|O(1)|O(n)|O(n)|O(1)|O(1)|O(n)

用 add first 或 add last 这套新的 API 改写 Deque 的代码

//简单使用单链表实现，也可以使用双向链表实现
private Node head; //头的节点
    private int size; //当前元素的数量

    public LinkedDeque(int length){
        head = new Node(null);
        this.size = 0;
    }

    @Override
    public void addFirst(Object o) {
        Node newNode = new Node(o);
        if(head.next != null){
            newNode.next = head.next;
        }
        head.next = newNode;
    }

    @Override
    public void addLast(Object o) {
        Node newNode = new Node(o);
        Node tmp = head;
        for (int i = 0; i < size; i++) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
    }

    private class Node<T> {
        Node next;
        T value;

        private Node(T value){
            this.value = value;
        }
    }

学习方法和内容总结

• 首先是解题的五毒神掌
• 实际操作上在第一遍的时候：首先枚举出可能的思路写下来，然后每个方法写一遍之后再进行复杂度分析
• 一般的方法是：暴力法，可以通过基本情况枚举也就是找到重复子，然后就是递归和loop
• 对于最近相关性问题一般使用栈这个数据结构来解决，如：对括号对称性问题
• 一个核心**是：用空间换取时间
• 对于双层for循环中的：夹逼，从中间到两端，追赶遍历都要非常熟练的写出来
• 对于接触到一个新的题目首先是用五到十分钟看一遍题目，没有思路就直接看解法，看了解法之后就自己写，把-cn去掉之后再看前三名答案仔细理解体会，务必做五遍

时间安排

每一个老师讲解的题目：听讲解，自己作答，看别人解法，自己写出来，优化自己的解法，基本上一个算法题大概需要花费一个小时的时间，虽然周末两天基本上没有怎么休息，都是再搞算法，下面就把时间平均在每天里面去完成下个周的作业，挤在周末完成时间太赶

我的问题

我是一名前端，对于栈和队列的学习和练习，老师能不能给一个方向性的指导呢？

1. 数组 链表 跳表

• 跳表是接触到的新知识点 实际工作中也较少用到 用空间换时间的概念非常印象深刻
• 练习题中对于数组的应用 练习题26 去除数组中重复元素的地方 除了课堂上学习的双指针的**，看了其他解答中学习到的一点新的思考是：假如数组中没有一个重复元素 按照解答的逻辑走下来就会产生元素无谓的移动。于是增加判断是否两个不同的元素是相邻的。方法贴在下面。
  public int removeDuplicates(int[] nums) {
  int i = 0;
  for(int j = 1; j < nums.length; j++){
  if(nums[i] != nums[j]){
  if(j - i > 1){
  nums[i+1] = nums[j];
  }
  i++;
  }
  }
  return i+1;
  }

2. 栈 队列 优先队列 双端队列

• 这一部分平时有用到具体实现但没有仔细考虑过内部的原理及其效率问题 是需要加强的地方
• 练习题也是 会很难想到利用栈和队列的** 现在通过课程学习掌握到的是：需要配对的问题 类似四则运算，括号匹配的问题可以用栈的思维考虑
• 栈和队列可以互相转化：双栈转化为队列 双队列转化为栈
• 队列的实际应用还需要加强练习

源码分析

Python 的deque双端队列

Python 中没有queue数据结构，有双端队列 deque

用list实现简单的队列queue

class Queue:

    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    def size(self):
        return len(self.queue)

用list实现一个简单stack栈

class Stack:

    def __init__(self):
        self.stack = []

    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()

    def push(self, item):
        self.stack.append(item)

    def size(self):
        return len(self.stack)

python collections包里面的deque

官方文档
源码位于：Modules/_collectionsmodule.c
能力有限，不太能看懂c
deque 是 Python 中的一个双端队列，deque 来源于 double-ended queue 的缩写，写作 deque 读作 deck。对于常见的数据结构 list 来说，下标为 0 的 push 和 pop 操作需要移动整个 list。而 deque 则不需要。并且它是线程安全的。除此之外还能为其设置 max-length，当 deque 满时，会自动丢弃相反一端的元素
------Python deque 源码分析

Python heapq--- 堆队列算法（Priority Queue）

官方文档
源码：Lib/heapq.py
每次增加/删除元素都会重新建堆

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem



def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

作业：绘制自己的数据结构和算法脑图

要求：用脑图的方式把知识的脉络串联起来，不管对于学习新知识还是巩固已有知识，都是一种很好的学习方式。同学们可以将目前自己所掌握的数据结构和算法知识绘制成脑图，在绘制过程中可以查阅资料，补充目前掌握欠缺的部分，找到自己薄弱的地方。后面再通过课程的学习和刻意练习，动态地将自己绘制的脑图逐步补充、完善，从而达到真正的融会贯通。

脑图绘制工具不限。

• 双指针法在解决数组和链表相关问题有神奇作用
• 看题解和国际站的讨论，真的太关键太关键了
• 很多题回过头再做的时候，发现即使之前会了，放下一段时间还是会忘。要刻意的多练习

学习方法总结

本周最大的收获是掌握了一套学习方法，深刻领悟了刻意练习的重要性，这些方法不仅用于学习本次训练营，同时适用于学习其他技能，结合自己的经历和理解总结如下：

1、确定学习目标

确定学习目标，并通过查询资料分析自己达成目标需要掌握的知识点

2、切碎知识点

2.1、庖丁解牛

将知识点进行分解，将大问题变成小问题，将复杂的问题变成简单的问题，方便理解学习。

2.3、脑图

使用脑图将所有知识点关联起来形成脉络图，方便整体连通理解，实现学习目标。同时可以加强记忆，人脑更加容易记住脑图类型的知识结构。

3、刻意练习

这个和10000小时法则是相通的，过去人们过于看中一个人天赋，聪明度的重要性，其实后天的练习更加重要，几乎所有竞技类的职业化选手都是不断反复的刻意练习才获得成功的。

3.1、过遍数

对拆解后的知识点，进行专项刻意练习，比如乒乓球练习，分解每个动作进行反复练习，直到把他变成你的肌肉记忆。
关于数据结构和算法，老师给出了“五毒神掌”的练习法则

• 第一遍：五分钟读题思考->看解法->背诵默写优秀解法
• 第二遍：自己写，多种解法比较、体会、优化
• 第三遍：一天后重复做题，不同解法专项练习
• 第四遍：一周后反复练习相同题目
• 第五遍：面试前一周恢复性训练

通过多次反复练习，达到熟能生巧。

3.2、练习缺陷、弱点地方

针对自己弱势，更加应该反复练习，这个时候会不舒服、不爽，但疼苦就是成长的过程，克服了就你进步了。

4、反馈

4.1、即时反馈

就像在游戏里每做完一个任务都能达到反馈，即时反馈能帮助获得成就感，更好的坚持下去。 我们也可以把我们切碎的知识点分成一个个小任务，每完成一个就可以给自己一些激励。比如刷题，如果提交后看到你击败了80%的人，成就感就会有。另外也可以给自己一些物质奖励，比如完成了什么任务就吃顿大餐，买个什么礼物奖励自己。

4.2、主动型反馈

自己去看行业大牛门是怎么做的，比如看别人的代码，看大神的直播等，通过向大神学习，找到自己的不足，取长补短。

4.3、被动式反馈

任务完成后，找高手来帮忙指点，看那方面做的不足。

5、总结分享

如果学完后自己能把相关收获进行总结梳理，并分享给别人，让别人一起收获，不但能加强自己对知识的理解，同时可以提升自己的影响力

Hi各位同学，俗话说“三人行，必有我师”，因此我们鼓励大家在整个学习期间，多多 Review 同班同学的代码并进行点评。在这个过程中：

• 可能你会从其他同学的代码中学到一个更优的思路
• 可能你会因为其他同学给你的评论启发新的灵感
• 可能你的代码会得到大家纷纷的点赞
• 有时候也可能因为其他小伙伴的一句“学习了”而备受鼓舞

“让优秀的人一起学习”，大家可以在互相 Review 的过程中思考更多、获得更多。因此，请把你的算法题作业链接（你自己仓库的链接就好）回复在下面，这样大家就可以更方便的进行代码 review 啦！

跟帖格式：

学号后三位：
姓名（你在班里的姓名，便于同学可以跟你讨论）：
你的代码链接：

第一周作业总结

练习过的题目

1. LC_01_TwoSum
   • 在思考思路的时候，因为之前老师讲解过，可以使用双指针的方式去将双循环将为单循环，
     但是最后考虑到，如果需要排序的话，那么返回的数组下标将不准确, 所以如果用这种双指针法去降低时间复杂度，
     还需要使用数组或者哈希辅助记录原来元素的数组，在确定目标数据之后，再取出元素的旧下标，返回；
     这样就是牺牲空间复杂度，来换取时间(也有可能会带来源码层面更大的时间复杂度消耗),故此路不通
   • 另外，在leetcode的国内站点或者国际站都出现用辅助哈希来降低时间复杂度为O(n), 但是这种解法的时间复杂度
     并不为O(n), 在计算时间复杂度的时候，直接忽略了jdk源码处理哈希所带来的消耗
2. LC_11_ContainWithMostWater
   • 解法除了暴力枚举，还用到了双指针法，从边界遍历夹逼，寻找目标元素输出；并且双边指针也是根据计算结果来动态移动，
     这种方式比较巧妙
3. LC_15_ThreeSum
   • 3sum的暴力枚举写出来的代码超出来leetcode的时间限制
   • 双指针法将O(n^3)的复杂度将为O(n^2); 我觉得其中巧妙的地方处理使用双指针的方式去寻找元素之外，
     还有就是在双边指针移动的时候，很巧妙的利用了java运算的方式去避免相同值的元素重复计算while (i < j && nums[i] == nums[++i]);
4. LC_26_RemoveDuplicatesFromSortedArray
   • 使用指针标记确认了非重复元素的位置，并在符合条件的时候，往后移动这个指针，数据只变更标记后面的元素信息；
     题目要求直接返回非重复元素的个数，所以直接将这个指针+1返回即可
5. LC_70_ClimbingStairs
   • 爬楼梯是一个涉及到动态规划的问题，这个题目对动态规划对感受不是很深，
     所以对斐波那契数列的规则计算的方式比较容易理解；而动态规划的算法，后面需要更加深刻的理解并练习
6. LC_283_MoveZeroes
   • 移动0位置这道题，当初自己写的时候，使用了swap来对调两个元素的位置，但是其实看了discuss之后，发现主要关注非0元素位置即可，而0元素位不需要处理

个人总结

• 在预习周学习了刷题技巧之后，本周跟着老师的课程，实战进入了leetcode的刷题状态，避免了像以前一样，
  一道题看了题目之后，就埋头思考解法，结果耗费了很多时间，产生了自己一定要解出来，不然就是能力的问题，
  就这样陷入了死胡同，一直以来的挫败感压抑着，心中产生了对刷题特别是算法题的畏惧；而这两周的刷题技巧实战，
  让我纠正了这种心理
• 另外针对解题技巧，也积累了万能的暴力循环法、双指针法、还有遇到没头绪的题目可以用列举进行归纳找规律等思路，很受用
• 不过，反思了一下这周的算法学习以及刷题时间，这周自己都是在晚上十点以后，或者周末这种能够有大片时间的时段来学习及刷题
  这样的话，既然自己无法利用碎片时间让自己学习，那就合理安排这种一大段时间来系统学习算法，只有这样静下来连续学习，
  才能系统的建立自己的知识架构；希望这个可能让我养成这个习惯，以后运用到别的专业知识的学习上

第一周学习的是最基础的数据结构
数组, 链表, 栈, 队列

第一周课程过后, 深刻体会到, 算法主要还是一些套路, 和一些分析问题的套路.老师讲的几点对以后的工作生活应该都是受益终生的.

1. 切题四件套
2. 5遍刷题法(刻意练习)
3. 拿到一个问题, 懵逼的时候 先想想暴力的方法, 或者从基本情况出发, 由此再来优化问题的解法(找最近重复的子问题)
4. 一道题确实非常忌讳只刷一遍, 需要不停地寻求反馈, 还有尝试写出各种可能的解法

把目前了解的数据结构和算法有关的内容以脑图的形式记录在了我的文件夹（id_441）中。用vscode打开的话需要安装一个名为vscode-mindmap的插件来支持.km后缀的文件。

 本周作为算法训练营的预习周，通过仔细学习了覃超老师的3个预习性视频，深有体会，主要有以下几点：

1. 数据结构和算法脑图，在没有查看老师给出的脑图之前，我自己画了自己知道数据结构和算法的脑图(脑图已经提交【 pull request】)，然后对比了老师给出的脑图，发现自己虽然数据结构掌握的比较全面，但是数据结构运用在算法上面还是很欠缺的。
2. 学习了刷题五步法：

• 第一步：用5-15分钟对题目进行思考，想出头绪
  • 如果5-15分钟还没想出头绪，那么直接看答案，理解答案并背诵
• 第二步：关闭答案，自己写程序，直到测试通过
• 第三步：第二天对前一天的程序进行重新写
• 第四步：一周后对程序进行重新写
• 第五步：面试准备前半周或者一周，对题目进行重新写

3. 切题四件套：

• 读懂题目，理解题目，和面试官做好足够的沟通，防止自己对题意误解
• 想出所有能想到的解法
  • 分析时间/空间复杂度
  • 选出最优解法
• 写程序
• 写测试样例进行测试

4. 老师提供了mac上面的很好的工具建议，通过视频我安装了iTerm2 + Oh My Zsh的终端，现在自己mac上的终端比系统提供的好用多了
5. 关于IDE，我之前一直使用IDEA，通过学习，我安装了Vscode，并在Vscode安装了leetcode的插件，并对插件功能进行简单的研究。现在可以在Vscode方便的刷题了。
6. 关于code style和IDE的top tip，对之前掌握的进行查漏补缺，工欲善其事必先利其器。
7. 老师讲解的自顶向下的编程方式，结合自己工作中的编程方法，的确，只有自顶向下的编程，才能让代码的BUG减少，并具有更高可阅读性和维护性。
8. 最后是时间复杂度的开篇介绍，通过开篇的预习热身，希望在后面每个专题里面，对算法的时间和空间复杂度做更加全面的掌握，并能在写算法题的时候，对每种不通解法寻求最优时间复杂度。

开学预习周，虽然说是预习，但是内容也是非常重要的。老师的3个视频，让我补充了之前没有接触过的方面的开发方面的东西。加油~！

本周主要是学习简单的链表，数组，队列，栈等比较初级的数据结构，我最大的收获其实应该是获得了一些刷题时候的经验，有些代码的小技巧都是通过老师讲课，或者看别人的更优解法得到的，有时候会感慨有些**的确自己想不到，非常的巧妙；但是我认为主要原因还是积累得不够多，以后加强积累的深度和熟练度，应该也能达到举一反三的效果。

1. 最大的困难： 克服自己，利用自己的零碎时间。 平时时间再忙也要坚持学习。 刚开始学习肯定是很难得，所以需要克服内心的挫折感。
2. 怎么学习： 学习还是靠自己。 google + 题解 + 5遍做题法
3. 优化**： a. 升维 b.空间换时间
4. 解题思路： 寻找重复性的子问题。

要求

1. 每周从覃超老师布置的题目中，至少完成并提交两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章或总结，切忌流水账。

作业提交 Deadline

2019年10月20日 23:59 （以当地时间为准）
未按时提交作业，会在个人作业总分钟 -3 分

本周作业概述

本周需要完成学习的视频内容：

• 第 3 课 | 数组、链表、跳表
• 第 4 课 | 栈、队列、优先队列、双端队列

以上两课视频后，覃超老师都给出了大家可以练手的算法题。

其中，第 4 课的课后作业（第2节视频后）还包括：

• 用add first或add last这套新的API改写Deque的代码
• 分析Queue和Priority Queue的源码

请大家将此部分作业，放在本周学习总结中一并提交

本周算法习题库：

第三课课后习题：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
https://leetcode-cn.com/problems/rotate-array/
https://leetcode-cn.com/problems/merge-two-sorted-lists/
https://leetcode-cn.com/problems/merge-sorted-array/
https://leetcode-cn.com/problems/two-sum/
https://leetcode-cn.com/problems/move-zeroes/
https://leetcode-cn.com/problems/plus-one/

第四课课后习题：

https://leetcode.com/problems/design-circular-deque
https://leetcode.com/problems/trapping-rain-water/
用add first或add last这套新的API改写Deque的代码
分析Queue和Priority Queue的源码

改写代码和分析源码这两项作业，需要在你的本周学习总结中一并提交。

1. 数组 链表 跳表

• Array
  时间复杂度 prepend O(1) append O(1) lookup O(1) insert O(n) delete O(n)

• Linked list
  链表需要额外内存空间，通过指针串联数据。
  时间复杂度 prepend O(1) append O(1) lookup O(n) insert O(1) delete O(1)
  常见的链表结构
  单链表
  双向链表
  循环链表

• 常见缓存策略
  先进先出 FIFO(First In, First out)
  最少使用 LFU(Least Frequently Used)
  最近最少使用 LRU(Least Recently Used)

• 跳表
  通过增加索引，加快查询效率，是一个空间换时间的做法。
  复杂度：search O(logn)，更新索引分为两部分，删除、修改为O(1)，但是需要先查询，所以总的时间复杂度为O(logn)
  应用场景：redis->zset

• 数组，链表题目，解法思路收集：
  1.前后夹击，双指针
  2.快慢循环，双指针
  3.利用额外内存空间记录（哈希）
  4.递归
  5.栈解法，利用栈特性
  6.跳跃循环 ->https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/fei-di-gui-ba-kge-jie-dian-kan-zuo-yi-ge-zheng-ti-/

2.栈、队列、优先队列、双端队列

• 栈 Stack
  从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许再一端插入和删除数据。栈主要包含连个操作，入栈和出站，也就是在栈顶插入一个数据和从栈顶删除一个数据
  先进后出，后进先出
  栈的实现
  用链表实现的栈，叫链式栈
  用数组实现的栈，叫顺序栈
  时间复杂度：access O(n) search O(n) insert O(1) delete O(1)

• 队列 Queue
  先进先出，后进后出
  时间复杂度 search O(n) access O(n) insertion O(1) deletion O(1)

• 双端队列 Deque: Double-End Queue
  双端队列可以在队首添加/删除元素，也可以在队尾添加/删除元素在实际应用中，一般使用双端队列替代普通队列​
  Queue 和 Stack 的结合体
  时间复杂度 access O(n) search O(n) insertion O(1) deletion O(1)

• 优先队列 PriorityQueue
  时间复杂度 insert O(1) pop O(logN) // 按照优先级取出

本周跟随覃超老师重新学习了一下基本数据结构的定义和实现，包括数组、链表、跳表、栈、队列等。大学时期学习数据结构时候，是刚接触计算机理论课程，当时完全不理解，加上没有编程的实践经验，感觉学习枯燥，导致自己没有学好这门功课，更别提理解和使用了。经过多年的编程工作，自身已经积累了很多解决问题的办法。结合自己重新学习和思考，已经能够理解数据结构和算法所解决的实实在在的问题。通过leetcode和覃超老师结合实战的习题讲解，感觉自己对数据结构和算法又有了新的认识上的提高。现在意识到自己缺乏很多的算法能力，需要花更多的时间和精力去刷更多的题，更好的记忆和理解，才能在未来编程工作上有更好的方法论指导作用。希望和其他同学一同努力，坚持到底，到最后肯定能够战胜自己，战胜这么多算法问题！加油！！

第一周的课程学习下来，主要是一些解题思路比较重要，另外还需要大量的时间将这些思路在题目上进行练习。

1. 左右指针来确定最大面积，要比双层的嵌套循环的时间复杂度要好很多。
2. 用空间换时间，可以用多维的数据结构来代替一维的数据结构，从而来减少时间复杂度（新接触的跳表这一个数据结构）。
3. 可以多去LeetCode国际站上多看看其他国家的网友的解题思路，多看之后还需要多练。

改写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.pollFirst());

}

System.out.println(deque);

阅读Queue源码

Java中的Queue是一个借口，扩展了Collection接口

Queue提供了两类方法

阅读优先队列源码

java的优先队列通过用数组表示的小顶堆实现。PriorityQueue继承了AbstractQueue抽象类，AbstractQueue实现了Queue接口。
在生成优先队列实例的时候可以指定Comparator也可以使用元素自身的顺序属性。

优先队列的入队和出队时间复杂度为O(log n)，对应方法为offer ，poll， remove， add。

底层使用数组存储 Object[] queue
记录数组保存元素的数量 int size

方法 add 调用了offer

方法

add

直接调用offer方法

offer

判断容量，容量不足调用grow函数扩容。原来的容量不足64，增加2；否则*2

如果当前队列为空，加入元素直接放在queue[0]
否则调用siftUp方法，插入元素并维持堆特性

remove

remove方法也通过调用poll方法实现

poll

出队元素是queue数组的第一个元素。
如果队首元素出队后size不为0，那么调用siftDown方法，调整堆的结构

学习总结

本周学习了数组、链表、队列、栈和跳表的知识。数组和链表的属于平时接触比较多的数据结构，所以学习的时候没有什么理解上的问题。

在做算法题时，经常发现自己的思路和题解的差不多，但是代码总是通不过测试。原因是经常没有考虑边界条件，输入为空等情况。通过先把思路写下来，在情况比较复杂的时候画图更更加清晰。还感受到了覃超老师说的过遍数的重要性。只做一两遍只能对题目 有个印象，连所有的解法思路都记不全。另外在做完之后要记得分析自己的解法的时间复杂度和空间复杂度。要降低时间复杂度时候，可以用空间来换时间，比如使用hashMap的快速访问减少一层循环遍历。也可以通过左右夹逼或者首尾指针来减少循环。

Queue 源码分析

如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此队列，成功时返回true，如果当前没有可用空间则抛出IllegalStateException。
boolean add(E e)

如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此队列，成功时返回true，如果当前没有可用空间则返回 false。
boolean offer(E e)

检索并删除此队列的头部元素。 此方法与poll的不同之处仅在于，如果此队列为空，则抛出异常 NoSuchElementException
E remove()

检索并删除此队列的头部，如果此队列为空，则返回null。
E poll()

检索但不删除此队列的头部。 此方法与peek的不同之处仅在于，如果此队列为空，则抛出异常 NoSuchElementException。
E element()

检索但不移除此队列的头部，如果此队列为空，则返回null。
E peek()

PriorityQueue 源码分析
http://www.pianshen.com/article/8414215817/

新API实现 Dueue
import java.util.Deque;
import java.util.LinkedList;

public class DequeTest {

/**
 * @param args
 */
public static void main(String[] args) {

	Deque<String> deque = new LinkedList<>();
	
	deque.addFirst("apple");
	deque.addFirst("google");
	deque.addFirst("oracle");
	
	System.out.println(deque);
	
	String str = deque.getFirst();
	System.out.println(str);
	
	str = deque.getLast();
	System.out.println(str);
	

	deque.addLast("ibm");
	deque.addLast("linux");
	deque.addLast("rehat");
	
	str = deque.getLast();
	System.out.println(str);
	
	System.out.println("=====================================================================");
	
	while (deque.size() > 0) {
		System.out.println(deque.pollFirst());
	}
}

}

经过预习周和第一周的学习，让我对数据结构和算法有了重新认识，同时通过刻意的训练来达到对数据结构和算法熟练程度，学会使用它，并且接触到新的技术能够了解背后使用哪些数据结构，复杂的框架也是由各种数据结构和算法组装而成的，甚至觉得代码看不懂，数据结构和算法没学到家

IDE键盘快捷操作技巧（Mac）

fn + delete : 删除光标右侧

command + left / right : 光标移至行头、行尾

option + left / right : 光标按单词切分

option + delete : 向光标左侧删除单词

fn + option + delete : 向光标右侧删除单词

commond + delete : 向光标左侧删除至行头

fn + commond + delete : 向光标右侧删除至行尾

shift + command + left / right : 选中光标所在行内容至行头、行尾

shift + option + left / right : 选中光标所在单词至头部、尾部

Top tips for <IDE name>

自顶向下编程方式：先写好主干逻辑，再写细节。

Week1-学习总结

1. 用 add first 或 add last 这套新的 API 改写 Deque 的代码

Deque<String> deque = new LinkedList<String>();
deque.addFirst("a");
// deque.offerFirst("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.pollFirst());
}
System.out.println(deque);

2. 分析 Queue 和 Priority Queue 的源码 （JDK8）

package java.util;
// 队列是一个FIFO的数据结构, Java中的实现继承了Collection
/* BlockingQueue接口：不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用，实现了阻塞接口的类如下：
 * ArrayBlockingQueue ：一个由数组支持的有界队列。
 * LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
 * PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
 */　
// LinkedList实现了java.util.Queue接口和java.util.AbstractQueue接口, 没有实现阻塞接口，PriorityQueue 和 ConcurrentLinkedQueue也不阻塞
/* <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @see java.util.Collection
 * @see LinkedList
 * @see PriorityQueue
 * @see java.util.concurrent.LinkedBlockingQueue
 * @see java.util.concurrent.BlockingQueue
 * @see java.util.concurrent.ArrayBlockingQueue
 * @see java.util.concurrent.LinkedBlockingQueue
 * @see java.util.concurrent.PriorityBlockingQueue
 * @since 1.5
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 */
public interface Queue<E> extends Collection<E> {
    // 增加一个元索。如果队列已满，则抛出一个IllegalStateException异常
    boolean add(E e);
    // 添加一个元素并返回true。如果队列已满，则返回false
    boolean offer(E e);
    // 移除并返回队列头部的元素。如果队列为空，则抛出一个NoSuchElementException异常
    E remove();
    // 移除并返问队列头部的元素。如果队列为空，则返回null
    E poll();
    // 返回队列头部的元素。如果队列为空，则抛出一个NoSuchElementException异常
    E element();
    // 返回队列头部的元素。如果队列为空，则返回null
    E peek();
}

package java.util;
// 继承AbstractQueue，而AbstractQueue继承AbstractCollection，实现Queue接口
public class PriorityQueue<E> extends AbstractQueue<E> {
	// 内部使用堆实现，每次取堆顶元素
    transient Object[] queue; // non-private to simplify nested class access
    
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    // 主要构造函数：initialCapacity 为初始堆大小，一般来说，为了避免扩容，或者空间浪费，要选择合适的值，默认值为 DEFAULT_INITIAL_CAPACITY = 11
    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator){
        ...
    }
    // 添加元素
    public boolean add(E e) {
        return offer(e);
    }
    // 调用的是offer
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        // 主要是记录修改次数，实际上是为了防止在遍历的时候更改数据造成不一致，会抛出ConcurrentModificationException 异常
        modCount++;
        int i = size;
        // 检查是否需要扩容，queue就是真实数据
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
        // 使用经典的siftUp上移最后添加的元素，保证堆还是有序的
        siftUp(i, e);
        return true;
    }
	// 删除元素
	public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
    		// 使用 siftDown，首先将最后一个元素移到堆顶，再调整堆
            siftDown(0, x);
        return result;
    }
    // 获取元素
    // 也可以使用父类AbstractQueue的element()方法
    public E peek() {
    	// 直接返回数组的第一个值
        return (size == 0) ? null : (E) queue[0];
    }
}

3. 学习笔记

Week1-4-数组，链表，跳表

• 数组：插入/删除平均复杂度 O(n)，查找O(1) （随机存取）。对Java ArrayList进行插入操作，涉及arraycopy，效率偏低

• 单链表：node --> next，prepend/append复杂度O(1)，插入/删除复杂度 O(1) （指针修改的2次操作），查找O(n)。

• 双向链表 (Java中默认的)（应用于实现LRU cache）：prev <-- node --> next，插入/删除复杂度O(1)，查找复杂度O(n)

• 循环链表：tail-->head

• 跳表（skip list，应用于Redis）：为克服链表访问的复杂度O(n)，采用升维+空间换时间策略进行加速：加索引：一维-->二维

  • 一级索引：指向next+1，跨越2个元素

  • 二级索引：跨越4个元素

  • 多级索引：log2(n)级索引

  • 最终达到增加/删除log(n)的时间复杂度，但维护成本较高，因为要更新索引，空间复杂度为O(n)，但比同为O(n)的简单链表要大

很多算法靠自己想出来是不可能的，需要去学习前人的总结，所以没有什么不好意思的。

Week1-5-栈，队列

• Stack: FILO，增加删除O(1)，查询（需要遍历）O(n)
• Queue: FIFO，增加删除O(1)，查询O(n)
• Deque: Double-end queue, 增加删除O(1)，查询O(n)
• Priority Queue：插入O(1)，取出O(logn)，按优先级取出，为了保持有序性，可以用heap/bst/treap实现

每种数据结构在不同编程语言都可能由不同底层来实现，甚至由多个其他数据结构实现，比如用两个栈实现队列

一维数组的坐标变换，i/j嵌套遍历，双指针夹逼，枚举中间找左右边界等套路代码，需要非常熟练

Week01总结：

• 数组

  随机访问的时间复杂度为 O(1)
  如果在数组的末尾插入元素，复杂度为 O(1)
  如果在开头 ，复杂度为 O(n)
  删除同插入

• 旋转数组

//挂起本次目标位元素
//降前一轮挂起元素 放入目标位
//目标位 = (起始位+ 移动位数) 同 长度 取模

`public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;  //考虑移动位数大于长度 so 取模 
        int count = 0; //转换次数不能超过数组长度
        for (int start = 0; count < nums.length; start++) { // 0位开始移动
            int current = start; // 起始位：0
            int prev = nums[start]; //初始化前一轮被复制(挂起)元素 ： 第0个
            do {
                    int next = (current + k) % nums.length;  // +k位坐标( 前一轮被复制元素的目标位置)  
                    int temp = nums[next];   //复制(挂起) 目标位置元素 
                          
                    nums[next] = prev;   //前一轮被复制元素 填入
                    prev = temp;    // 目标位置原有元素作为下一轮被移动(填入)元素
                    current = next;  //下一轮起始位
                    count++;
            } while (start != current);
        }
    }
}`

梳理逻辑的草图@_@

• 栈：

后进先出，简称LIFO结构
peek() 取得栈顶
pop() 取得栈顶并从栈中移除栈顶
push(E item) 入栈

• 接雨水

  `public int trap(int[] height) {

    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    int index = 0;
    while (index < height.length) {
        while (stack.size() > 0 && height[index] > height[stack.peek()]) {
            //数组当前index下值>数组中栈顶元素对应值----》  确定一组边界
            int top = stack.pop();            //保存并弹出栈顶元素                                 
            if (stack.empty()) {
                break;
            }
            int h = Math.min(height[index], height[stack.peek()]) - height[top];
            //长度差=min(数组中index下值,数组中当前栈顶下值)-数组中当旧栈顶(top)下值
            //旧栈顶对应的一组边界的面积已经在旧栈顶入栈时计算，所以去和原栈顶的长度差？？
            int d = index - stack.peek() - 1; // 宽度=数组坐标差
  
            res = res + h * d;
        }
        stack.push(index++);
    }
    return res;
  

  }`

草图@_@

PriorityQueue 优先队列 有优先顺序的queue

• 优先队列的元素会根据构造时提供的Comparator进行排序
• 不能加入null和不能排序比较的Object
• 非线程安全 需要线程安全需使用PriorityBlockingQueue

poll() 取得并移除队列头部元素
peek() 取得但不移除队列头部元素
add() ,offer()
语义相同，都是向优先队列中插入元素 ,并按自然顺序或比较器Comparator的顺序排序
offer 插入失败时返回false
add插入失败时返回异常
插入或移除元素时 会对队列进行扩容 或减小size 并调用siftUp,siftDown重新调整排序

第一周主要是找感觉和方法

1. 仔细审题，譬如2sum的题目，题目已经说是有解的，合并链表是排好序的。
2. 先不要code，想出各种能解决的方法，然后再对比时间复杂度，空间复杂度，和代码实现难易程度，来决定哪一个最好。如果有互相对比就更好。
3. 如果不是为了算法比赛，代码还是不要糙快猛，这种习惯是逐渐养成的。
4. 如果比较抽象，比如链表的指针赋值、变化，可以再纸上画图帮助自己理解过程。

要求

1. 每周从覃超老师布置的题目中，至少完成并提交两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章或总结，切忌流水账。

作业提交 Deadline

2019年10月27日 23:59 （以当地时间为准）
未按时提交作业，会在个人作业总分中 -3 分

本周作业概述

本周需要完成学习的视频内容：

• 第 5 课 | 哈希表、映射、集合
• 第 6 课 | 数、图、二叉树、二叉搜索树
• 第 7 课 | 泛型递归、树的递归
• 第 8 课 | 分治、回溯

以上四课视频后，覃超老师都给出了大家可以练手的算法题。

其中，第 5 课的课后作业（第2节视频后）还包括：

• 写一个关于HashMap的小总结
  说明：对于不熟悉Java语言的同学，此项作业可选做。

请大家将此部分作业，放在本周学习总结中一并提交

本周算法习题库：

第五课课后习题：

https://leetcode-cn.com/problems/valid-anagram/description/
https://leetcode-cn.com/problems/group-anagrams/
https://leetcode-cn.com/problems/two-sum/description/
写一个关于HashMap的小总结
说明：对于不熟悉Java语言的同学，此项作业可选做。
请大家将HashMap的小总结放在本周学习总结中一并提交

第六课课后习题：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

第七课课后习题：

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
https://leetcode-cn.com/problems/combinations/
https://leetcode-cn.com/problems/permutations/
https://leetcode-cn.com/problems/permutations-ii/

第八课课后习题：

https://leetcode-cn.com/problems/majority-element/description/
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
https://leetcode-cn.com/problems/n-queens/

1、升维（一维 到 二维 到多维）

2、空间换时间

3、双指针 就是利用两个指针去遍历数组。一般来说，遍历数组采用的是单指针（index）去遍历，两个指针一般是在有序数组中使用，一个放首，一个放尾，同时向中间遍历，直到两个指针相交，完成遍历。时间复杂度也是O(n)

由于第一周有过预习，并且也用golang实现了数组 链表的简单操作。还有能点概念能理解。接下来的可能就需要换一种方式来学习了。

过视频，视频学习过程中，把相应的leetcode题目的解法用golang抄写一遍。
过作业题目，至少两遍。
再过视频，整理知识点总结，有时间去看下底层实现。

第一周学习总结

摘要

• 数组
• 链表
• 栈
• 队列
• 源码分析

数组

• 数组是一个线性表，是一组连续的存储空间

  • 支持随机访问
  • 低效的“插入”和“删除”
  • 警惕数组的访问越界问题
  • 下标从0开始
    • 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移(offset)”,
      • 如果用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地址，
      • a[k]就表示偏移k个type_size的位置，
      • 所以计算a[k]的内存地址只需要
      • a[k]_address = base_address + k * type_size
    • 若是数组从1开始计数，那么我们计算数组元素a[k]的内存地址就是
      • a[k]_address = base_address + (k-1) * type_size
      • 从1开始编号，每次随机访问数组元素都多了一次减法运算，对于cpu来说，就是多了一次减法指令。
  • 容器类实现
    • Java的 ArrayList
      • 支持动态扩容

• 操作时间复杂度

  • prepend O(1)
  • append O(1)
  • lookup O(1)
  • insert O(n)
  • delete O(n)

链表 Linked list

• 是一种在内存中通过节点记录内存地址而互相链接形成一条链的存储方式
• 操作时间复杂度
  • prepend O(1)
  • append O(1)
  • lookup O(n)
  • insert O(1)
  • delete O(1)
• 解题技巧
  • 警惕指针丢失和内存泄露
    • 插入结点时，注意操作的顺序

      new_node->next = p->next;
      p->next = new_node;

    • 删除链表结点时，记得手动释放内存空间

      p->next = p->next->next;

  • 不用哨兵结点插入首结点、删除尾结点

    if (head == null) {
    head = new_node;
    }
    if (head->next == null) {
    head = null;
    }

  • 利用哨兵简化实现难度
    • 头结点为哨兵结点
  • 重点留意边界条件处理
  • 举例画图，辅助思考
  • 多写多练
• 常考题
  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第n个结点
• 经典应用场景
  • LRU 缓存淘汰算法
• 缓存
  • 是一种提高数据读取性能的技术
  • 常见策略
    • LFU(Least Frequently Used) 最少使用策略
    • LRU(Least Recently Used) 最近最少使用策略
• 常用链表结构
  • 单链表
    • 插入与删除
  • 循环链表
    • 是一种特殊的单链表
    • 典型应用
      • 约瑟夫问题
  • 双链表
  • 双向循环链表

栈

• 是一种受限的线性表
• 先进后出
• 表现
  • 数组实现叫 顺序栈
  • 链表实现叫 链式栈
• 应用
  • 函数调用

    int main() {
        int a = 1; 
        int ret = 0;
        int res = 0;
        ret = add(3, 5);
        res = a + ret;
        printf("%d", res);
        reuturn 0;
   }
    int add(int x, int y) {
        int sum = 0;
        sum = x + y;
        return sum;
    }

  • 表达式求值

    34+13*9+44-12/3

  • 括号匹配
    • 用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；
    • 当扫描到右括号时，从栈顶取出一个左括号。
    • 如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。
    • 如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
  • 浏览器前进后退功能

队列

• 是一种操作受限的线性表
• 先进先出
• 与栈区分
  • 栈只需维护一个 栈顶指针
  • 队列需要维护两个指针
    • 队首 Head 永远指向队首元素索引位置
    • 队尾 Tail 永远指向队尾元素下一个索引位置
• 表现
  • 用数组实现的队列叫 顺序队列
  • 用链表实现的队列叫 链式队列
• 循环队列
  • 队空
    • tail == head
  • 队满
    • (tail+1)%n == head

      public class CircularQueue {
          // 数组：items，数组大小：n
          private String[] items;
          private int n = 0;
          // head 表示队头下标，tail 表示队尾下标
          private int head = 0;
          private int tail = 0;
      
          // 申请一个大小为 capacity 的数组
          public CircularQueue(int capacity) {
              items = new String[capacity];
              n = capacity;
          }
          // 入队
          public boolean enqueue(String item) {
              // 队列满了
              if ((tail + 1) % n == head) return false;
              items[tail] = item;
              tail = (tail + 1) % n;
              return true;
          }
          // 出队
          public String dequeue() {
              // 如果 head == tail 表示队列为空
              if (head == tail) return null;
              String ret = items[head];
              head = (head + 1) % n;
              return ret;
          }
      }

• 阻塞队列
  • 在队列的基础上增加阻塞操作
  • 应用
    • 生产者 - 消费者 模型
• 并发队列
  • 线程安全的队列
    • 最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
    • 实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
    • 实现无锁并发队列
      • cas + 数组
• 其它应用
  • 分布式应用中的消息队列 如 kafka

• Chunk it up 切碎知识点
  庖丁解牛：数据结构和算法本身是具有一定的抽象性，切碎后相对要更容易理解一些。
  类比：人脑不适合记忆和思考那些抽象的事物，类比就是对那些我们切小了的，相对没有那么抽象的知识跟我们生活中能理解的事物进行类比，有助于理解和记忆。
  形成树状结构：将那些切碎的知识点用树状联系起来，可以有个整体认知，也能对那些结点进行查漏不缺。

• Deliberate practicing 刻意练习

    写在前面：刻意练习是前几年自己看过的书，让我印象最深的就是，刻意练习不是无效的重复就可以，但也没有去细究和应用到自己的学习，希望通过老师的讲解能够学而习之，化之。
     1.过遍数：五遍刷题法
           第一遍：5分钟读题思考，没有思路直接看解法，看多种解法，比较优劣，然后背诵默好的写法
           第二遍：马上自己写，多种解法比较、体会并优化。---》提交到LeetCode
          第三遍：过了一天后，在重复做前面的题，对不同解法中自己不熟悉的解法进行专项练习
         第四遍：过了一周后，反复练习相同的题目，并根据做题反馈，进行专项练习
         第五遍：面试前一周恢复性练习
           用时间复杂度来讲，在我的理解，这是O(1)复杂度，1不是一边，而是一个常数。对于不同知识背景和学习能力来说，多少遍合适不能一概而论。后续正式课程开始后，我也会再次总结自己的过遍数的遍数。
    
    2.练习自己的缺陷和弱项部分
    3.不舒服、不爽等说明自己待在舒适区外，处于成长状态
  

• Feedback 反馈
  及时反馈：在LeetCode上做题时，你是否通过、运行时间、内存消耗都能提供到及时反馈
  主动型反馈：主动去GitHub,LeetCode等寻找高手的代码进行比较和思考牛逼在哪呢？我能学习到什么呢？
  被动式反馈：老师给我们code review 时做反馈

切题四件套
Clarification ：审题
Possible solutions：思考可能的解决方案
compare(time/space)：比较时间和空间复杂度
optimal ：加强
Coding :多写
Test cases:测试那些解决方案

• 双指针
  • 双指针碰撞
  • 双指针左右夹逼
  • 快慢指针
• 数组下标的计算方式
  • 索引循环实现环形队列（在循环双端队列的实现中体现）
  • 索引步长增长，构成环状旋转
• 链表的哨兵模式简化代码（在合并有序链表的实现中体现）

费曼的学习方法

费曼的方法很简单，但非常有效果。只有四步：

第一步，选择一个概念。

这种方法适用于所有概念，从物理学到世界历史，再到商界。

第二步，教授这个概念

就像你在教授别人一样，将你知道的和这个主题相关的一切都写下来，并解释这个概念。这里要以一个小学生作为教授对象，而不是某一个很聪明的朋友。

这可能听起来很傻，但真的非常有效。

不要使用任何高级的词汇或复杂的概念，因为使用它们时你很容易又陷入自欺的怪圈。使用小学生都可以听懂的语言和概念。用这种方法写下对一个概念的理解时，你其实是在迫使自己更深刻的理解这个概念。同样重要的是，你会发现自己在哪里还没有理解清楚。

第三步，返工

在第二步中，在开始时，不可避免的，你会发现自己理解上的问题，忘记的重要方面，或者难以解释的地方。这其实是学习中非常有价值的反馈。返回到源材料中，不管是书本还是网络资料，重新有针对性的学习相关的部分。

学习完成后，合上书本，不再看参考材料，使用第二步提到的方法，重新解释你之前不清楚的部分。当你可以解释清楚后，回到对原来概念的解释中，继续第二步，直到你可以完整的将概念解释出来。

第四步，回顾和精简

现在，经过前三步，你已经写下了对于这个概念的解释。重新回顾这些解释，确保你没有借用任何复杂概念来解释这个概念。将这些解释大声读出来。如果读起来不够简洁，或者听起来让人困惑，这就说明你在这些地方还可以进一步加深理解。你也可以尝试用常见事物和现象的类比来解释。

最后，你就可以用最简单的语言，用最少的文字将这个概念解释清楚了。而这时，也就表明你真的理解了这个概念的实质。当你使用这种方法时，你慢慢地穿过这个技巧的每一个步骤，精确地发现你还有哪些内容没有理解。这种学习非常高效，很少浪费时间。

费曼的学习方法

费曼的方法很简单，但非常有效果。只有四步：

第一步，选择一个概念。

这种方法适用于所有概念，从物理学到世界历史，再到商界。

第二步，教授这个概念

就像你在教授别人一样，将你知道的和这个主题相关的一切都写下来，并解释这个概念。这里要以一个小学生作为教授对象，而不是某一个很聪明的朋友。

这可能听起来很傻，但真的非常有效。

不要使用任何高级的词汇或复杂的概念，因为使用它们时你很容易又陷入自欺的怪圈。使用小学生都可以听懂的语言和概念。用这种方法写下对一个概念的理解时，你其实是在迫使自己更深刻的理解这个概念。同样重要的是，你会发现自己在哪里还没有理解清楚。

第三步，返工

在第二步中，在开始时，不可避免的，你会发现自己理解上的问题，忘记的重要方面，或者难以解释的地方。这其实是学习中非常有价值的反馈。返回到源材料中，不管是书本还是网络资料，重新有针对性的学习相关的部分。

学习完成后，合上书本，不再看参考材料，使用第二步提到的方法，重新解释你之前不清楚的部分。当你可以解释清楚后，回到对原来概念的解释中，继续第二步，直到你可以完整的将概念解释出来。

第四步，回顾和精简

现在，经过前三步，你已经写下了对于这个概念的解释。重新回顾这些解释，确保你没有借用任何复杂概念来解释这个概念。将这些解释大声读出来。如果读起来不够简洁，或者听起来让人困惑，这就说明你在这些地方还可以进一步加深理解。你也可以尝试用常见事物和现象的类比来解释。

最后，你就可以用最简单的语言，用最少的文字将这个概念解释清楚了。而这时，也就表明你真的理解了这个概念的实质。当你使用这种方法时，你慢慢地穿过这个技巧的每一个步骤，精确地发现你还有哪些内容没有理解。这种学习非常高效，很少浪费时间。

第一周学习总结

总体

获得

• 如何自主学习算法
• 五毒神掌的运用实践
• 牢记空间换时间，升维
• 算法都是找最近重复性

缺失

• 没有做预习
• 许多解题都没有自己的思路
• 做题经常缺少最后一步 去国外网站查看discuss
• 没有把写代码前的思路先写出来 -> clean code -> 新闻稿

具体

1. 如何自主学习算法

   • 搜索引擎的运用
     • Queue java source ${version}
     • Queue java ${version}
     • java source code
   • 分析源码
     • 由于java鲁棒性强，所以可以查看java代码
     • 先看注释了解大致思路
     • 找到核心逻辑点
       • 看代码
       • 反复debug（不会的）逻辑点

2. 五毒神掌的使用

   • https://leetcode-cn.com/submissions/#/1 查看这个网址 去看 1天前做的什么题目 5天前做的什么题目

3. 空间换时间

4. 最近重复性

   1. 栈 ：结合现实-> 洋葱 了解其结构 最近相关性 使用栈
   2. 队列： 结合现实 -> 排队 了解其结构 先来后到 使用队列

5. 没有做预习

   1. 这周开始做预习

6. 做题没有思路

   1. 花多一些时间 原本 5 -> 8分钟
   2. 把基础巩固扎实

7. 经常忘记查看discuss

   1. feedback的感觉不是很强烈 除了有一次看到比较逗比的算法除外

其他

1. 奇妙算法

   • 旋转数组 为什么可以通过 通过三次反转来将最后的结果获得？

2. 现实中运用栈这个数据结构，使用Deque。

3. 双指针

   1. 快慢指针
      1. 环状问题
      2. 重复值问题
   2. 夹壁定律？

4. review

   1. LeetCode_1_386

      1. 暴力法时间复杂度是O(n^2)

      2. 解法也是错误的其会反复利用同一个值

      3. 题目

         1. 他的解法

            class SumOfTwoNumbers {
                public int[] twoSum(int[] nums, int target) {
                    int[] n = new int[2];
                    for (int i = 0; i < nums.length; i++) {
                        for (int j = 0; j < nums.length; j++) {
                            if (i != j && (nums[i] + nums[j] == target)) {
                                // System.out.println(i + ", " + j);
                                if (i < j) {
                                    n[0] = i;
                                    n[1] = j;   
                                } else {
                                    n[0] = j;
                                    n[1] = i;
                                }
                                return n;
                            }
                        }
                    }
                    return new int[0];
                }
            }

         2.  我修改后的解法

            class Solution {
              public int[] twoSum(int[] nums, int target) {
                    int[] n = new int[2];
                    for (int i = 0; i < nums.length - 1; i++) {
                        for (int j =i + 1; j < nums.length; j++) {
                            if (i != j && (nums[i] + nums[j] == target)) {
                                n[0] = i;
                                n[1] = j;
                                return n;
                            }
                        }
                    }
                    return new int[0];
                }
            }

         3. 但时间复杂度过高 应该考虑 升维 通过使用 map来存储 每次遍历将元素存入，如果遇到以前存过的值和当前遍历值之和为目标直接返回有如下代码：

            public int[] twoSum(int[] nums, int target) {
                  Map<Integer,Integer> map = new HashMap<>(nums.length);
                    for (int i = 0; i < nums.length; i++) {
                        Integer oldIndex = map.get(target - nums[i]);
                        if (oldIndex == null) {
                            map.put(nums[i],i);
                        }else {
                            return new int[] {oldIndex,i};
                        }
                    }
                    throw new RuntimeException("error not found");
                }

   2. LeetCode_ 26_506

      1. 说明： 这个方法和官方题解思维逻辑上没有太大的区别。但存在边界值的问题. 然后发现自己写得代码传入空数组也是一样返回1，应加入前置判断

          if (nums.length == 0) return 0;

   3. https://github.com/algorithm004-01/algorithm004-01/pull/163/files 这个自己有写测试类，移出重复值仍然跟上面一样存在问题。

   4. mark #160 别人的解题方式。比我的高级多了，可以学习一下

      每道题的第一次完解控制在1h
      \1. 审题,理解题意
      \2. 先问自己,这个问题属于哪类算法问题?
      \1. 列出所有可能得算法,每种方法的时间复杂度
      \2. 要将不熟悉的题转换成熟悉的题(比如:三数求和—>2数求和—>双指针)
      \3. 再思考并写下所给条件中有哪些性质是可以利用的?
      \1. 比如题中有序数组的有序就是一个可以利用的条件)
      \2. 比如题中是否存在,就联想到哈希表的数据结构
      \4. 这类算法问题通常的解题思路?
      \1. “解决链表问题最好的办法是在脑中或者纸上把链表画出来”
      \2. 数组—>双指针
      \5. 以上4点需要在15min 内完成
      \6. 先用伪代码写出逻辑，再补全小段代码
      \7. 找重复性(重复单元)
      \8. notion记录自己的解题过程(这一点很重要,可以发现自己的缺陷,方便日后对景对情),和最优解做对比
      \9. 将不同的解法,制成anki 卡片记录
      \1. 搜索优质解题方法和思路(博客,leetcode 国际站)
      \2. 制作 gif 图片
      \10. 五遍刷题法,重写所有的解法

      最后可以将所有的题目类似的 进行归类 反向归类

   5. #109 我也可以将自己梳理的发到自己的博客上。

【282-week1】关于二分查找的一些新的理解

第一周学习总结

知识要点

数组

一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据
访问O(1)，插入、删除O(n)

数组的读取很方便，但是插入和删除很麻烦，会反复读写内存，如果不够还要开辟新空间
适合修改少而查询多的情景

链表

访问O(n)，插入、删除O(1)
基本实现代码如下

class LinkedList { 
    Node head; // head of list 
    /* Linked list Node*/
    class Node { 
        int data; 
        Node next; 
  
        // Constructor to create a new node 
        // Next is by default initialized 
        // as null 
        Node(int d) { data = d; } 
    } 
}

链表与数组正好相反，适合查询少而修改多的场景

跳表

解决查找问题

跳表的本质是为了解决链表的查询问题而增加了索引
所以可以一定程度上的解决链表的查询速度，但是，也增加了修改的时间

综上所述，没有一种绝对优点的数据结构，只有符合使用场景的相对优点数据结构，所以要选择适合的数据结构，这点很重要。换句话说，如果真有一种绝对优点的数据结构，那其他就没有存在的意义了

栈

一种先进后出的数据结构

队列

一种先进先出的数据结构

以上两种数据结构也是正好相反，就像链表和数组是一对一样，这两个也是一对
同样，为了解决这两种数据结构的缺点，也引入了双端队列这种结构

这周学习到的点

升维想法，以空间换时间

这是一种很常见的解决问题思路，但是我认为也是有一定局限性的，比如数据过大，内存有限制
所以可以作为一种常规解决思路，但不能硬靠

阅读源码学习

阅读源码确实是一种很好的学习方法，以前也只是听说过，但是并没有实践过
看了讲解之后，觉得阅读源码也没有那么可怕和费劲，可以尝试

学习方法实践

我觉得这周最重要的是对学习方法的实践，不论是怎么做题亦或是怎么寻找答案
我认为建立正确和高效的学习方法以及学习习惯是非常重要的，因为这可以在未来一直有效

解题思路

有两种值得记录的解题方法，一种是左右指针，在浏览很多算法答案的时候，发现这种方法还是很常见的，从左从右一点点夹出答案，这让我想到了二分法，也是左一下右一下把答案砍出来了
另外一种就是暴力法，简单有效，但是没有效率，只是能帮你把问题解决而不管怎么解决的，作为结果导向是很合适的

其他想法

我觉得有些代码是可以背一下的，因为不至于大脑一片空白
我很认同多写多练，那我自己就应该多练一点

源码分析

优先队列Priority Queue

说实话，没怎么看懂，这里的不懂是指原理，不是使用
所以在网上搜索了一些解读，大概知道是用堆实现的
其中最大的特点在于，每次插入和删除元素之后，会重新进行排序（上浮和下潜）

【701-week1】第一周学习总结

数组

特点：

• 是一种线性数据结构，用连续的存储空间存储相同类型数据；
• 下标从 0 开始；
• 支持 随机访问，根据下标随机访问的时间复杂度为 O(1)；
• 低效的 插入 和 删除；
• 警惕 越界 访问问题；
• 基于数组类型的 容器类型 支持动态扩容；

复杂度分析：

• 时间复杂度：平均的时间复杂度为 O(n)
  • prepend/append：O(1)
  • lookup： 按下标访问是 O(1)
  • insert：最好是 O(1)，最坏是 O(n)，平均是 O(n)
  • delete：最好是 O(1)，最坏是 O(n)，平均是 O(n)
• 空间复杂度：O(1)

链表

特点：

• 常用于插入/删除操作较频繁的场景（空间换时间）
• 元素数量未知
• 缓存机制

复杂度分析：

• 时间复杂度
  • prpend：O(1)
  • append：O(1)
  • lookup：O(n)
  • insert：O(1)
  • delete：O(1)
• 空间复杂度：O(1)

实现思路：

• 理解指针或引用的含义
• 警惕指针丢失和内存泄漏
• 利用 哨兵 简化实现难度
• 重点留意边界条件
• 举例画图，辅助思考
• 多写多练

常见操作：

• 单链表反转
• 链表中环的检测
• 两个有序链表的合并
• 删除链表倒数第 n 个结点
• 求链表的中间结点

工程应用：

• LRU Cache - Linked List
• Redis - Skip List

单链表

双链表

循环链表

跳表

通过为链表添加 有序索引 的方式解决传统链表的 低效查找问题，以 空间换时间

• 在跳表中查询任意数据的时间复杂度是 O(logn)
• 空间复杂度是 O(n)

总结

数组是一种简单的 线性 数据结构，在内存中是一段只能存储 同种数据类型 的 连续的内存空间。其原理和实现思路是通过提前开辟好一段合适大小的内存空间，方便数据 按下标方式 能够进行快速查找。为了解决数组低效的插入和删除操作，链表应运而生，其在内存中是 非连续 的，通过 指针 方式来进行 动态扩容，这样一来，和数组相比，对应的插入和删除操作就非常高效，只需要移动对应结点的指针指向即可。基于此种数据结构衍生的数据结构类型还有 循环链表、双链表、调表。其中跳表是为了解决传统链表结构中低效的查询操作，所以其对应的实现思路是通过在原始链表的基础上建立 n 级有序索引 的方式来进行快速查找，是一种 以空间换时间 的解决方法。

数组、链表、跳表的复杂度如下表所示：

栈 & 队列

• stack：FILO，add&del：O(1),find：O(n)
• queue：FIFO，add&del：O(1),find：O(n)

双端队列

• 两端都可以进出的 Queue
• add&del: O(1)

优先队列

• 插入操作：O(1)
• 取出操作：O(logN) - 按照元素的优先级取出
• 底层具体实现的数据结构较为多样和复杂：heap，bst，treap

总结

栈(FILO) 和 队列(FIFO) 依然是 线性 的数据结构，这两种数据结构只允许同时在一端进行插入/删除操作，时间复杂度是 O(1)，实际工程中基于前两种数据结构又衍生出了 双端队列，该种类型的队列允许在两端进行插入/删除操作，时间复杂度为 O(1)；此外，基于此有产生了 优先队列，这种数据结构通过为对应结点设置优先级的方式来进行级别控制，在实际工程应用中较为广泛，例如会员系统的设计。

源码解析 - C# 版

Stack

通过查看源码得知，Stack 是采用 array 这种数据类型来进行相关操作，初始大小为 10 个单位长度。入栈操作为 push，函数内部直接对目标数组进行增加元素操作，期间会对数组长度进行安全检查；出栈操作为 Pop，函数内部直接对目标数组进行最后下标访问，返回该元素，并将数组中对应元素置空；查找操作为 Peek，该操作只会返回数组末尾元素对应的值，并不会对该数字进行任何修改。上述三种操作对应的时间复杂度均为 O(1)；Contains 方法为查找目标元素是否存在，其内部采用 while 循环的方式进行查找，时间复杂度为 O(n)。此外，Stack 本身是 非线程安全的, 所以 .NET 也提供了线程安全类型的版本 SyncStack。

Deque

通过查看源码得知，Deque 是采用 array 这种数据类型来进行相关操作，初始状态为 0 个单位长度，入队操作为 EnqueueTail，函数内部直接对目标数组进行增加元素操作，期间也会对数组进行动态扩容；出队操作为 DequeueHead 和 DequeueTail；这几种操作方式都相对简单，对应的时间复杂度均为 O(1)。此外，由于官方并未提供查找接口，所以我们只能通过 GetEnumerator 方式来进行查找，其内部采用 while 循环方式转为为 list 并返回，其对应的时间复杂度为 O(n)。

PriorityQueue

通过查看源码得知，PriorityQueue 内部采用了一个有序列表 SortedList<int, PriorityChain<T>> 和一个缓存栈 Stack<PriorityChain<T>> 来进行组合管理，有序列表是存着当前的所有数据，考虑到优先队列中数据优先级的修改频繁，将每次入队出队的数据都缓存到缓存栈中一份，避免对象的频繁创建，其中缓存栈的初始大小为 10 个单位长度；入队操作为 Enqueue，函数内部会往有序列表中添加元素（移动指针方式），同时会在缓存栈中进行出栈操作；出队操作为 Peek，该操作会将有序列表中的最后一个元素移除并返回；删除操作为 RemoveItem，函数内部会首先对有序列表中的对应元素执行删除操作，同时会将缓存栈执行入栈操作，将删除的目标数据加入到缓存栈中。

1.跳表在哪些场合适合代替红黑树，需要进一步思考
2.左右指针的方式，很巧妙。
3.老师说的懵逼状态的2步：1.暴力 2.最近最优

目录 (有道云笔记支持)
[toc]

总览

数据结构与算法总览

切碎知识点

• 脉络相连，形成脑图，体系化
• 数据结构
  • 一维
    • 基础：数组array(string)，链表linked list
    • 高级：栈stack，队列queue，双端队列deque，集合set，映射map(hash or map)...
  • 二维 (一维泛化而来)
    • 基础：树tree (想象成一维链表分叉之后形成树)，图graph
    • 高级 (在树的基础上增加条件)：二叉搜索树binary search tree(Red-black tree, AVL)，堆heap，并查集disjoint set，字典树trie
  • 特殊 (主要用于工程中的特定场景)
    • 位运算Bitwise，布隆过滤器BloomFilter (基于位运算)，LUR缓存LRU Cache
• 算法
  • 基石 (找到重复单元)
    • 逻辑切换 if-else, switch
    • 循环 for, while loop
    • 递归 Recurision(Divide & Conquer, Backtrace)
  • 高级
    • 搜索Search：深度优先搜索Depth first search，广度优先搜索Breadth first search，启发式搜索A*
    • 动态规划Dynamic Programming
    • 二分查找Binary Search
    • 贪心Greedy
    • 数学Math，几何Geometry

刻意练习

• 将基础动作分解，并反复练习 (至少五遍)
• 刷弱项：离开舒适区，踏入成长区

即时反馈

• 主动反馈：第一视角，寻找最佳实践，Github，LeetCode
• 被动反馈：Code Review

四解题步 (切题四件套)

• 审题：反复与面试官确认理解
• 想所有可能的解法：比较各解法时间、空间复杂度
• 写代码
• 测试样例

五遍刷题 (五毒神掌)

• 第一遍
  • 读题、思考 (5-15min)
  • (若无思路) 直接看解法：比较不同解法优劣
  • 理解、背诵、默写好的解法 (discuss)
• 第二遍
  • 自己写，跑LeetCode
  • 多解法比较、体会、优化 (领先80%)
• 第三遍 (24 Hours)
  • 对不熟悉的，专项训练
• 第四遍 (1 Week)
  • 对不熟悉的，专项训练
• 第五遍 (面试前恢复性训练)

环境设置、编码技巧、CodeStyle

• Windows Terminal
• LeetCode
  • 中文站为主
  • 国际站为辅：Discuss > Most Votes
  • Plugin
• Google Java Code Style
• IDE快捷操作
• 自顶向下编程方式
  • 主干逻辑在public
  • 细节逻辑private

时间复杂度、空间复杂度

时间复杂度

• 常见时间复杂度
  • O(1)常数复杂度
  • O(log n)对数复杂度
  • O(n)线性
  • O(n^2)平方
  • O(n^3)立方
  • O(2^n)指数
  • O(n!)阶乘
• 如何看时间复杂度
  • 看代码根据n运行多少次
  • 不考虑常数系数
  • 写代码时下意识的分析时间、空间复杂度
  • 递归的时间复杂度
    • 把递归执行顺序，画出树型结构的递归状态树 (有道云笔记支持)

      graph TD
      A["fib(6)"]-->B["fib(5)"]
      A-->CA["fib(4)"]
      B-->CB["fib(4)"]
      B-->DB["fib(3)"]
      CA-->DCA["fib(3)"]
      CA-->ECA["fib(2)"]
      CB-->DCB["fib(3)"]
      CB-->ECB["fib(2)"]
      DCA["fib(3)"]-->EDCA["fib(2)"]
      DCA["fib(3)"]-->FDCA["fib(1)"]
      DCB["fib(3)"]-->EDCB["fib(2)"]
      DCB["fib(3)"]-->FDCB["fib(1)"]
      

  • 主定理 (Master Theorem)
    • Binary search 二分查找 (一维数组二分查找): O(logn)
    • Binary tree traversal 二叉树遍历: O(n)
      • 每个节点访问且仅访问一次
    • Optimal sorted matrix 有序二维矩阵 (二维有序矩阵查找): O(n)
    • Merge sort 归并排序: O(nlogn)

第一周总结：

1. 顺序表 ： 查， 不利于增删改（因为需要遍历之后， 再进行crud操作，还需要对后续的数据进行位移）
   链表 ： 增删改，不利于查找(只能遍历链表，一个一个的找，O(n))

   例题总结：
   1.1 移动零
   -> 新建数组，将非0元素插入既可/可以通过辅助索引来交换非0值的位置，最后补0。

   1.2 盛水最多的容器
   -> 两层遍历，最后获取最大值/双指针, 两两夹逼， 求最大面积

   1.3 爬楼梯
   -> 需要找出重复性的点， 通过规律看，可用递归或者循环的方式

   1.4 三数之和
   -> 固定一个位置, 然后在后续的空间中使用双指针， 两两夹逼.
   ( 需要注意值相等的情况要跳过即可 )

   1.5 环形链表
   -> 双指针/快慢指针。 如果是循环的链表, 则一定会有出现重复的地方。
   （判断是否环形 / 判断环形的起点）

2. 队列： 先进先出(FIFO)
   栈 ： 先进后出(FILO)

   例题总结：
   2.1 有小括号
   -> 利用栈的FILO的特性， 遍历字符组, 每次将字符的对称字符压栈,
   直到出现对称字符的时候，和栈顶元素作对比
   2.2 最小栈
   -> 利用辅助栈, 辅助栈用来存储最小值（保持最小值在栈顶）
   如果主栈pop的值为最小值， 则辅助栈要弹出栈顶元素
   2.3 滑动窗口最大值
   -> 暴力解法,2层遍历获取最大值
   -> 双端队列 *** 暂时没理解的解法
   个人理解： 主要是在比较相邻的两个数的大小，然后通过索引的移动，继续进行比较。
   如果当前索引超过长度k的大小范围，则弹出前面的元素。
   如果当前元素大于队列的最后一个元素，则弹出最后一个元素。
   在每次判断完之后，判断当前索引是否大于长度k-1，是则插入结果列表。
   -> 集合，利用集合排序的特性， 每次遍历n个值，就弹出最后一个最大的值，并找到当前n+1减去k的位置的元素并删除

   2.4 柱状图中最大的矩形
   -> 暴力解法1，两层遍历， 固定一点，遍历剩余的部分，找出最小高度， 获取面积最大值。
   -> 利用栈， 遍历柱体 （存储索引值）
   使 -1 作为栈的初始栈顶， 便于计算面积， 即使是相等， 也不会出现距离为0的情况
   2.4.1 判断待入栈的柱体的高度, 是否大于栈顶的高度。
   2.4.2 如果大于， 则入栈。 反之，则处理该元素，算出面积，继续判断栈顶元素的大小。
   直到栈顶元素为-1或者栈顶元素小于待入栈元素
   2.4.3 最后还需要清空栈， 继续计算最大的面积。直到栈顶为-1

3. 课后作业：
   3.1 循环数组的设计
   -> 毫无思路， 直接看题解， 看到仍然是双指针，又类似双端队列。
   -> 头尾指针的移动， 前移则仅需加1再求余， 后移除了减1还需要加上数组长度再求余（才可以真正的回到下一个位置）
   -> 还需要考虑一下边界的问题， 头指针的位置指向以及尾指针的位置指向。
   （在图例上来看， 头尾指针的位置一直是对称，不重和的）

   3.2 求盛水量
   -> 暴力解法也是用的类似双指针的解法， 只是用的for循环
   -> 双指针解法， 通过头尾指针， 向中间靠拢， 同时比较左右的最大高度，
   求出指针与最大高度的最小值,使之和指针指向的柱体高度做减法获取到盛水量。

4. 总结：
   虽然大多数的题都是略微思考下， 就看题解， 然后手写， 默写， 靠记忆盲敲， 第二天再敲一遍，还是能发现一些小缺漏
   接触了一些之前没看过没了解过的知识点，有一些则是知道特性， 却没有实际应用。
   看到题解之后，确实有一种很微妙的感觉， 解法很巧妙。
   第一周的课程收获就蛮多的
   一是移动指针， 双指针等。 个人认为是索引/下标的一种高级用法。
   二是栈和队列的运用，虽然做的题还不是很熟练， 但是觉得解题的过程开始变得有趣起来.
   三是会开始注意到边界条件， 一些空的或者越区的经常会漏掉。

课后作业

1. 重写Deque

public class RewriteDeque {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addLast("a");
        deque.addAll(Arrays.asList("b", "c"));
        deque.forEach(System.out::println);
        System.out.println(deque.peekFirst());
        deque.forEach(System.out::println);
        while (!deque.isEmpty())
            System.out.println(deque.pollFirst());
        System.out.println(deque.size());
    }
}

2. PriorityQueue源码分析

queue 接口

• 两个添加方法：add 和offer
  add：如果不违反容量限制的情况下，插入成功则返回 true，否则抛出异常。
  offer：如果成功返回 true，失败则返回 false。

• 两个取出但不移除操作：element 和 peek
  element：如果队列为空，则抛出异常
  peek：如果队列为空，则返回 null

• 两个移出操作：remove 和poll
  remove：如果队列为空，则抛出异常
  poll：如果队列为空，则返回 null

PriorityQueue分析

优先队列是一个无界队列，底层实现基于平衡二进制堆。内部元素的排序依赖于它们的自然顺序或者根据不同构造函数所传入的比较器进行排序。优先队列不允许空元素，并且当依赖元素的自然顺序进行排序时，也不允许插入不可比较的元素，这样可能会抛出异常。

队列的头是按照指定排序后的最小元素，如果多个同样的最小元素，则头部是其任意一个。

虽然优先队列是无界的，但是内部有一个数组存储队列的数据，数组的长度最少和队列一样大。当有元素加入队列时，其容量自动增加。

队列实现了Collection的iterator方法，但是其迭代方法不能保证顺序。如果需要按顺序遍历，则将队列转为数组，在进行排序。

同样的，优先队列不是并发安全的，应该进行外部同步，如果无法外部同步，则需要使用阻塞优先队列。

O(log n) -> offer poll remove() add
O(n) -> remove(object) contains(Object)
O(1) -> peek element size

从源码的迭代器代码处开始，还没有看明白，目前还在继续。

课后总结

第一次学习算法，会有一个奇怪的现象，如果不管是写业务逻辑代码，还是服务器部署，如果不会肯定会直接搜索，然后查看文档，心理不会有任何其他情绪。但是对于算法，在大概知道应该用哪种数据结构进行解答，却对题目本身逻辑上想不通的话，就会一直心有不甘的纠结，而不会像平常一样不会就去搜索，去看答案。

而正是这种心有不甘的情绪，就会造成一道题会研究很长时间，甚至一下午，而最后放弃在看答案，又会造成自己很笨的感觉，而这种负反馈很有可能会带来恶性循环，从而放弃，我猜这也是以前算法给我的感觉吧。

老师说，一道题如果看 5 分钟看不出结果就直接看答案，然后背下来，然后一点点的再去理解，最后举一反三。我能理解为什么让背，因为一个东西如果你一开始无法理解，那么肯定会忘得很快，所以需要不断反复的刷题。

这一周学习我的进度非常慢，原因就是我特别想自己能独立解决一道题，就算实在没有头绪，我也只是看一眼结题思路而不看解析代码，最后自己写出来了，再去看优秀的代码。

比如，我目前有两三道题，不看任何提示的情况下，通过不断的 debug，可以解答出来，而且不是暴力求解。虽然执行时间慢了点，调试花费了 3、4 个小时，但是这个时候，正反馈带来的信心大概有 50%。然后去看结题思路，但是依然不看结题代码，自己根据结题思路在优化一次，这时信心大概 80%了。最后查看别人的优秀代码，在进行改进，这个时候心情就非常开心了。但是时间耗费的太久了。

我先在主要的问题就在这，听老师的吧，很不甘心，毕竟数据结构都知道用什么，可自己就是想不出来。任凭自己想吧，也许能想出来，但时间成本太高了。所以我真的需要权衡一下。毕竟时间成本才是最重要的。

总结：下周开始，我决定按照老师的思路来，思考 20 分钟，没有结果，就直接看答案。效果的话，在下次总结中写。