数组、链表、跳表的基本实现和特征

Array

Java: int a[100];
python: list = []
javascript: let x = [1,2,3]
数组里面的元素可以泛型，将任意类型放进去

实例：

• Java类：ArrayList

Linked List

Double Linked List

实例：

• Java类：Linked LIst（双向链表）

Skip List

• 跳表是为了解决链表查询慢的问题而出现的，解决的办法是添加多级索引,以空间换时间的方式提高查询效率。

提升效率的办法

• 升维**
• 空间换时间

时间复杂度

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

实战题目

练习步骤：

• 5-10分钟：读题和思考
• 有思路：自己开始做，不然马上看题解
• 默写背诵、熟练
• 然后开始自己写（闭卷）

移动零

解题思路：

• loop，count zeros 循环统计0元素，将非0元素移到最前面, O(n^2)
• 重新开一个新数组，loop，0往后面放，非0往前面放 O(n)
• 直接在数组中index操作，遇到非0元素就移动到头部 O(n)

python的交换两个元素技巧：x, y = y, x

盛水最多的容器

解题思路：

• 一维数组的坐标变化，i，j
  ** 枚举：left bar x，right bar y，（x-y) * min( height(x), height(y)) O(n^2)
• 左右夹逼：
  • 双指针，一个指针指向头，一个指向尾
  • 每次比较两个指针位置的值大小，由于在两边所以跨度最大，而内侧的柱子跨度会更小，只能内部柱子更高，才能大于两边的柱子产生的面积
  • 向内侧移动值较小的指针，直到指针相遇结束

爬楼梯

解题想法

• 找最近重复子问题
• 因为我们只能写if/else loop recursion

解题思路：

