2019提前批——拼多多笔试题一(85)二(100)三(100)四(5)

57 阅读 0 评论 38 点赞

我是靠谱客的博主哭泣树叶，最近开发中收集的这篇文章主要介绍2019提前批——拼多多笔试题一(85)二(100)三(100)四(5)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一(85)

给定两个数组A和B。其中数组A是几乎严格升序排列的，几乎的定义是只需改变其
中一个数，即可满足完全升序排列。
你的任务是从数组A中找到这个数字，并从数组B中选取1数将其替换，使得数
组A是完全严格升序排列的严格升序排列，即不允许相邻两个为相同的数>
请找出数组B中满足要求的最大数字，并输出最终有序的数组。如果不存在就输出
输入描述：
共两行，第一行是数组A，第二行是数组3,元素之间用空格分隔
(数组A的长度，数组3的长度< 100)
输出描述：
共一行，为最终有序的数组。不存在则输出NO

入:
1 5 4 9
1 2 3 4 5 6 7 8 9
出:
1 5 8 9

需要考虑的情况

长度为1
长度为2 ，相同或乱序不同。
长度大于等于3

长度大于等于3的有三种情况：

3 3 5 前两个相同，改第一个第二个都行
3 3 4 前两个相同，只能改第一个
2 4 4 末尾两个相同，改第一个第二个都行
3 4 4 末尾两个相同，只能改第二个
4 2 6 改中间

其中12可以合并，34可以合并。
因为遍历数组B，所以情况2改第二个与情况4改第一个，肯定找不到。

import java.util.Arrays;
import java.util.Scanner;


public class Test1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line1 = scanner.nextLine();
        String line2 = scanner.nextLine();
        String[] line1split = line1.split(" ");
        String[] line2split = line2.split(" ");
        int[] arr1 = new int[line1split.length];
        int i = 0;
        for (String s : line1split) {
            arr1[i++] = Integer.valueOf(s);
        }
        int[] arr2 = new int[line2split.length];
        i = 0;
        for (String s : line2split) {
            arr2[i++] = Integer.valueOf(s);
        }
        if (arr1.length == 0 || arr2.length == 0) {
            System.out.println("NO");
            return;
        }
        boolean res = findNumberIndex(arr1, arr2);
        if (res) {
            for (int k = 0; k < arr1.length - 1; k++) {
                System.out.print(arr1[k] + " ");
            }
            System.out.println(arr1[arr1.length - 1]);
        } else {
            System.out.println("NO");
        }

    }

    public static boolean findNumberIndex(int[] arr1, int[] arr2) {
        if (arr1.length >= 3) {
            for (int i = 1; i < arr1.length - 1; i++) {
                if (arr1[i - 1] >= arr1[i] && arr1[i + 1] >= arr1[i]) {
                    int max = Integer.MIN_VALUE;
                    if (arr1[i - 1] == arr1[i]) {
                        // 改后
                        for (int j = 0; j < arr2.length; j++) {
                            if (arr2[j] > arr1[i - 1] && arr2[j] < arr1[i + 1]) {
                                max = Math.max(max, arr2[j]);
                            }
                        }
                        if (max != Integer.MIN_VALUE) {
                            arr1[i] = max;
                            return true;
                        }
                        // 改前
                        for (int j = 0; j < arr2.length; j++) {
                            if (i - 2 >= 0) {
                                if (arr2[j] > arr1[i - 2] && arr2[j] < arr1[i]) {
                                    max = Math.max(max, arr2[j]);
                                }
                            } else {
                                if (arr2[j] < arr1[i]) {
                                    max = Math.max(max, arr2[j]);
                                }
                            }
                        }
                        if (max != Integer.MIN_VALUE) {
                            arr1[i - 1] = max;
                            return true;
                        }
                    } else {
                        // 5 3 7
                        for (int j = 0; j < arr2.length; j++) {
                            if (arr2[j] > arr1[i - 1] && arr2[j] < arr1[i + 1]) {
                                max = Math.max(max, arr2[j]);
                            }
                        }
                    }
                    if (max != Integer.MIN_VALUE) {
                        arr1[i] = max;
                        return true;
                    } else {
                        return false;
                    }
                }
            }
            if (arr1[arr1.length - 2] >= arr1[arr1.length - 1]) {
                int max = Integer.MIN_VALUE;
                for (int j = 0; j < arr2.length; j++) {
                    if (arr2[j] > arr1[arr1.length - 2]) {
                        max = Math.max(max, arr2[j]);
                    }
                }
                if (max != Integer.MIN_VALUE) {
                    arr1[arr1.length - 1] = max;
                    return true;
                } else {
                    return false;
                }
            }
        } else if (arr1.length == 2) {
            if (arr1[0] >= arr1[1]) {
                int max = Integer.MIN_VALUE;
                for (int j = 0; j < arr2.length; j++) {
                    if (arr2[j] < arr1[1]) {
                        max = Math.max(max, arr2[j]);
                    }
                }
                if (max != Integer.MIN_VALUE) {
                    arr1[0] = max;
                    return true;
                } else {
                    return false;
                }
            } else {
                return true;
            }
        }
        return true;
    }
}

