轻松学算法 互联网算法面试宝典pdf

轻松学算法 互联网算法面试宝典 作 者 ：赵烨

轻松学算法 互联网算法面试宝典 出版社： 电子工业出版社

轻松学算法 互联网算法面试宝典 内容简介

《轻松学算法——互联网算法面试宝典》共分为12 个章节，首先介绍了一些基础的数据结构，以及常用的排序算法和查找算法；其次介绍了两个稍微复杂一些的数据结构——树和图，还介绍了每种数据结构和算法的适用场景，之后是一些在工作与面试中的实际应用，以字符串、数组、查找等为例介绍了一些常见的互联网面试题及分析思路，便于读者了解这些思路，顺利地通过互联网公司的面试；最后介绍了一些常见的算法思想，便于读者对今后遇到的算法问题更轻易地想出解决方案。

《轻松学算法——互联网算法面试宝典》的讲解轻松有趣，易于读者把烦琐、枯燥的算法学习变为有趣、愉快的学习，把被动学习变为主动学习。《轻松学算法——互联网算法面试宝典》也介绍了一些会在工作面试中用到的算法。对于一些正在学习算法的人来说，《轻松学算法——互联网算法面试宝典》绝对是可以帮你轻松掌握算法的辅助资料；对于已经了解算法的人来说，可以从《轻松学算法——互联网算法面试宝典》中了解到这些算法是如何在实际工作中使用的。

《轻松学算法——互联网算法面试宝典》适合即将毕业的学生、初入职场的工程师及想补充基础算法知识的人学习，也适合作为一本互联网公司面试的参考书，更是一本不可多得的便于读者时常补习算法知识的收藏宝典。

轻松学算法 互联网算法面试宝典 目录

前言

第1章 数组、集合和散列表

1.1 要用就要提前想好的数据结构——数组

1.2 升级版数组——集合

1.3 数组的其他应用——散列表

1.4 小结

第2章 栈、队列、链表

2.1 汉诺塔游戏——栈

2.2 火爆的奶茶店——队列

2.3 用栈实现队列

2.4 链表

2.5 链表其实也可以用数组模拟

2.6 再谈汉诺塔

第3章 排序算法

3.1 算法基础

3.2 快而简单的排序——桶排序

3.3 咕嘟咕嘟的冒泡排序

3.4 最常用的快速排序

3.5 简单的插入排序

3.6 直接插入的改进——希尔排序

3.7 简单选择排序

3.8 小结

第4章 搜索，没那么难

4.1 最先想到的——顺序查找

4.2 能不能少查点——二分查找

4.3 行列递增的矩阵查找——二分查找思维拓展

4.4 分块查找

4.5 查找算法小结

4.6 搜索引擎与倒排索引

第5章 树

5.1 树的定义及存储结构

5.2 二叉树

5.3 二叉树的查找算法

5.4 B-树、B+树

5.5 在MySQL数据库中是如何应用B+树的

5.6 哈夫曼树

5.7 堆

5.8 红黑树

第6章 图

6.1 图的定义及相关术语

6.2 图的表示与存储方式

6.3 更多的图

6.4 深度优先遍历与广度优先遍历

6.5 最短路径

第7章 字符串

7.1 字符及字符串简介

7.2 字符的全排列

7.3 反转字符串

7.4 判断回文

7.5 寻找最大的回文子串

7.6 将字符串转换为数字

7.7 判断字符串包含的问题

第8章 数组还有好多玩法

8.1 从数组中找出其和为指定值的两个数

8.2 找出连加值最大的子数组

8.3 数组正负值排序

8.4 将数组随机打乱顺序

8.5 数组赋值

8.6 寻找旋转数组的拐点

8.7 荷兰国旗问题

第9章 查找又来了

9.1 出现次数超过一半的数字

9.2 寻找缺少的数字

9.3 在10亿个数中找出最大的1万个数

第10章 更多

10.1 不使用额外的空间交换两个数

10.2 拿乒乓球的问题

