拼多多9.26Java笔试

第一题，识别数字

解析：找规律，从0到9规律明显，其中0和8要单独对比一下。（AC）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] apl = {"4444444","2322224","4622226","4424244","2344722","2625244","4225444","6622222","4444444","4445224"};
        int T =in.nextInt();
        for(int i=0;i<T;i++){
            int N = in.nextInt();
            boolean[][] arr = new boolean[N][N];
            int[] one_sum = new int[N];
            for(int ai=0;ai<N;ai++){
                int one_tmp = 0;
                for(int aj=0;aj<N;aj++){
                    int tmp = in.nextInt();
                    if(tmp==1){
                        arr[ai][aj] = true;
                        one_tmp++;
                    }else{
                        arr[ai][aj] = false;
                    }
                }
                one_sum[ai] = one_tmp;
            }
            int bei = N/10;
            StringBuffer sb = new StringBuffer();
            for(int ai=bei;ai<N-2*bei;ai+=bei){
                sb.append(one_sum[ai]/bei);
            }
            for(int sn=0;sn<10;sn++){
                if(isequal(sb.toString(),apl[sn])){
                    if(sn==0||sn==8){
                        if(arr[N/2-1][N/2]==true){
                            System.out.println(8);
                            break;
                        }else{
                            System.out.println(0);
                            break;
                        }
                    }else{
                        System.out.println(sn);
                        break;
                    }
                }
            }
        }

    }
    public static boolean isequal(String s, String t){
        for(int i=0;i<s.length()-1;i++){
            if((s.charAt(i+1)-s.charAt(i))!=(t.charAt(i+1)-t.charAt(i))){
                return false;
            }
        }
        return true;
    }
}

测试用例：

10
10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

第二题迷宫问题

解析：利用队列存储每步可达的位置，用pre记录好路径，获取所有结果后进行比较（85%通过，其他超限）

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            Node start = null;
            List<Node> end = new ArrayList<>();
            int[][] maze = new int[n][m];
            for(int ni=0;ni<n;ni++){
                String str = in.next();
                for(int mi=0;mi<str.length();mi++){
                    if(str.charAt(mi)=='0'){
                        maze[ni][mi] = 0;
                    }else if(str.charAt(mi)=='X'){
                        maze[ni][mi] = 0;
                        end.add(new Node(ni, mi, null));
                    }else if(str.charAt(mi)=='T'){
                        maze[ni][mi] = 0;
                        start = new Node(ni, mi, null);
                    }else if(str.charAt(mi)=='1'){
                        maze[ni][mi] = 1;
                    }
                }
            }
            Queue<Node> queue=new LinkedList<Node>();
            queue.add(start);
            Boolean isFound = false;
            List<Node> res = new ArrayList<>();
            while (!queue.isEmpty()){
                Node node=queue.poll();
                Node temp;
                do {
                    temp=find(node, maze);
                    if (temp!=null){
                        queue.add(temp);
                    }
                }while (temp!=null);
                for(Node nod:end){
                    if(nod.exist(node)){
                        isFound = true;
                        res.add(node);
                    }
                }
            }
            if(isFound){
                List<Node> real = new ArrayList<>();
                int step = Integer.MAX_VALUE;
                for(Node noe:res){
                    int tmp = print(noe);
                    if(step>tmp){
                        step = tmp;
                        real.clear();
                        real.add(noe);
                    }else if(step==tmp){
                        real.add(noe);
                    }
                }
                System.out.println(step-1);
                for(Node noe:real){
                    System.out.print(noe.x+" "+noe.y+" ");
                }
            }else{
                System.out.println("0");
            }
        in.close();
    }

    private static int print(Node node) {
        int sum = 1;
        if (node.pre==null){
            return sum;
        }else {
            sum+=print(node.pre);
        }
        return sum;
    }

    private static Node find(Node node, int[][] maze){
        if (node.x+1<maze.length && maze[node.x+1][node.y]==0){
            maze[node.x+1][node.y]=2;
            return new Node(node.x+1, node.y, node);
        }
        if (node.x-1>=0 && maze[node.x-1][node.y]==0){
            maze[node.x-1][node.y]=2;
            return new Node(node.x-1, node.y, node);
        }
        if (node.y+1<maze[0].length && maze[node.x][node.y+1]==0){
            maze[node.x][node.y+1]=2;
            return new Node(node.x, node.y+1, node);
        }
        if (node.y-1>=0 && maze[node.x][node.y-1]==0){
            maze[node.x][node.y-1]=2;
            return new Node(node.x, node.y-1, node);
        }
        return null;
    }

    static class Node{
        int x;
        int y;
        Node pre;

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

        public boolean exist(Node node){
            if(this.x==node.x && this.y==node.y){
                return true;
            }else{
                return false;
            }
        }
    }
}