• 懵逼的时候
  • 能不能暴力
  • 最简单的问题（泛化），找重复性
    • 1 1种
    • 2 2种
    • 3 3 种
    • n f(n) = f(n-1) + f(n-2) fibnacci数列

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int

        1:1
        2:2
        3: f(1) + f(2) 等于前两次走法之和，因为f(1)走2步到f(3),f(2)走一步到f(3),两个的和构成3
        4: f(3) + f(2)
        实际上就是求fibnacci数列
        解决算法问题的办法就是找重复子问题
        """
        f1, f2, f3 = 1, 2, 3
        if n <= 2:
            return n
        # 使用n + 1是因为range参数的第二个在循环中不包含
        # 取3的原因是fibnacci数列是从1开始的不是0，所以3正好的第三个数
        for i in range(3, n + 1):
            f3 = f1 + f2
            f1 = f2
            f2 = f3
        return f3

数组

为什么数组要从 0 开始编号，而不是从 1 开始呢？

从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。最主要的原因可能是历史原因。C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。

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

注意：

• 数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。
• 即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。
• 所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。

插入操作解决方案：

直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。 快排

删除操作解决方案：

实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？

先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

JVM 标记清除垃圾回收算法的核心**

警惕数组的访问越界问题

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。

数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。

很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。

链表

常见的缓存淘汰策略有三种：

• 先进先出策略 FIFO（First In，First Out）
• 最少使用策略 LFU（Least Frequently Used）
• 最近最少使用策略 LRU（Least Recently Used）

与数组对比

底层的存储结构不同

数组需要一块连续的内存空间来存储，对内存的要求比较高。

链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

基本概念

我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

链表要想随机访问第 k 个元素，就没有数组那么高效了。链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

循环链表

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。

双链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。
所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

删除结点中“值等于某个给定值”的结点

尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

删除给定指针指向的结点

但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！

插入同理

如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。

双向链表应用

Java 语言中LinkedHashMap 这个容器

如何轻松写出链表代码？

1.理解指针或引用的含义
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
2.警惕指针丢失和内存泄漏
3.利用哨兵简化实现难度
4.重点留意边界条件处理
5.举例画图，辅助思考
6.多写多练，没有捷径

需要熟练的题目

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

队列

你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

操作受限的线性表数据结构。·

比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；
Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

循环队列

阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

并发队列

线程安全的队列我们叫作并发队列。

最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？

我们一般有两种处理策略。

第一种是非阻塞的处理方式，直接拒绝任务请求；

另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。

那如何存储排队的请求呢？

我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。

队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

栈

就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。

后进者先出，先进者后出，这就是典型的“栈”结构。

栈是一种“操作受限”的线性表。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

栈的应用

• 函数调用栈
• 编译器利用栈来实现表达式求值
• 栈在括号匹配中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。

内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。

静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。

栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。

堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。

·

“五毒神掌”式学习方法是很有用的，算法题只刷一遍的话是记不住的，主要在于有人带领学习，能够把算法中的干活教给你很重要，学习各种算法和数据结构并在题中结合应用，很多算法题在于**的巧妙，自己真的很难想出来，甚至困难难度的看题解都很难理解，更需要多加训练，反复巩固，希望自己再接再厉把每周的课程都上好，坚持下去，算法最后一定不会是我的弱点

经过第一周学习，发现自己基础知识薄弱，一些基础数据结构的实现不扎实，代码能力弱，老师讲的很好，主要靠自己练习。后面会认真练习，结合基础知识练习代码能力。

学习总结

• 学习了数组、链表、跳表、栈、队列这五种数据结构。熟悉了其基本特征以及使用方法
• 在分析上述五种数据结构的时间复杂度时，视频课上讲的更多是普通情况下的时间复杂度，在实际使用时有很多其他的场景需要去做复杂度分析，所以关键是要掌握复杂度分析的方法，这点在“算法与数据结果之美“”专栏中有很多介绍。常见的其他常见有比如
  1. 有序数组的查找，二分法能达到logn的时间复杂度；根据数组的值查找元素，那查找到时间复杂度也是O(n)的
  2. 双向链表、单向循环链表、双向循环链表在链表是否有序的情况下复杂度也是不一样的
  3. 如果只能从头节点操作链表、跳表的话，那无论是插入、查找、删除，时间复杂度都是跳表更好，只是会占用更多空间
• 在实际的开发过程中，使用的数据结果基本就是list和map，数组使用的都很少，对其他数据结构不熟悉，还需要多多练习
• 在做题的时候，发现解题自己想的话除了暴力破解，基本没有其他思路。当自己去看题解时，如果只看代码，想要把题解的思路理清要花很长时间，所以我开始找带动图的题解，然后再自己在纸上划一划，效果更好。

在之前的一段时间，自己也刷过LeetCode的几十道题，很多解题思路在看了题解之后，感觉自己是个废物，很多题解感觉根本就不可能想到，后来就麻木了，有些题直接看题解去做。现在学了前几节课之后，总算对这一点释怀了，不再花更多的时间去想是怎么推导出这个算法的，而是更多的考虑这类题的特征，为什么能用这种算法，也算是总结规律吧。在学习了“五毒神掌”之后我是有疑虑的，我觉得一道题刷五遍有点过分了，但现在回去看看之前刷的题，还是会做不出来，所以多刷几遍是非常有用的，而且不是一口气刷完，间隔一段时间效果会更好

第一个：暴力法
第二个：双指针法
第三个：正确使用数据结构来解决实际的问题
第四个：升维
第五个：时间换空间

解题算法**：

• 在数组和链表这两种数据结构中，都可以考虑双指针法，比如在数组中的夹逼**，或者链表中的快慢指针
• 升维**，将一维数据结构升维，优化时间复杂度，比如跳表
• 空间换时间**

数组(array)

特点：

• 非受限线性表，顺序结构
• 连续的内存空间，相同的数据类型
• 低效的插入和删除

时间复杂度：

• 随机访问O(1)
• 插入、删除O(n)

链表(linkedlist)

特点：

• 非受限线性表，链式结构
• 不支持随机访问
• 高效的插入与删除
• 需要额外的空间存储指针

时间复杂度：

随机访问O(n)
插入、删除O(1)

多样链表：

• 双链表
• 循环链表
• 静态链表

跳表(skip list)

特点：

• 有序
• 多维的数据结构
• 占用更多内存空间（空间换时间）

时间复杂度：

插入、删除、查找O(logn)

空间复杂度：

O(n)

应用：

redis有序集合使用跳表实现

栈(stack)

特点：

• 受限线性表
• 先进后出

时间复杂度：

入栈、出栈O(1)

应用：

• 浏览器的前进与后退
• 括号匹配
• 表达式计算

队列

特点：

• 受限线性表
• 先进先出

多样队列：

• 双边队列
• 优先级队列

应用：

• LRU cache

数组和链表的异同

相同点：两个都是线性的数据结构，是非常基础的数据结构，是后续高级数据结构的前提，例如树、图。

队列和堆栈是操作受限的线性数据结构，前者先进先出，后者先进后出。这两种数据结构的底层既可以是数组，也可以是链表。覃超老师推荐使用双端队列，deque。

不同点：

• 数组占据内存中连续的部分，而链表对内存要求没有那么严格。
• 数组能够随机访问任意一个位置，而链表则必须一个个遍历过去。
• 两种数据结构查找时间复杂度都是O(n),。如果数组是有序数组，那么通过二分查找，可以让查找变为O(log n).但是链表即便是有序链表也得挨个走过去。不过链表可以升维，有序的链表可以进化成跳表，也就是加多级索引，提高查找效率，这就是一种空间换时间的**。
• 数组的插入和删除操作都是O(n)的时间复杂度，链表则是O(1)的时间复杂度。

本周刷题的时候，覃超老师介绍了五毒神掌，五遍刷题法。之前上过算法小课，刷过一次题目，现在再刷一次题目的时候，发现之前刷过的题目又陌生了，果断药不能停，刷题还需要继续。

此外，有一个理念非常重要，不懂的题目，要果断看答案，不要用太太太多时间思考，否则就会有很强的挫败感。这样子看来，之前的我还是太“憨厚”了，不想出来不看题解，导致时间浪费了，还没有收获（也不是没有，收获了挫败感）。现在觉得算法这个东西，就是听覃超老师的，多刷题才行，熟练度上去了，感觉就有了，后续才有自信心继续做下去，形成良性循环。

本周大部分数组和题目都用到了快慢指针的概念，

• 移动0的时候，就是用慢指针确定不为0的位置，快指针找到0的位置，
• 在去掉重复值，也是慢指针确定重复元素的位置，快指针移动到下一个不相同的元素，然后进行转换。
• 三数之和，用到了三个指针。第一个指针确定第一个元素，二三指针 则是在两侧向内移动

在链表的时候，有以下两个领悟

• 哑节点，作为头节点的前一个节点，确定了合并后链表的起始节点
• 链表合并后，如果其中一个元素提前结束，剩下的节点，只要用指针指过去即可
• 快慢指针是好东西，确定中间位置，确定是否有环，都用得到。

入班第一周的感受：
1、注意审题：有时候做不出来可能是自己想的太复杂了，所以要确认好了题意再做题。强迫自己问个问题。
2、不要浪费时间：不会做就看答案，看答案还不会就一步一步debug，把自己不会的地方用debug看会了，看会了就写总结，是哪里没有考虑清楚，把没考虑清楚的地方记录下来。
3、注重解题**：看答案要多看看人家写的文字，文字中体现了做题人的**，**比代码重要。
4、重复练习：重复练习的时候先把题目的**考虑一遍，第一步干什么、第二步干什么。。。
5、手抄代码：重复做还是不会的话就多抄几遍，并且思路也梳理出来1、2、3 这样加强自己做题的逻辑性。

1 题目过程中，首先先考虑临界条件，数组为null，长度为0的条件。
2 数组的题目都可以优先考虑双指针。
3 递归的时候，就把递归函数当成普通函数写一次。只是设计他的返回值，入参值。
4 做关于树的题目，比如最大值，最小值，路径等题目。
都可以用同一套模板。

1、学习方法
1.1先预习
根据老师给出的链接，熟悉相应的数据结构。

1.2五毒神掌
第1遍，
15分钟之后，没有思路的话，直接看解法，然后背诵解法。
第2遍
马上自己写出刚才背诵的程序-》leetcode提交,多种解法，优化，关注执行时间。
第3遍，（24小时后）
不同解法的熟练程度重复练习
第4遍，（1周之后）
不同解法的熟练程度重复练习
第5遍，面试前一周，
重复之前做的题目。
2、学习内容
学习数组、链表、跳表，栈、队列、优先队列、双端队列
跳表是第一次接触，跳表是针对链表的查询效率低上的改进，引入多级索引的结构。
但是所有的内容也只是过了一遍，还需要刷题来更加的熟悉。
3、学习中遇到的问题
因为对python的语法还没有接触过，所以在看视频的时候，不能完全掌握。需要花时间把python语法了解后，通过5遍学习法，把leetcode的题目，完全消化。本周涉及的知识点和题目都没有完全掌握，下周继续每天多投入时间刻意练习。

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

正文部分，字数不限。

1. 所有的逻辑最终都会归结为 if else, for loop, 和 recursion;
2. 不同语言对于数据结构的实现形式不太一样:
   比如java有stack, queue (priority queue),但是javascript并没有做区分,统一称之为array,也就是双端队列,但其实本质都是相似的;
3. 认识到了数组和链表在计算机内部的存储形式: 数组是需要一段连续的内容,链表可以把分散的内存链接在一起;

还学习到了常用的解决算法的方法:

1. 两个for loop:第二个loop和第一个loop的起始值不一样,可以相差一,也可以一个从头开始,一个从尾部开始;
2. 快慢指针:一个for loop,每次遍历时当符合条件是使慢指针增加一位

在做LeetCode 641题的时候，对于队头队尾的理解很容易把逻辑搞乱。
如：依此往对头添加进两个元素【1，2】，那队尾的元素为1；但如果往队尾依此添加【1，2】的时候，对头元素是多少？这个时候就很容易搞混以为是2。
做题的时候，我觉得很有必要在草稿纸上画出模型，这样有利于自己的理解

1. 用栈的方法来解决坐标系里柱状图的问题
   比如这次做到过的LeetCode 84题 LeetCode 42题，都可以用栈的方法来解决。
   以我所见，这种题目最大的问题都是可以确定一边的边界，而另外一边的边界，要通过不断的遍历才能确定。
2. 链表的双指针解题方法可以覆盖大多数链表的题目，少数特殊的题目完全可以靠记住大概的逻辑来完成。
3. 在C++中有std::array和std::vector两种类似数组的容器，区别是array是从堆上申请的临时内存，而vector是在栈上申请的内存。

删除排序数组中的重复项
刚开始拿到这个题的时候我的第一反应便是用另一个数组来存放数字，但是犯了一个致命错误，就是没有仔细审题。题目说道要在原地修改数组，所以我改变了思路。题目说道不需要考虑超出新长度后面的元素，也就是说在输出的时候我只要输出前面部分的数字即可，所以想到通过循环，与前面数字对比，若不相同，则把前面重复数字替换掉，例如112这情况，在第三个位置发现与第一个位置数字不同的时候，替换第二个位置的数字，使成为122，输出的时候只要将前面两个位置输出即可。

旋转数组
看到题目上说了要求使用空间复杂度为O(1)算法，但第一次还是尝试了通过存放到另一个数组来先将排序排好，再将临时的数组依次存回原来原来数组中。
但毕竟这方法的空间复杂度高了，不符合题意。所以用第二个方法，就是一位一位移动。先将最后一个数字临时存起，再将整个表右移动一位，最后把临时存的数字放置第一位，以此循环k次，实现旋转。但这个方法的时间复杂度高，为O(k*n)。

最后看了别人的题解，学会了用reverse这个函数，即反转。这个方法是基于这样的事实：当旋转数组k次的时候，k%n个尾部元素就会被移到头部，剩下向后移动。这个方法首先将所有元素反转，接着反转前k个元素，最后反转n-k个元素，就能得到相应的结果。此方法时间复杂度为O(n)。

合并两个有序链表
由于在链表上面还不太熟悉，所以直接看了别人的题解。在这题上，运用了迭代的方法。创建一个存储元素的链表，设置一个哨兵点，这样可以在后面容易返回合并后的链表。对比两个链表中的元素大小，存储在创建的链表中，排序后输出哨兵点后的元素，得到最终结果。

合并两个有序数组
由于题目中说明了第一个数组有足够空间存放第二个数组的元素，所以我在这先将第一个数组后面无关的数字进行替换，替换成第二组的数字，接着通过sort函数，直接对替换后的第一个数组排序，得到最终结果。

两数之和
看到题目后第一反应便是通过暴力方法，逐一排查，如果有相等情况，记录下相应位置。但是暴力法导致的就是时间复杂度高，为n^2^
所以看了别人的方法，运用哈希表。通过空间换时间的方式，可以将时间复杂度降到O(1)。在进行迭代并把元素放到列表中的同时，，还会回头来检查表是否已经存在当前元素对应的目标元素。

移动零
此题其实方法也简单，只需要在遍历过程中记录下数为0的个数，再进行数组中位置交换，将0移动到后方。

加一
第一次拿到这题就理解错误了，我将它理解为只需要改变最后一个数字即可，但此题的意思是这个数组就是整个数字，加上一就相当于总数加一得到新的总数。所以要考虑到9+1进一位的情况。这题可能会出现9999这样的所有位数上都为9的情况。所以需要从数组最后一位进行遍历，如果无9，直接加一并返回数组即可，若出现上面说的情况，则数组上所有的数都换为0。遍历结束后，将数组增加一位，并放上0，将数组第一个数字换为1即可得到答案。

如何有效学习算法和数据结构
线上课程

1. 注重预习 - 基础知识自己预习和查看
2. 课堂互动 - 跟着我一起思考和回答问题
3. 课后作业 - 按照切题方法

期待效果

• 职业顶尖级别 - 对于算法数据结构的理解
• 一线互联网公司面试
• Leetcode 300+ 的积累量

《异类：不一样的成功启示录》

精通一个领域

• Chunk it up 切碎知识点
• Deliberate Practing 刻意练习
• Feeback 反馈
• 主动反馈
• 被动反馈

Chunk it up

• 庖丁解牛
• 把复杂的繁杂的知识体系解析为脉络相连的结构
• 人脑是不适合记忆零散的知识的，要掌握这些知识必须要把它变成树状结构

数据结构

• 一维

基础： 数组array（string） 链表linked list
高级：栈stack、队列queue、双端队列deque、集合set、映射map（hash or map） etc

• 二维

基础：树tree，图graph
高级：二叉搜索树binary search tree（red-black tree， AVL），堆heap，并查集disjoint set，字典树Trie，etc

• 特殊：

位运算Bitwise，布隆过滤器BloomFliter
LRU Cache

算法

• IF-ELSE，Switch --> branch
• FOR, WHILE-LOOP --> Iteration
• 递归 Recursion (Divide & Conquer, Backtrace)
• 搜索Search: 深度优先搜索 Depth First Search, 广度优先搜索 Breadth first search, A*, etc
• 动态规划 Dynamic Programming
• 二分查找 Binary Search
• 贪心 Greedy
• 数学 Math， 几何 Geometry
• 注意：在头脑中回忆上面每种算法的**和代码模板

职业要求

• 基本功是区别业余和职业选手的根本
• 基础动作的分解训练和反复练习 --》最大的误区
• 一个题目做一遍是远远不够的

Deliberate Practing 刻意练习

• 刻意练习 -- 过遍数（五毒神掌）
• 练习缺席、弱点地方
• 不舒服、不爽、枯燥
• 生活中的例子：乒乓球、台球

Feeback 反馈

• 即时反馈
• 主动型反馈（自己去找）
• 高手代码（Github，leetcode, etc）
• 第一视角直播
• 被动式反馈 （高手给你指点）
• code review
• 教练看你打，给你反馈

切题四件套

• Clarification 理解题目
• Possible solutions 考虑所有可能
• compare
• optimal （加强）
• Coding（多写）
• Test cases

刷题第一遍
5分钟：读题+思考
直接看解法：注意！多解法，比较解法优劣
背诵、默写好解法

刷题第二遍
马上自己写 -->提交到LeetCode
多种解法比较、体会 --> 优化, 在leetcode上优化比较

刷题第三遍
过一天后，再重复做题
不同解法的熟练程度 --> 专项练习

刷题第四遍
过了一周后：反复回来练习相同题目

刷题第五遍
面试前一周恢复性训练

在参加训练营前自己也做过leetcode的题，大概100多道吧。在参加训练营后听完覃超老师的课，让我对算法的学习有了新的认识。
从前对于一些简单的题，accept后就不管了，也没有对于一些通式（或者说是解题的套路）进行总结，导致解一些难题的时候发现自己的思路太少。
后来慢慢感觉到不对，在做完100多道题后开始学会总结，在思路上的空间确实在增加，但缺乏刻意练习，也就是“五毒神掌”。
希望在得到老师和同学们的指点后，自己可以更好的提高自己的算法水平。

1. 用栈的方法来解决坐标系里柱状图的问题
   比如这次做到过的LeetCode 84题 LeetCode 42题，都可以用栈的方法来解决。
   以我所见，这种题目最大的问题都是可以确定一边的边界，而另外一边的边界，要通过不断的遍历才能确定。
2. 链表的双指针解题方法可以覆盖大多数链表的题目，少数特殊的题目完全可以靠记住大概的逻辑来完成。
3. 在C++中有std::array和std::vector两种类似数组的容器，区别是array是从堆上申请的临时内存，而vector是在栈上申请的内存。

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

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

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

跟帖格式：

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

1. 数组与链表的时间复杂度分析比较

2. 栈和队列的特性

• 栈 Stack：先进后出 FILO
• 队列 Queue：先进先出 FIFO
• 栈和队列的添加、删除操作皆为O(1)，查询为O(n)
• 双端队列的插入和删除的时间复杂度为O(1)，查询为O(n)
• 优先级队列的插入操作为O(1)，取出操作为O(logn) （按元素的优先级取出）

3. 实战题目：[283] 移动零

• 题目

  给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  示例:

  输入: [0,1,0,3,12]
  输出: [1,3,12,0,0]
  

  说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。

• 思路：

• 解法一：遍历数组，遇0删除，在末尾添加0

  • 设置一个尾指针 end = nums.length - 1

  • 遍历数组，若那一项为0，则splice删除那一项，在数组末尾push一个0

  • i-- 以及 end--

  • 如果 i >= end 就停止循环

  • O(n^2)

• 解法二：遍历数组，设定一个指针指向数组开头，若当前遍历项不为0，则把当前遍历项的值放到指针所指项去，若当前项与指针所指向不同，则当前项变为0，指针后移一位。这样就能保证，数组前面的元素都是非0的，而数组后面的元素都是0

  • 设置指针 j 指向数组的开头（j = 0）

  • 遍历数组

  • 如果当前遍历的数组的这一项不为0，则把这一项的值赋给指针 j 所指向的数组那一项的值

    nums[j] = nums[i]

  • 如果 i 和 j 的值不相等的话， 就把 i 这一项的值赋给 0 nums[i] = 0

  • 指针后移一位j++

• 代码实现

  function moveZeroes(nums){
    // 解法一：
    let len = nums.length;
    let end = len - 1;
  
    for (let i = 0; i < len; i++) {
        if (i >= end) break;
  
        if (nums[i] === 0) {
            nums.splice(i, 1);
            i--;
            nums.push(0);
            end--;
         }
    }
  
    //解法二：
    let j = 0;
    let len = nums.length;
  
    for (let i = 0; i < len; i++) {
      if (nums[i] != 0) {
        nums[j] = nums[i];
  
        if (i != j) {
          nums[i] = 0;
        }
  
        j++;
      }
    }
  }

4. 实战题目：[11] 盛水最多的容器

• 方法一：双重循环，暴力枚举

• 时间复杂度：O(n^2)

  // height是一个数组类型
  function maxArea1(height){
      let max = 0;
      
      for(let i = 0; i < height.length - 1; i++){
          for(let j = i + 1; j < height.length; j++){
              let area = (j - i) * Math.min(height[i], height[j]);
              if(area > max) max = area;
          }
      }
      
      return max;
  }

• 方法二：双指针 + 左右夹逼（左右边界，往中间收敛）

• 时间复杂度：O(n)

• 这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

  我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 max 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 max，并将指向较短线段的指针向较长线段那端移动一步。

• i 指向数组开头， j 指向数组末尾（此时宽度最大，但高度不一定最高），每次拿到 i 与 j 中较小的值，计算面积，往中间靠

  每次高度较小的指针所指项往中间移一位，往后找看看能否找到高度更高的项，虽然宽度减少了，但如果高度足够高也可以增大面积

  在宽度较大的情况下，若能比较找到高度较高的项，就能找到面积最大的

  function maxArea2(height){
      let max = 0;
      let len = height.length;
      
      for(let i = 0, j = len - 1; i < j;){// 注意这里循环的结束条件
          let minHeight = height[j] > height[i] ? height[i++] : height[j--];
          let area = (j - i + 1) * minHeight;
          max = Math.max(max, area);
      }
      
      return max;
  }

5. 实战题目：[70] 爬楼梯

• 题目：

  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  **注意：**给定 n 是一个正整数。

  示例 1：

  输入： 2
  输出： 2
  解释： 有两种方法可以爬到楼顶。
  1.  1 阶 + 1 阶
  2.  2 阶
  

  示例 2：

  输入： 3
  输出： 3
  解释： 有三种方法可以爬到楼顶。
  1.  1 阶 + 1 阶 + 1 阶
  2.  1 阶 + 2 阶
  3.  2 阶 + 1 阶
  

• 思路一：求第i个斐波那契数 (较优)

  根据思路二的推导可得公式：

  f(n) = f(n-1) + f(n-2)

  时间复杂度：O(n) / 空间复杂度：O(1)

  function climbStairs1(n){
      if(n <= 3) return n;
      
      let f1 = 2, f2 = 3, f3 = 0;
      while(n>3){
          f3 = f2 + f1;
          f1 = f2;
          f2 = f3;
          n--
      }
      
      return f3
  }

• 思路二：动态规划

  本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和

  1. 爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
  2. 爬上 n-2 阶楼梯的方法数量，因为再爬2阶就能到第n阶

  所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
  同时需要初始化 dp[0]=1和 dp[1]=1
  时间复杂度：O(n)

  • 台阶 n 为1：总共爬楼梯的方法 f 为1

  • n=2, f=2

  • n=3, f=3 = f(n=2) + f(n=1)

  • n=4, f=5 = f(n=3) + f(n=2)

    ......

  • f第n阶台阶 = f第n-1阶台阶走1步 + f第n-2阶台阶走2步

  • 找最近重复子问题

• 时间复杂度：O(n) / 空间复杂度：O(n)

  function climbStairs2(n){
      const dp = [];
      
      dp[0] = 1;
      dp[1] = 1;
      
      for(let i = 2; i <= n; i++){
          dp[i] = dp[i-1] + dp[i-2];
      }
      
      return dp[n];
  }

6. 实战题目：[15] 三数之和

• [1] 两数之和

  给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

  你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

  示例:

  给定 nums = [2, 7, 11, 15], target = 9
  
  因为 nums[0] + nums[1] = 2 + 7 = 9
  所以返回 [0, 1]
  

  • 思路

  // 方法一：两重暴力循环
  function twoSum1(nums, target){
  	for(let i = 0; i < nums.length - 1; i++){
          for(let j = i + 1; j < nums.length; j++){
              if(nums[j] === target - nums[i]) return [i, j];
          }
      }
  }
  
  
  //方法二：Hash表
  function twoSum2(nums, target){
      let temp = [];
      
      for(let i = 0; i < nums.length; i++){
          if(temp[nums[i]] !== undefined){
              return [temp[nums[i]], i]
          }
          temp[target - nums[i]] = i;
      }
  }

• 三数之和

  给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

  **注意：**答案中不可以包含重复的三元组。

  示例：

  给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  
  满足要求的三元组集合为：
  [
    [-1, 0, 1],
    [-1, -1, 2]
  ]
  

• 思路：由 两数之和的 a + b = target 变为了 a + b + c = 0 (即：a + b = -c)

  // 方法一：暴力三重循环 [但是这样不能剔除重复数组]
  // 时间复杂度：O(n^3)
  function threeSum1(nums){
      let ans = [];
      for(let i = 0; i < nums.length - 2; i++){
          for(let j = i + 1; j < nums.length - 1; j++){
              for(let k = j + 1; k < nums.length; k++){
                  if(nums[i] + nums[j] + nums[k] === 0){
                      ans.push([nums[i], nums[j], nums[k]]);
                  }
              }
          }
      }
      
      return ans;
  }

• 方法二：hash表

• 方法二：排序 + 双指针

  三数之和图解

  function threeSum(nums){
      let ans = [];
      const len = nums.length;
      
      if(len < 3 || nums === null) return ans;
      
      //升序
      nums.sort((a, b) => a - b);
      
      for(let i = 0; i < len; i++){
          if(nums[i] > 0) break;
          
          if(i > 0 && nums[i] === nums[i-1]) continue;
          
          let L = i + 1, R = len - 1;
          while(L < R){
              const sum = nums[i] + nums[L] + nums[R];
              
              if(sum === 0){
                  ans.push([nums[i], nums[L], nums[R]]);
                  //去重
                  while(L < R && nums[L] === nums[L+1]) L++;
                  while(L < R && nums[R] === nums[R-1]) R--;
                  L++;
                  R--;
              }
              
              else if(sum < 0) L++;
              else if(sum > 0) R--;
          }
      }
      
      return ans;
  }

7. 实战题目：[141] 环形链表

• 方法一：暴力解法 (哈希表)

  • 遍历链表，使用Set记录下来你访问过的节点，如果有重复，则说明有环
  • 空间复杂度：O(n)

  function hasCycle(head){
    let set1 = new Set();
  
    while (head) {
      if (set1.has(head)) return true;
  
      set1.add(head);
      head = head.next;
    }
  
    return false;
  }

  • 第一种方法，还看见有人通过Symbol设置一个独一无二的值flag，然后把链表中的所有值都修改为flag，如果遍历时有节点的值和flag相等，则有环，否则无环。（ps: 不是很赞同这种修改原数据的解法）

• 方法二：快慢指针 （双指针）

  • 使用O(1)的内存来解决问题
  • 设置一快一慢两个指针，快指针一次走两步到.next.next，慢指针一次走一步到.next，如果链表不存在环形结构，那么快指针和慢指针不会相遇，且快指针会先走到null。如果存在环形结构，快指针总会和慢指针相遇。

  function hasCycle(head){
      if(!head || !head.next) return false;
      
      let fast = head.next;
      let slow = head;
      
      while(fast !== slow){
          if(!fast || !fast.next) return false;
          
          fast = fast.next.next;
          slow = slow.next;
      }
      
      return true;
  }

8. 学会的解题**

1. 升维**

2. 空间换时间

3. 指针 / 双指针

4. 双指针 + 左右夹逼（左右边界，往中间收敛）

5. 找最近重复子问题

6. 没有思路的时候，就列举一些情况，找规律，然后递推，找出公式，找重复的地方

how
chunk it up
语法树，明确根/主干 将叶子detail hang on
deliberate practicing
过遍数
缺陷
不舒服 不爽 枯燥
feedback
主动 -- 自己去找 高手代码 第一视角直播
被动 -- 高手指点 code review
切题 -- 系统性思考习惯
1.clarification
2.possible solutions compare time/space
3.coding (多写)
4.test case

一维数据结构
不受限 array(string) linkedlist
受限 stack queue deque

在刷题的过程中，发现题目还是挺多的，全刷完压力挺大，自己按五毒神掌计划了一下
工作日刷一遍实践题、完成作业，周末第二遍，下周末再刷一下这周的题

课前总结

1. 如何精通一个领域

• Chunk it up 切碎知识点
  • 把知识分类切分
  • 建立脑图（任何知识都是关联的）
• Deliberate Practicing 刻意练习
  • 过遍数（五毒神掌）
    • 任何题目至少过5遍
    • 刷第一遍
      • 读题思考时间控制（5-10分钟）
      • 若没思路，直接看解法。注意：多解法，比较优劣
      • 背诵，默写好的解法
    • 第二遍
      • 马上自己写-->提交leetcode
      • 多种解法，体会优化
    • 第三遍
      • 过一天后，重做题目
      • 不同解法的熟练程度，进行专项训练
    • 第四遍
      • 过了一周，反复来回练习相同题目
  • 练习缺陷，弱点的地方
• Feedback反馈
  • 主动式反馈
    • 阅读高手代码（github、leetcode）
    • 第一视角直播
  • 被动式反馈
    • 高手指点
    • code review

注意

1. 视频以1.5～2.0倍速度播放，暂停+难点反复
   （三分理解，七分训练）

2. 摒弃旧习惯（最重要）

• 不要死磕
• 五毒神掌（敢于放手、敢于死记硬背代码）
• 不懒于看高手代码（注意leetcode国际版高票代码）

week 01学习总结

1. 刚开始做的leetcode的题目时候，虽然脑中已知道有五毒神掌大法，但发现自己依然还是按照过去的旧习惯做法，几天下来，发现学习效率依然很慢，无法提高。后来回看笔记，突然醒悟，时刻提醒自己，学习算法及数据结构务必紧尊五毒神掌大法，必须摒弃旧有的习惯，切记切记。

2. 在leetcode上目前遇到的题目，的确，不管难度与否，要找出马上最优解是不可能，但题目的暴力解法可以算是最基础的解法，此解法是必须理解的。对于最优解，可以从基本情况出发，找出最近重复的子问题，最终加以优化。

3. 对于数组这样基础数据结构所构成的问题解法，一般可以采用双指针解法，例如：左右指针向中间夹逼。另外，可以考虑以空间换时间的**。

4. 在查看最优解的过程中，我的理解，最优解不单时间复杂度要低，但我认为代码简单明白却是比时间复杂更为重要，毕竟代码是一种解决问题的语言，要让他人从自己所写的代码中，理解解决问题的**更为重要。

学习笔记 week01 Summary

Array:

• Prepend: O(1) [*]
• Append: O(1)
• Lookup: O(1)
• Insert: O(n)
• Delete: O(n)

LinkList:

• Prepend: O(1)
• Append: O(1)
• Lookup: O(n)
• Insert: O(1)
• Delete: O(1)

Skip List:

升维 + 空间换时间

Add index for some node: 一级索引，二级索引(more coarse)，……，多级索引

时间复杂度 O(log n)

维护成本较高。添加和删除都要重新对索引进行修改

空间复杂度 O(n)

Q70

！找最近 重复子问题

第三级台阶走法：第一级台阶 + 2步； 第二级台阶 + 1步

f(3) = f(1) + f(2)

f(4) = f(2) + f(3)

->fibonacci

懵逼时候：

1. 能不能暴力解？基本情况
   
2. 找最近重复子问题 （重复性）

双指针方法

1.可能要排序？

2.向中缩进 （根据题目条件判断缩进策略）

E.g, 3 sums and 两柱中间面积

* 快慢指针 （检测链表有环）

deque 双端队列

Priority queue

Push: O(1)

Pop: O(log n) 按照元素优先级取出

底层具体实现的数据结构较为多样和复杂：heap, bst, treap

最近相关性 -> 用栈来解决

E.g. 括号字符串的有效性 Q20

先来后到 -> queue

E.g. Sliding window -> queue Q239

这是第一周，感觉自己没有太跟上节奏以及进度，到最后整的自己有点手忙脚乱，幸好第一个星期没有太复杂的内容，还能勉强跟上，希望自己以后能跟上课程的节奏。这个星期从最开始的预习视频看起直到昨天晚上才把第一个星期的视频看完。期间搭建了 vscode 编程环境，第一次通过 vscode 提交题目答案，看官方题解，重新默写题解等。没有严格按照老师讲的“五毒神掌”的方式来练，主要是时间有些不够了。这个星期的收获通过视频了解了“跳表”，学习了双指针移动零，使用递归、动态规划等方式解决爬楼梯。有了第一个星期的经验，下个星期应该能做的更好吧。

一：双端队列的2种实现方式对比：
连接见：https://leetcode-cn.com/problems/design-circular-deque/

1. Clarificaiton

• 不能使用内置的双端队列库，即需要自己定义一套；
• 只需支持双端插入、删除、查询；
• 数据类型为整形，范围在[1, 1000]，不存在大数据量的情况，不会因为数据量造成OutOfMemoryError。

2. Possible solution

• 利用带头指针的双向链表存储，在首尾的插入、删除、查询的时间复杂度均为O(1);
• 利用数组存储，需要2个指针，记录首尾元素的位置，使插入、删除、查询的时间复杂度均为O(1)；
• 2种方案时间复杂度均可接受，链表需要存储前、后指针，所以空间占用较大，但实现容易；数组方式时间需要边界条件的处理技巧。

3. Coding
   链表见：https://github.com/geekzhu1314520/algorithm006-class01/blob/ece6a8cc063c0314ad194c3e137ab6c414057d6f/Week_01/G20200343030523/id_523/LeetCode_641_523_List.java
   数组见：https://github.com/geekzhu1314520/algorithm006-class01/blob/ece6a8cc063c0314ad194c3e137ab6c414057d6f/Week_01/G20200343030523/id_523/LeetCode_641_523_Array.java

4. Test Cases
   需覆盖队尾增删查、队首增删查、对满空判断。

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

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addFirst("a");
        deque.addFirst("b");
        deque.addFirst("c");
        System.out.println(deque);

        String str = deque.getFirst();
        System.out.println(str);

        while (!deque.isEmpty()){
            System.out.println(deque.pop());
        }
        System.out.println(deque);
    }
}

三、分析 Queue 和 PriorityQueue 的源码

1. Queue是队列的抽象接口，PriorityQueue是对接口Queue一种实现；
2. Queue定义了基本的增（add、offer）、删（remove、poll）、队首查（element、peek）操作。
3. PriorityQueue是一种完全二叉树，通过二叉小顶堆实现，底层数据结构是动态数组；
4. PriorityQueue中，对于下标为k的元素，其父节点下标为 (k - 1) >>> 1，左孩子下标为(k << 1) + 1，右孩子下标为(k << 1) + 2，这个规律是插入和删除元素的关键点；
5. 插入元素，关键代码如下，默认从最大下标size，开始不断预期父节点((k - 1) >>> 1)比较。如果比父亲节点小，则与父节点交换位置，直到找到大于父亲节点的位置，进行插入。

    public boolean offer(E e) {
        if (e == 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;
    }

    @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

6. 删除元素，关键代码如下，把最后位置（size-1）的元素，从删除节点开始，与左右孩子节点（(k << 1) + 1、(k << 1) + 2）较小者比较，如果>,则交换位置，直到找到<=孩子节点的位置，赋值并停止。

    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

7. PriorityQueue时间复杂度，add/offer：O(logn)、remove：O(logn)、peek:O(1)

在进行链表相关操作时，可在头节点前设置一个前驱节点，以此简化操作并防止头节点丢失。

Array数组

• Array

  • Length fixed, Memory Wrap-around
  • 数组Array是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据
  • Index（access elements via index, 通过索引随机访问， O(1)）
  • Insert (insert, following elements move backwards, O(n))
  • Delete (delete, following elements move forwards, O(n))

  Operation	Complexity
  access	O(1)
  insert	O(n)
  delete	O(n)

• 数组编程

  • 快慢指针，e.g. 移动零
  • 左右夹逼，e.g. 三数之和
  • 警惕数组访问越界

• 容器能否完全代替数组

  • 如Java的ArrayList，可以将很多数组操作的细节封装起来，支持动态扩容，存储空间不够时，自动扩容1.5倍
  • 最好在创建ArrayList的时候事先指定数据大小
  • ArrayList无法存储基本类型，如int需要封装为Interger，封箱开箱有一定性能消耗
  • 数据大小事先已知，对数据的操作非常简单，用不到ArrayList提供的大部分方法，可以直接使用数组
  • 多维数组时用数组更直观
  • 业务开发可直接使用容器，底层开发要求性能时用数组

• 大多数编程语言，数组从0开始编号，而不是从1

  • 数组的下标其实时地址的偏移
  • 如果从0开始，a[0]表示首地址，a[k]就表示偏移k个type_size的位置
  • 如果从1开始，a[1]表示首地址，a[k]就表示偏移k-1个type_size的位置，每次随机访问就多一次减法操作

LinkedList链表

• 数组：内存空间连续，长度固定
• 链表：内存空间不需要连续，通过指针Next串联各节点Node
• LinkedList
  • Improve Insert and Delete
  • Length unknown
• 顺序查找法适用于存储结构为 顺序 或 链式 的线性表，即为数组和链表。

Singly Linked List 单链表

• Element have a Pointer, point to Next Element

• Access (Need traverse from begin, O(n))

• Insert (New node Next point to next, and pre point to new, O(1)), 无需像数组一样大量拷贝和挪动

• Delete (O(1))

  Operation	Complexity
  space	O(n)
  prepend	O(1)
  append	O(1)
  lookup	O(n)
  insert	O(1)
  delete	O(1)

数组与链表的区别

• 链表适合插入、删除，给定前驱节点时，时间复杂度是O(1)，数组适合通过下标随机访问(数组适合查找)，O(1)

• 数组查找最好的时间复杂度(快排)是O(logn)

  操作	数组	链表
  随机访问	O(1)	O(n)
  插入	O(n)	O(1)
  删除	O(n)	O(1)
  连续	元素必须连续	节点可不连续
  长度	固定，超出需扩容并拷贝	无限

如何基于链表实现LRU（最近最少使用，Least Recently Used）缓存淘汰算法

• 维护一个有序单链表，越靠近链表尾部的是越早之前访问的
• 当有一个新的数据被访问时，就从链表头开始顺序遍历链表
• 如果此数据之前已经被缓存在链表中，遍历得到这个数据对应的节点，并将其从原位置删除，插入到链表的头部
• 如果此数据没有在缓存链表中，可以分为两种情况
  • 如果此时缓存未满，则将此节点直接插入到链表的头部
  • 如果此时缓存已满，则链表尾节点删除，将新的数据节点插入链表的头部
• 至此就用链表实现了一个LRU缓存
• 每次都需要遍历链表，O(n)，可以使用散列表Hash Table记录每个数据的位置将其降到O(1)
• 还可以用双向链表等实现LRU算法

其他链表形式

• 单链表，单链表有环，循环链表，双向链表，双向循环链表
• Doubly Linked List 双向链表: Element have Next and Previous pointer

链表为空的判断条件

• 带头单链表，head.Next = null
• 带头循环链表，head.Next = head
• 其他
  • 带头的双向链表，head.Next = head && head.Prev = head
  • 不带头的（循环）链表，list = null

链表编程

• 理解指针的含义
  • p.Next = q, .Next在赋值等号左边，表示指针，将p的Next指针指向q，即p的下一个节点是q
  • q = p.Next, .Next在赋值等号右边，表示节点，将p的下一节点赋值给q
• 警惕指针丢失、重复指向
  • p节点后面插入x

  //p -> 
  //p -> x -> 
  //错误:
  //p.Next = x
  //x.Next = p.Next //环
  //正确1:
  //tmp := p.Next
  //p.Next = x
  //x.Next = tmp 
  //正确2 (better) : 
  //x.Next = p.Next
  //p.Next = x
  

• 使用前驱指针pre，使用锚点dummy or hint
• 注意边界条件

Skip List 跳表

• 链表加速
  • 前提：基于链表已经排好序，一般是递增
  • 方法：增加logn级索引
  • **：升维+空间换时间(常用加速策略)
• 时间复杂度
  • 查询，TC: O(logn), SC: O(n) - e.g. 查1024，只需要遍历10步
  • 插入、删除，需要处理索引，TC: O(logn)
• 跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，甚至可以替代红黑树（Red-black tree）
• Redis中的有序集合（Sorted Set）使用跳表而不是红黑树
  • Redis有序集合是跳跃表实现的，直接这么说有失偏驳，他是复合数据结构，准确说应该是由一个双hashmap构成的字典和跳跃表实现的
  • Redis中的有序集合支持的核心操作主要有下面这几个：
    • 插入一个数据；
    • 删除一个数据；
    • 查找一个数据；
    • 按照区间查找数据（比如查找值在[100, 356]之间的数据）；
    • 迭代输出有序序列。
  • 其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
  • 对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
  • 当然，Redis之所以用跳表来实现有序集合，还有其他原因，比如，跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

Stack 堆栈

• FILO (压栈)
• 插入，取出，O(1)
• 随机访问，O(n)
• 如何实现栈：Slice or Linked List
  • 用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈
• 应用举例
  • 函数调用栈，临时变量、函数都放在栈中
  • 表达式求值，两个栈：元素值，运算符
  • 浏览器的前进后退，两个栈
• 为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
  • 其实，我们不一定非要用栈来保存临时变量，
    只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，是最顺理成章的选择。
  • 从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。
    所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。
    而要实现这个，用栈就非常方便。
    在进入被调用函数的时候，分配一段栈空间给这个函数的变量，
    在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。
• 在栈空的情况下，不能作出栈操作，否则产生溢出
• 栈一定是顺序存储的线性结构? 不一定，栈分顺序栈和链式栈。
• 空栈就是所有元素都为0的栈？错误
• 一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D？错误
• 将元素1、2、3、4、5进行入栈出栈操作（一次只能操作一个元素）。
  其中入栈需按从小到大的顺序，那么可能的出栈顺序有：
  • 1, 3, 2, 4, 5
  • 4，5，3，2，1

  A：
  入：1
  出：1
  入：2 3
  出：3 2
  入：4
  出：4
  入：5
  出：5
  
  D:
  入：1 2 3 4
  出：4
  入：5
  出：5 3 2 1
  

Queue 队列

• FIFO（排队）
• 插入、取出，O(1)
• 随机访问，O(n)
• 如何实现队列：Slice or Linked List
  • 用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列
    • 在用数组实现的非循环队列中，队满的判断条件是tail == n，队空的判断条件是head == tail
  • 循环队列，避免数据搬移
    • 循环队列，队列为空的判断条件仍然是head == tail
    • 当队满时，(tail+1)%n=head
  • 阻塞队列其实就是在队列基础上增加了阻塞操作
    • 生产者-消费者模型
  • 并发队列，线程安全的队列
• 对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队
  • e.g. 线程池
• 在有头节点的链队列的出队操作中，一般只需修改队头指针；
  但当原队列中只有一个节点时，该节点既是队头也是队尾，故删去此节点时也需要修改队尾指针，
  使其指向头节点，且删去此节点后队列变空。正确。

Deque 双端队列

• Double-End Deque，两端可以进出
• 插入、取出，O(1)
• 随机访问，O(n)

Stack, Queue, Deque

• Java, Python, C++ 等已有基础实现

PriorityQueue

• 优先队列
• 正常入，按照优先级出
• 插入，O(1)
• 取出，O(logn) - 按照元素的优先级取出
• 实现较为多样和复杂，如以下
  • Heap 堆
    • 如：Binary（二叉堆）, Binomial（多项式堆）, Fibonacci（斐波那契堆）
    • 如 Mini Heap 小顶堆，越小优先级越高，是二叉堆，每一个根节点要小于其左、右子节点，则最小的永远在根节点
    • 如 Max Heap 大顶堆
    • https://en.wikipedia.org/wiki/Heap_(data_structure)
  • Binary Search Tree 二叉搜索树 （平衡二叉树，红黑树，AVL树等都可）
  • Treap

算法当中几个点的重要性排序： 有序空间 > 时间 > 无序空间

当一个问题具有最近相关性的时候用栈来解决

很多困难的解法是生活中已经存在的解法，只是被换成了代码的方式把它显示出来，在写代码前用条件语句画出来再写代码，代码会更优美

链表和哈希表的组合使用

• LRU缓存，双向链表（快速插入删除） + 哈希表（快速查找），新增的时候有些麻烦，先看新增元素在缓存中是否存在，存在就将该元素从所在位置移动至尾部，不存在的话如果空间没有满则插入到末尾，如果满了则将首节点删除再出入尾部。
  

• redis有序集合，有序集合中有六个方法：

1. 添加一个成员对象；
2. 按照键值来删除一个成员对象；
3. 按照键值来查找一个成员对象；
4. 按照分值区间查找数据，比如查找积分在 [100, 356] 之间的成员对象；
5. 按照分值从小到大排序成员变量；
6. 根据排名区间查找成员对象
   方法1-5可以通过散列表和跳表组合完成，其中查找为O(1)，新增修改为O(logn),但是第六个方法则很费时间，相关优化暂时还没学到有关知识点，后面更新。

• linkedhashmap 其中linked 代表双向链表而不是代表链表法，散列表实现中有开放地址法和链表法，其中前者适合在数据较少情况下使用，工业级的链表法中如果在对散列表扩容时要缓慢的将旧表移到新表中，期间要维护两张表的数据。

priorityQueue源码分析：

二叉堆的介绍：
其中小顶堆中父节点肯定小于子节点，大顶堆相反。
二叉堆源码分析

1. 编码技巧方面：自顶向下编码设计
2. 刷题方法：五毒神掌（过遍数）误区：只刷一遍。一定要把常见解题套路，烂熟于心。
3. 常见解题套路：1.暴力法 2双指针 3.升维，空间换时间
4. 万变不离其宗：解题思路，找最近 重复子问题
5. 个人理解：数组和链表是最基本的数据结构，栈，队列，优先队列，双端队列这些数据结构，底层都有数组和链表的实现版本
6. 对java 数据结构的Api的使用有了新的认识。

在解决算法题之前，梳理题目，并将整体流程大概写下，不会写的方法先抽象出来，再单独将抽象出来的复杂逻辑玩成。这样可以方便在遇到陌生问题时高效的进行分析。如果在分析问题时总是想复杂的逻辑，会浪费大量时间。

1、仔细审题不要上来看个大概就开始写。
2、没有思路的话直接看题解，不要一直纠结自己为什么什么想法都没有。
3、看了题解还是一脸懵逼，就照着别人的多敲几遍，debug几次，看看输出的内容，反复几次就会有不一样的感觉。
4、每个题都要都要手敲。
5、多找几种不同的解题方法。
6、多练！多练！多练！
7、一开始可能刷题时间会很慢，但是万事开头难，只要坚持住，就会有胜利的希望。

学习的本质

最近我听一位老师说：学习的本质就是模仿加反复地刻意练习，这个观点与覃超老师的观点不谋而合。

他说告诉我们，如果一个题如果想了20分钟还做不出来，就不要去想了，直接去看优秀的答案，然后学习他们的方式就行了。这个过程正是“模仿“的过程；他还提出了一个五毒神掌的方法，这个方法其实就是“反复刻意练习”的过程。

学习算法的时候，总会让人自我怀疑，怀疑自己是个笨蛋。越学越沮丧，导致难以坚持。学习的过程中如果有不断地正向反馈，这个学习过程才能持续下去，否则什么都学不到。我们一开始花了太多的时间在一个题目上，一是时间不允许，二是这样违背了学习的基本规律。所以，感谢覃超老师一开始就把我的那个心结给打开了。

另外一件事情，他说的非常有意义，就是我们有一个最大的误区就是：算法题目只做一次。实际上，根据艾宾浩斯遗忘和惨痛的学习经验告诉我，学习只学一遍是对自己大脑过分的自信了。好在我是一个iOS软件工程师，我专门针对五毒神掌方法开发了一个超级粗糙的Algo App。这个功能是在日历中添加2天、一周、半个月、一个月后的时间提醒。我每次做完第一遍的算法题目之后，就在我这个Algo中快捷添加事件提醒。这样督促我执行五毒神掌。

覃超老师常说，授人以鱼不如授人以渔。他授予我最大的渔就是以上两点。

这周主要学习了有关array / linked list / stack /queue 的内容，虽然内容不难但题目还是挺灵活的。我做那个rotate array的题时，完全没想到可以先全部翻转array，然后再部分翻转，但看完答案觉得这简直也太巧妙了吧！还有在刷题时的一个感觉，经常是写完 提交一气呵成，但经常是想的过于简单，一些特殊/边界情况没有考虑周全。还有知道了五毒神掌，并在逐渐实践，因为原来我确实是基本做完了一道题就不怎么再看了。
以及记录一下这类题的常见考点：
Array：经常会用到two points的移动，注意边界条件， 注意题目是否说明sorted/是否需要in place，经常是一个loop O(n) 但要想好每次loop需要做的事情
Linked list：可以通过画图，主要是要一步步弄清楚每个node在连接谁以及被谁连接，细心！注意是否在操作时让list成环了，以及判断cycle：一快一慢
Stack/queue/deque：根据不同情况用不同结构，stack主要表现一种两两队赢的相关性，比如成对的括号/计算能装多少水/记录之前的结果并能对应上马上之后的结果；queue比较体现顺序；deque是兼顾两边。虽然stack本身很简单，但这次遇到的hard问题我才知道原来stack的用法是很需要技巧的。
这周写的的题目还需要复习，加油ww

1、底层核心数据结构：Object[] 组成的数组，作为优先队列盛放数据的容器
2、初始大小：默认的构造方法 数组的初始大小为：DEFAULT_INITIAL_CAPACITY = 11，同时默认的构造方法中的Comparator为null
3、扩容方式：当原数组元素个数 < 64时，将扩容至原数组长度 * 2 +2。
当原数组元素个数 >64时，将扩容至原数组长度的1.5倍，即 原数组长度 + (原数组长度 / 2)
4、offer、poll、remove、add操作的时间复杂度分析 O（logn）
remove(Object obj)和contains()操作的时间复杂度为O（n）
peek、element和size操作的时间复杂度为O（1）

[21] 合并两个有序链表 题目总结
（1）迭代法：
归并排序的**，因为两个链表有序，只做一次排序即可，稍作改进，当其中一个有序表结束时，可以将 next 指向另一个链表的剩余节点，不需要遍历完之后作判断，这样节省了比较时间，时间复杂度 O（n + m）
（2）递归法：终止条件：当 l1 或 l2 为空时，返回剩余 l2 或 l1 结束；
返回值为每一层都已排好序的头指针；
递归内容：当 l1 的值 val 较小时，l1 的 next 指向之后排完序的链表头，否则，l2 的 next 指向排好序的链表头；
时间复杂度：O（n + m）空间复杂度也是一样，递归会消耗（n + m）个栈空间

[42] 接雨水 题目总结
（1） 暴力法 遍历每一根柱子，找出该柱子左右两边最高的柱子取较小值，较小值与当前柱子差值为接雨水数
此题有很多解法，后续抽空总结...

[641] 设计循环双端队列 题目总结 https://blog.csdn.net/xiaoma_2018/article/details/103997820
实现该循环队列，需要注意以下几点：

1.判断队列为空？ 当收尾指针相等，队列为空，head == tail
2.判断队列已满？ 当尾指针的下一位等于头指针，队列已满，(tail + 1 + capacity) % capacity == head;
3.初始化队列时？ 首尾指针从0开始， head = tail = 0
4.从头部插入数据？ head 指针向前移动， head = (head - 1 + capacity) % capacity
5.从尾部插入数据？ tail 指针向后移动， tail = (tail + 1) % capacity
6.从头部删除数据？ head 指针向后移动， head = (head + 1) % capacity
7.从尾部删除数据？ tail 指针向前移动， tail = (tail - 1 + capacity) % capacity
8.从尾部读取数据？ 考虑头部插入（head 前移一位）和尾部插入（插入后，tail后移一位），所以读取data[(tail - 1 + capacity) % capacity]

[26] 删除排序数组中的重复项 题目总结

用双指针遍历

学习笔记
1.一道题要做好几遍才会懂 参考别人的思路自己写 跑不过 再改 再写 最后挑出个人最好的解法放到作业本里
2.一开始 看着别人的思路 自己动手写就出现各种错误 原因还是自己不够熟练💪
3.C++在操作数组的时候一定要检查数组越界
4.在有序线性数据结构中可以使用一快一慢的指针来处理很多问题
5.可以利用空间换时间来提高速度 例如unordered_map heap 等

第一周时间比较仓促，也总算开头了，立两个flag吧：

1. 增加遍数，即五遍刷题法；
2. 增加量，每周尽量多做几道题（把每周作业里的题目做完更好）；

有一段时间没有刷过题了，感觉有些生疏，后面加大刷题力度。

了解了一些数据结构

• 数组
• 链表
• 跳表
• 栈
• 队列
• 双端队列

学到了一些代码技巧

• 自顶向下的代码组织结构
• 双指针
• 用栈解决“洋葱”类问题

实践了一些学习方法

• 查阅jdk源码学习数据结构
• leetcode做题技巧：审清题、看题解、自己写、多次写

认识了一些算法**

• 升维
• 空间换时间

关于Queue与Priority Queue的源码分析

Queue

Queue在java中只是接口协议，具体实现类是ArrayQueue和Priority Queue；
接口声明了入队方法：add, offer, 出队方法：remove, poll, 返回队头方法：element, peek；
在队列操作失败时，前者抛出错误，后者返回特殊值；

Priority Queue

除了实现队列接口的基本方法，对入队方法进行的调整，让队头有序，按元素大小的排序出队；
入队方法将队列实现为一棵完全二叉树，默认是小顶堆，也可以通过自定义比较器的方式调整为大顶堆或其它优先级；

学习笔记

1.数组

概念

• 数组是一种线性表的数据结构，用一组连续的内存空间存储相同类型的数据
• 线性表：每个数据最多只有一个前驱和后继节点如数组、链表、队列、栈
• 非线性表：树、图、堆
• 连续的内存空间和相同的数据类型保证了可以实现随机访问

操作

• 随机访问：时间复杂度O(1)
• 插入：尾部插入O(1)；随机插入O(n)
• 删除：删除最后一个O(1)；随机删除O(n)

2. 链表

概念

• 链表是一种物理存储单元谁给你非连续、非顺序的存储结构，数据元素的逻辑顺序通过链表中的指针实现
• 循环链表：尾结点只想头结点，可以是单链表也可以是双链表
• 单向链表：值、指针；插入删除：O(1)；随机访问：O(n)
• 双向链表: 值、prev、next;头部、尾部、给定节点操作O(1)
• 静态链表: 值、指针、下标；用数组描述链表

操作

• 随机访问：O(n)
• 插入：随机插入O(n)
• 删除：随机删除O(n)

3.跳表

概念

• 在有序的链表的基础上，通过维护对层次的索引链加快查询、插入、删除速度

操作

• 查询：O(log(n))
• 插入：O(log(n))
• 删除：O(log(n))

4.栈

概念

• 栈是一种操作受限的线性表，体现在只能在一端插入删除数据，先进后出 FILO
• 数组实现：顺序栈；链表实现：链式栈

操作

• 入栈push：栈顶压入O(1)
• 出栈pop：栈顶取出O(1)
• 访问栈顶：peekO(1)

5.队列

概念

• 队列是一种操作受限的线性表，先进先出FILO
• head指针+tail指针
• 顺序队列：isFull = tail==capacity；isEmpty = head==tail;
• 双端对垒：同时具有队列和栈的特性，支持从两端添加、取出元素

操作

• 入队：队尾加入O(1)
• 出队：队首取出O(1)

6.优先队列

概念

• 使用堆实现，元素具有优先级，入队最大（最小）优先级加入堆顶，出队最大（最小）优先级弹出

操作

• 入队：堆实现log(n)
• 出队：堆实现log(n)

算法套路

• 五毒神掌
• 升维**
• 空间换时间
• 阅读代码添加注释
• 变量命名辅助理解

• 刷题五遍是个很好的建议，题目不在做的多，在于精
• 这道题目 的 stack 解法很巧妙，官方给出的 solution 也很详细

一、 知识笔记

1. 复杂度 常见的复杂度

   O(1): Constant Complexity 常数复杂度
   O(log n): Logarithmic Complexity 对数复杂度

   O(n): Linear Complexity 线性时间复杂度

   O(n^2): N square Complexity 平⽅方
   O(n^3): N square Complexity ⽴立⽅方
   O(2^n): Exponential Growth 指数
   O(n!): Factorial 阶乘


2. 数据结构与算法

   a. 程序**=数据结构+**算法

   b. 数据结构: 线性结构和非线性结构。

   线性结构: 顺序存储结构(数组)和链式存储结构(链表)

   1. 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
   2. 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
   3. 线性结构常见的有:数组、队列、链表和栈

   非线性结构: 二维数组，多维数组，广义表，树结构，图结构

二、 课后作业

1. 两数之和: 借助hashmap 来求解,时间复杂度数组的大小O(n) ,空间复杂度取决于hashmap中元素的个数O(n)

2. 盛水最多的容器: 采用双指针向内收敛法 其实就是就面积 area = x * y ; x= (rear - head) ; y = Math.min(nums[rear],nums[head]);

3. 三数只和: 核心** 排序 + 双指针 或者 使用哈希表 题目重点: 1. 排序, 2 双指针手敛,3. 数组中重复元素问题

4. 删除数组中的重复项: 1. 有序的数组 2. 双指针法解决相同元素 3. 返回的是新数组的长度特别注意返回新数组的长度,遍历的时候一定要根据返回的数组的新的长度进行遍历

5. 加一: 其实就是多位数加1之后的值 特殊情况就是出现9的时候需要进位,如果999这种数字,加1之后需要进位,需要给数组扩容

6. 爬楼梯: 方法一使用递归,效率不高,方法二使用初始化3个值,每次修改前2个值,第三个值等于前两个值只和

7. 合并2个有序数组:

   方式1 将输出数组中的有效值存放到复制数组中nums1_copy, 分别定义2个指针到nums1_copy p1和nums2 p2 然后循环判断p1和p2所对应的值,将其添加到输出数组中

   方式2 从后往前在原数组上进行操作,减少了空间复杂度

   需要注意的地方 题干明确表示需要 1. 有序整数数组 2. nums1 有足够的空间来保存 nums2 中的元素如果nums1保存不下nums2那么会报数组下标越界

8. 旋转数组: a. 使用取余的方式判断i+k大于len 则从头开始 arr[(i + k) % nums.length]

   b. 需要重新开辟一个数组去存放旋转之后的值 用于改变原数组的顺序

   关于官方题解中的 使用环状和使用反转 现阶段理解比较困难

   9. 移动0: 做这个题目的时候,老师的这段代码**可以理解,就是最终卡到了赋值 i!=j num[i] = 0 这块,遇到第1个0开始,下一次遍历j和i 就不相同了此时要先使用nums[j]记录nums[i]当前的值,然后把nums[i]修改为0

三、 总结

1. 基础知识点的复习: 每天复习一遍数据结构与算法的脑图,记住数据结构与算法的脉络
2. 代码过数遍: 当敲完一遍的时候,可以理解,第二天需要重新复习一下才能将结果敲出来
3. 看题解
4. 最重要的还是强迫自己不断的敲代码,训练自己的思维能力
5. 感谢助教的帮助

四、建议

​ 知识点稍微在细一点 ,现阶段对于知识点只能自己在网上搜索总结

一般做leetcode的题的时候想到的总是最low的想法,根本不知道题目还能这样做

看过一句话：优秀的程序员会站在无穷大规模的问题上考虑解决方案。反之，平庸的程序员会考虑一个个具体规模的问题。无穷大并非一个数，而是一个趋势。学习复杂度就是在帮助我们把握一个算法随着问题规模的扩大消耗资源的趋势。
分析复杂度时忽略低次项并非说明低次项的数值小，而是趋势由高次项主导，低次项对趋势的贡献可以忽略。
追求低复杂度的算法一方面能够更快的得到答案，另一方面也能让我们把握是否能利用有限资源处理更大规模的问题。
除了追求低复杂度，还有追求高复杂度的场景。比如今天的加密技术并非理论上无法破解，而是它的复杂度让现有的计算能力无法在一个安全时间段内破解。
这些都需要我们对复杂度有深入的了解。

要求

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

作业提交 Deadline

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

截至毕业，每缺一周学习总结，-5 分
截至毕业，每缺一周代码作业，-9 分

本周作业概述

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

• 第 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. 数据结构和算法总揽
2. 复杂度和其他
3. 数组，链表，跳表
4. 栈，队列，优先队列，双端队列

感受：
以前多习惯用现成的库来完成业务功能，对所使用的数据结构和算法并没有认真分析空间和时间复杂度，更注重的是业务结构和代码结构。这样的确在优化的过程中因为缺乏更细节的理解做不到最优。这次从结构和算法本身做了一次清洗的梳理，在优化的层面来讲，获益匪浅。这是一个非常良好的开始。

• keep it simple，keep it stupid！源码中感受到真理；
• 看几遍、读几遍，还得多写几遍；
• 仔细读题，潜藏线索、潜藏坑；
• 先不考虑限定条件下的思路，容易有误导性，虽然解出来了，但是会一直重复整个思路去优化，不能跳开；

学习笔记

2020/2/10

• 视频进度：今日看了第三课1,2，3看了一半

• 题目：跟着视频2做了

• 题目完成情况
  删除排序数组中的重复项
  盛最多水的容器

• 代码片段

  • 用于循环一维数组，i和j下标不重复

   for(int i=0;i<length-1;++i){
       for(int j=i+1;j<length;++j){
           
       }
   }

2020/2/11

• 视频进度：今日看完了第三课3,4
• 题目
  3sum
  暴力解，怎么去重？
  环形链表
  双指针法，1快1慢
• 其他
  链表问题一定要考虑边界情况，node是空的情况