拼多多提前批笔试题

1 严格升序

题目描述

给定两个数组 A 和 B。其中数组 A 是几乎严格升序排列的，几乎的定义是只需改变其中一个数，即可满足完全升序排列。你的任务是从数组 A 中找到这个数字，并从数组 B 中选取一个数将其替换，使得数组 A 是完全严格升序排列。（严格升序排列，即不允许相邻两个为相同的数）请找出数组 B 中满足要求的最大数字，并输出最终有序的数组。如果不存在就输出 NO。

> 输入描述

共两行，第一行是数组 A，第二行是数组 B，元素之间用空格分隔（数组 A 的长度，数组 B 的长度 < 100)

> 输出描述

共一行，为最终有序的数组。不存在则输出 NO

> 示例 1

输入：

1 3 7 4 10 2 1 5 8 9

输出

1 3 7 9 10

解题说明

先遍历一遍数组 A，找到前一个数比后一个数大的地方。这时有两种替换方法：

替换后一个数（优先）
替换前一个数（1 失败才考虑 2）

如：$A_0, A_1, A_2, …, A_{k-1}, A_k, A_{k+1}, A_{k+2}, …, A_{n-1}$，遍历一遍后，发现$A_k \geq A_{k+1}$ 这时要遍历数组 B：

对于替换 $A_{k+1}$ 的情况，要在 B 中查找最大数字 $x$，满足 $A_k \le x \le A_{k+2}$，需要注意 $A_{k+1}$ 刚好为数组最后一个元素的情况
对于替换 $A_k$ 的情况，要在 B 中查找最大数字 $y$，满足 $A_{k-1} \le y \le A_{k+1}$，需要注意 $A_k$ 刚好为数组第一个元素的情况

找到这两个数，

如果存在 $x$，就替换 $x$，直接打印替换后的数组 A；
否则如果存在 $y$，就替换 $y$，然后打印数组 A；
如果 $x$ 和 $y$ 都不存在，打印 NO

import java.util.Scanner;

public class Main {
    public boolean solve(int[] a, int[] b) {
        if (a.length < 2) {
            return true;
        }

        int i = 0;
        for (; i < a.length - 1; i++) {
            if (a[i] >= a[i + 1]) {
                break;
            }
        }

        if (i == a.length - 1) {
            return true;
        }

        int ret1 = Integer.MIN_VALUE;
        int ret2 = Integer.MIN_VALUE;
        for (int value : b) {
            if (i > 0 && value > a[i - 1] && value < a[i + 1] ||
                    i == 0 && value < a[i + 1]) {
                if (value > ret1) {
                    ret1 = value;
                }
            }

            if (i < a.length - 2 && value > a[i] && value < a[i + 2]
                    || i == a.length - 2 && value > a[i]) {
                if (value > ret2) {
                    ret2 = value;
                }
            }
        }

        if (ret1 == Integer.MIN_VALUE && ret2 == Integer.MIN_VALUE) {
            return false;
        }

        if (ret2 != Integer.MIN_VALUE) {
            a[i + 1] = ret2;
        } else {
            a[i] = ret1;
        }

        return true;
    }

    private static String array2Str(int[] array) {
        if (array == null || array.length == 0) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(array[0]);

        for (int i = 1; i < array.length; i++) {
            sb.append(" ").append(array[i]);
        }

        return sb.toString();
    }

    private static int[] strArray2IntArray(String str) {
        if (str.isEmpty()) {
            return new int[0];
        }

        String[] strs = str.split(" ");

        int[] ret = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            ret[i] = Integer.valueOf(strs[i]);
        }

        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String strA = in.nextLine();
        String strB = in.nextLine();
        int[] arrayA = strArray2IntArray(strA);
        int[] arrayB = strArray2IntArray(strB);

        Main main = new Main();
        if (main.solve(arrayA, arrayB)) {
            System.out.println(array2Str(arrayA));
        } else {
            System.out.println("NO");
        }
    }
}

2 环形字符串数组

题目描述

