米哈游 程序综合A卷笔试 8.15 JAVA版

序言

单选10道，一道1分。
多选15道，一道2分。
算法题3道，一道20分。
投的JAVA岗却被转到GO了。选择题全是C语言判断对错，而且都是C特有的语法，完全不会，太难了。最终30min蒙了，留一个半小时做算法，结果50min就把三道算法ak了。我？？？早知道先做算法再慢慢猜选择题了。米忽悠不愧是米忽悠~

1. 插入ab使其等于目标字符串

题目描述

对于一个空字符串，可以在任意位置插入ab，给出是否能在若干次插入后得到一个目标字符串。

解析

逆向思维，能不能对于一个字符串不停消去ab，使其为空？那只要不停替换ab为空不就好了？看最后字符串长度是否为0.

import java.util.Scanner;

public class Main1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t>0){
            String s = scanner.next();
            fun(s);
            t--;
        }
    }

    private static void fun(String s) {
        int l = s.length();
        while(true){
            s = s.replace("ab","");
            if(s.length()==0||s.length()==l)
                break;
            l = s.length();
        }
        if(s.length()==0)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

2. 同频数组

题目描述

若所有的i满足a[i] = a[i-2]，则称这个数组为同频数组。输入一个长度为偶数的数组，求最少操作多少次使其变为同频数组？

解析

将原数组按奇偶拆分成两个数组，分别求奇偶数组出现最高的频率f1和f2，最后n-f1-f2即为最小次数。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main2 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] b = new int[n];
        for(int i=0;i<n;i++)
            b[i] = scanner.nextInt();
        Map<Integer,Integer> map = new HashMap<>();
        Map<Integer,Integer> map2 = new HashMap<>();
        for(int i=0;i<n;i = i+2)
            map.put(b[i],map.getOrDefault(b[i],0)+1);
        for(int i=1;i<n;i = i+2)
            map2.put(b[i],map2.getOrDefault(b[i],0)+1);
        int maxT1 = 0;
        for(int key:map.keySet())
            maxT1 = Math.max(map.get(key),maxT1);
        int maxT2 = 0;
        for(int key:map.keySet())
            maxT2 = Math.max(map.get(key),maxT2);
        System.out.println(n-maxT1-maxT2);
    }
}

3. 排雷

题目描述

一张n×m的地图，起始点为（x1，y1），雷的位置在（x2，y2），雷边上的八个点为排雷点。排雷兵可以上下左右移动，每次移动一格耗时1。地图上也有若干点为路障不能抵达（能抵达的用“.”表示，不能抵达的用“#”表示），当他抵达任意一个排雷点时的最小时间消耗为t，求（x1×x2）、t、（x1×x2）这三个数的异或结果。

解析

标准的bfs模板题，说几个关键点吧。

节点的增生

将原节点上下左右四个节点加入下次的集合中（除了路障）

判断结束：

A. 抵达排雷点结束，则x与x2的绝对值和y与y2的绝对值都得小于1。
B. 集合为空，则无法排雷，输出-1.

优化

用Set保存已经走过的节点作为缓存，若再次走到，直接剪枝。

可能做错的点

输入x1，y1，x2，y2时候为了存进数组所以减去了一，因此计算异或时需要加一将其还原。

import java.util.*;

public class Main {

    static class P{
        int x;
        int y;

        public P(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        while(t>0){
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int x1 = scanner.nextInt()-1;
            int y1 = scanner.nextInt()-1;
            int x2 = scanner.nextInt()-1;
            int y2 = scanner.nextInt()-1;
            char[][] map = new char[n][m];
            for(int i=0;i<n;i++){
                String s = scanner.next();
                for(int j=0;j<m;j++)
                    map[i][j] = s.charAt(j);
            }
            int step = 0;
            List<P> list = new ArrayList<>();
            list.add(new P(x1,y1));
            Set<String> set = new HashSet<>();
            int flag  = 0;
            while(flag==0){
                List<P> list2 = new ArrayList<>();
                if(list.size()==0){
                    flag = 1;
                    continue;
                }
                for(P p:list){
                    //缓存
                    if(set.contains(p.x+","+p.y))
                        continue;
                    set.add(p.x+","+p.y);
                    //检查是否到终点
                    if(reach(p.x,p.y,x2,y2)){
                        flag = 2;
                        break;
                    }
                    //扩展
                    if(p.x+1<n&&map[p.x+1][p.y]=='.')
                        list2.add(new P(p.x+1,p.y));
                    if(p.y+1<m&&map[p.x][p.y+1]=='.')
                        list2.add(new P(p.x,p.y+1));
                    if(p.x-1>=0&&map[p.x-1][p.y]=='.') 
                        list2.add(new P(p.x-1,p.y));
                    if(p.y-1>=0&&map[p.x][p.y-1]=='.')
                        list2.add(new P(p.x,p.y-1));

                }
                list = list2;
                if(flag!=2)
                step++;
            }
            if(flag==1)
                System.out.println(-1);
            else{
                x1++;
                y1++;
                x2++;
                y2++;
                System.out.println(step^(x1*x2)^(y1*y2));
            }
            t--;
        }
    }
    public static boolean reach(int x,int y,int x2,int y2){
        int t1 = Math.abs(x-x2);
        int t2 =  Math.abs(y-y2);
        return t1 <= 1 && t2 <= 1;
    }
}