#携程笔试# 20220830
四题AC（JAVA版）分享给大家
第一题
坑点在于要求不能有前导零 && 所有数字都要参与排列。最开始以为凑成偶数，自动去掉前导零就得了。。。
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
for(int i = 0; i < q; i++){
int x = sc.nextInt();
if((x & 1) == 0){
System.out.println(x);
continue;
}
if (x < 10){
System.out.println(-1);
continue;
}
String str = String.valueOf(x);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < str.length(); j++){
int num = str.charAt(j) - '0';
if(j + 1 < str.length() && (num & 1) == 0 && str.charAt(j + 1) != '0'){
sb.append(str.substring(j + 1));
sb.append(num);
break;
}else{
sb.append(num);
}
}
if (str.equals(sb.toString())){
System.out.println(-1);
continue;
}
System.out.println(sb);
}
} 第二题
贪心：先计算 you 的个数 * 2，再对剩余的连续 n 个 o，取 n - 1 分。注意对 n < 2 的情况特殊处理。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
sc.nextLine();
for (int i = 0; i < q; i++){
String[] split = sc.nextLine().split(" ");
int a = Integer.parseInt(split[0]), b = Integer.parseInt(split[1]), c = Integer.parseInt(split[2]);
int ans = Math.min(a, Math.min(b, c));
b -= ans;
ans *= 2;
ans += b >= 2 ? b - 1 : 0;
System.out.println(ans);
}
} 建图，认为当前节点及孩子节点的 r g b 个数大于 0 && 除该子树外的其他节点的 r g b 之和也大于0，则满足两个连通块各恰有三种颜色。
dfs
坑点在于题目未指出根节点，所以需双向建图 && 使用 visit 数组记录已访问节点。而树作为连通图，从任意节点开始遍历都可以了。
static int ans = 0;
static int r, g, b;
static boolean[] vis;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
String str = scanner.nextLine();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == 'r') r += 1;
if (c == 'g') g += 1;
if (c == 'b') b += 1;
}
// build tree
ArrayList<Integer>[] nodeMap = new ArrayList[n];
for (int i = 0; i < n; i++) {
nodeMap[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
nodeMap[x].add(y);
nodeMap[y].add(x);
}
vis = new boolean[n];
dfs(str, nodeMap, 0);
System.out.println(ans);
}
public static ChildColorNumber dfs(String str, ArrayList<Integer>[] nodeMap, int node) {
vis[node] = true;
ArrayList<Integer> children = nodeMap[node];
ChildColorNumber colorNumber = new ChildColorNumber();
for (Integer child : children) {
if (vis[child]) continue;
ChildColorNumber ccn = dfs(str, nodeMap, child);
if (ccn.red > 0 && ccn.green > 0 && ccn.blue > 0 && ccn.red < r && ccn.green < g && ccn.blue < b) ans += 1;
colorNumber.red += ccn.red;
colorNumber.green += ccn.green;
colorNumber.blue += ccn.blue;
}
if (str.charAt(node) == 'r') colorNumber.red += 1;
if (str.charAt(node) == 'g') colorNumber.green += 1;
if (str.charAt(node) == 'b') colorNumber.blue += 1;
return colorNumber;
}
}
class ChildColorNumber {
public int red;
public int green;
public int blue;
public ChildColorNumber() {
this.red = 0;
this.blue = 0;
this.green = 0;
}
} 第四题 计算包括当前节点之前的任意两相邻数差的绝对值的最大值、再记录包括当前节点之后的任意两相邻数差的绝对值的最大值。
暴力遍历每一个节点，对其作平滑处理：将该节点改成左右两点平均值后的绝对值最大值。再取三者最大值即为修改当前节点所能得到的平滑值。
最后取最小的平滑值。
算是暴力了。。。
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
int[] pre = new int[n];
int[] suc = new int[n];
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
}
int ans = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
pre[i] = Math.abs(array[i] - array[i - 1]);
if (pre[i] < pre[i - 1]) pre[i] = pre[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
suc[i] = Math.abs(array[i] - array[i + 1]);
if (suc[i] < suc[i + 1]) suc[i] = suc[i + 1];
}
for (int i = 0; i < n; i++){
int pre_val = i > 0 ? pre[i - 1] : 0;
int suc_val = i < n - 1 ? suc[i + 1] : 0;
int mid = (i > 0 && i < n - 1) ? (Math.abs(arr[i - 1] - arr[i + 1]) + 1) / 2 : 0;
mid = Math.max(mid, Math.max(pre_val, suc_val));
ans = Math.min(ans, mid);
}
System.out.println(ans);
} 
谷歌公司福利 178人发布
投递快手等公司10个岗位