给定一个字符串数组（字符串长度和数组的长度均大于 1 且小于 1024），所有字符均为大写字母。请问，给定的字符串是否能通过更换数组中元素的顺序，从而首尾相连，形成一个环，环上相邻字符串首位衔接的字符相同。

> 输入描述

一行输入，空格分隔，表示字符串数组

> 输出描述

一行输出，返回 true 或者 false，表示是否可能形成环。

> 示例 1

输入

CAT TIGER RPC

输出

true

解题说明

这是一个欧拉回路的问题（即一笔画问题）

欧拉回路定义： 图 G 中的欧拉回路是包含 G 的每一条边的简单回路
充要条件： 含有至少两个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度为偶数；有向强连通图 G 有欧拉回路，当且仅当每个节点的入度等于出度

输入的每个字符串相当于一条边，字符串的第一个字符和最后一个字符是边的两个顶点。
要判断是否能衔接成环形字符串，首先要判断图是否连通（不存在，直接返回 false），然后再统计每个节点的出度和入度是否相等，如果相等那就存在欧拉回路，否则不存在。

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

public class Main {

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

        int[] graph = new int[26];
        int[] UF = new int[26];
        Arrays.fill(UF, -1);
        int aRoot = -1;
        while (in.hasNext()) {
            String tmp = in.next();
            int head = tmp.charAt(0) - 'A';
            int tail = tmp.charAt(tmp.length() - 1) - 'A';

            // 统计节点出度和入度之差
            graph[head]++;
            graph[tail]--;

            // 并查集
            if (UF[head] == -1) UF[head] = head;
            if (UF[tail] == -1) UF[tail] = tail;

            if (UF[head] == UF[tail]) {
                continue;
            }

            int t = UF[tail];
            int root = UF[head];
            for (int i = 0; i < 26; i++) {
                if (UF[i] == t) {
                    UF[i] = root;
                }
            }
            aRoot = root;   // 记录某个根节点
        }

        // 判断是否连通
        for (int a : UF) {
            if (a != -1 && a != aRoot) {
                System.out.println("false");
                return;
            }
        }

        // 判断所有节点出度是否等于入度
        for (int a : graph) {
            if (a != 0) {
                System.out.println("false");
                return;
            }
        }

        System.out.println("true");
    }
}

3 最短平均等待时间

题目描述

0时刻，某人收到了N个工作，完成每个工作所需的时间为cost[i]，工作的完成存在先后的依赖关系（即某些工作必须在其它工作之前完成）。一个人顺序完成N个工作，问如何安排完成工作的顺序，使得完成工作的平均响应时间最短，输出这样的顺序，在满足平均响应时间最短的情况下，要求字典序最小？（响应时间：从接收到工作到工作完成的时间）

> 输入描述

第一行输入两个数字：n, m。n为任务个数，m为任务依赖个数。第二行输入 n 个数字，表示每个任务的执行时间。最后输入m 行，每行两个数，如 A B，表示任务 B 依赖 A。

> 输出描述

程序执行顺序

> 示例 1

输入

5 6 1 2 1 1 1 1 2 1 3 1 4 2 5 3 5 4 5

输出

1 3 4 2 5

4 搭积木

题目描述

多多鸡宝宝在玩搭积木游戏。有 N 个长方体积木，每个积木的高都是 1，长宽都为 Li，重量为 Wi。现在多多鸡宝宝想要用这些积木搭一个高高的金字塔。他打算金字塔的每一层是由且仅由一块积木组成，同时每一层的积木边长都严格比其下方的积木小。在多次尝试之后，多多鸡宝宝发现每块积木只能承受自身重量的 7 倍。多多鸡宝宝想请你帮他计算一下最高可以搭一个多高的金字塔？数据范围： 1 <= N <= 100 1 <= Li <= 1000 1 <= Wi <= 1000

> 输入描述

第一行包含 1 个正整数 N，表示积木的数量。第二行包含 N 个正整数，第 i 个数表示第 i 个积木的长度 Li。第三行包含 N 个正整数，第 i 个数表示第 i 个积木的重量 Wi。

> 输出描述

输出占一行，仅包含一个整数，表示可以搭出的金字塔的最高高度。

> 示例 1

输入

10 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 10

输出

9