Home

Awesome

Awesome-Algorithm-Study

从零构建算法核心知识地图，打通你的任督二脉~

<div align="center"> <img src="https://raw.githubusercontent.com/JsonChao/Awesome-Android-Performance/master/screenshots/algorithm_map.png"> </div>

什么是算法面试？

如何准备算法面试？

在学习和实践做题之间，要掌握平衡。

如何回答算法面试问题？

1、注意题目中的条件，例如

2、当没有思路时

3、优化算法

4、预处理信息（排序）

5、在瓶颈处寻找答案：O(nlogn) + O(n^2)、O(n^3)

6、实际编写问题

7、面试答题四件套：

时间复杂度

1、到底什么是大 O？

n 表示数据规模，O(f(n)) 表示运行算法所需要执行的指令数，和 f(n) 成正比。

2、数据规模的概念——如果想在1s之内解决问题

3、空间复杂度

4、简单的时间复杂度分析

为什么要用大O，叫做大O(n)？

忽略了常数，实际时间 T = c1 * n + c2。

为甚不加上其中每一个常数项，而是要忽略它？

比如说把一个数组中的元素取出来这个操作，很有可能不同的语音基于不同的实现，它实际运行的时间是不等的。 就算转换成机器码，它对应的那个机器码的指令数也有可能是不同的。就算指令数是相同的，同样一个指令在 CPU 的底层，你使用的 CPU 不同，很有可能执行的操作也是不同的。所以，在实际上我们大概能说出来这个 c1 是多少，但是很难准确判断其具体的值。

大O的表示的是渐进时间复杂度，当 n 趋近于无穷大的时候，其算法谁快谁慢。

5、亲自试验自己算法的时间复杂度

O(log(n)) 与 O(n) 有着本质的差别。

6、递归算法的复杂度分析

7、均摊时间复杂度分析（Amortized Time Analysis）与 避免复杂度的震荡

均摊时间复杂度分析

假设 capacity = n，n + 1 次 addLast/removeLast，触发 resize，总共进行 2n + 1 次基本操作平均来看，每次 addLast/removeLast 操作，进行 2 次基本操作均摊计算，时间复杂度为 O（1）。

复杂度震荡

当反复先后调用 addLast/removeLast 进行操作时，会不断地进行 扩容/缩容，此时时间复杂度为 O（n）出现问题的原因：removeLast 时 resize 过于着急。 解决方案：Lazy （在这里是 Lazy 缩容）等到 size == capacity / 4 时，才将 capacity 减半。

目录

一、排序算法

算法稳定性时间复杂度空间复杂度备注
选择排序×N21
冒泡排序√N21
插入排序√N ~ N21时间复杂度和初始顺序有关
希尔排序×N 的若干倍乘于递增序列的长度1改进版插入排序
快速排序×NlogNlogN
三向切分快速排序×N ~ NlogNlogN适用于有大量重复主键
归并排序√NlogNN
堆排序×NlogN1无法利用局部性原理

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。

Hot Question

二、数组

数组最大的优点：快速查询，动态数组实现：

Hot Question

三、队列

队列的基本应用 - 广度优先遍历

Hot Question

四、栈

栈的应用：

Hot Question

五、链表

链表，在节点间穿针引线。

为什么链表很重要？

数组和链表的区别？

链表的时间复杂度：

总结：链表不适合去修改，且只适合 增、删、查 链表头的元素，此时时间复杂度为 O(1)。

Hot Question

六、哈希表

什么是哈希函数？

哈希函数：将 "键" 转换为 "索引"，每一个 "键" 对应唯一的一个索引。

哈希函数的设计

通用的方法——转换为整形处理：

1、小范围正整数直接使用。

2、小范围负整数进行偏移。（-100100 => 0200）

3、大整数：通常做法——取模，例如对身份证号取模后6位，即取最后6位， 因为倒数第5、6位是表示1~31，所以会导致分布不均匀的情况。 一个简单的解决办法就是模一个素数，例如7. 素数取值表：http://planetmath.org/goodhashtableprimes

4、浮点型：在计算机中都是32位或64位的二进制表示，只不过计算机解析成了浮点数。我们可以直接将二进制转换为整形来处理。

5、字符串：

