阿里云开发者社区--面试算法题详解

一、数组变换

等级：中等
知识点：排序、贪心
给出一个长度为 n 的数组，和一个正整数 d。
你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] - d，这算作一
次操作。
你需要将所有的元素全部变成相等元素，如果有解，请输出最小操作次数，如果
无解请输出 -1。
输入数字 n、数字 d，和一个长度为 n 的数组 a。1 <= n <= 100000，1 <= d
<= 100, 1 <= a[i] <= 100000。
8 　
输出一个数字，表示最小的操作次数，如果无解输出 -1。
示例 1
输入：

5
2
[3,5,7,1,9]

输出：

注意
最优解为全部变为 5，共 1 + 0 + 1 + 2 + 2 = 6 次

数组变换解题思路

首先判断无解的情况，可以发现 a[i]，a[i]+d, a[i]-d 在模 d 情况下的余数不会发生
改变，因此如果原数组中的存在任意两个数字它们对 d 取余结果不同，那么此时无解。
设余数为 r。判断完无解之后，需要求出最小值。
先将数组 a[i] 排序，然后除以 d，得到从 r 变成 a[i] 需要的步数。
枚举元素 a[i]，将所有元素全部变成 a[i] 需要考虑两部分，i 之前和 i 之后 : 对于 i
之前的元素，假设都是 r，那么需要 (i-1)*a[i]，但是因为并不都是 0，所有我们可以
用一个变量 val 存放前 i-1 项的和，然后我们在减去 val 就是前 i-1 个元素真正需要
操作的步数。
对于 i 之后的元素，也是类似的。我们假设 i 之后的所有项和为 val，假设我
们要将它们变为 r，则消耗即为 val，但是我们只需要将其变为 a[i]，因此需要减去
(n-i)*a[i]。
答案后续

二、算法比赛模拟题精解之“Tairitsu and Dynamic Objects”

题目描述
题目等级：容易
知识点：贪心
查看题目：Tairitsu and Dynamic Objects
Hikari 和 Tairitsu 面前有 n 个物品，这些物品编号为 1,2,…,n。
每个物品有两个属性。第 i 个物品的两个属性分别为 ai, bi 。
初始 n 个物品均可被选取。Hikari 与 Tairitsu 会轮流选取当前可选取的物品中
的一个，并把它拿走，这个物品之后不可被选取。第一轮 Hikari 先选取。
设 Hikari 选取的物品编号的集合为 H ，Tairitsu 选取的物品编号的集合为 T 。
所有物品均被选取完之后，Hikari 得分为∑ ai(i ∈ H) ；而 Tairitsu 得分为
∑ bi(i ∈ T) 。
Hikari 和 Tairitsu 都希望自己的得分比对方大，你需要求出双方都使用最优策略
的情况下，双方各会获得多少分。
注意：若对于某个人来说，剩余的物品中有多个对两人分数大小关系影响相同的
物品，那么他会优先选择 bi 最大的那个。
40 　　>　算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
输入一个正整数 n，表示物品个数。
再输入两个数组 a 和 b，分别表示 n 个物品的 A 属性和 n 个物品的 B 属性。（保
证 1<=n<=2*1e5, 0<=ai,bi<=1e9）
输出一行，两个整数分别表示 Hikari 和 Tairitsu 的得分。
示例 1
输入：

5
[1,2,3,4,5]
[5,4,3,2,1]

输出：

[9,6]

Tairitsu and Dynamic Objects解题思路：

根据题意，分析得知，Hikari 和 Tairitsu 每次会优先选择 ai+bi 的值最大的物
品，当物品的 ai+bi 值相等时，选择 bi 大的那个。
因此，可以对物品进行排序，排序有两个依据，优先依据 ai+bi 的值，然后是 bi
的值。降序排好后，Hikari 和 Tairitsu 依次按顺序选择物品，Hikari 先选择，选择好
以后，分别计算 Hikari 和 Tairitsu 的分数即可。

时间复杂度：O(n)
空间复杂度：O(1)

三、变换的密钥

题目等级：中等

知识点：广度优先搜索 /BFS、Floyed 最短路、图
查看题目：变换的密钥
Tom 最开始有一个密钥 s1，s1 是长度为 n 的由小写字母组成的字符串。Jerry
也有一个长度为 n 的由小写字母组成的密钥 s2。
现在有 m 组关系，每组关系由两个数字 [u,v] 构成 (1<=u,v<=26)，表示 26 个
字母表中的第 u 个小写字母可以直接转换为第 v 个小写字母。
假设 u=1，v=2, 那么说明字母 ‘a’ 可以直接转换为字母 ‘b’。现在 Tom 对于 s1
104 　　>　算法笔试模拟题精解之“变换的密钥”
的每个字母使用无数次转换，请判断 s1 能否转换为 s2。
输入内容为四部分，第一部分为 n(1<=n<=100000)，代表字符串的长度。接下
来两部分分别是长度为 n 的 s1,s2。
第四部分为 m（1 <=m <=325），代表关系个数。接下来是 m 组 [u,v] 关系。
如果 s1 能变成 s2, 则输出 YES, 否则输出 NO。
示例 1
输入：

