数据结构与算法

本文是王争老师的《算法与数据结构之美》的学习笔记，详细内容请看王争的专栏 。有不懂的地方指出来，我做修改。

 

数据结构与算法思维导图



数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。

数据结构是为算法服务的，算法是要作用再特定的数据结构上的。

最常用的数据结构预算法:

数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
	
算法： 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
1  算法的复杂度

1.1大O复杂度表示法

 公式:



 

T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式， 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

      所以，第一个例子中的T(n) = O(2n+2)，第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

      当n很大时，你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录-个最大量级就可以了，如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。

 

1.2.复杂度分析法则

1）单段代码看高频：比如循环。

2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。

3）嵌套代码求乘积：比如递归、多重循环等

4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

 

1.3 时间复杂度分析

只关注循环执行次数最多的一段代码
	
加法法则：总复杂度等于量级最大的那段代码的复杂度
	
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
1.4 几种常见时间复杂度实例分析



多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，

O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，

O(2^n)（指数阶）、O(n!)（阶乘阶）

O(1) :
常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。

O(logn)、O(nlogn)
i=1;
while(i<=n) {
    i = i*2;
}



x=log2n，所以，这段代码的时间复杂度就是 O(log2n)

O(m+n)、O(m*n)
 

   int cal(int m, int n) {
      int sum_1=0;
      int i=1;
      for(;i<m;++i){
         sum_1 = sum_1 + i;
      }
      int sum_2 = 0;
      int j=1;
      for (;j<n;++j){
         sum_2 = sum_2 + j;
      }
      return sum_1 + sum_2;
   }

