3-29 百度 笔试 java后台开发，三道题AC答案
做题的时候写的很匆忙，没有优化，大佬们可以指出（PS: 互联网大厂最后一题经常出图论题目，我最近总是遇到）
题目描述大家可以看16楼
第一题：
由于n和n-1一定互质，所以直接返回 n*(n-1) -1
注意用long保存答案，使用int，乘法运算会溢出（python用户可以窃喜）
import java.util.Scanner;
public class Solution1 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
long n=s.nextLong();
System.out.print((n-1)*n-1);
}
} 第二题： 模拟法，每次选取最大的一项的值为max；更新最大项max=max%N; 其余每项加上 max/N；
一直循环到满足题目要求，数组每项都小于N
import java.util.Scanner;
public class Solution2 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
long[] nums=new long[N];
long sum=0;
for (int i = 0; i < N; i++) {
nums[i]=s.nextLong();
}
while(!isValid(nums)){
long max=0;
int index=0;
for (int i = 0; i < nums.length; i++) {
if(max<nums[i]){
max=nums[i];
index=i;
}
}
sum+=max/N;
for (int i = 0; i <N ; i++) {
nums[i]+=max/N;
}
nums[index]=max%N;
}
System.out.println(sum);
}
public static boolean isValid(long[] nums){
boolean res=true;
for(long l:nums){
if(l>=nums.length){
res=false;
}
}
return res;
}
} 第三题： 当做图模型来解题，求图中权值递增的最长路径；根据题意，图中只有N-1条边，且无法从权值大的点走到权值小的点，因此遍历图的时候，并不会出现“往回走”，“死循环”的问题
所以这里可以直接用深度优先遍历
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution3 {
static int max=0;
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int N=s.nextInt();
int[] nums=new int[N+1];
for (int i = 1; i < N+1; i++) {
nums[i]=s.nextInt();
}
List<Integer>[] graph=new ArrayList[N+1];
for(int i=0;i<graph.length;i++){
graph[i]=new ArrayList<>();
}
for (int i = 0; i <N-1 ; i++) {
int l=s.nextInt();
int r=s.nextInt();
graph[l].add(r);
graph[r].add(l);
}
for (int i = 1; i <N ; i++) {
dfs(graph,nums,i,0);
}
System.out.println(max);
}
public static void dfs(List<Integer>[] graph,int[] nums,int now,int len){
len+=1;
max=Math.max(max,len);
List<Integer> nexts=graph[now];
for (int next:nexts ) {
if(nums[next]>nums[now]){
dfs(graph,nums,next,len);
}
}
}
} 找实习/工作不容易，楼主投简历时也很紧张，心态经常起伏，与大家共勉，祝大家都能拿到满意的offer。
腾讯开放平台一面41人在聊
投递百度等公司8个岗位