首页 > 拼多多9.26Java笔试
头像
连续决策
编辑于 2020-09-26 21:29
+ 关注

拼多多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;
            }
        }
    }
}


第三题：受限0-1背包

todo

第四题：近似多重背包问题

todo
拼多多集团-PDD求职资料大礼包领取
真题
历年笔试真题附答案
拼多多2021笔试真题集
拼多多2020校招部分编程题合集
拼多多2019秋招部分编程题合集
全部 >
面经
面试常考问题整理
迟到的多多挂经
拼多多 星越计划
拼多多客户端开发（Android）一面面经
全部 >
内推
员工内推码获取
米哈游内推~内推码：AFX50～
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(5) 回帖
加载中...
话题 回帖
博文推荐

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术（软件）/信息技术类
美团 792 华为 561 OPPO 323 诚迈科技 139 腾讯音乐娱乐集团 130
查看全部

近期精华帖

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”