从代码中可以看出，m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复 杂度就是0(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

1.5 空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {
    inti=0;
    int[] a = new int[n];
    for (i; i <n; ++i) {
        a[i] =i* i;
    }
    for(i=n-1;i>=0;--i){
        print out a[i]
    }
}

跟时间复杂度分析一样，我们可以看到，第2行代码中，我们申请了一个空间存储变量i,但是它是常最阶的，跟数据规模n没有关系，所以我们可以忽略。第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。

我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。

1.6 复杂度增长趋势图:


最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。

一、复杂度分析的4个概念

1.最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。

2.最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。

3.平均时间复杂度：代码在所有情况下执行的次数的加权平均值。

4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。


二、为什么要引入这4个概念？

1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。

2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。


三、如何分析平均、均摊时间复杂度？

1.平均时间复杂度

代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。

2.均摊时间复杂度

两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

1、数组

线性表:   线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构：数组，链表、队列、栈等。



 

什么是数组:

 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
	
 连续的内存空间和相同类型的数据(随机访问的前提)
	
优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低
数组怎么根据下标随机访问的？
通过寻址公式：a[i]_address = base_address + i * data_type_size

其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

 

为何数组插入和删除低效：


插入：

若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。

最好情况时间复杂度 O(1)



如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到最后，然后将插入的数据直接放在第k个位置上。

最坏情况复杂度为O(n)



平均负责度为O(n)

2. 低效的插入和删除

1） 插入：从最好O(1) 最坏O(n) 平均O(n)

2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。

3） 删除：从最好O(1) 最坏O(n) 平均O(n)

4） 多次删除集中在一起，提高删除效率

记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

 

2、链表

什么是链表
1.和数组一样，链表也是一种线性表。

2.从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。

3.链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。



 

链表的特点
1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。



2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

常用链表
1.单链表



1）每个节点只包含一个指针，即后继指针。

2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。

3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

 

2.循环链表



1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。

2）适用于存储有循环特点的数据，比如约瑟夫问题。

 

3.双向链表



1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。

2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。

3）性能特点：

和单链表相比，存储相同的数据，需要消耗更多的存储空间。

插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。

对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表：



首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。

选择数组还是链表？
1.插入、删除和随机访问的时间复杂度

数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。

链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。



2.数组缺点

1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。

2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

3.链表缺点

1）内存空间消耗更大，因为需要额外的空间存储指针信息。

2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

4.如何选择？

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

如果代码对内存的使用非常苛刻，那数组就更适合。

应用
1.如何分别用链表和数组实现LRU缓冲淘汰策略？

1）什么是缓存？

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

2）为什么使用缓存？即缓存的特点

缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。

3）什么是缓存淘汰策略？

指的是当缓存被用满时清理数据的优先顺序。

4）有哪些缓存淘汰策略？

常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。

5）链表实现LRU缓存淘汰策略

当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。

6）数组实现LRU缓存淘汰策略

方式一：首位置保存最新访问数据，末尾位置优先清理

当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。

方式二：首位置优先清理，末尾位置保存最新访问数据

当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）

2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如 上海自来水来自海上）

1）前提：字符串以单个字符的形式存储在单链表中。

2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。

3）将链表中的字符倒序存储一份在另一个链表中。

4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。

六、设计思想

时空替换思想：“用空间换时间” 与 “用时间换空间”

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

 

 

3、队列

 

什么是队列:

队列是一种受限的线性表数据结构,只支持两个操作:入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。



特点:

1 . 队列跟栈一样,也是一种抽象的数据结构。

2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

 

实现:

队列可以用数组来实现,也可以用链表来实现。

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

 

基于数组的队列:

实现思路:

实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。



当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.



随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。

当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。



基于链表的实现: 

需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.



 

循环队列:

我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。



我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:



队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,



就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

解决浪费一个存储空间的思路:定义一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size—，入队时size++

阻塞队列和并发队列(应用比较广泛)

阻塞队列其实就是在队列基础上增加了阻塞操作。

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



你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基干阴寒队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"

 

小结:

队列最大的特点就是先进先出,主要的两个操作是入队和出队。

它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。

阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阴寒,并发队列就是队列的操作多线程安全。

 

4、递归算法

 

一、什么是递归？


1.递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。

2.方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。

3.基本上，所有的递归问题都可以用递推公式来表示，比如

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

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

f(n)=n*f(n-1);


二、为什么使用递归？递归的优缺点？


1.优点：代码的表达力很强，写起来简洁。

2.缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。


三、什么样的问题可以用递归解决呢？


一个问题只要同时满足以下3个条件，就可以用递归来解决：

1.问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。

2.问题与子问题，除了数据规模不同，求解思路完全一样

3.存在递归终止条件


四、如何实现递归？


1.递归代码编写

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

2.递归代码理解

对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。

那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归的关键是终止条件

五、递归常见问题及解决方案


1.警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。

2.警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。


六、如何将递归改写为非递归代码？


笼统的讲，所有的递归代码都可以改写为迭代循环的非递归写法。如何做？抽象出递推公式、初始值和边界条件，然后用迭代循环实现。

5、排序




一、排序方法与复杂度归类

（1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。

（2）复杂度归类

冒泡排序、插入排序、选择排序 O(n^2)

快速排序、归并排序 O(nlogn)

计数排序、基数排序、桶排序 O(n)


二、如何分析一个“排序算法”？

<1>算法的执行效率

1. 最好、最坏、平均情况时间复杂度。

2. 时间复杂度的系数、常数和低阶。

3. 比较次数，交换（或移动）次数。

<2>排序算法的稳定性

1. 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

2. 稳定性重要性：可针对对象的多种属性进行有优先级的排序。

3. 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。

<3>排序算法的内存损耗

原地排序算法：特指空间复杂度是O(1)的排序算法。

常见的排序算法:

 



冒泡排序



冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。

代码:

  public int[] bubbleSort(int[] a) {
        int n = a.length;
        if (n<=1) {
            return a;
        }
        for (int i = 0; i < n; i++) {
            //提前退出冒泡循环的标志
            boolean flag = false;
            for (int j = 0; j < n-i-1; j++) {
                if (a[j]>a[j+1]) {//
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;

                    flag = true;//表示有数据交换
                }
                if (!flag) {
                    break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
                }
            }
        }
        return a;
    }



四、插入排序



插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。


代码:

    public int[] insertionSort(int[] a) {
		int n = a.length;
		if (n<=1) return a;
		
		for (int i = 1; i < n; i++) {
			int value = a[i];
			int j = i-1;
			for (; j >=0; j--) {
				if (a[j] > value) {
					a[j+1] = a[j];//移动数据
				}else {
					break;
				}
			}
			a[j+1] = value;//插入数据
		}
		
		return a;
	}



五、选择排序



选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。

代码:

public int[] selectionSort(int[] a) {
		int n = a.length;
		
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = i+1; j < a.length; j++) {
				//交换
				if (a[i] > a[j]) {
					int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
		}
		
		return a;
	}

六、归并排序

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。



 实现思路:



merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

代码:

 // 归并排序算法, a是数组，n表示数组大小
  public static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n-1);
  }

  // 递归调用函数
  private static void mergeSortInternally(int[] a, int p, int r) {
    // 递归终止条件
    if (p >= r) return;

    // 取p到r之间的中间位置q
    int q = (p+r)/2;
    // 分治递归
    mergeSortInternally(a, p, q);
    mergeSortInternally(a, q+1, r);

    // 将A[p...q]和A[q+1...r]合并为A[p...r]
    merge(a, p, q, r);
  }

  private static void merge(int[] a, int p, int q, int r) {
    int i = p;
    int j = q+1;
    int k = 0; // 初始化变量i, j, k
    int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
   
    // 1 排序
    while (i<=q && j<=r) {
      if (a[i] <= a[j]) {
        tmp[k++] = a[i++]; // i++等于i:=i+1
      } else {
        tmp[k++] = a[j++];
      }
    }

    // 2 判断哪个子数组中有剩余的数据
    int start = i;
    int end = q;
    if (j <= r) {
      start = j;
      end = r;
    }

    // 3 将剩余的数据拷贝到临时数组tmp
    while (start <= end) {
      tmp[k++] = a[start++];
    }

    // 4 将tmp中的数组拷贝回a[p...r]
    for (i = 0; i <= r-p; ++i) {
      a[p+i] = tmp[i];
    }
  }


