5-jd笔试

30道选择题--略

算法题一

坦克游戏:

输入:a b c d四个输入数字分别代表,坦克数量,碉堡生命值,碉堡一次性可以炸毁的坦克数量,碉堡数量

输出:如果坦克胜利,返回需要几个回合,如果碉堡胜利,返回-1;

以下为一整个回合:

• 上回合:坦克攻击碉堡,如果坦克的数量大于当前碉堡的生命值,则碉堡炸掉,溢出的伤害由下一个碉堡承受
• 下回合:碉堡反击,其反击伤害为c*(剩余碉堡数),如果伤害为10,则摧毁10量坦克

private static void method1() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int tankNum = scanner.nextInt();
            int blood = scanner.nextInt();//生命值
            int count = scanner.nextInt();//一次可以炸毁的坦克数量
            int buildNum = scanner.nextInt();
            boolean vs = true;
            int nextBlood = blood;
            int c=0;
            while (tankNum > 0 && buildNum > 0) {
                if (vs) {
                    c++;
                    if (nextBlood < tankNum) {
                        buildNum-= tankNum / blood;
                        nextBlood -= tankNum % blood;
                    }else if(nextBlood==tankNum){
                        buildNum--;
                    }else{
                        nextBlood-=tankNum;
                    }
                    while (nextBlood<=0){
                        nextBlood+=blood;
                        buildNum--;
                    }
                } else {
                    int kill=count*buildNum;
                    tankNum-=kill;
                }
                vs = !vs;
            }
            if(tankNum==0&&buildNum==0||(tankNum>0)){
                System.out.println(c);
            }else{
                System.out.println(-1);
            }
        }
    }

算法题二

输入:

3 3  地点的个数 边的行数(关系的行数)

1 2 4 表示连接点1和点2的权重为4

1 3 5

2 3 3

输出:联通所有点的至少需要的权重1->2为4,2->3为3,所以权重至少为4;权重不为5因为不仅可以从1到达3,也可以通过2这个权重为3的点到达3

题目背景:压路机需要通过所有的路段1-n,我们需要知道压路机重量至少为多少才不会压垮权重为w的路段

private static void m2() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int points = scanner.nextInt();
            int count=scanner.nextInt();
            Map map=new HashMap<>(points);
            int temp=1;
            while (temp<=points){
                map.put(temp,new Node(temp));
                temp++;
            }
            for (int i = 0; i < count; i++) {
                int d1=scanner.nextInt();
                int d2=scanner.nextInt();
                int weight=scanner.nextInt();
                map.get(d1).add(d2,weight);
                map.get(d2).add(d1,weight);
            }
            int res=Integer.MAX_VALUE;

            for (int i = 1; i <=points ; i++) {
                boolean[] used = new boolean[points + 1];
                used[i]=true;
                int tem=0;
                for (int j = 1; j <= points; j++) {
                    if(used[j])continue;
                    if(map.get(i).map.containsKey(j)){
                        used[j]=true;
                        tem=Math.max(tem,map.get(i).map.get(j));
                    }
                }
                res=Math.min(res,tem);
            }
            System.out.println(res);
        }
    }
class Node{
    int self;
    Map map=new HashMap<>();
    public Node(int self) {
        this.self = self;
    }
    public void add(int id, int weight){
        map.put(id, weight);
    }
}

美团部分笔试题:

给出一组数字,第一个代表数字的数量,剩下的是具体数字,求出加起来最大的是7的倍数的数

比如输入 4 1 6 2 5->输出14

//全局优先队列,用于存储所有的和,并且以大数在上面优先
    static PriorityQueue queue=new PriorityQueue<>((a,b)->{return b-a;});
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//输入流对象
        while (scanner.hasNext()){
            int num=scanner.nextInt();
            int[] arr = new int[num];
            int sum=0;//最后要输出打印的值
            for (int i = 0; i < arr.length; i++) {
                arr[i]=scanner.nextInt();//处理成数组
            }
            Arrays.sort(arr);//数组排序
            int begin=0;
            dfs(begin,arr,sum);
            System.out.println(queue.poll());//取出栈顶的值就可以了
        }

    }

    private static void dfs(int begin, int[] arr, int sum) {

        //添加条件
        if(sum>0&&sum%7==0){
            queue.add(sum);
        }
        //终止条件
        if(begin==arr.length)return;

        //回溯
        for (int i = begin; i < arr.length; i++) {
            if(i>begin&&arr[i]==arr[i-1])continue;//排重
            sum+=arr[i];
            dfs(i+1,arr,sum);
            sum-=arr[i];
        }
    }

寻找中位数,给定一个数组[1,2,3,4,5],求出所有可能的奇数中位数的和1+2+3+4+5+[123]的2+[234]的3+345的4+12345的3;

1和5计算了1次,2和4计算了2次,3计算了3次,总体来说是和当前数在数组中的位置相关,其计算的次数等于min(index,len-1-index)+1