百度9.3笔试编程题3道

老早投了深圳的Java开发岗，筛完了简历也没面试，现在应该是进到正式批了，今天面试发现自己果然还是很菜啊。三道题没有一道OC的。
19个选择题，选择题也挺有分量的，有好几个算时间空间复杂度的，好几个SQLyuj还有AVL树

第一题，能被90整除的最大数

给你一些数字，不是0就是5，问你能用这些数字凑出的最大可以被90整除的数是多少
我的思路是每9个5凑出的数（555555555）是可以整除9的，那后面再添0就可以了。
如果没有给0，那么必然不能整除，返回-1。
最后是通过了90%，百思不得解。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int zeros = 0;
        int fives = 0;
        for (int i = 0; i < n; i++) {
            if(scanner.nextInt()==5)
                fives ++;
            else
                zeros ++;
        }
        if(zeros == 0) {
            System.out.println(-1);
            return;
        }
        int maxFives = fives - fives%9;
        StringBuilder sb= new StringBuilder();
        for (int i = 0; i < maxFives; i++) {
            sb.append("5");
        }

        for (int i = 0; i < zeros; i++) {
            sb.append("0");
        }
        System.out.println(sb.toString());
    }
}

第二题，优质奶牛

• 有T组测试用例
  • 每组测试用例有n个奶牛，m个条件
    • 满足条件的牛以区间的形式给出。
    • 满足全部条件才是优质奶牛。

思路：

• 刚开始的时候是想用一个长度为n的数组存满足的条件数，数目=m则是优质，然后计数返回，但是提示超时，然后用ArrayList<int[]> 区间的方式处理，还是超时，我估计是代码循环哪里有问题，实在想不出，也没办法了。
  跑不出结果的代码如下：

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = Integer.parseInt(scanner.nextLine());
        StringBuilder ssb= new StringBuilder();
        for (int i = 0; i < T; i++) {
            // 每组测试
            String[] nm = scanner.nextLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            ArrayList<int[]> goodCows = new ArrayList<>();
            goodCows.add(new int[]{0,n-1});
            for (int j = 0; j < m; j++) {
                // 每个特性
                int k = Integer.parseInt(scanner.nextLine());
                ArrayList<int[]> ngc = new ArrayList<>();
                for (int l = 0; l < k; l++) {
                    //每个特性的范围
                    String[] se = scanner.nextLine().split(" ");
                    int start = Integer.parseInt(se[0]);
                    int end =Integer.parseInt(se[1]);
                    for (int[] ints : goodCows) {
                        int rstart = ints[0];
                        int rend = ints[1];
                        int mstart = Math.max(rstart, start);
                        int mend = Math.min(rend, end);
                        if (mstart <= mend)
                            ngc.add(new int[]{mstart, mend});
                    }
                }
                goodCows = ngc;
            }
            int t = 0;
            StringBuilder sb= new StringBuilder();
            for (int[] group : goodCows){
                int s = group[0];
                int e = group[1];
                t += e-s+1;
                for (int j = s; j <= e; j++) {
                    sb.append(j+1).append(" "
                    );
                }
            }
            ssb.append(t).append("\n").append(sb.toString().trim()).append("\n");
        }
        System.out.print(ssb.toString());
    }
}

第三题，走台阶

有n个台阶，每次可以走1~m步，且第i步的长度不能和第i-1、第i-2一样。要恰好走完，问有多少种走法，以10e9+7取模。
应该是在LeetCode见过这题，但是忘记了，暴力搜索pass了40%。

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        go(0,0,n,m);
        System.out.println(count);
    }

    private static int count = 0;
    private static void go(int last1,int last2,int remain,int m){
        if(remain <0)
            return;
        if(remain ==0) {
            count++;
            if(count > 10e9+7)
                count -=10e9+7;
        }
        for (int i = 1; i <= m; i++) {
            if(i == last1 || i == last2)
                continue;
            go(last2,i,remain-i,m);
        }
    }
}