merge是这样执行的:



代码分析:



 

 



 

七、快速排序

快排的思想:    如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

快排利用的分而治之的思想







 

八、线性排序:

时间复杂度O(n)

我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

特点:

非基于比较的排序算法 

 

桶排序

 

桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

对排序的数据要求苛刻:

1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

2 ,数据在各个桶之间的分布是比较均匀的。

3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限，无法将数据全部加载到内存中。

 



 

计数排序

计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

代码:

 // 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
  public static void countingSort(int[] a) {
	int n = a.length;
    if (n <= 1) return;

    // 查找数组中数据的范围
    int max = a[0];
    for (int i = 1; i < n; ++i) {
      if (max < a[i]) {
        max = a[i];
      }
    }

    // 申请一个计数数组c，下标大小[0,max]
    int[] c = new int[max + 1];
    for (int i = 0; i < max + 1; ++i) {
      c[i] = 0;
    }

    // 计算每个元素的个数，放入c中
    for (int i = 0; i < n; ++i) {
      c[a[i]]++;
    }

    // 依次累加
    for (int i = 1; i < max + 1; ++i) {
      c[i] = c[i-1] + c[i];
    }

    // 临时数组r，存储排序之后的结果
    int[] r = new int[n];
    // 计算排序的关键步骤了，有点难理解
    for (int i = n - 1; i >= 0; --i) {
      int index = c[a[i]]-1;
      r[index] = a[i];
      c[a[i]]--;
    }

    // 将结果拷贝会a数组
    for (int i = 0; i < n; ++i) {
      a[i] = r[i];
    }
  }

散列表

什么是散列表:

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

原理:

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

散列函数的设计要求:

散列函数计算得到的散列值是一个非负整数;.
	
如果key1 = key2,那hash(key1) == hash(key2);
	
如果key1 != key2,那hash(key1)  !=  hash(key2),
散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

解决散列冲突的方法有两种: 

开放寻址法(open addressing)和链表法(chaining)

开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

装在因子:  散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

链表法:

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。



 

 

系列文章

第一章：基础知识

第二章：线性表

第三章：栈和队列 

第四章：字符串和数组

第五章：树和二叉树

第六章：图

第七章：排序算法

前言

数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存储）物理结构和数据的运算三个部分。



为什么要学数据结构？

首先，因为数据结构作为计算机专业的专业基础课程，是计算机考研的必考科目之一，如果打算报考计算机专业的研究生，你必须学好它；其次，数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一，想要顺利通过这些考试，你也必须学好它；最后，数据结构还是你打算今后学习计算专业其他课程的基础，如操作系统、编辑原理、数据库管理系统、软件工程、人工智能等。总而言之，你既然已经与计算机接轨就必须掌握好它。