二(100)

给定一个字符串数组（字符串长度和数组的长度均大于1且小于1024)，
所有字符均为大写字母。请问，给定的字符串数组是否能通过更换数组中
元素的顺序，从而首尾相连，形成一个环，环上相邻字符串首尾衔接的字
符相同。
输入：
一行输入，空格分隔，表示字符串数组
输出：
是否可以 true or false

示例

1.
CAT TAB BADC
true
2.
CAT TAB
false

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

public class Test2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] lineSplit = line.split(" ");
        Map<Character, Integer> map = new HashMap<>();
        int i = 0;
        for (String s : lineSplit) {
            map.put(s.charAt(0), map.getOrDefault(s.charAt(0), 0) + 1);
            map.put(s.charAt(s.length() - 1), map.getOrDefault(s.charAt(s.length() - 1), 0) + 1);
        }
        boolean res = true;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() % 2 == 1){
                res = false;
            }
        }
        System.out.println(res);
    }
}

三(100)

单线程完成任务，要求平均时长最短，返回时长为完成任务时刻-接收任务时刻。假设，零时，接收全部任务。
任务有依赖关系。
输入：
N M n个任务耗费，m个依赖关系
X X X… N个耗费
X Y Y依赖于X， X需要先完成
输出：
任务完成序列（字典序最小）

示例输入：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Test3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n个节点
        int m = sc.nextInt(); // m个关系
        sc.nextLine();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
            nodes[i].cost = sc.nextInt();
            nodes[i].index = i + 1; // 从1开始
        }
        sc.nextLine();
        // 构建图
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt() - 1;
            int to = sc.nextInt() - 1;
            sc.nextLine();
            nodes[from].nexts.add(nodes[to]);
            nodes[to].rudu++;
        }
        int deleteCount = 0;
        List<Integer> res = new ArrayList<>();
        while (deleteCount < n) {
            boolean isHaveRudu0 = false;
            ArrayList<Node> deleteNodeSet = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                Node node = nodes[i];
                if (node != null) {
                    if (node.rudu == 0) {
                        isHaveRudu0 = true;
                        deleteNodeSet.add(node);
                    }
                }
            }
            deleteNodeSet.sort(new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    int res1 = Integer.compare(o1.cost, o2.cost);
                    if (res1 == 0) {
                        return Integer.compare(o1.index, o2.index);
                    }
                    return res1;
                }
            });
            if (isHaveRudu0) {
                Node node = deleteNodeSet.get(0);
                // 删除
                nodes[node.index - 1] = null;
                res.add(node.index);
                deleteCount++;
                for (Node nn : node.nexts) {
                    nn.rudu--;
                }
            } else {
                return;
            }
        }
        for (int i = 0; i < res.size() - 1; i++) {
            System.out.print(res.get(i) + " ");
        }
        System.out.println(res.get(res.size() - 1));
    }

    static class Node {
        int cost = 0;
        int rudu = 0;
        int index = -1;
        List<Node> nexts = new ArrayList<>();
    }
}

