（计算机基础 核心知识）数据结构（1-20）

1.你最喜欢的数据结构上的或者从其它地方学到的算法是什么，你为什么喜欢它

梯度下降算法

梯度下降算法是机器学习和深度学习中的训练算法的具体实现，换句话说没有它也就没有今天的机器学习和深度学习，它的作用在于使得我们的机器学习算法能够尽可能接近训练的目标（正常情况下不会完全接近目标），进而结束漫长的训练过程。

我们都知道 1m=100cm，但是他们之间的关系，我们可以通过一次次不断的训练或者说猜测来得到。假设我们的输入为：x, 权重为: w , 输出为: y, 可以得到：y = xw x可以理解为我们输入的1（m）, 权重不知道，初始化为：0.1，因此，我们可以得到：yi = 10.1=0.1,然而我们的实际结果是y=100, 结果误差是：y-yi = 100-0.1=99.9, 这个时候我们知道误差太大了，也就意味着我们的权重设置过小了，此时，我们设置w=2， 则yi = 1*2=2, 此时的误差为：y-yi = 100-2=98，我们惊喜的发现，误差减小了，意味着，我们只要一直这样猜下去，我们就会得到w=100的时候，就能得到最终的输出结果了（当然，我们猜测的过程中可能会出现各种的笑话，如果我们随机的猜测w的值，在接近实际结果y的时候，也就是我们的误差不断减少的时候，我们是很开心的，因为马上就要成功了，这时候我们就会说，w老哥继续加油，我们的输出马上就靠近真实值了，然而当我们的误差变为负数，也就是我们的输出超过真实值的时候，意味着w的步子迈大了，以至于不是接近真实值，而是直接超过了真实值，这时候，我们就会说，w老哥，你跑偏了，快退回来一点，于是w就开始减小一点，再去计算误差），从最开始不知道w到最终我们得到准确的w的过程，就称之为训练过程，或者说学习过程。

但是聪明的你们一定发现了什么，惊喜的是原来这就是传说中的的学习过程，悲哀的是，原来学习的过程是一次次猜出来的 ，哈哈 这就太难了吧，w太小了，我们得叫它加速，w太大了，跑偏了，我们还得把它叫回来，跟小孩子一样啦。这个学习过程如果交给人类来做可能比较费时，但是交给强大的计算机这都不是事，但是呢，咱也不能说有资源就随便浪费是吧，因此，我们的学习过程肯定要有一个规划好的算法来执行才是最佳的，随机猜测都是不靠谱的，科学才是硬道理对吧，因此，梯度下降就随之出现了。

梯度其实就是一个向量，它指向函数值上升最快的方向，相反，梯度前面添加一个符号，就是函数下降最快的方向，因此我们就可以不用像上面那样没有方向的去猜测w啦，而是根据函数下降或者上升最快的方向去猜测，这样学习过程就更加快了呢

相比我们定义来看，多了1/2,和平方项，多了个平方项在于数学中，用误差的平方比单纯的相减误差的评判更好一些，而多了个1/2原因在于方便求导，因为误差函数的梯度求解是需要在误差函数的当前值对w进行求导的，对上式求导的话，就会得到，1/2*2=1，抵消了平方项带来的2，总之写成上面对的式子不会对我们的最终实验结果产生大的偏差，甚至效果更好

梯度下降流程：首先，我们假设最开始误差函数处于左右的某一个随机点，由于此时的误差不是最小，那么我们就会采用梯度下降公式，向着误差函数的梯度下降方向移动，进行w的不断更新，误差函数就不断的减小，w就不断的靠近误差函数为最低的的w值，直到更新到误差函数的最低点附近时，此时的w即为最佳值。梯度下降公式，也即w的更新公式如下：

然而更新的过程什么时候停止呢？通常情况下，知道默认误差函数小于哦我们设置的阈值就可以停止了，比如说该时刻的w对应的误差函数的值为0.0001之类的，我们就默认w已经学习好了，就会停止训练

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：

