当前位置 : 首页 » 文章分类 :  算法  »  面试准备13-算法

面试准备13-算法

Java面试准备之算法

labuladong的算法小抄
https://labuladong.gitbook.io/algo/

labuladong / fucking-algorithm
https://github.com/labuladong/fucking-algorithm


位运算

利用a^a=0消除元素

LeetCode.268.Missing Number 连续数组中缺失的数
LeetCode.389.Find the Difference 找出两个数组的不同
LeetCode.136.Single Number 数组中只出现一次的数

异或是无进位的加号


异或 ^ 被称为不进位的加号
左移 << 是一种进位或者乘法符号
公式:a + b = ( a ^ b ) + ( ( a & b ) << 1 )

LeetCode.371.Sum of Two Integers 不用加减号计算整数加法


-i==~i+1-i等于i各位取反加1

i 为正数或负数时都成立

8的补码 0000 1000
-8的补码 1111 1000

整数二进制表示中最低位1对应的值

lowbit(i) 将i转化成二进制数之后,只保留最低位的1及其后面的0,截断前面的内容,然后再转成10进制数

1、lowbit(i) = i & -i;
证明:
将 i 的二进制表示写为 a1b,其中 b 是0个或多个0,也就是1是最低位的1
-i = ~i+1 = ~(a1b)+1 = (~a)0(~b) +1 = (~a)1b
i&-i = a1b & (~a)1b = 01b 也就是仅保留最低位1其余全是0的二进制对应的数

2、lowbit(i) = i - (i & (i-1));
将 i 的二进制表示写为 a1b,其中 b 是0个或多个0,也就是1是最低位的1
i-1 = a0(~b)
i & (i-1) = a1b & a0(~b) = a0b
i - (i & (i-1)) = a1b - a0b = 01b

LeetCode.260.Single Number III 数组中只出现一次的数3


位运算技巧总结

判断一个整数是奇数还是偶数:将该数与 1 相与,结果为 0 则是偶数,结果为 1 则是奇数。
判断第 n 位是否是 1:x & (1<<n),结果为 1 说明是,为 0 说明不是。
将第 n 位设为 1:y = x | (1<<n)
将第 n 为设为 0:y = x & ~(1<<n)
将第 n 位的值取反:y = x ^ (1<<n)
将最右边的 1 设为 0:y = x & (x-1)
分离最右边的 1:y = x & (-x)
将最右边的 1 后面都设位 1:y = x | (x-1)
分离最右边的 0:y = ~x & (x+1)
将最右边的 0 设为 1:y = x | (x+1)

你必须知道的基本位运算技巧
https://blog.whezh.com/bit-hacks/


循环左移/右移n位

循环右移就是依次将移出的低位放到该数的高位
循环左移就是依次讲移出的高位放到该数的低位

32位整数val循环左移n位 leftRotateN(val) = (val << n) | (val >>> (32-n))
32位整数val循环右移n位 rightRotateN(val) = (val >>> n) | (val << (32-n))
注意这里的右移一定是逻辑右移>>>,即右移左补0的右移,如果写成算术右移(符号右移)>>就错了


数学

不引入新变量交换两个数的值

加法

int a = a + b;
int b = a - b;
int a = a - b;

对于加减法实现的交换方法,有可能发生溢出。

异或

int a = a ^ b;
int b = a ^ b;
int a = a ^ b;

对于异或运算实现的交换方法,当 a=b 时结果为0


数组

抽屉原理/鸽巢原理

抽屉原理/鸽巢原理,即“一个萝卜一个坑”,十个萝卜放到9个坑里,肯定有一个坑里有2个萝卜。