如何学习数据结构？

对于初学者来说，数据结构是门概念上比较抽象的课程，不是太容易掌握，需要构思和理解。万事开头难，只要你掌握了学习这门课的方法和技巧，就会变得很容易了。不管学什么，首先应该做好充分的心理准备，建立好自信心，拥有一颗战胜困难的决心，才能不畏惧、不退缩，直至胜利归来。其次，就是最好有C语言基础，这样学起来事半功倍，当然没有C语言基础也行，可以一边学数据结构一边巩固C语言知识。最后，就是多动手！多动手！多动手！重要的事情说三遍！只有亲自动手上机操作或用笔在纸上画画写写才能加深映像，方便理解记忆。?

第一章：基础知识

第1节：数据结构概述

  1.1 概念术语

  1.2数据的逻辑结构

  1.3数据的存储（物理）结构

  1.4抽象数据类型

  1.5算法

1.6时间复杂度

1.7空间复杂度

第2节：C语言基础

2.1 开发环境

2.2 递归与非递归（重点）

2.3参数传递

2.4 结构体和联合体

2.5 链表

2.6 内存的分配与释放

 

第1节：数据结构概述

数据结构的主要任务是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机课实现的物理结构，从而便于计算机处理。

 

  1.1 概念术语

（1）数据（Data）是能被计算机处理的符号或符号集合，含义广泛，可理解为“原材料”。如字符、图片、音视频等。

（2）数据元素（data element）是数据的基本单位。例如一张学生统计表。

（3）数据项（data item）组成数据元素的最小单位。例如一张学生统计表，有编号、姓名、性别、籍贯等数据项。

（4）数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如正整数N={1，2，3，····}。

（5）数据结构（data structure）是数据的组织形式，数据元素之间存在的一种或多种特定关系的数据元素集合。

（6）数据类型（data type）是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型是由若干个类型组合而成，是可以再分解的。

 

  1.2数据的逻辑结构

逻辑结构（logical structure）是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

（1）集合结构：集合的数据元素没有其他关系，仅仅是因为他们挤在一个被称作“集合”的盒子里。

（2）线性结构：线性的数据元素结构关系是一对一的，并且是一种先后的次序，就像a-b-c-d-e-f-g·····被一根线穿连起来。

（3）树形结构：树形的数据元素结构关系是一对多的，这就像公司的部门级别，董事长-CEO\CTO-技术部\人事部\市场部.....。

（4）图结构：图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图，一个城市有很多线路连接不同城市。

 

  1.3数据的存储（物理）结构

存储结构（storage structure）也称为物理结构（physical structure），指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

（1）顺序存储结构：是把数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。

（2）链式存储结果：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。

 

小结：数据的逻辑结构和物理结构是密切相关的，在学习数据的过程中会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。

 

  1.4抽象数据类型

抽象数据类型（abstract data type，ADT）是描述具有某种逻辑关系的数据模型，并对在数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与在计算机内部表示无关，计算机中的整数数据类型是一个抽象数据类型，不同处理器可能实现方法不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。“抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解、抽象、信息隐藏等特性，可以把现实中的大问题分解为多个规模小且容易处理的小问题，然后建立起一个能被计算机处理的数据，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。就类似建一栋房子，分成若干个小任务，如地皮规划、图纸设计、施工、装修等，整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何，设计图纸人员不需要了解施工的地基、砌墙的具体细节，装修工人不用关系图纸和搬砖过程，这就是抽象类型中的信息隐藏。

抽象数据类型的概念可能让初学者不太容易理解。例如线性表的抽象数据类型的描述数据对象集合：线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素；除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。

 

  1.5算法

算法（algorithm）是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

（1）数据结构和算法的关系

两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作，而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。

（2）算法的五大特性

有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。

确定性，是指算法执行的每一步骤在一定条件下只有一条执行路径，也就是相同输入只能有一个唯一的输出结果。

可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。

输入，是指算法具有零个或多个输入。

输出，是指算法至少有一个或多个输出。

 