梯度下降法的缺点：

（1）靠近极小值时收敛速度减慢，如下图所示；

（2）直线搜索时可能会产生一些问题；

（3）可能会“之字形”地下降。

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数小，但是对于大规模样本问题效率低下。

随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

牛顿法最大的特点就在于它的收敛速度很快。

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。

牛顿法的优缺点总结：

优点：二阶收敛，收敛速度快；

缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

2.解释算法的复杂度，并用实际生活中的例子，来说明不同复杂度的算法对我们生活的影响

这个公式的全称是：算法的渐进时间复杂度。

T(n) = (1+2n)*颗粒时间，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)

为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

所以上面的例子中，如果n无限大的时候，T(n) = time(1+2n)中的常量1就没有意义了，倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。

常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)

对数阶O(logN)

还是先来看代码：

int i = 1;
while(i<n)
{
    i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n 也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

线性阶O(n)

这个在最开始的代码示例中就讲解过了，如：

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。 举例：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²) 如果将其中一层循环的n改成m，即：

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的时间复杂度就变成了 O(m*n)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) 举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

空间复杂度 O(n)

我们先看一个代码：

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

例子用数据库吧

数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上

目前大部分数据库系统及文件系统都采用B Tree或其变种B+Tree作为索引结构

哈希索引

3.如何判断链表是否有环

哈希表

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

快慢指针

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

只要你设置分别走 1 步 和 2 步，那么只要有环就一定会碰上。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head,fast=head;
        //注意初始化条件和while循环条件
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            //如果是看有没有环，这里直接返回true就行了
            if(slow==fast){
                ListNode index=head;
                //从头出发
                while (index!=slow){
                    index=index.next;
                    slow=slow.next;
                }
                //此时相等 随便返回一个即可
                return index;
            }
        }
        return null;
    }
}

4.指针和引用有什么区别

引用和指针的的定义，指针本身就是个变量，它里面存储的是他所指向的变量的地址，而引用只是一个变量的别名

1.引用不可以为空，但指针可以为空。前面也说过了引用是对象的别名，引用为空——对象都不存在，怎么可能有别名！故定义一个引用的时候，必须初始化。因此如果你有一个变量是用于指向另一个对象，但是它可能为空，这时你应该使用指针；如果变量总是指向一个对象，你的设计不允许变量为空，这时你应该使用引用。

指针在声明的时候可以为空，也正是因为这点，指针在初始化的时候要进行判空操作，而引用就不需要。

2.其次，引用不可以改变指向，对一个对象"至死不渝"；但是指针可以改变指向，而指向其它对象。

虽然引用不可以改变指向，但是可以改变初始化对象的内容。例如就++操作而言，对引用的操作直接反应到所指向的对象，无论是赋值操作还是++操作，都直接反映到引用所指向的对象，而不是改变指向；而对指针的操作，会使指针指向下一个对象，而不是改变所指对象的内容。

3.引用的大小是所指向的变量的大小，因为引用只是一个别名而已；指针是指针本身的大小，4个字节。

4.最后，引用比指针更安全。由于不存在空引用，并且引用一旦被初始化为指向一个对象，它就不能被改变为另一个对象的引用，因此引用很安全。对于指针来说，它可以随时指向别的对象，并且可以不被初始化，或为NULL，所以不安全。

指针可用通过定义为const 指针，也可以达到不能改变指向的作用，虽然不能改变指向，但仍然存在空指针，并且有可能产生野指针（即多个指针指向一块内存，free掉一个指针之后，别的指针就成了野指针）

5.常量指针和指针常量

常量指针：指向常量的指针，在指针定义语句的类型前加const，表示指向的对象是常量。 常量指针定义"const int* pointer=&a"告诉编译器，pointer是常量，不能将pointer作为左值进行操作。

指针常量 在指针定义语句的指针名前加const，表示指针本身是常量。在定义指针常量时必须初始化！而这是引用天生具来的属性，不用再引用指针定义语句的引用名前加const。