原理1:把多于n+1个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
原理2:把多于mn(m乘n)+1(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。
原理3:把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体

LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数

数组下标哈希

一看到题干中有 1 ≤ a[i] ≤ n,立即就要想到是用数组下标技巧做。
数组下标原地哈希法,在输入数组本身以某种方式标记已访问过的数字,用下标a[i]处的值a[a[i]]标记数值a[i]是否出现过
但是下标 a[i] 上原有的值不能被覆盖,那怎么办呢?
由于数组中所有元素值都是正数,可以将元素值取反来标记此下标对应的值位出现过。
对于数据中的每个值 a[i] ,将值 a[a[i]] 取反来表示这个值出现过,利用原数组空间的同时还不覆盖原数组的值(通过取绝对值可得原值)。
这样做的好处是不需要额外的空间,空间复杂度为 O(1)

下面是非常典型的3个题:
1、遍历过程中遇到已经是负值的对应的下标是出现过的重复的数
LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数

2、遍历一遍后没有被取反的元素对应的下标是缺失的数
LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数

无法直接进行数组下标哈希,要先对原数组的数据进行处理
LeetCode.041.First Missing Positive 数组中缺失的第一个正数

3、即求重复的,又求缺失的
LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数

数组形式的链表

把数组看做链表,即把下标 i 处的值 a[i] 看做 next 指针,也就是每个元素的值是下一个链表节点的地址,则数组转化为链表。
LeetCode.287.Find the Duplicate Number 数组中重复的数


双指针

滑动窗口/快慢指针

LeetCode.003.Longest Substring Without Repeating Characters 最长非重复子串

slow, fast 快慢(左右)指针,slow左边是要保留的元素
LeetCode.283.Move Zeroes 将数组中的零移到末尾
LeetCode.027.Remove Element 从数组中移除指定元素
LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项
LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

LeetCode.392.Is Subsequence 判断是否子序列

倍速指针

2倍速指针,快指针是慢指针的2倍速
有环单链表的环长、环起点和链表长
LeetCode.141.Linked List Cycle 判断链表是否有环
LeetCode.142.Linked List Cycle II 有环链表的环起点

LeetCode.287.Find the Duplicate Number 数组中重复的数

链表中使用2倍速指针,找链表中点
LeetCode.234.Palindrome Linked List 判断是否回文单链表

k间隔指针

k间隔指针,快指针比慢指针先走k步
LeetCode.061.Rotate List 旋转链表

LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点

左右指针/前后指针

low 从前往后扫描,high 从后往前扫描
LeetCode.027.Remove Element 从数组中移除指定元素

交替互换指针

LeetCode.160.Intersection of Two Linked Lists 两链表的交点


二分搜索

LeetCode.153.Find Minimum in Rotated Sorted Array 旋转排序数组中的最小值
LeetCode.033.Search in Rotated Sorted Array 在旋转有序数组中搜索


链表

找链表中的环

有环单链表的环长、环起点和链表长
LeetCode.141.Linked List Cycle 判断链表是否有环
LeetCode.142.Linked List Cycle II 有环链表的环起点

把链表连成环

LeetCode.061.Rotate List 旋转链表


跳跃表(skiplist)

有时候会被问到链表如果做到二分搜索,可能会有部分的人会去把链表中的值保存到数组来进行二分,但是如果知道跳跃表的话,那么这个数据结构就可以解决这个困惑,它允许快速查询一个有序连续元素的数据链表,它的效率可以做到和二分相同,都是O(logn)的平均时间复杂度,其空间复杂度为O(n)。

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。
像是redis中有序集合就使用到了跳跃表。

跳跃表的性质;
1、由很多层结构组成;
2、每一层都是一个有序的链表,排列顺序为由高层到底层,都至少包含两个链表节点,分别是前面的head节点和后面的nil节点;
3、最底层的链表包含了所有的元素;
4、如果一个元素出现在某一层的链表中,那么在该层之下的链表也全都会出现(上一层的元素是当前层的元素的子集);
5、链表中的每个节点都包含两个指针,一个指向同一层的下一个链表节点,另一个指向下一层的同一个链表节点;


跳跃表

可以看到,这里一共有4层,最上面就是最高层(Level 3),最下面的层就是最底层(Level 0),然后每一列中的链表节点中的值都是相同的,用指针来连接着。跳跃表的层数跟结构中最高节点的高度相同。理想情况下,跳跃表结构中第一层中存在所有的节点,第二层只有一半的节点,而且是均匀间隔,第三层则存在1/4的节点,并且是均匀间隔的,以此类推,这样理想的层数就是logN。

搜索
其基本原理就是从最高层的链表节点开始,如果比当前节点要大和比当前层的下一个节点要小,那么则往下找,也就是和当前层的下一层的节点的下一个节点进行比较,以此类推,一直找到最底层的最后一个节点,如果找到则返回,反之则返回空。
跳跃表查找操作的时间复杂度是O(logN)

插入
既然要插入,首先需要确定插入的层数,这里有不一样的方法。1. 看到一些博客写的是抛硬币,只要是正面就累加,直到遇见反面才停止,最后记录正面的次数并将其作为要添加新元素的层;2. 还有就是一些博客里面写的统计概率,先给定一个概率p,产生一个0到1之间的随机数,如果这个随机数小于p,则将高度加1,直到产生的随机数大于概率p才停止,根据给出的结论,当概率为1/2或者是1/4的时候,整体的性能会比较好(其实当p为1/2的时候,也就是抛硬币的方法)。
当确定好要插入的层数以后,则需要将元素都插入到从最底层到第k层。
跳跃表插入操作的时间复杂度是O(logN)

删除
在各个层中找到包含指定值的节点,然后将节点从链表中删除即可,如果删除以后只剩下头尾两个节点,则删除这一层。
总体上,跳跃表删除操作的时间复杂度是O(logN)

跳跃表原理和实现
https://www.cnblogs.com/George1994/p/7635731.html

漫画算法:什么是跳跃表?
http://blog.jobbole.com/111731/


栈和队列

最大栈(最小栈)

用java实现栈,增加getMaxValue()方法(最大栈)
思路分析:在栈中实现一个方法 每一调用该方法可以获得当前栈中的最大值 通过把两个栈封装在一个栈中 其中的一个栈存放正常的元素 另一个栈max只存最大元素

如果push()一个数 如果这个数比 最大栈的栈顶值max.peek()还要大 说明插入的该元素是栈中的最大的元素,将其同时插入max。 否则 在max栈中插入max.peek(),即之前的最大值。出栈时同时将max栈顶pop即可。

实现一个最大栈、最小栈
http://blog.csdn.net/u013078669/article/details/51029935

用两个栈实现一个队列

真正性能较高的,其实是另一个变种。即:
入队时,将元素压入s1。
出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。但在实际面试中很少有人说出,可能是时间较少的缘故吧。

用两个栈实现一个队列——我作为面试官的小结
https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html

两个栈实现队列 两个队列实现栈
https://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

两个队列实现一个栈

q1是专职进出栈的,q2只是个中转站。元素集中存放在一个栈中,但不是指定(q1 或 q2)。
定义两个指针:pushtmp:指向专门进栈的队列q1; tmp:指向临时作为中转站的另一个栈q2

入栈:直接入pushtmp所指队列即可
出栈:把pushtmp的除最后一个元素外全部转移到队列tmp中,然后把刚才剩下q1中的那个元素出队列

使用两个队列实现一个栈
https://www.cnblogs.com/ming-zi/p/6379697.html

两个栈实现队列 两个队列实现栈
https://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html


用java实现生产者消费者模式


排序

快速排序(nlogn不稳定)

思想:首先选取一个枢纽元(pivot),然后将数据划分成左右两部分,左边的大于(或等于)枢纽元,右边的小于(或等于枢纽元),最后递归处理左右两部分。

步骤及实现

步骤:
1、选择枢轴
2、按枢轴分割
3、递归对左右两个子序列进行快速排序

按枢轴分割
改进的双向扫描
枢纽元保存在一个临时变量中,这样左端的位置可视为空闲。j从右向左扫描,直到A[j]小于等于枢纽元,检查i、j是否相交并将A[j]赋给空闲位 置A[i],这时A[j]变成空闲位置;i从左向右扫描,直到A[i]大于等于枢纽元,检查i、j是否相交并将A[i]赋给空闲位置A[j],然后 A[i]变成空闲位置。重复上述过程,最后直到i、j相交跳出循环。最后把枢纽元放到空闲位置上。

代码实现

public static void quickSort(int[] arr){
    qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
    if (low < high){
        int pivot=partition(arr, low, high);        //将数组分为两部分
        qsort(arr, low, pivot-1);                  //递归排序左子数组
        qsort(arr, pivot+1, high);                  //递归排序右子数组
    }
}
private static int partition(int[] arr, int low, int high){
    int pivot = arr[low];    //枢轴记录
    while (low<high){
        while (low<high && arr[high]>=pivot) --high;
        arr[low]=arr[high];            //交换比枢轴小的记录到左端
        while (low<high && arr[low]<=pivot) ++low;
        arr[high] = arr[low];          //交换比枢轴小的记录到右端
    }
    //扫描完成,枢轴到位
    arr[low] = pivot;
    //返回的是枢轴的位置
    return low;
}

时间复杂度

快速排序最佳运行时间 O(nlogn),最坏运行时间 O(N^2),随机化以后期望运行时间 O(nlogn)

可以看出,每一次调用partition()方法都需要扫描一遍数组长度(注意,在递归的时候这个长度并不是原数组的长度n,而是被分隔出来的小数组,即n×(2^(-i))),其中i为调用深度。而在这一层同样长度的数组有2^i个。那么,每层排序大约需要O(n)复杂度。而一个长度为n的数组,调用深度最多为log(n)层。二者相乘,得到快速排序的平均复杂度为O(nlogn)。

通常,快速排序被认为是在所有同数量级的排序方法中,平均性能最好。

快速排序对数组中的数据分布很敏感,当数据分布较随机时,快速排序性能最好,复杂度为O(nlogn),如果数组已基本有序,快排性能最差,复杂度为O(N^2),退化为冒泡排序。


快速排序优化

优化枢轴选取

select_pivot(T A[], int p, int q),该函数从A[p…q]中选取一个枢纽元并返回,且枢纽元放置在左端(A[p]的位置)。
固定选取:取序列的第一个元素为枢轴
随机选取:顾名思义就是从A[p…q]中随机选择一个枢纽元
三数取中:即取三个元素的中间数作为枢纽元,一般是取左端、右断和中间三个数,也可以随机选取。

分割到一定程度后使用插入排序

当待排序序列的长度分割到一定大小后,使用插入排序。
原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排

if (high - low + 1 < 10) {
    InsertSort(arr,low,high);
    return;
}//else时,正常执行快排
递归栈优化(尾递归优化)

此外,快速排序需要一个递归栈,通常情况下这个栈不会很深,为log(n)级别。但是,如果每次划分的两个数组长度严重失衡,则为最坏情况,栈的深度将增加到O(n)。此时,由栈空间带来的空间复杂度不可忽略。如果加上额外变量的开销,这里甚至可能达到恐怖的O(n^2)空间复杂度。所以,快速排序的最差空间复杂度不是一个定值,甚至可能不在一个级别。

为了解决这个问题,我们可以在每次划分后比较两端的长度,并先对短的序列进行排序(目的是先结束这些栈以释放空间),可以将最大深度降回到O(㏒n)级别。

此外,快排函数在函数尾部有两次递归操作,我们可以对其使用尾递归优化
原因:如果待排序的序列划分极端不平衡,递归的深度将趋近于n,而栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多。优化后,可以缩减堆栈深度,由原来的O(n)缩减为O(logn),将会提高性能。

private static void qsort(int[] arr, int low, int high){
    while (low < high){
        int pivot=partition(arr, low, high);
        qsort(arr, low, pivot-1);
        low = pivot + 1;  //尾递归改为循环
    }
}

其实这种优化编译器会自己优化,相比不使用优化的方法,时间几乎没有减少

快速排序(简介、清晰)
https://www.cnblogs.com/codeskiller/p/6360870.html

三种快速排序以及快速排序的优化
http://blog.csdn.net/insistgogo/article/details/7785038

快速排序 优化 详细分析
http://blog.csdn.net/zuiaituantuan/article/details/5978009


快速排序应用

寻找第k大/小的数(找前k大/小的数)

输入n个整数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。(剑指offer,面试题30,页数:167)
随机选取枢轴进行一次分割,得到分割后的枢轴位置loc,如果loc等于k,则找到第k小的数;如果loc大于k,继续在左边找;如果loc小于k,继续在右边找

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数

求数组的众数/主元素(出现次数过半的数)

随机选取枢轴进行一次分割,得到分割后枢轴的位置loc,如果loc等于mid,则找到主元素;如果loc小于mid,在右边子序列中找主元素;如果loc大于mid,在左边子序列中找主元素。

其实用快速排序性质来找主元素比较麻烦,更好的方法是 摩尔投票算法,参考
LeetCode.169.Majority Element 数组的众数/主元素

//找出 arr 中 第  n/2  大的那个元素
public static int media_number(int[] arr){
    int left = 0;
    int right = arr.length - 1;
    int center = (left + right) / 2;

    int pivot_index = parition(arr, left, right);//枢轴元素的索引

    while(pivot_index != center)
    {
        if(pivot_index > center){
            right = pivot_index - 1;
            pivot_index = parition(arr, left, right);
        }
        else{
            left = pivot_index + 1;
            pivot_index = parition(arr, left, right);
        }
    }
    return arr[center];
}

快速排序及其应用
https://www.2cto.com/kf/201308/235343.html


归并排序(nlogn稳定)

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略

归并排序将待排序数组A[1..n]分成两个各含n/2个元素的子序列,然后对这个两个子序列进行递归排序,最后将这两个已排序的子序列进行合并,即得到最终排好序的序列。

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(NlogN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

图解排序算法(四)之归并排序
http://www.cnblogs.com/chengxiao/p/6194356.html

白话经典算法系列之五 归并排序的实现(讲的真好)
https://blog.csdn.net/yuehailin/article/details/68961304

排序算法(2)——归并排序
https://blog.csdn.net/tmylzq187/article/details/51816084


Timsort(归并加插入)(nlogn稳定)

TimSort排序算法是Python和Java针对对象数组的默认排序算法。TimSort排序算法的本质是归并排序算法,只是在归并排序算法上进行了大量的优化。对于日常生活中我们需要排序的数据通常不是完全随机的,而是部分有序的,或者部分逆序的,所以TimSort充分利用已有序的部分进行归并排序。

TimSort算法的核心在于利用数列中的部分有序。

Timsort是结合了归并排序(merge sort)和插入排序(insertion sort)而得出的排序算法,它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用(TimSort 是 Python 中 list.sort 的默认实现)。该算法找到数据中已经排好序的块-分区,每一个分区叫一个run,然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序,现在Java SE7和Android也采用Timsort算法对数组排序。

TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退,将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字,而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列,每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run,这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。

综上述过程,Timsort算法的过程包括
(0)如何数组长度小于某个值,直接用二分插入排序算法
(1)找到各个run,并入栈
(2)按规则合并run

run是已经排好序的一块分区。run可能会有不同的长度,每个run最少要有2个元素。Timesort根据run的长度来选择排序的策略。例如如果run的长度小于某一个值,则会选择插入排序算法来排序。

Timesor按照升序和降序划分出各个run:

  • run如果是是升序的,那么run中的后一元素要大于或等于前一元素;
  • 如果run是严格降序的,即run中的前一元素大于后一元素,需要将run 中的元素翻转(这里注意降序的部分必须是“严格”降序才能进行翻转。因为 TimSort 的一个重要目标是保持稳定性stability。如果在 >= 的情况下进行翻转这个算法就不再是 stable)。

Timsort原理介绍
https://blog.csdn.net/yangzhongblog/article/details/8184707

简易版的TimSort排序算法
https://www.cnblogs.com/nullzx/p/6014471.html

深入理解 timsort 算法(1):自适应归并排序
http://blog.jobbole.com/99681/


希尔排序(减少插入排序的移动次数)

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,小的基本在前,大的基本在后。然后缩小增量,到增量为1时,其实多数情况下只需微调即可,不会涉及过多的数据移动。

希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2…1}(希尔增量),其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

图解排序算法(二)之希尔排序
https://www.cnblogs.com/chengxiao/p/6104371.html


堆排序(nlogn不稳定)

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
用简单的公式来描述一下堆的定义就是:
大顶堆:arr[i] >= arr[2i+1] 且 arr[i] >= arr[2i+2]
小顶堆:arr[i] <= arr[2i+1] 且 arr[i] <= arr[2i+2]

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换(或者说将堆顶输出),此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

图解排序算法(三)之堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html

寻找第k大/小的数(找前k大/小的数)

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.347.Top K Frequent Elements 前K个高频元素

容量为k的小顶堆(更常用)

寻找第k大的数
建立一个长度为K的最小堆,用数组的前K个元素初始化,然后从第K+1个元素开始
如果大于堆顶,压入堆中,如果堆大小大于k,则弹出堆顶。 (或者如果大于堆顶元素,先弹出堆顶,再压入当前元素。也就是先弹出堆顶还是后弹出都一样。)
如果小于堆顶,直接忽略,继续读入下一个
这样最后最小堆里剩的就是最大的K个元素
时间复杂度 O(nlogk),空间复杂度 O(k)

容量为n的大顶堆(不常用)

维护一个容量为 n 的大顶堆(n是数组长度),把所有元素依次放入堆中,最后把堆顶的 k-1 个元素弹出,也就是弹出前 k-1 大的数,则剩下的堆顶就是第 k 大值。
向大小为 n 的堆中添加元素的时间复杂度为 O(logn),重复 n 次,故总时间复杂度为 O(nlogn),空间复杂度 O(n)

所以,可以看出如果用最大堆解决,需要容量为数组长度的最大堆,当数据长度非常大时(比如几亿个数据中找top 10),空间开销非常大,所以不推荐用最大堆。
所以 求前k大,用最小堆,求前k小,用最大堆。


树和二叉树

完全二叉树(Complete Binary Tree)

完全二叉树(Complete Binary Tree)
在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。

完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉搜索树(二叉排序树)(BST)

二叉查找树(也叫二叉搜索树)(Binary Search Tree)就是二叉排序树(Binary Sort Tree)

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点,那么会有y.key<=x.key;如果y是x右子树中的一个节点,那么有y.key>=x.key。

查找与性能分析O(logn)->O(n)

若假设树的高度是h,那么查找过程的时间复杂度就是O(h)。
若n个结点的二叉搜索树是平衡的,查找复杂度为O(logn),最坏情况下(比如用有序数组创建BST),二叉查找树退化成了一棵具有n个结点的线性链(单边树),查找复杂度为O(n)。

递归实现:

//递归实现
Tree_Search(x, k):
if x == NIL or x.key == k :
    return x
if k < x.key
    return Tree_Search(x.left, k)
else return Tree_Search(x.right, k)

非递归迭代实现:

//非递归迭代实现
Tree_Search(x, k) :
while x!=NIL and k!=x.key:
    if k < x.key
        x = x.left
    else x = x.right
return x

深入理解二叉搜索树(BST)
https://blog.csdn.net/u013405574/article/details/51058133

把BST转换为双向链表

http://blog.csdn.net/brucehb/article/details/58381745


平衡二叉树(AVL)

AVL树是根据它的发明者G. M. Adelson-Velskii和E. M. Landis命名的。AVL树本质上还是一棵二叉搜索树,它的特点是:
本身首先是一棵二叉查找树。带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1

平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡(通过旋转实现)。

平衡二叉树很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

平衡二叉树详解
https://blog.csdn.net/u010442302/article/details/52713585


红黑树(RBT)

R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树是一种近似平衡的二叉查找树,它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。

红黑树的特性:
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树的插入

将一个节点插入到红黑树中,需要执行哪些步骤呢?首先,将红黑树当作一颗二叉查找树,将节点插入;然后,将节点着色为红色;最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。

1、把红黑树当做BST插入结点

第一步: 将红黑树当作一颗二叉查找树,将节点插入。
红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
好吧?那接下来,我们就来想方设法的旋转以及重新着色,使这颗树重新成为红黑树!

2、把插入结点染为红色

第二步:将插入的节点着色为”红色”。
为什么着色成红色,而不是黑色呢?为什么呢?在回答之前,我们需要重新温习一下红黑树的特性:
(1) 每个节点或者是黑色,或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
(4) 如果一个节点是红色的,则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
将插入的节点着色为红色,不会违背”特性(5)”!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。

为什么将插入结点看做红色?

因为要满足红黑树的这五条性质,如果我们插入的是黑色节点,那就违反了性质五,需要进行大规模调整,如果我们插入的是红色节点,那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时,违反性质二,所以,我们把要插入的节点的颜色变成红色。

3、旋转与着色使之再次成为红黑树

在树的结构发生改变时(插入或者删除操作),红黑树的条件可能被破坏,需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类:一类是颜色调整,即改变某个节点的颜色;另一类是结构调整,集改变检索树的结构关系。结构调整过程包含两个基本操作:左旋(Rotate Left),右旋(RotateRight)。

红黑树的应用

红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

1、广泛用于C++的STL中,map和set都是用红黑树实现的.
2、著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
3、IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查.
4、ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
5、java中TreeMap的实现.

红黑树与AVL对比

平衡二叉树是一种严格的平衡树,平衡因子小于等于1。由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.

AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势,其应用上也有不同。
结构对比: AVL的结构高度平衡,RBT的结构基本平衡。平衡度AVL > RBT.
查找对比: AVL 查找时间复杂度最好,最坏情况都是O(logN)。RBT 查找时间复杂度最好为O(logN),最坏情况下比AVL略差。
插入删除对比:

  1. AVL的插入和删除结点很容易造成树结构的不平衡,而RBT的平衡度要求较低。因此在大量数据插入的情况下,RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。
  2. 如果需要平衡处理时,RBT比AVL多一种变色操作,而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。
  3. 当插入一个结点都引起了树的不平衡,AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后,AVL最多需要logN 次旋转操作,而RBT最多只需要3次。因此两者插入一个结点的代价差不多,但删除一个结点的代价RBT要低一些。
  4. AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。
    总体评价:大量数据实践证明,RBT的总体统计性能要好于平衡二叉树。

二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比
https://blog.csdn.net/z702143700/article/details/49079107

浅谈AVL树,红黑树,B树,B+树原理及应用
https://blog.csdn.net/whoamiyang/article/details/51926985

红黑树(一)之 原理和算法详细介绍
http://www.cnblogs.com/skywang12345/p/3245399.html

最容易懂得红黑树
https://blog.csdn.net/sun_tttt/article/details/65445754

史上最清晰的红黑树讲解(上)(结合Java TreeMap讲解)
https://www.cnblogs.com/CarpenterLee/p/5503882.html

漫画:什么是红黑树? - 程序员小灰
http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191832&idx=1&sn=12017161025495c6914b5ab9397baa59


B-树(B树)

B-树就是B树,也就是英文中的B-Tree,中间是横线不是减号,一般直接读作B树(读作B减树不规范,但好多人这么读)

一个m阶的B树具有如下几个特征:
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

为什么数据库索引使用B树?

数据库索引是存储在磁盘上的,索引大小可能有几个G甚至更多。当利用索引查询的时候,不能把整个索引都加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页对应着索引树的结点。每次加载一个结点,都需要进行一次磁盘IO,磁盘IO的次数等于索引树的高度。

为了减少磁盘IO的次数,需要把原本“瘦高”的树结构变得“矮胖”。B树是一种多路平衡查找树,由于是多叉的,对于同样的结点个数n,B树比平衡二叉树的高度更小,这就是B树相对于平衡二叉树的优点。

由于B树每个节点上有多个key值,所以查询时比较次数其实不比平衡二叉树少,但相对于耗时的磁盘IO,内存中的比较耗时几乎可以忽略。只要高度足够低,IO次数足够少,就可以提高查找性能。

漫画:什么是B-树?
http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190965&idx=1&sn=53f78fa037386f85531832cd5322d2a0


B+树

B+树是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。

一个m阶的B+树具有如下几个特征:
1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

B+树与B树对比

B+树相比于B树的优势:
1、IO次数更少(磁盘IO代价低)
相对于B树,B+树每个节点存储的关键字数更多,这就意味着,数据量相同的情况下,B+树的层级更少(高度更低、更矮胖),所以IO次数更少,查询数据更快。
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。

2、查询性能稳定
B+树中所有关键字指针都存在叶子节点,所以每次查询都必须最终查到叶子节点上,而B树只要找到匹配元素即停止。所以B树查找性能并不稳定(最好情况只查根节点,最坏情况查到叶子节点),而B+树每次查找都是稳定的。
由于内部结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

3、范围查询方便(顺序遍历)
B树中做范围查询只能先找到边界点(比作左边界),再做中序遍历直到右边界,很繁琐。由于B+树中所有叶子节点形成有序链表,所以B+树中做范围查询只需先找到边界点(比如左边界),然后在链表上顺序遍历到右边界即可。
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题,而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库中频繁使用的range query,B+树有着更高的性能。

漫画:什么是B+树?
https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191027&idx=1&sn=4ba22e3ec8bd149f69fc0aba72e4347e

浅谈AVL树,红黑树,B树,B+树原理及应用
https://blog.csdn.net/whoamiyang/article/details/51926985

B树与B+树
https://blog.csdn.net/guoziqing506/article/details/64122287

B树和B+树与索引

B树主要应用于文件系统以及部分数据库索引,比如著名的非关系数据库MongoDB
而大部分关系型数据库,比如mysql,则使用B+树作为索引。

在 MySQL 中,主要有四种类型的索引,分别为: B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。

B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引,而且只支持索引单个 AUTO_INCREMENT 列。

不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。

一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引。当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息(增加了顺序访问指针),这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。

B-树和B+树的应用:数据搜索和数据库索引
http://blog.jobbole.com/107800/


Trie树/前缀树/字典树

Trie树,又叫字典树、前缀树(Prefix Tree)、单词查找树 或 键树,是一种多叉树结构。


Trie树

上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。

Trie树特性:
第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
第二:从根节点到某一节点,路径上经过的字符连接起来,就是该节点对应的字符串。
第三:每个单词的公共前缀作为一个字符节点保存。

Trie树应用:
1、字符串检索
检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较:
如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在。
如果所有的字符全部比较完并且全部相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)。

