8.15 【携程旅行】2021校招研发A卷

携程笔试

第一题

题目

铺砖

现在有充足的长度为a和长度为b的两种规格瓷砖。现在从这些瓷砖中任取k块来铺路，按递增的顺序输出所有可能的铺成道路的长度。

例子：

输入a、b、k 1 2 3 输出一个数组 [3,4,5,6]

代码：AC

package ctrip;

import java.util.Scanner;

public class P1 {

    static int[] divingBoard(int a, int b, int k) {
        if (k == 0) return new int[0];
        if (a == b) {
            int[] result =  new int[1];
            result[0] = a*k;
            return result;
        }
        int[] result = new int[k+1];
        if (a > b){
            int t = a;
            a = b;
            b = t;
        }
        for (int i = 0; i <= k; i++) {
            result[i] = a *(k-i) +i*b;
        }

        return result;
    }
}

第二题

题目

在业务系统中，通常会执行多个任务，各个任务之间存在一定的依赖关系，我们称之为任务节点。每一个节点会设计一个最大的超时时间，如果发生超时现象，那么中断该路径的后续操作。

现在需要计算一个流程的最大执行时间。项目执行从HEAD开始。如果节点执行结束后，没有后续需要执行的任务节点，那么以END作为结束。

*提示：如上图所示，执行TaskC最长需要50ms，TaskD最长需要80ms，如果TaskD执行发生了超时，那么TaskC + TaskD最长需要消耗130ms的时间。此题中，不需要考虑超时的场景。每个节点的最大执行时间等于超时时间，仅需要计算各个路径中的超时时间之和即可。 *注意：需要检查输入的合法性，如果输入不合理，节点定义错误等异常场景，输出结果为-1 *注意：无需进行闭环间测

输入描述

输入和题干中的内容一致,系统从HEAD开始，每一个节点用“|”分割，每一个节点的信息用“`”分割，如果存在多个子节点例如ABC，用“,”分割。

例如：

HEAD`0`A,B,C|A`20`END

表示，这是一个开始节点，他执行时间需要0ms，接下来可以同时执行A,B, C三个子任务节点。 A任务节点，最大执行时间需要20ms，没有需要执行的后续节点

输出描述

如图所示，ABC相互之间没有依赖，可以并行执行，但是DE需要等待C执行完成才可以开始执行。最大执行时间应该为： timeout(C) + timeout(E) = 200ms。 timeout(C) + timeout(D) + timeout(F) = 160ms。 timeout(B) = 100ms timeout(A) = 20ms 所以最大值为 200ms样例输入

HEAD`0`A,B,C|A`20`END|B`100`END|C`50`D,E|D`80`F|E`150`END|F`30`END

样例输出

代码：55%

package ctrip;
import java.util.*;
import java.util.stream.Collectors;

class WorkflowNode {
    String nodeId;
    int timeoutMillis;
    List<WorkflowNode> nextNodes;
    boolean initialised;
    boolean loadF = false;

    public static WorkflowNode load(String value) {
        // Create head node;
        Map<String, WorkflowNode> map = new HashMap<>();
        WorkflowNode head = new WorkflowNode("HEAD", 0, null);
        map.put(head.nodeId, head);
        String[] split = value.split("\\|");
        if (split.length == 0) {
            head.loadF = true;
            return head;
        }
        String[] split1 = split[0].split("\\`");
        if (!split1[0].equals("HEAD")){
            head.loadF = true;
            return head;
        }
        for (String nodeValue : value.split("\\|")) {
            String[] properties = nodeValue.split("\\`");
            if (properties.length != 3){
                head.loadF = true;
                return head;
            }
            WorkflowNode node = map.get(properties[0]);
            if (node == null){
                head.loadF = true;
                return head;
            }
            node.timeoutMillis = Integer.parseInt(properties[1]);
            if (node.timeoutMillis < 0){
                head.loadF = true;
                return head;
            }
            node.initialised = true;

            // Check next nodes
            if (properties[2].equals("END")) {
                continue;
            }
            node.nextNodes = Arrays.stream(properties[2].split(","))
                    .map(p -> new WorkflowNode(p, 0, null))
                    .collect(Collectors.toList());

            node.nextNodes.forEach(p -> map.put(p.nodeId, p));

            map.put(node.nodeId, node);
        }

        return head;
    }

    public WorkflowNode(String nodeId, int timeoutMillis, List<WorkflowNode> nextNodes) {
        this.nodeId = nodeId;
        this.timeoutMillis = timeoutMillis;
        this.nextNodes = nextNodes;
    }
}

public class Main {
    public static void main(String args[]) {
        Scanner cin = new Scanner(System.in);
        WorkflowNode head = null;
        while (cin.hasNext())
        {
            head = WorkflowNode.load(cin.next());
        }

        if (head == null ||head.loadF) {
            System.out.println("-1");
            return;
        }
        int height = height(head);
        System.out.println(height);
    }

    private static int height(WorkflowNode node){
        if (node.nextNodes == null){
            return node.timeoutMillis;
        }
        int maxH = 0;
        for (WorkflowNode workflowNode:node.nextNodes) {
            int height = height(workflowNode);
            if (height > maxH) maxH = height;
        }
        return maxH + node.timeoutMillis;
    }
}

#携程##笔试题目#