有向图

带权图

邻接矩阵存储方法

存储费空间，使用方便

领结表存储方法

节省空间、使用耗时

如何存储微博、微信等社交网络中的好友关系？

判断用户A是否关注用户B

判断用户A是否是用户B的粉丝

邻接表

逆邻接表

O(n^2)排序算法 3

• 冒泡排序
• 插入排序
• 选择排序

选择排序不稳定，相同元素可能会变化，因此这三种不选择选择排序。

代码中，把执行一个赋值语句的时间粗略地计为单位时间。冒泡排序需要 3 个赋值操作temp存储临时变量，而插入排序只需要 1 个 a[j]=a[j+1]移动数据。时间比值：1：7。

最优方法：插入排序。

O(nlogn) 排序算法 3

归并排序

• 方法：利用了分治思想，用递归代码来实现归并排序。先分，再合。

• 时间复杂度： T(n)=Cn+nlog2n。非常稳定，所有情况都是O(nlogn)。

• 空间复杂度：不是原地排序算法，每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时空间释放。 O(n)。
• 处理过程：是由下到上的，先处理子问题，然后再合并。

快速排序

方法：利用主元分区，每次分为左边小区，右边大区。直至区内只有一个元素之后，排序完成。

时间复杂度：分区每次右边都没有元素。就从 O(nlogn) 退化成了 O(n2)。

处理过程：是由上到下的，先分区，然后再处理子问题。

堆排序

10 亿个搜索关键词的日志文件，Top 10 最热门的搜索关键词

用户搜索的关键词，有很多可能都是重复的，散列表先记录次数。

用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出次数，若次数多>顶堆，则删除顶堆。遍历完成后得到top10。

然而10亿太大了。

哈希之后，将 10 亿条搜索关键词先通过哈希算法分到10个文件。在进行上述步骤，然后得到10x10个关键字。租后排序得到top10。

问题

10 个接口访问日志文件，每个日志文件大小约 300MB，日志都是按照时间戳从小到大排序的

将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后也是从小到大排序。

机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这10 个日志文件合并吗？

每次从各个文件中取一条数据，在内存中根据数据时间戳构建一个最小堆，然后每次把最小值给写入新文件，同时将最小值来自的那个文件再出来一个数据，加入到最小堆中。这个空间复杂度为常数，但没能很好利用1g内存，而且磁盘单个读取比较慢，所以考虑每次读取一批数据，没了再从磁盘中取，时间复杂度还是一样O(n)。

线性排序 3

桶排序（Bucket sort）

要求：

• 容易划分为m个桶，且天然有序
• 分布均匀，若分布不均匀全在一个桶里会退化为log（n/m log(n/m)) = log(n logn)
• 外部排序。数据大，内存有限，无法将数据全部加载到内存，存放于外部磁盘中。

10GB数据，如何按照订单金额排序？

• 扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 1…

• 将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内，第二个1001-2000，类推。每个桶按照范围命名。

• 理想状态均匀分布，则划分为100个100M文件。按文件编号，依次将文件放入内存快排，在写入同一个文件。
• 若部分文件很大，无法写入内存，继续划分，直到对所有文件都可读入内存为止，再依次快排。

计数排序（Counting sort）

要求：

• 数据量大，数据区间小
• 非负整数。若为不符合该条件，则转化即可。

如何根据年龄给 100 万用户排序？

年龄的范围最小 1 岁，最大不超过 120 岁；

遍历这 100 万用户，根据年龄将其划分到这 120 个桶里；

依次顺序遍历这 120 个桶中的元素。

高考查分系统，省内50万名考生，分数范围为900-0。

数据范围小，我们划分为901个桶，桶内为分数相同的学生。

此时不需要在排序，而是只需要依次输出到数组即可，只需一次扫描操作，时间复杂度O(n)。

ps. 若考生分数有小数点后一位，则需要所有分数乘10，转为整数，再放进9010个桶内。

基数排序（Radix sort）

要求：

• 数据可以分割出独立的“位”来比较，位之间有递进的关系（高位优先）
• 每一位的数据范围不能太大，要可以用线性排序算法来排序

10万个11位电话号码排序（等长）

• 规律：比较两个号码a、b，若前几位a已经大于b，则后面不用看。
• 方法：先按照最后一位排序，再按照倒数第二位，以此类推。最后按照第一位来排序。11排序之后，手机号码有序。
• 时间复杂度：按照每一位排序，数字只有0-10，可以使用桶排序，时间复杂度可以做到 O(n)。排序的数据有 k 位，时间为O(k*n)。k不大的时候，近似为O(n)。

排序牛津字典中的20 万个英文单词（非等长1-45）

• 解决非等长：把所有的单词补齐到相同长度，位数不够的可以在后面补“0”。根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响排序。
• 接着使用基数排序