2、词频统计。
可能有人要说了,词频统计简单啊,一个hash或者一个堆就可以打完收工,但问题来了,如果内存有限呢?还能这么 玩吗?所以这里我们就可以用trie树来压缩下空间,因为公共前缀都是用一个节点保存的。

3、前缀匹配
就拿上面的图来说吧,如果我想获取所有以”a”开头的字符串,从图中可以很明显的看到是:and,as,at,如果不用trie树, 你该怎么做呢?很显然朴素的做法时间复杂度为O(N2) ,那么用Trie树就不一样了,它可以做到h,h为你检索单词的长度, 可以说这是秒杀的效果。

【面试被虐】游戏中的敏感词过滤是如何实现的?
https://mp.weixin.qq.com/s/LaD99uoUtIwsv2OXvvj-0g

Trie树(Prefix Tree)介绍
https://blog.csdn.net/lisonglisonglisong/article/details/45584721


图的遍历

图的遍历就是从图中的某个顶点出发,按某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的顶点在遍历过程中仅访问一次,要为每一个顶点设置一个访问标志。通常有两种方法:深度优先搜索(DFS)和广度优先搜索(BFS).这两种算法对有向图与无向图均适用。

数据结构(17)–图的遍历DFS和BFS
http://blog.csdn.net/u010366748/article/details/50792759

