2020-04-17阿里巴巴实习生笔试题

2020.4.17

阿里巴巴实习生笔试题

1、输入一个数 n，要输出 n个数，这n个数是 1-n 的排列，

要求满足，

对于排列中 i<k<j，有 ai + aj != 2*ak ；

我的思路是：

对一个存有1-n按顺序排好的数组，

每次从首尾拿，

比如n = 4，

数组-》1 2 3 4

从首部拿 1，

数组-》2 3 4

从尾部拿 4

数组-》2 3

从首部拿 2

数组-》3

从尾部拿 3

输出 1 4 2 3。

样例通过0.0%。。。

不解？？？

之后在小伙伴的悉心分析下，原来 i<k<j 中，i，k，j 是不连续的！！！!

2、在一个有 n 个节点的环形图中，有 n 条无向边，

前 n-1 条边的权值为 第 i 个节点到 第 i+1 个节点的距离，

第 n 条边的权值为第 n 个节点到第 1 个节点的距离，

现有 q 个人，每个人都有各自的起点和终点。

很明显，从起点到终点的路径有两条，默认会走距离小的那条。

n 条边每条边有相同的概率会被切断，

问：每个人从起点到站点的距离变大的概率，对每个人输出对应的概率，用最简分数表示。

输入：

第一行：2个数 n 和 q；

第二行：n个数，代表 n 条边的权值；

其余 q 行，每行 2 个数，为 q 个人对应的起点和终点；

输出：

q 行，每行用最简分数表生，如 1/3。

想着用数组 d[i] 记录第 1 个节点按节点编号的顺序走到第 i 个节点的距离，

第 1 个节点到第 n 个节点的直接距离记为 w，

先得到未切割边时起点 u 到 终点 v 的两个距离为

路径1：按节点编号顺序到达终点的距离 L1 = d[v] - d[u]，路径含 (u-v-1) 条边；

路径2：不按节点编号顺序到达终点的距离 L2 = d[n] - d[v] + d[u] + w，路径含 n-(u-v-1) 条边；

比较 L1 和 L2 的大小。

如果 L1 小，则当切断的边包含在路径1时，从起点到终点的距离会变大，那么最终的概率为 (v - u - 1)/n；

同理，如果 L2 小，则当切断的边在路径2中时，从起点到终点的距离会变大，最终的概率为 (n-u+v+1)/n；

以上是我的思路，并未得到证实。

记一次历时一小时的 0 题笔试体验。