携程笔试 08.30 AC
笔试有点简单啊，和美团第一次笔试一样
#校招##笔试##携程##23届秋招笔面经#
恶心，至今没面试
第二题
题目：
y，o，u 三个字母各有 a-b-c 个数，拼接成 you，加2分；每两个连续o，加一分。问最多可以多少分
解答：
ret = min(y. o. u) o = o - ret if o > 0: ret=ret+o-1
第三题
题目：
有一个无环图/树，每个节点可能是R或G或B。选择一条边将其删除，得到两个图，每个图都包含RGB节点。问能有几种删除方法。
解答：
有没有更好的方法呢！因为这个算是压着时间线过去的。
随机选择一个节点作为根结点（做的时候犯傻了，没必要选度为1的节点）
getColor 获得整个图 & 每个子树的RGB个数，即cnt。
checkDelete 查看每个边能否删除。
第四题
题目：
长度n的数组。可以选择数组中的某一个位置更新为任意值（也可以不更新），来获得最小的 max(abs(a[1]-a[0]), abs(a[2]-a[1]), .....)。
打印最小的值。
before： 1 10000 10 after: 1 5 10 结果：max(4, 5) = 5
解答：
比较繁琐的方法：
修改的位置有3种情况，0索引、n-1索引、其余索引。
对于其余索引 i 来说，value = 左侧sub的最大值，右侧sub的最大值，中间 arr[i-1], arr[i+1] 两者差值的一半。
左侧数组数组差值的最大值使用最大值栈来存储，右侧在遍历过程中更新rightMax就可以了。
另一种非常简单的方法是：
维护最大和第二大差值，以及他们所在的索引，然后进行处理，具体代码略。
// 比较麻烦的办法
public static void main4(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long arr[] = new long[n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextLong();
}
long sub[] = new long[n-1];
for(int i = 0; i < n-1; i++) {
sub[i] = Math.abs(arr[i] - arr[i+1]);
}
if(n == 2){
System.out.println(0);
return;
}
// 最大栈
Stack<Long> s = new Stack<>();
s.add(0L);
for(int i = 0; i < n-1; i++) {
s.add(Math.max(s.peek(), sub[i]));
}
// n-1 状态
long rightMax = 0;
s.pop();
long ret = s.peek();
// n-2 状态
for(int i = n-2; i >= 1; i--) {
s.pop();
// s.peek() 左侧的最大值
// rightMax 右侧最大值
// 剩余中间的
ret = Math.min(ret, Math.max(
Math.max(s.peek(), rightMax),
(int)(Math.abs(arr[i+1]-arr[i-1]) + 1)/2));
rightMax = Math.max(rightMax, sub[i]);
}
// 0 状态
ret = Math.min(ret, rightMax);
System.out.println(ret);
} 
投递美团等公司10个岗位 >
阿里巴巴一面146人在聊