6
"aabbcc"
"cdbcad"
4
[[1,3],[3,1],[1,4],[2,3]]

输出：

"YES"

解题思路一：一般思路

根据题意，只要根据给出的初始关系，计算出对于每个字母可以变成的字母，就
算法笔试模拟题精解之“变换的密钥”　<　　 105
可以直接判断 s1 能不能转化成 s2 了。
例如样例中计算过后
a -> a,c,d
b -> b,c
c -> a,c,d
d -> d

方法一

对于这个结果，可以使用一个 26*26 的二维数组 change 来保存。每一行表示
原始字母，每一列表示可以变换成的字母。1 表示可以变化，0 表示不能变换。
计算过程：

初始化，根据给出的关系填充数组
记得数组对角线要填为 1，表示每个字母可以不进行变换，是自己本身。
计算经过无数次变换后的数组。
对于第三步可以直接进行多次 for 循环，因为数组不大，一般不会超时。

方法二：矩阵快速幂

经过 0-2 次变换后可以达到的字母的结果相当于 changechange，0-3 次对
应的相当于 changechangechange，0-n 次对应的就是 change^n。这是一个矩
阵求幂的过程。
对于求幂操作有可以加快计算的方法，叫做矩阵快速幂。这里用求数的次幂举例。
假设要求 x^13。直接的方法是进行 12 次相乘。
我们可以观察到 13 = 8 + 4 + 1= 2^3 + 2^2 + 1
所以 x^13 = x^8 + x^4 + x= (x⁴⁾2 + (x²⁾2 + 0(x)^2 + x
从右向左，每一项都是前一项的平方。这样原来需要 12 次乘法的操作变成了 3
106 　　>　算法笔试模拟题精解之“变换的密钥”
次惩罚，3 次加法（第二项系数为 0，不用加）。
与求数的次幂类似，矩阵也可以用相同的方法加速计算。对于这道题本身，因为
矩阵中非 0 的结果表示可以进行变换，所以相乘时没有必要算出具体的值，只需要判
断结果是否非 0。
因为只有 26 个字母，所以只需要算到 26 次幂就可以了，也可以计算 32 次幂来
去掉加法的部分。
时间复杂度 O(5262626) 5 是求 32 次幂需要的矩阵乘法次数。262626
是一次乘法需要的时间复杂度。
空间复杂度 O(226*26) 一个二维数组保存当前结果，一个保存相乘后的结果。

四、找出二叉搜索树的第2大的数

概述：
给定一个二叉搜索树，找出其第二大的数。

示例1
比如二叉搜索树如下

那么第二大的值是25

注意
对于二叉搜索树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
（TreeNode的right，left，val这三个成员，分别表示左子节点，右子节点，节点值。）
解题思路
这是一个关于二叉搜索树的知识点。
对于二叉搜索树，若它的左子树不空，则左子树上所有结点的值均小于它的根结
点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
因为题中没有说这是一棵平衡的树，所以某些节点可能只有一棵子树。
对于树中最大的数是很容易找到的，一直选择右子树直到右子树为空就可以了。
对于第 2 大的数，存在两种情况。一种是最大数的节点存在左子树，一种是不存
在左子树。
在这里插入图片描述
第一种情况下。根据二叉搜索树的性质，可以知道 25 的左子树中的所有值都比
算法笔试模拟题精解之“找出二叉搜索树的第 2 大的数”　<　　 137
25 小，也都比 25 的父节点（20）大。所以第二大的数应该出现在 25 的左子树中。
寻找 25 左子树中的最大值即可。
在这里插入图片描述
第二种情况下。第二大的数就是最大数节点（60）的父节点（25）. 因为 25 的父
节点和左子树都比 25 小。而右子树中只有最大数一个值。
对于特殊情况，根节点没有右子树。可以归类到情况 1 中，根节点为最大的树。
如果也没有左子树的话，那就是样例有问题了，因为这样树中只有一个数。
时间复杂度 O(n) 因为树不是平衡的，所以最差的情况下，从根节点开始都只有
右子树，需要完整遍历整棵树。
空间复杂度 O(1) 只需要保存当前遍历到的节点即可。