首页 > 百度9.3笔试编程题3道
头像
PraveZhang
编辑于 2020-09-03 21:48
+ 关注

百度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);
        }
    }
}

全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