算是博主参加的第一场笔试吧，有点惨烈，都是神仙打架。算法岗和服务端是一样的四道编程题，考察知识有数组、回溯、拓扑排序和动态规划等，下面依次给出题解，不一定是对的。
https://www.hytheory.com/algorithm/pdd-exam/

几乎严格升序

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

例如A=[1,3,8,7,10]，违反严格升序的数字有两个，可以是8也可以是7，代码的基本思路是从A中找到这两个数组，并且得到替换数字的两个区间，之后再从大到小遍历B，看是否有落在上述两个区间之一的数字。可怜的我就过了65，写这篇post 的时候才看到题目要求最大数字，而我并没有对B排序o(TヘTo)。

public class E1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            String[] aa = in.nextLine().split(" ");
            String[] bb = in.nextLine().split(" ");
            int[] a = new int[aa.length];
            int[] b = new int[bb.length];
            for(int i = 0; i < aa.length; ++i) {
                a[i] = Integer.parseInt(aa[i]);
            }
            for(int i = 0; i < bb.length; ++i) {
                b[i] = Integer.parseInt(bb[i]);
            }
            int cur = 0;
            for(; cur < a.length - 1; ++cur) {
                if(a[cur] >= a[cur+1]) break;
            }
            int left1 = cur == 0 ? Integer.MIN_VALUE : a[cur-1];
            int right1 = a[cur+1];
            int left2 = a[cur];
            int right2 = cur == a.length-2 ? Integer.MAX_VALUE : a[cur+2];

            Arrays.sort(b);
            int i = b.length - 1;
            for(; i >= 0; --i) {
                if(left1 < b[i] && b[i] < right1) {
                    a[cur] = b[i];
                    break;
                } else if(left2 < b[i] && b[i] < right2) {
                    a[cur+1] = b[i];
                    break;
                }
            }
            if(i == -1) {
                System.out.println("NO");
            } else {
                for(i = 0; i < a.length; ++i) {
                    System.out.print(a[i]);
                    if(i != a.length-1) System.out.print(" ");
                }
                System.out.print("\n");
            }
        }
    }
}

首尾相连的一组字符串

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

看到牛客上po了一些回答，记录所有字符串头尾字母的出现次数，如果是全部出现偶数次即可形成环。这种思路其实是有问题的，例如["AA","BB"]，虽然字母A和B均出现偶数次，但是首尾不相等。

题目本质上应该是一个排列问题，可用回溯列出所有排列，判断是否首尾相连。

public class E2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            String[] words = in.nextLine().split(" ");
            if(null == words || words.length < 2) System.out.println("false");
            boolean[] isUsed = new boolean[words.length];
            boolean flag = backtrack(words, new ArrayList<String>(), isUsed);
            if(flag) System.out.println("true");
            else System.out.println("false");
        }
    }

    private static boolean backtrack(String[] words, ArrayList<String> curList, boolean[] isUsed) {
        boolean flag = false;
        if(words.length == curList.size()) {
            String first = curList.get(0);
            String last = curList.get(curList.size()-1);
            return last.charAt(last.length()-1) == first.charAt(0);
        }
        for(int i = 0; i < words.length; ++i) {
            if(isUsed[i]) continue;
            if(curList.size() == 0) {
                curList.add(words[i]);
            } else {
                String prev = curList.get(curList.size()-1);
                if(prev.charAt(prev.length()-1) != words[i].charAt(0)) continue;
                curList.add(words[i]);
            }
            isUsed[i] = true;
            flag = backtrack(words, curList, isUsed);
            isUsed[i] = false;
            curList.remove(curList.size()-1);
            if(flag) break;
        }
        return flag;
    }
}

但是这种方法只过了95，还是没有AC，找不到问题在哪。

多任务的执行顺序

现在一共有N个待执行的任务，每个任务需要Pi的时间完成执行。同时任务之间可能会有一些依赖关系，比如任务1可能依赖任务2和任务3，那么任务1必须等任务2和任务3执行完成后才能开始执行。为了最小化任务的平均返回时长，请安排所有任务的执行顺序。假设在零时刻，所有N个任务已到达系统。