指针常量定义”int* const pointer=&b”告诉编译器，pointer是常量，不能作为左值进行操作，但是允许修改间接访问值，即*pointer可以修改。

6.大量数据，如何选取最大的50个？

top K问题

分治法，即大数据里最常用的Map（映射）Reduce（归约）。

100亿数据找出最大的1000个数字

a、将100亿个数据分为1000个大分区，每个区1000万个数据

b、每个大分区再细分成100个小分区。总共就有1000*100=10万个分区

c、计算每个小分区上最大的1000个数。

为什么要找出每个分区上最大的1000个数？举个例子说明，全校高一有100个班，我想找出全校前10名的同学，很傻的办法就是，把高一100个班的同学成绩都取出来，作比较，这个比较数据量太大了。应该很容易想到，班里的第11名，不可能是全校的前10名。也就是说，不是班里的前10名，就不可能是全校的前10名。因此，只需要把每个班里的前10取出来，作比较就行了，这样比较的数据量就大大地减少了。我们要找的是100亿中的最大1000个数，所以每个分区中的第1001个数一定不可能是所有数据中的前1000个。

d、合并每个大分区细分出来的小分区。每个大分区有100个小分区，我们已经找出了每个小分区的前1000个数。将这100个分区的1000*100个数合并，找出每个大分区的前1000个数。

e、合并大分区。我们有1000个大分区，上一步已找出每个大分区的前1000个数。我们将这1000*1000个数合并，找出前1000.这1000个数就是所有数据中最大的1000个数。

a、b、c为map阶段，d、e为reduce阶段

最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（m）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。该算法的时间复杂度为O（nlogm+m），空间复杂度是10000（常数）。

堆调整的时间复杂度是O(log n)

最小堆，是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。

每次有数据输入的时候可以先与根节点比较。若不大于根节点，则舍弃；否则用新数值替换根节点数值。并进行最小堆的调整。

如果使用最大堆，排序时，都是对所有的对象进行排序，虽然就取了前几个

7.有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是f，p，现在求Q中元素的个数？

在循环队列中,头指针指向队列当中的第一个元素,而尾指针指向最后一个元素的下一位

假设循环队列的队尾指针是rear，队头是front，其中QueueSize为循环队列的最大长度。

(1) 入队时队尾指针前进1：(rear+1)%QueueSize

(2) 出队时队头指针前进1：(front+1)%QueueSize

(3) 队列长度：(rear-front+QueueSize)%QueueSize

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)

答案：(rear-front+N)%N

为了区分队空还是堆满的情况，有多种处理方式：

方式1： 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即约定以"队头指针在队尾指针的下一位置作为队满的标志"。

​ 队满条件为：(rear+1)%QueueSize==front

​ 队空条件为：front==rear

方式2： 增设表示队列元素个数的数据成员size，此时，队空和队满时都有front==rear。

​ 队满条件为：size==QueueSize

​ 队空条件为：size==0

方式3： 增设tag数据成员以区分队满还是队空

​ tag表示0的情况下，若因删除导致front==rear，则队空；

​ tag等于1的情况，若因插入导致front==rear则队满

8.快速排序最好时间复杂度和最坏时间复杂度会出现在什么情况？

快速排序是每个程序员都应当掌握的排序算法。当然我们接触的第一个排序算法可能是插入排序或者冒泡排序，但数据量一旦超过几万，插入和冒泡的性能会非常差。这时时间复杂度的渐进优势就表现出来了。 平均情况下快速排序的时间复杂度是Θ(nlgn)，最坏情况是n2，但通过随机算法可以避免最坏情况

快速排序算法其实很简单，采用分治策略。步骤如下：

1. 选取一个基准元素（pivot）
2. 比pivot小的放到pivot左边，比pivot大的放到pivot右边
3. 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2

可以用完全有序构造最坏情况，每次取第一个元素作为划分元素

9.什么是二叉平衡树（AVL