有些人认为可视化只是把计算分析的结果图形化。

实则不然，可视化是人类认识、分析复杂数据的重要途径。

针对有序数据集合的查找算法

1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？

该功能不要占用太多的内存空间，最多不要超过 100MB。

二分思想

O(logn) 惊人的查找速度

二分查找的递归与非递归实现

最简单的情况就是有序数组中不存在重复元素。

1. 循环条件：low<=high

2. mid取值：

   low 和 high 比较大的话，mid=(low+high)/2和可能会溢出。

   改进方式1为，mid=low+(high-low)/2

   改进方式2为，除以 2 操作转化成位运算 mid = low+((high-low)>>1)

3. low和high更新

   low=mid+1，high=mid-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 循环二分查找
def search(arr, n, value):
    low = 0
    high = n - 1
    while low <= high:
        mid = int((high + low) / 2)
        if arr[mid] == value:
            return mid
        elif arr[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return -1


# 递归二分查找
def Binarysearch(arr, low, high, value):
    if low > high:
        return -1
    # 位操作，防止溢出
    mid = low + ((high - low) >> 1)
    if arr[mid] == value:
        return mid
    elif arr[mid] < value:
        return Binarysearch(arr, mid + 1, high, value)
    else:
        return Binarysearch(arr, low, mid - 1, value)


a = [1, 2, 3, 4, 6, 8, 9]
n = len(a)
value = 1

print(search(a, n, value))
print(Binarysearch(a, 0, n - 1, value))

LRU 缓存淘汰策略

内存管理的一种页面置换算法。LRU全称是Least Recently Used,即最近最久未使用的意思，最久未使用的数据，下次被访问的可能最小，我们需要删除它。

链表实现

维护一个有序单链表，靠近尾部是最早访问，头部为最新访问。当有新数据被访问，我们从头开始遍历链表：

• 若此数据之前已有，从原来的位置删除，再将数据放在头结点；
• 若之前没有：缓存未满，直接放在头部；缓存已满，删除尾部数据，将其放在头部。

时间复杂度：时间复杂度为 O(n)，需要遍历。

LRU缓存淘汰算法

散列表实现

1.上面所讲的几个散列表和链表组合的例子里，我们都是使用双向链表。如果把双向链表改成单链表，还能否正常工作？为什么呢？
2.假设猎聘网有10万名猎头，每个猎头可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这10万个猎头的ID和积分信息，让它能够支持这样几个操作：
1）根据猎头ID查收查找、删除、更新这个猎头的积分信息；
2）查找积分在某个区间的猎头ID列表；
3）查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。

以积分排序构建一个跳表，再以猎头 ID 构建一个散列表。

1）ID 在散列表中所以可以 O(1) 查找到这个猎头；
2）积分以跳表存储，跳表支持区间查询；
3）这点根据目前学习的知识暂时无法实现，老师文中也提到了。

第1章 Html介绍

本章节主要讲解html和css样式的关系，以及html标签、html文件结构、head标签,最后讲解了在html中的注释代码的作用。

关系：

学习web前端开发基础技术需要掌握：HTML、CSS、JavaScript语言。下面我们就来了解下这三门技术都是用来实现什么的：

1. HTML是网页内容的载体。内容就是网页制作者放在页面上想要让用户浏览的信息，可以包含文字、图片、视频等。
2. CSS样式是表现。就像网页的外衣。比如，标题字体、颜色变化，或为标题加入背景图片、边框等。所有这些用来改变内容外观的东西称之为表现。
3. JavaScript是用来实现网页上的特效效果。如：鼠标滑过弹出下拉菜单。或鼠标滑过表格的背景颜色改变。还有焦点新闻（新闻图片）的轮换。可以这么理解，有动画的，有交互的一般都是用JavaScript来实现的。

第一章 入门

本章节主要讲解如何在HTML文件中添加JavaScript代码，掌握必备的基础语法，为以后来章学习打下基础。

第二章 请和我互动

本章节主要讲解如何向网页中输入内容，如何与浏览器窗口进行交互，通过简单的对象方法就可以轻松实现。

原型链

创建对象有几种方法

1
2
3
4
5
6
7
8
9

// 1.字面量对象方式
var o1={name:'o1'};
var 02=new Object{name:'o2'};
// 2.通过构造函数
var M=function(name){this.name=name};
var o3=new M('o3');
// 3.Onject.create
var p={name:'p'};
var o4=Object.create(p);

常量

const x = “123”;//常量，定义后不能修改

作用域：var 定义的 i 变量是一个全局变量

let 声明的变量：块作用域

应用三：求中位数、第k%大的数字

维护大顶堆和小顶堆，分别存储n/2个数据（奇数则大顶堆维护n/2+1个）

大数据：

10亿关键字，Top10关键字。

散列表