本题应该是考察图的拓扑序，即所有的任务根据依赖关系可以画出一张依赖图，每轮迭代执行一批入度为0的任务，为了满足平均返回时长最小的要求，入度为0的任务再根据任务时长短的优先执行的贪心策略执行，可以使用优先队列实现。

public class E3 {
    static class Task {
        int seq;
        int weight;
        public Task(int n, int w) {
            seq = n;
            weight = w;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            Task[] t = new Task[n+1];
            for(int i = 1; i < n+1; ++i) {
                t[i] = new Task(i, in.nextInt());
            }
            // construct dependency raph
            Map<Integer, List<Integer>> graph = new HashMap<>();
            int[] indegree = new int[n+1];
            for(int i = 0; i < m; ++i) {
                int u = in.nextInt();
                int v = in.nextInt();
                if(graph.containsKey(u)) {
                    graph.get(u).add(v);
                } else {
                    List<Integer> edges = new ArrayList<>();
                    edges.add(v);
                    graph.put(u, edges);
                }
                indegree[v]++;
            }
            //topological sort
            PriorityQueue<Task> queue = new PriorityQueue<>(new Comparator<Task>() {
                @Override
                public int compare(Task o1, Task o2) {
                    return o1.weight-o2.weight;
                }
            });
            for(int i = 1; i < n+1; ++i) {
                if(indegree[i] == 0) queue.offer(t[i]);
            }
            List<Integer> res = new ArrayList<>();
            while(!queue.isEmpty()) {
                Task complete = queue.poll();
                res.add(complete.seq);
                if(graph.containsKey(complete.seq)) {
                    for(int i : graph.get(complete.seq)){
                        if(--indegree[i] == 0) {
                            queue.offer(t[i]);
                        }
                    }
                }
            }
            for(int i = 0; i < n; ++i) {
                System.out.print(res.get(i));
                if(i != n-1) System.out.print(" ");
            }
        }
    }
}

搭积木

有N个长方体积木， 每个积木的高都是1，长宽都为Li，重量为Wi。现在想要用这些积木搭一个高高的金字塔，每一层由且仅由一块积木组成，同时每一层积木的边长都比下方的积木小，每块积木智能承受自身重量的7倍重量，请计算最高可以搭一个多高的金字塔？

这题本质（应该？也许？）是一个LIS，最长递增子序列，大牛来指教。首先对所有的积木排序，对每一个状态来说，找到该状态之前，当前积木可以承受的重量的高度最高的状态。考试时写的代码忘记new Box()了，一直没过（sigh。

更新：经@sxzheng指点，之前的思路是错误的，本题应该以前i个积木能搭成高为h的金字塔的最小重量为状态，那么状态转移方程为dp[i][h]=min(dp[i][h], dp[k][h-1]+b[i].weight)。

public class E4 {
    static class Box {
        int len;
        int weight;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int n = in.nextInt();
            Box[] b = new Box[n+1];
            b[0] = new Box();
            for(int i = 1; i < n+1; ++i) {
                b[i] = new Box();
                b[i].len = in.nextInt();
            }
            for(int i = 1; i < n+1; ++i) {
                b[i].weight = in.nextInt();
            }
            Arrays.sort(b, (b1, b2) -> {return b1.len == b2.len ? b1.weight-b2.weight : b1.len - b2.len;});
            int res = 0;
            int[][] dp = new int[n+1][n+1];
            for(int i = 0; i < n+1; ++i) {
                for(int j = 0; j < n+1; ++j) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
            dp[0][0] = 0;
            for(int i = 1; i < n+1; ++i) {
                for(int k = 0; k < i; ++k) {
                    if(b[k].len < b[i].len) {
                        for(int j = 0; j <= k; ++j) {
                            if(dp[k][j] != Integer.MAX_VALUE && dp[k][j] <= b[i].weight*7) {
                                dp[i][j+1] = Math.min(dp[i][j+1], dp[k][j]+b[i].weight);
                                res = Math.max(res, j+1);
                            }
                        }
                    }
                }
            }
            System.out.println(res);
        }
    }
}