算法导论–图的遍历(DFS与BFS)
http://blog.csdn.net/luoshixian099/article/details/51897538

深度优先搜索(DFS)

深度优先搜索(DFS)
1.从图中某个顶点v0出发,首先访问v0;
2.访问结点v0的第一个邻接点,以这个邻接点vt作为一个新节点,访问vt所有邻接点。直到以vt出发的所有节点都被访问到,回溯到v0的下一个未被访问过的邻接点,以这个邻结点为新节点,重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。
3.若此时图中仍有未被访问的结点,则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程,直到图中的所有节点均被访问过。

遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。 当使用二维数组表示邻接矩阵作图的存储结构时,查找每个顶点的邻接点所需时间为O(n^2),其中n为顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e为无向图中边的数目或有向图中弧的数目。由此,当以邻接表作存储结构时,深度优先搜遍遍历图的时间复杂度为O(n+e)。

广度优先搜索(BFS)

广度优先搜索(BFS)
BFS类似与树的层次遍历,从源顶点s出发,依照层次结构,逐层访问其他结点。即访问到距离顶点s为k的所有节点之后,才会继续访问距离为k+1的其他结点。
1.从图中某个顶点v0出发,首先访问v0;
2.依次访问v0的各个未被访问的邻接点。
3.依次从上述邻接点出发,访问他们的各个未被访问的邻接点。始终保证一点:如果vi在vk之前被访问,则vi的邻接点应在vk的邻接点之前被访问。重复上述步骤,直到所有顶点都被访问到。
4.如果还有顶点未被访问到,则随机选择一个作为起始点,重复上述过程,直到图中所有顶点都被访问到。

