暑期实习3.9笔试记录（蚂蚁，阿里云，拼多多）

蚂蚁

• 第一题 签到题，按着规则一个一个字符来就行

• 第二题 数上节点的曼哈顿距离

首先对连线排序，根据第一个值从小到大排，相同时根据第二个值从小大到排，Hashset记录某节点有没有子树，HashMap记录节点的坐标 然后按序遍历连线，父节点没有子树的话，该节点就是左子树（x-1,y-1)，有的话就是右子树(x+1,y-1)。

• 第三题 求所有i和j组合的 nums[i] / nums[j]

题目范围是 10⁵，逐个遍历O(n²)一定会超时

由于nums[i]的范围是10⁵之内，对于重复的分子会有很多重复的结果。

我们可以枚举每个值作为分母的情况。对于nums[i], 区间 [ k*nums[i] , (k+1)*nums[i] -1] 的值为分子时，结果都是k：

所以我们可以记录下来所有值的频率，并构建前缀和快速查询。

接下来遍历所有分子和倍数，通过前缀和快速求得区间数值的次数，累加后就是答案：

// 遍历所有分母
for (int val = 1; val <= max; val++) {
  if (cnt[val] == 0) continue; //未出现过就 continue
  long sum = 0;
  for (int k = 1; k <=  max / val; k++) { //枚举所有可能的倍数
	int left = k * val;
	int right = Math.min((k + 1) * val - 1, maxA);
	sum += k * preSum[right] - preSum[left - 1]; // 使用前缀和快速获取该区间的数量
  }
  ans += sum * cnt[val]; // 别忘了这样的值一共有cnt[y]个
}

时间复杂度为 O(MlogM) 其中M为元素最大值。

阿里云

太难了！！

• 第一题 求符合标准子排列的长度之和

用的动态规划，维护dp[10],记录之前遍历过的元素中，以 i 为结尾的排列个数。因为题目暗含了数列要从1开始

• 第二题 求好字符串的字串个数：会不了一点，暴力过了25%

• 第三题 求交换数字位置：读懂题目是想求Max ( (ai - aj)*(ci - cj))了，但没想到怎么做，暴力过了20%

拼多多

• 第一题 签到题
• 第二题 按顺序使用的传送门 ：

我用的状态机DP，第一维度是使用过的传送门个数，第二维度的三个状态分别表示：未使用传送的距离，使用传送的最大距离，使用传送的最小距离

状态转移方程：

dp[i][0] = dp[i-1][0] +nums[i]; // 必须连续使用

dp[i][1] = Math.max(dp[i-1][1] +nums[i],-dp[i][0]); // 当前位置使用传送 或 从上一个状态转移

dp[i][2] = Math.min(dp[i-1][2] +nums[i],-dp[i][0]); // 当前位置使用传送 或 从上一个状态转移

• 第三题 读书的最大收获

只想到了反向的方法：首先算出来需要连续读书的次数：n-m

然后使用动态规划，第一维度是已读过的书，第二维度是已连续读书的次数。

dp数组存储了最小收获，最终答案就是 sum - dp[n][n-m];

状态转移方程：

dp[i][j] = Math.min(dp[i-1][j],dp[i-2][j-1]+ (nums[i]+nums[i-1])/2.0 ） //连续读 或 不连续读

• 第四题 计算拥挤指数之和：

本来以为要排序加二分来着，结果连二分都不用

首先根据身高排序，获得它们的座位号 s[i]

声明ArrayList<Integer> [] 存储第 i 行已入座的来宾 (甚至不需要二分查找等)

然后再按入场顺序逐一放入，检查入场的同行中有多少小于自己的来宾，加入ans即可