第11章 实现一些集合类

11.1 栈（Stack）的实现

11.2 变长数组（ArrayList）的实现

11.3 散列表（HashMap）的实现

第12章 方向

12.1 算法的一些常用思想

12.2 新兴算法

12.3 其他算法

轻松学算法 互联网算法面试宝典 精彩文摘

12.2 新兴算法

12.2.1 加密算法

加密算法其实不算是新兴算法，却是最近人们一直在讨论的内容。在MD5加密被碰撞破解之后，人们开始考虑各种各样的加密实现了。

这里给大家介绍几种常用的加密算法。

从理论上说，摘要算法也属于加密算法，MD5、SHA系列的算法都是摘要算法，是不可逆的，也就是无法解密的。

而RSA、3DES之类的可逆算法，是可以解密的。

加密算法又分为对称加密算法和非对称加密算法。对称加密算法使用同一密钥进行加解密；而非对称加密算法使用不同的密钥进行加解密。

当然，除了我们应该熟知的这些常用的加密算法，还有很多很少见的算法，比如椭圆曲线算法等。

12.2.2 商业算法

其实，近年来有很多新兴算法，因为人们在不断地探索更好的东西，去改变或者适应更好的业务。

很多算法是为了具体的产品而设计出来的。

比如图像识别算法，为了保证互联网用户上传的内容是健康的，我们需要一定的算法去识别图片中有没有不好的内容，比如用户在新浪微博、微信朋友圈上传的图片等，这靠人工审核是完全不可能做到的。

又比如推荐算法，若在淘宝上买东西，就总能看到向我们推荐的相关商品，这是如何推荐和排序的？这就是算法的作用。淘宝的商品那么多，如何能够达到秒级推荐？当然，没有一个良好的算法设计是不可能做到的。

12.3 其他算法

12.3.1 基数估计算法

给定一个数据集，求解数据集的基数（Cardinality，也译作“势”，表示一个数据集中不同数据项的数量）是非常普遍的需求。许多业务需求最终可以归结为基数求解，例如网站访问分析中的UV（访客数，指在一段时间内访问网站的不同用户的数量）。由于数据集基数是不可聚集指标（两个数据集的总基数无法通过各自的基数进行简单计算），因此如果要得到N个数据集任意组合的基数，则需要2N次数据集的重计算，这是一个复杂度非常高的计算过程。当数据量较小时，可以采取bitmap“按位或”方法获得较高的计算速度；而当数据量很大时，一般会采取概率算法对基数进行估计。

假如我们有一个巨大的含有重复数据项的数据集，无法将其全部放到内存中进行处理，若想知道其中有多少不同的元素，由于数据集没有排好序，则对如此大的一个数据集进行排序和计数几乎是不可行的，这时该怎么办呢？

这就是一个典型的应用了，当然，这一切没有那么简单。

我们发现，在很多商业应用中，在某些情况下是允许我们对大量数据集的计算结果有偏差或者错误的，但错误的范围是多少，性能好多少，是验证这个算法好坏的标准。

12.3.2 蚁群算法

每个蚂蚁会在没有事先告诉它们食物在什么地方的前提下开始寻找食物。当一只蚂蚁找到食物后，它会向环境释放一种挥发性分泌物pheromone（叫作信息素，该物质随着时间的推移会逐渐挥发、消失，信息素浓度的大小表征路径的远近），吸引其他蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其他蚂蚁一样总重复同样的路，它们会另辟蹊径，如果另开辟的道路比原来的道路更短，那么渐渐地，更多的蚂蚁会被吸引到这条较短的路上来。最后，经过一段时间的运行，可能会出现一条最短的路径被大多数蚂蚁使用。

这就是蚁群算法（Ant Colony Optimization，ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的几率型算法。

淘宝也有一个类似的算法，它将人们进行了兴趣分类，认为某类人有着相同的兴趣，把各类有相同兴趣的人喜欢的东西集合（这个分类一定是非常细致的），这样就可以方便地为人们推荐更好的商品了。