每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程,因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同,两者不同之处仅仅在于对顶点访问的顺序不同。

判断图的连通性(DFS/BFS)

如果一个图是连通的,那么从一个节点开始访问,采用深度优先或者广度优先对它进行遍历,那么必定能够访问完所有的节点。

EOJ 1816 判断图连通的三种方法——dfs,bfs,并查集
http://blog.csdn.net/fangpinlei/article/details/42127055


最短路径

无权图最短路径(BFS)

求从顶点A到B所含边数目最少的路径
只需从顶点A出发对图作广度优先搜索,一旦遇到顶点B就终止,此时得到从A到B的最短路径。

一个无权图G,使用某个顶点s作为输入参数,我们想要找出从s到所有其它顶点的最短路径。
这种搜索图的方法称为广度优先搜索(breadth-first search)。该方法按层处理顶点:距开始点最近的那些顶点首先被求值,而最远的那些顶点最后被求值。这很像对树的层序遍历

最短路径算法–无权最短路径
http://blog.csdn.net/tanga842428/article/details/52582817

赋权图单源最短路径(迪杰斯特拉算法)

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

迪杰斯特拉算法用于求带权有向图G0中从v0到其余各顶点的最短路径。

地杰斯特拉算法也适用于带权无向图,因为带权无向图可以看作是有往返二重边的有向图,只要在顶点vi 与vj 之间存在无向边(vi , vj ),就可以看成是在这两个顶点之间存在权值相同的两条有向边(vi , vj)和(vj , vi)