1.6时间复杂度

在进行算法分析时，语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量，记作T(n) = O（f（n））。它表示随问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中，f（n）是问题规模n的某个函数。

算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下，随着规模n的增大，次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列：O(1) < O(log2n) < O(n) < O(n²）<O(n³) ····<O(n!)



例如：

(a) 1;      // 时间复杂度为O(1)

(b)for(i =1 ; i<=n ;i++){  x= x+1;}    // 时间复杂度为O(n)，称为线性阶

(c)for(i =1 ; i<=n ; i++）{for(j=1;j<=n;j++){  x=x+1 } }  // 时间复杂度为O(n²),称为平方阶

 

1.7空间复杂度

空间复杂度（space complexity）作为算法所需存储空间的量度，记做S(n) = O (f(n))。其中，n为问题的规模；f（n）为语句关于n的所占存储空间的函数。

一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量，则称此算法为原地工作，空间复杂度为O(1)。

 

第2节：C语言基础

C语言作为数据结构的算法描述语言，广泛应用于系统软件和应用软件的开发。在真正开发学习数据结构知识之前，先复习一下C语言基础，为数据结构的学习扫清障碍。本节主要针对重点和难点部分详细讲解，包括开发环境、函数与递归、指针、参数传递、动态内存分配及结构体、联合体。

 

2.1 开发环境

C语言常见的开发环境有很多种，如LCC、Turbo C2.0、Visual C++、Borland C++，本章主要介绍使用最多的Turbo C 2.0和Visual C++ 6.0。

（1）Turbo C 2.0 ：1989年，美国Borland公司推出,简称TC。它集编辑、编译、连接和运行一体的C程序集成开发环境。界面简单、上手容易、使用方便，通过一个简单的主界面可以很容易编辑、编译和链接程序，也是初学者广发使用的开发工具。

（2）Visual C++6.0：是强大的C/C++软件开发工具，使用非常广泛，已经成为首选的开发工具。利用它可以开发Windows SDK、MFC等应用程序。

 

2.2 递归与非递归（重点）

在数据结构与算法实践过程中，经常会遇到利用递归实现算法的情况。递归是一种分而治之、将复杂问题转换成简单问题的求解方法。使用递归可以使编写的程序简洁、结构清晰，程序的正确性很容易证明，不需要了解递归调用的具体细节。

（1）函数的递归：就是函数自己调用自己，即一个函数在调用其他函数的过程中，又出现对自身的调用，这种函数称为递归函数。函数的递归调用就是自己调用自己，可以直接调用自己也可以间接调用。其中，在函数中直接调用自己称为函数的直接递归调用；如果函数f1调用了函数f2又再次调用了函数f1，这种调用的方式我们称之为间接递归调用。

例1：利用递归求n! ：有两种情况，当n=0递归结束，返回值为1 ；当n !=0时，继续递归。

//递归求n！函数实现

int factorial (int  n){

    if(n ==0 )
        return 1;

    else
        return n*factorial(n-1);
}


  例2：已知有数组a[] ，要求利用递归实现求n个数中的最大值。

a[] ={0,···，n-1}；

int findMax(int a[] ,int n){

    int  m ;

    if (n<=1)
        return a[0];

    else
    {
        m = findMax(a,n-1);
        return a[n-1] >= m ?a[n-1] : m ;//找到最大值
    }
}

 

（2）迭代与递归

迭代与递归是程序设计中最常用的两种结构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是，迭代使用的是循环结构，递归使用的是选择结构。大量的递归会耗费大量的时间和内存，每次递归调用都会建立函数的一个备份，会占用大量的内存空间。迭代则不需要反复调用函数和占用额外的内存。对于较为简单的递归问题，可以利用简单的迭代将其转化为非递归。而对于较为复杂的递归问题，需要通过利用数据结构中的栈来消除递归。

（3）指针

是C语言中一个重要概念，也是最不容易掌握的内容。指针常常用在函数的参数传递和动态内存分配中。指针与数组相结合，使引用数组成分的形式更加多样化，访问数组元素的手段更加灵活；指针与结构体结合，利用系统提供的动态存储手段，能构造出各种复杂的动态数据结构；利用指针形参，使函数能实现传递地址形参和函数形参的要求。接下里会介绍指针变量的概念、指针与数组、函数指针与指针函数。

指针是一种变量，也称之为指针变量，它的值不少整数、浮点数和字符，而是内存地址。指针的值就是变量的地址，而变量又拥有一个具体的值。因此，可以理解为变量名直接引用了一个值，指针间接地引用了一个值。

指针可以与变量结合，也可以与数组结合使用。指针数组是一种存放一组变量的地址。数组指针是一个指针，表示该指针指向数组的指针。数组指针可以进行自增或自减运算，但是数组名则不能进行自增或自减运算，这是因为数组名是一个常量指针，它是一个常量，常量值是不能改变的。函数指针与指针函数同理。

 

2.3参数传递

（1）传值调用：分为实际参数和形式参数。例如：

int GCD（int m ,int n）;

void main(){
    int a,b,v,
    v = GCD(a,b);  //实际参数
}

int GCD(int m ,int n){ //形式参数
    int r;
    r = m;
    do{
        m=n;
        n=r;
        r=m&n;
      }while(r);

    return n;
}

上面的函数参数传递属于参数的单向传递，即a和b可以把值传递给m和n，而不是可以把m和n传递给a和b。实际参数和形式参数的值的改变都不会互相收到影响。

（2）传指针地址参数：略

 

2.4 结构体和联合体

也称共用体，是自定义的数据类型，用于构造非数值数据类型，在处理实际问题中应用非常广泛。数据结构中的链表、队列、树、图等结构都需要用到结构体。教师表结构体如下所示。

//结构体类型
struct teacher{
    //数据项
    int no;
    char name[20];
    char sex[4];
    char headship[8];
    char degree[6];
    long int phone;
}

与结构体一样，联合体也是一种派生的数据类型。但是与结构体不同的是，联合体的成员共享同一个存储空间。定义联合体一般形式如下所示。

union 共用体名{

    成员列表；
}
变量列表；

——————————————————————————
union data{

    int a ;
    float b;
    char c;
    double d;
}abc;

//或写成
union data{
    int a;
    float b;
    char c;
    double d;
};
union data abc;



 

2.5 链表

在C语言中，处理已知数据可以使用数组。如果事先并不知道要处理的数据的个数，则需要使用链表结构。链表需要动态分配内存，链表的长度随时可以发生变化。链表有一个指针类型的成员指向自身，该指针指向与结构体一样的类型。例如如下语句：

struct node{
    int data;
    struct data *next;
}


自引用结构体类型为struct node，该结构体类型有两个成员：整数成员data，指针成员next。成员next是指向结构体为struct node类型的指针。通过这种形式定义的结构体通过next指针把两个结构体变量连在一起。这种自引用结构体单元称为结点，结点之间通过箭头连接起来，构成一张表，称为链表。

链表中第一个结点的指针称为头指针且可以访问链表的每一个结点。为了方便操作，在链表的第一个结点之前增加一个头结点。

2.6 内存的分配与释放

（1）malloc函数主要作用是分配一块长度为size的内存空间。void *malloc(unsigned int size);其中，size就是要分配的内存空间大小字节。使用时最好先检查一下是否分配成功，否则返回null，可以保证程序的正确运行。使用完分配后的空间要利用free函数及时释放。

（2）free函数主要作用是将内存空间释放。void free (void *p); 其中，参数p指向要释放的内存空间。不能使用已经被free函数释放的内存空间。

 

下一章：

数据结构与算法——从零开始学习（二）线性表

 

 

欢迎，😆大家关注公众号：（推送数据结构+算法+Java+人生感悟+理财知识+互联网事件等）

前言

本文是个人基于覃超老师的《算法训练营》的学习笔记，此笔记的内容都是学习后的个人记录、个人总结、理解和思想。仅供参考学习。

很多同学在大学的时候会觉得数据结构与算法很枯燥，很多小伙伴都不愿意听这门课程。甚至以前还觉得能开发一个项目就能成为一个合格的程序员。但是学会算法，或者接触过数据结构与算法后，发现懂这门知识的程序员编写出来的代码相对有更高的质量。代码的性能、写法、底层逻辑和解决问题的能力都会高于不懂数据结构与算法的程序员。
到了如今，如果想成为一个高级开发工程师或者进入大厂，不论岗位是前端、后端还是AI，算法都是重中之重。也无论我们需要进入的公司的岗位是否最后是做算法工程师，前提面试就需要考算法。所以小时不学算法，长大掉头发。
这系列的《算法学习笔记》，与大家一起重温或者学习数据结构与算法。

这里也赠送大家一句话：
“好记性不如烂笔头，好记性更不如好笔记”
愿大家在技术银河中终身漂泊学习时，习惯编写自己的笔记，以后这些笔记必定成为我们最珍贵的宝藏！✨

如何系统化学习算法
深入到精通一门知识的我们都需要一个系统化的学习方法，如果这门知识越是有难度，前期就越是枯燥无味，或者甚至觉得很困难。所以学习算法也是一样的：

枯燥无味

所以需要系统化学习；
小步快跑的方式进行学习；
不懂就找答案不要埋头苦学；


不牢固

越是庞大的知识，越学就会越觉得之前学到的知识忘的差不多了；
其实就是缺乏知识的稳固性；


预习

学习任何一门知识，都要先了解和预习这门知识；
同理，在学习一门新的开发语言时，我们都会先来一个hello world；


坚持leetcode刷题

要学会算法，并且稳固这一门知识，不断的刻意练习是重中之重；




系统化的效果
系统化学习和拿起一本书最终的效果是不一样的。很多时候我们开始学习一门知识，我们都会看：《xxx深入浅出》、《xxx指南》和《从0到1学会xxx》，其实里面的知识是很庞大的。只靠知识是无法支撑我们的实战和经验的，所以我们需要系统化的学习方法最终达到的目标也是不一样的，例如：

提升到职业顶尖水平
通过一线互联网大厂的面试
要有Leetcode 300+ 刷题量


推荐阅读《Outliner》这本书中的学习方法


精通一个领域
前面说到，任何一个领域的知识都是很庞大的。而且只靠看书，看文章学习都是不够的。所以一套好的学习方法，可以为我们打开一扇大门。而且在打开这扇大门的同时不会因为艰苦、困难、煎熬或者是枯燥而最后放弃。

切碎知识点 Chunk it up

庖丁解牛
脉络相连 - 从根部开始学习，到分支，再到树叶。让每一个知识点都有关联关系


刻意练习 Deliberate Practicing
反馈 Feedback


数据结构有什么？

一维：

基础： 数组 array (string)，链表 linked list
高级：栈 stack，队列 queue， 双端队列 duque，集合 set，映射 map (hash or map)，等等


二维：

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


特殊：

位运算 Bitwise，步隆过滤器 BloomFilter
LRU Cache (缓存)




参考：覃超老师的《数据库脑图》

算法有什么？
任何的高级算法与数据结构都会转换成If Else，for循环，其实也是最朴素的计算机的知识，没有什么AI，人工智能的知识。高级算法重点是找到重复单元。

跳转语句 (Branch) ：If-else，switch
循环 (Iteration) ：for, which，while loop
递归 (Recursion) ： Divide & Conquer, Backtrace
搜索 (Search) ：深度优先搜索 Depth first search，广度优先搜索 Breadth first search，启发式搜索 A*
动态规划 (Dynamic Programming)
二分查找 (Binary Search)
贪心 (Greedy)
数学 (Math)，几何 (Geometry)


参考：覃超老师的《算法脑图》

刻意练习 - Deliberate practice
无论是科学家、国家运动员、技术专家还是游戏职业选手，他们的优秀的背后都有一个共同点：刻意练习。
什么是刻意练习？

刻意练习 - 过遍数，持续多边形的练习，用数遍达到质变！（五毒神掌）；
练习不擅长的地方；
如果感到不舒服、不爽、枯燥的话，那证明我们正在爬坡，正在提升！


反馈 - Feedback
很多时候在学习中，特别是在自学的过程，我们永远不知道自己的学习的成果是怎么样的。或者我们有时候会遇到难点但是无法突破，甚至有时候我们以为自己很努力，或者已经很强了。但是其实还只是坐井观天而已。所以我们在学习的时候需要反馈。所谓的反馈有几种：

即时反馈

学会使用一门语言；
能写出能执行的代码；
能写出一个项目；
能实现一个功能；


主动型反馈

高手代码（Github、LeetCode）；
第一视角止步（看视频，看高手写的代码，学习思路）；


被动式反馈（高手指点）

代码审查 code review；
例如：教练看你打，给你反馈；




切题四件套
我个人认为也可以叫解题四大法则：

理解题目（Clarification）

在LeetCode看题后，先思考，认真确认和理解题目；
避免忽略了一些条件或者是误解题目；
面试的时候更加应该跟面试官确认清楚题目、条件、场景等；


多种解题方案（Possible solutions）

对比时间和空间复杂度 compare (time/spaace)
最优解 optimal (加强)


多编写（Coding）

代码反复练习和编写；
每一种解法都反复练习和编写；


多测试案例（Test cases）

在LeetCode上可以改变测试案例；
多测试几种案例，确保自己的代码可以适应各种特殊情况；




刷题方式（五毒神掌）
第一遍

5分钟：读题 + 思考；
5分钟过后，没有思路就直接看解法；
记录多个解题方法，比较解题方法的优弊；
尝试默写代码，训练刻意手写代码；

第二遍

自己编写，这时候就不要再看题解了；
LeetCode提交代码，确保能通过；
有Bug没有关系，重复debug到通过为止；
编写出多种解题方法；
持续优化 - 重点是 执行时间 （可参考LeetCode中打败了多少的人，也可以点击比较优秀的人，学习更好的写法）；

第三遍

过了一天后，再重复做题；
根据自己不熟悉的题目与程度做专项练习；
专项练习就是针对自己不熟悉的种类的题，从而刻意练习哪一种题；

第四篇

过了一周后，再反复练习；

第五遍

面试前，提前2-3周开始重复练习；


总结
这篇笔记中，我们记录了一下关键知识重点点：

如何深入学习一门知识

通过系统化学习一门知识；
最高效和持续的学习算法就是通过系统化的学习；
这里推荐大家，真的想学好一个技术，最好的方法就是找对老师，找对课程，找对人；


如何攻破庞大的知识体系变成编程职业高手

切碎知识点与建立脉络
刻意练习
反馈


数据结构中有什么？ - 看脑图
算法中有什么？- 看脑图
算法练习方法

切题四件套
五毒神掌




我是三钻，一个在技术银河中和你们一起来终身漂泊学习。

点赞是力量，关注是认可，评论是关爱！下期再见 👋！


公众号《技术银河》回复"算法资料"可以获得PDF版和脑图资料！

推荐阅读


📖《分析时间与空间复杂度《三钻数据结构与算法笔记》》 — 算法的核心时间和空间复杂度，《数据结构与算法》都是围绕着这个核心开展的。它的存在也是为了解决我们在编程的过程中性能问题，同时也让我们有更高级的思维和思路，写出更优质的程序。


📖《28关学会HTML与HTML5基础》 — 一个系列的文章和大家一起闯关进攻前端全方位知识点。没有闯过这些关卡的童鞋，无论前端能力如何，这个可以锻炼我们自己，也可以深入知道我们自己的前端水平和差距。想学习前端的童鞋可以从零开始学习，一起排除困难共同打开前端大门！


📖《44关深入浅出CSS基础之第一篇》 — 这周我们一起闯过了22关，下一期我们会一起把剩余的22关完成。学习是一种像爬山一样的过程，要经历过漫长的上坡路，一步一个脚印。“路漫漫其修远兮，吾将上下而求索。”， 在追寻知识的道路上，前方的道路还很漫长，但我们将百折不挠，不遗余力地，上天下地的去追求和探索。让我们继续坚持学习，终身学习成长。在大前端的时代爬到技术的巅峰，做一个有深度的技术人员。


🔥《前端必看的8个HTML+CSS技巧》 — CSS是一个很独特的语言。看起来非常简单，但是某种特殊效果看似简单，实现起来就颇有难度。这篇文章主要是给在学习前端的童鞋分享一些新的CSS技巧，一些在前端教程和培训课堂中不会讲到的知识。第二就是让还在前端开发这条道路上的童鞋们，重新燃起对前端排版和特效的热爱和热情！🔥