166 = 1 * 10^2 + 6 * 10^1 + 6 * 10^0
code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0
code = c * B^3 + o * B^2 + d * B^1 + e * B^0
hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M(素数）
降低计算量：
hash(code) = ((((c * B) + o) * B + d) * B) + e) % M
避免整形溢出：
hash(code) = ((((c % M） * B + o) % M * B + d) % M * B + e) % M
代码形式：
int hash = 0;
for(int i = 0;i < s.length();i++) {
    hash = (hash * B + s.charAt(i)) % M;
}

6、复合类型：也是利用字符串的上述公式，例如 Date：year、month、day。

hash(code) = (((date.year % M) * B + date.month) % M * B + date.day) % M

设计原则：

Java 中 Object 的 hashCode 是根据每一个对象的地址映射成整形。

哈希冲突的处理

1、链地址法（Separate Chaining）：

算法复杂度分析：

总共有 M 个地址，如果放入哈希表的元素为 N。

为了实现均摊复杂度 O(1)，需要对哈希表进行动态空间处理，即

更复杂的动态空间处理方法

扩容 M -> 2 * M => 不是素数

解决方案：使用素数取值表中的值：http://planetmath.org/goodhashtableprimes

哈希表相比 AVL、红黑树 而言，牺牲了顺序性，换来了更好的性能。

集合、映射：

更多的哈希冲突处理方法：

1、开发地址法（线性探测法）：对于开放地址法来说，每一个地址就是直接存元素， 即每一个地址都对所有的元素是开放的。如果有冲突，直接存到当前索引的下一个索引对应的位置， 如果位置还被占用，继续往下寻找即可。 (平方探测法)： +1、+4、+9、+16。 (二次哈希法)：使用另外一个 hash 算法来计算出下一个位置要去哪儿，hash2(key)。 负载率（LoaderFactory）：元素占总容量比，超过它就需要进行扩容， 一般选取为50%，选取合适时间复杂度可以到达 O(1)。

2、再哈希法（Rehashing）：使用另外一个 hash 算法来计算出下一个位置要去哪儿。

3、Coalesced Hashing：综合了 Separate Chaining 和 Open Addressing。

两类查找问题：

常见操作：

Hot Question

七、（二分搜索）树

树结构本身是一种天然的的组织结构，用树存储数据能更加高效地搜索。

二叉树：和链表一样，动态数据结构。二叉树天然的递归结构，空也是一颗二叉树。

注意：一个节点也是二叉树、空也是二叉树。

满二叉树：除了叶子节点外，每个节点都有两个子节点。

二分搜索树：

什么是遍历操作？

如何对二叉树进行遍历？

对于遍历操作，两颗子树都要顾及。

心算出二叉搜索树的前中后序遍历：每一个二叉树都会被访问三次，从根节点出发，

前序遍历的非递归实现（深度优先遍历）：需要使用栈记录下一步被访问的元素。

对于二叉搜索树的非递归实现一般有两种写法：

层序遍历（广度优先遍历）：需要使用队列记录当前出队元素的左右子节点。

广度优先遍历的意义：

从二分搜索树中删除最小值与最大值：往左走的最后一个节点即是存有最小值的节点，往右走的最后一个节点即是存有最大值的节点。

删除二分搜索树种的任意元素：

1、找到 s = min(d->right), s 是 d 的后继(successor)节点，也即 d 的右子树中的最小节点。 s->right = delMin(d->right), s->left = d->left, 删除 d，s 是新的子树的根。

2、找到 p = max(d->left), p 是 d 的前驱(predecessor)节点。

如何高效实现 rank（E 是排名第几的元素）？ 如何高效实现 select（查找排名第10的元素）？

最好的方式是实现一个维护 size 的二分搜索树：给 Node 节点添加新的成员变量 size。

Hot Question

八、映射

映射 Map

非常容易使用链表或者二分搜索树来实现。

                            LinkedListMap  BSTMap       平均      最差

add、remove、set、get、contains O(n) O(h) O(logn) O(n)

Hot Question

九、堆、优先队列

应用场景：操作系统的任务调度，动态 选择优先级最高的任务进行处理。医生和患者之间的关系。

优先队列底层实现入队出队
普通线性结构O(1)O(n)
顺序线性结构O(n)O(n)
 堆       |    O(logn)   |  O(logn) |

堆的基本结构

二叉堆：满足特殊性质的二叉树。

用数组存储二叉树：

parent = (i - 1) / 2
leftNode = 2 * i + 1
rightNode = 2 * i + 2

Hot Question

十、递归与回溯

递归：本质就是将原来的问题转换为更小的问题。

递归算法通常分为两步：

递归调用是有代价的：函数调用 + 系统栈空间

其它常见的链表类型：

Hot Question

十一、动态规划

什么是动态规划？

斐波那契数列——解决递归中的 重叠子问题 && 最优子结构：通过求子问题的最优解，可以获得原问题的最优解：

动态规划将是将原问题拆解成若干个子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

Hot Question

十二、贪心算法

贪心算法: 它也存在最小生成树与最短路径中。

Hot Question

十三、其它问题

Bloom Filter 布隆过滤器：

位运算操作：

0s 表示一串 0，1s 表示一串 1。

x ^ 0s = x      x & 0s = 0      x | 0s = x
x ^ 1s = ~x     x & 1s = x      x | 1s = 1s
x ^ x = 0       x & x = x       x | x = x

利用 x ^ 1s = ~x 的特点，可以将一个数的位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。

1^1^2 = 2

利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。

01011011 &
00111100
--------
00011000

利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。

01011011 |
00111100
--------
01111111

位与运算技巧

n&(n-1) 去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。

01011011 &
01011010
--------
01011010

n&(-n) 得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。

10110100 &
01001100
--------
00000100

n-(n&(-n)) 则可以去除 n 的位级表示中最低的那一位 1，和 n&(n-1) 效果一样。

移位运算

>> n 为算术右移，相当于除以 2n，例如 -7 >> 2 = -2。

11111111111111111111111111111001  >> 2
--------
11111111111111111111111111111110

>>> n 为无符号右移，左边会补上 0。例如 -7 >>> 2 = 1073741822。

11111111111111111111111111111001  >>> 2
--------
00111111111111111111111111111111

<< n 为算术左移，相当于乘以 2n。-7 << 2 = -28。

11111111111111111111111111111001  << 2
--------
11111111111111111111111111100100

mask 计算

Java 中的位操作

static int Integer.bitCount();           // 统计 1 的数量
static int Integer.highestOneBit();      // 获得最高位
static String toBinaryString(int i);     // 转换为二进制表示的字符串

Hot Question

知识星球（推荐）

现如今，Android 行业人才已逐渐饱和化，但高级人才依旧很稀缺，我们经常遇到的情况是，100份简历里只有2、3个比较合适的候选人，大部分的人都是疲于业务，没有花时间来好好学习，或是完全不知道学什么来提高自己的技术。对于 Android 开发者来说，尽早建立起一个完整的 Android 知识框架，了解目前大厂高频出现的常考知识点，掌握面试技巧，是一件非常需要重视的事情。

去年，为了进入一线大厂去做更有挑战的事情，拿到更高的薪资，我提前准备了半年的时间，沉淀了一份 「两年磨一剑」 的体系化精品面试题，而后的半年，我都在不断地进行面试，总共面试了二三十家公司，每一场面试完之后，我都将对应的面试题和详细的答案进行了系统化的总结，并更新到了我的面试项目里，现在，在每一个模块之下，我都已经精心整理出了 超高频和高频的常考 知识点。

在我近一年的大厂实战面试复盘中逐渐对原本的内容进行了大幅度的优化，并且新增了很多新的内容。它可以说是一线互联网大厂的面试精华总结，同时后续还会包含如何写简历和面试技巧的内容，能够帮你省时省力地准备面试，大大降低找到一个好工作的难度。

这份面试项目不同于我 Github 上的 Awesome-Android-Interview 面试项目：https://github.com/JsonChao/Awesome-Android-Interview，Awesome-Android-Interview 已经在 2 年前（2020年 10 月停止更新），内容稍显陈旧，里面也有不少点表述不严谨，总体含金量较低。而我今天要分享的这份面试题库，是我在这两年持续总结、细化、沉淀出来的体系化精品面试题，里面很多的核心题答案在面试的压力下，经过了反复的校正与升华，含金量极高。

在分享之前，有一点要注意的是，一定不要将资料泄露出去！细想一下就明白了：

1、如果暴露出去，拿到手的人比你更快掌握，更早进入大厂，拿到高薪，你进大厂的机会就会变小，毕竟现在好公司就那么多，一个萝卜一个坑。

2、两年前我公开分享的简陋版 Awesome-Android-Interview 面试题库现在还在被各个培训机构当做引流资料，加大了现在 Android 内卷。。

所以，这一点一定要切记。

获取方法：扫描下方的二维码。

<div align="center"> <img src="https://user-images.githubusercontent.com/17464480/227223150-0b614156-7cfd-4b85-9f51-ff84c321acf8.png" width=50%> </div>

出身普通的人，如何真正改变命运？

这是我过去七年一直研究的命题。首先，是为自己研究，因为我是从小城镇出来的，通过持续不断地逆袭立足深圳。越是出身普通的人，就越需要有耐心，去进行系统性地全面提升，这方面，我有非常丰富的实践经验和方法论。因此，我开启了 “JsonChao” 的成长社群，希望和你一起完成系统性地蜕变。

星球目前有哪些服务？

超哥的知识星球适合谁？

<div align="center"> <img src="https://user-images.githubusercontent.com/17464480/227224387-dc9c669a-0d9b-4a53-9fd2-e225071cce2f.png" width=50%> </div>

公众号

我的公众号 JsonChao 开通啦，专注于构建一套未来Android开发必备的知识体系。每个工作日为您推送高质量文章，让你每天都能涨知识。如果您想第一时间获取最新文章和最新动态，欢迎扫描关注~

<div align="center"> <img src="https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/7da61f2739d34818be8a51a7afbbbb53~tplv-k3u1fbpfcp-watermark.image?" width=30%> </div>