算法的思路:
Dijkstra算法采用的是一种贪心的策略,声明一个数组dis[]来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

设T是已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为x)或者是边(s,x)(s为起点),或者是中间只经过T中顶点到达x的路径。
反证法:假设此路径上有一个顶点不在T中,则说明存在一条终点不在T中而长度比此路径短的路径。但是,这是不可能的。因为我们是按路径长度递增的次序来产生各最短路径的,故长度比此路径短的所有路径均已产生,他们的终点必定在T中,所以假设不成立。

时间复杂度O(n^2)

赋权图多源最短路径(弗洛伊德算法)

依次以图中每个顶点为起点,重复n此迪杰斯特拉算法,可得到每一对顶点间的最短路径,复杂度为O(n^3)
弗洛伊德算法,复杂度也是O(n^3),但形式上更简单。

对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]表示从Vi到Vj需要经过的点,初始化D[i][j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,则D[i][j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。


LeetCode刷题

马呆萌-LeetCode标签
http://madaimeng.com/tags/LeetCode/


尾递归优化(改为循环)

与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。
尾递归:http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/tail-recursion-explanation.html


上一篇 面试准备14-智力题

下一篇 面试准备12-计算机基础

阅读
评论
14,888
阅读预计55分钟
创建日期 2018-05-28
修改日期 2020-02-21
类别
标签
目录
  1. 位运算
    1. 利用a^a=0消除元素
    2. 异或是无进位的加号
    3. -i==~i+1-i等于i各位取反加1
    4. 整数二进制表示中最低位1对应的值
    5. 位运算技巧总结
    6. 循环左移/右移n位
  2. 数学
    1. 不引入新变量交换两个数的值
      1. 加法
      2. 异或
  3. 数组
    1. 抽屉原理/鸽巢原理
    2. 数组下标哈希
    3. 数组形式的链表
  4. 双指针
    1. 滑动窗口/快慢指针
    2. 倍速指针
    3. k间隔指针
    4. 左右指针/前后指针
    5. 交替互换指针
  5. 二分搜索
  6. 链表
    1. 找链表中的环
    2. 把链表连成环
    3. 跳跃表(skiplist)
  7. 栈和队列
    1. 最大栈(最小栈)
    2. 用两个栈实现一个队列
    3. 两个队列实现一个栈
    4. 用java实现生产者消费者模式
  8. 排序
    1. 快速排序(nlogn不稳定)
      1. 步骤及实现
      2. 时间复杂度
      3. 快速排序优化
        1. 优化枢轴选取
        2. 分割到一定程度后使用插入排序
        3. 递归栈优化(尾递归优化)
      4. 快速排序应用
        1. 寻找第k大/小的数(找前k大/小的数)
        2. 求数组的众数/主元素(出现次数过半的数)
    2. 归并排序(nlogn稳定)
    3. Timsort(归并加插入)(nlogn稳定)
    4. 希尔排序(减少插入排序的移动次数)
    5. 堆排序(nlogn不稳定)
      1. 寻找第k大/小的数(找前k大/小的数)
        1. 容量为k的小顶堆(更常用)
        2. 容量为n的大顶堆(不常用)
  9. 树和二叉树
    1. 完全二叉树(Complete Binary Tree)
    2. 二叉搜索树(二叉排序树)(BST)
      1. 查找与性能分析O(logn)->O(n)
      2. 把BST转换为双向链表
    3. 平衡二叉树(AVL)
    4. 红黑树(RBT)
      1. 红黑树的插入
        1. 1、把红黑树当做BST插入结点
        2. 2、把插入结点染为红色
          1. 为什么将插入结点看做红色?
        3. 3、旋转与着色使之再次成为红黑树
      2. 红黑树的应用
      3. 红黑树与AVL对比
    5. B-树(B树)
      1. 为什么数据库索引使用B树?
    6. B+树
      1. B+树与B树对比
      2. B树和B+树与索引
    7. Trie树/前缀树/字典树
    1. 图的遍历
      1. 深度优先搜索(DFS)
      2. 广度优先搜索(BFS)
      3. 判断图的连通性(DFS/BFS)
    2. 最短路径
      1. 无权图最短路径(BFS)
      2. 赋权图单源最短路径(迪杰斯特拉算法)
      3. 赋权图多源最短路径(弗洛伊德算法)
  10. LeetCode刷题
  11. 尾递归优化(改为循环)

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论