四(5)

多多鸡宝宝在玩搭积木游戏。有N个长方体积木，每个积木的高都是
1，长宽都为Li ,重量为 Wi。
现在多多鸡宝宝想要用这些积木搭一个高高的金字塔。他打算金字塔的每
一层是由且仅由一块积木组成，同时每一层的积木边长都严格比在其下方
的积木小。
在多次尝试之后，多多鸡宝宝发现每块积木只能承受自身重量的7倍重量
一若超过7倍自重，搭建的金字塔会因此变得不稳定。具体来说即：对于
每一块积木，在其上方的积木重量之和必须小于等于其自重的7倍。
多多鸡宝宝想请你帮他计算一下最高可以搭一个多高的金字塔？
数据范围：
1 <= N <= 100
1 <= Li <= 1000
1 <= Wi <= 1000

入:
10
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 10
出:
9

package shen.leetcode.solution.bishi.pinduoduo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Test4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        Jm[] arr = new Jm[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new Jm();
            arr[i].length = sc.nextInt();
            arr[i].index = i;
        }
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            arr[i].weight = sc.nextInt();
        }
        Arrays.sort(arr, (o1, o2) -> Integer.compare(o2.length, o1.length));
        if (arr.length == 0) return;
        System.out.println(putFirst(arr));
    }

    // 放第一个
    public static int putFirst(Jm[] jms) {
        List<Jm> jmList = new ArrayList<>();
        int maxLength = jms[0].length;
        int nextLengthIndex = 0;
        // 选择当前所有边长一样的(最长的)
        for (int i = 0; i < jms.length; i++) {
            if (jms[i].length == maxLength) {
                jmList.add(jms[i]);
                nextLengthIndex = i;
            } else {
                break;
            }
        }
        nextLengthIndex++;
        int maxHeight = 0;
        // 肯定选重的,先排个序
        jmList.sort((o1, o2) -> Integer.compare(o2.weight, o1.weight));
        // 递归求解上面的答案
        maxHeight = Math.max(maxHeight, putJM(jms, nextLengthIndex, jmList.get(0).weight * 7));
        // 返回高度 + 当前板子
        return maxHeight + 1;
    }

    public static int putJM(Jm[] jms, int curLengthIndex, int currentMinWeight) {
        // 如果所有长度都放完了,或者 已经无法承受重量了,返回高度0
        if (curLengthIndex >= jms.length || currentMinWeight <= 0) {
            return 0;
        }
        // 当前准备拿的积木列表
        List<Jm> jmList = new ArrayList<>();
        int curMaxLength = jms[curLengthIndex].length;
        int nextLengthIndex = 0;
        // 选择当前所有边长一样的
        for (int i = curLengthIndex; i < jms.length; i++) {
            if (jms[i].length == curMaxLength) {
                jmList.add(jms[i]);
                nextLengthIndex = i;
            } else {
                break;
            }
        }
        // 跳到下一个积木长度的索引
        nextLengthIndex++;
        int maxHeight = 0;
        // 当前这一层是否可以放
        boolean isCurChaoZhong = true;
        for (Jm jm : jmList) {
            // 不能超重
            if (jm.weight <= currentMinWeight) {
                // 可以放就不超重
                isCurChaoZhong = false;
                // 不超重情况下,计算一下,下一层的承受重量
                currentMinWeight = Math.min(currentMinWeight - jm.weight, jm.weight * 7);
                maxHeight = Math.max(maxHeight, putJM(jms, nextLengthIndex, currentMinWeight));
            }
        }
        // 当前层不超重,结果可以+1,即使maxHeight是0
        if (!isCurChaoZhong) {
            maxHeight++;
        }
        return maxHeight;
    }

    static class Jm {
        int weight;
        int length;
        int index;
    }
}