百度校招Java研发工程师笔试卷

001还原数列
老板给度度熊n个数，每一次从a【i】中取出一个最大的数减去n，其他n-1个数加上1，一直重复直到最大的a[ i ]<n,执行次数为k，老板想知道最少要执行多少次操作才能使n个数都小于n？

解题关键思路
不管对哪个数进行操作，操作的先后顺序不影响最后结果，因此不需要考虑最大的数减小到什么时候会变成第二大的数，对每个数都先处理到比n小，一直循环到满足条件为止。
做加减就要想到除和模。

Solution

public class restore {
    public static void main(String args[]){
        Scanner cin = new Scanner(System.in);
        int a = cin.nextInt();
        String nul = cin.nextLine();
        String lin = cin.nextLine();
        ArrayList<Long> arr = new ArrayList<Long>();
        String[] arrLine = lin.split("\\s+");
        for(int i =0; i<arrLine.length; i++){
            arr.add(Long.valueOf(arrLine[i]));
        }
        long k =0;
        Collections.sort(arr);
        while(arr.get(a-1)>=a){
            long tmp = arr.get(a-1)/a; 
            arr.set(a-1, arr.get(a-1)%a);  //对每个数都先处理到比n小
            for(int j=0; j<a-1; j++){
                arr.set(j, arr.get(j)+tmp);
            }
            k = k+tmp;
            Collections.sort(arr);
        }
        System.out.println(k);
    }
}

002最小公倍数与最大公约数
度度熊请你找出两个数a，b，满足1<=a,b<=n且lcm（a,b)-gcd(a,b)尽量大，输出最大的lcm(a,b)-gcd(a,b)
其中lcm（a,b）表示a b 最小公倍数，gcd（a,b）表示最大公约数
输入：
一行一个数字n（2<=n<=10^9）
输出：
一个数表示最大值lcm(a,b)-gcd(a,b)

题目讲解
最小公倍数：比如求45和30的最小公倍数。
45=335
30=235
最小公倍数等于2335=90
最大公约数：比如求45和30的最大公约数。
最大公约数等于35=15
如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。

解题关键思路
如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。

Solution

public class max_lcm_gcd {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long n = cin.nextLong();
        System.out.println(n*(n-1)-1);
    }
}

003树上上升序列

题目讲解
路径长度表示（u…v）中包含多少个顶点，所以maxway开始时为1
解题关键思路
这一题先构建一个邻接表去表示这个图，然后可以想成是对一个图进行深度优先遍历，拿到某个顶点的邻接点，然后再从邻接点出发去访问别的邻接点，在这个过程中去更新路径长度.
Solution

import  java.util.*;
public class uptree {

//        static List<List<Integer>> graph = new ArrayList<>();
        static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        static int max = 0;

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] num = new int[n];
            for (int i = 0; i < n; i++) {
                num[i] = sc.nextInt();
            }
            System.out.println(graph);
            for (int i = 0; i < num.length; i++) {
                graph.add(new ArrayList<>());
            }
          //  System.out.println(graph);
            // 构建图,邻接矩阵
            for (int i = 0; i < n - 1; i++) {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 1;
                graph.get(a).add(b);
                graph.get(b).add(a);
            }
           // System.out.println(graph);
            for (int i = 0; i < num.length - 1; i++) {
                dfs(num, i, 1);//路径长度表示（u...v）中包含多少个顶点，所以maxway开始时为1
            }
            System.out.println(max);
        }
        public static void dfs(int[] num, int start, int wayNum) {
            max = Math.max(max, wayNum);
            for (int i : graph.get(start)) {  //拿到某个顶点i的邻接点
                if (num[i] > num[start]) {  //从这个邻接点出发去访问别的邻接点
                    dfs(num, i, wayNum + 1);
                }
            }
        }
}

希望通过这种记录的方式让我坚持认真的刷题！！！
希望这次打破flag必到的魔咒！！！
希望大家刷的开心！！！