用友8.1笔试有感

用友8.1笔试原题

前言

第一题是图论遍历，但是题目描述的有些模糊。（目前没有ac题解）

第二题是基础的dp，也可以用数学技巧来做，leetcode的题目343的简单改版。

第三题也是动态规划，但是需要进行状态转移的记录。

第四题是回溯，条件比较复杂，需要分析清楚一些才可以写得好，是有一定的难度的。

小友的生产线

小友设计了一条新的生产线，在该条生产线上共有0-n种工序。每种工序之间可能存在上下游关系，如果一种工序没有下游工序，则为终点工序。如果一种工序其所有可能下游工序均可到达终点工序，则称该工序为合规工序。

给你一个有向图，其中有n个节点，表示不同种工序，以及不同工序之间的关系，请计算该条生产线中，所有的合规工序，并按照升序排列。

注意：终点工序无下游工序，默认为合规工序。

输入描述

第一行输入正整数n，表示共有n个工序节点；

接下来n行，每行有j(1<=j<n)个数，表示工序节点i与其余j个工序节点上下游关系。

注意：若工序节点i为终点工序，则j=1，且数值为-1

输出描述

输出一个数组，用来表示所有的合规工序，并按照升序排列

补充说明
● n == graph.length
● 1 <= n <= 104
● 0 <= n[i].length <= n
● -1 <= n[i][j] <= n - 1
● n[i] 按严格递增顺序排列
● 图中可能包含自环

示例 1

输入

5
1 2 3 4
1 2
3 4
0 4
-1

输出

4

说明

只有工序4是终点工序，即为合规工序

示例 2

输入

7
1 2
2 3
5
0
5
-1
-1

输出

2 4 5 6

说明

工序5和6为终点工序，即为合规工序 工序2和4开始的所有下游工序最终都指向终点工序，按照升序排列最终结果为2，4，5，6

**未ac代码 ** 在codefun中并不能ac，只通过了九个用例。

思路未模拟，将每个项目需要的下标都记录下来，继续递归遍历。

public class YongYou {

    private static HashMap<String, Set<String>> map;
    private static HashSet<String> targets;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        map = new HashMap<>();
//        ArrayList<List<String>> nums = new ArrayList<>();
//        终点
        targets = new HashSet<>();
//        in.nextLine();
        for (int i = 0; i < len; i++) {
            String s = in.nextLine();
            if (s.equals("")) s=in.nextLine();
            Set<String> list = Arrays.stream(s.split(" ")).collect(Collectors.toSet());
            if (s.equals("-1")) {
                targets.add(i + "");
            } else {
                map.put(i + "", list);

            }
        }
        long start = System.currentTimeMillis();

        ArrayList<String> res = new ArrayList<>();
        map.forEach((key, list) -> {
//            已经存在了
//            if (dict[Integer.parseInt(key)] != 0) {
//                if ()
//            }
            boolean judge = judge(key, list, new HashSet<>());
            if (judge) {
                res.add(key);
            }
        });
        res.addAll(targets);
        res.sort((o1, o2) -> {
            return Integer.compare(Integer.valueOf(o1), Integer.valueOf(o2));
        });
        long end = System.currentTimeMillis();
//        System.out.println("耗时：" + (end - start));
//        System.out.println(res);
        for (String re : res) {
            System.out.print(re+" ");
        }
//        System.out.println(targets);

    }

    static int[] dict = new int[104];

    private static boolean judge(String key, Set<String> list, Set<String> pass) {
        if (list.size() == 0) {
            dict[Integer.parseInt(key)] = 1;
            return true;
        }
        ;
        if (list.stream().anyMatch(pass::contains)) {
            dict[Integer.parseInt(key)] = 2;
            return false;
        }
        Set<String> next = new HashSet<>();

        for (String s : list) {
            if (dict[Integer.parseInt(s)] == 2) {
                dict[Integer.parseInt(key)] = 2;
                return false;
            }
            if (!targets.contains(s) && dict[Integer.parseInt(s)] != 1) {
//                if (dict[Integer.parseInt(s)]==2){
//                    return false;
//                }else if (dict[s]==1)
//                没有 需要继续递归
                next.addAll(map.get(s));
            }
        }
        pass.addAll(list);
        return judge(key, next, pass);
    }
}

小友策划游戏人物

小友是一个游戏策划，他计划设计一个新人物，该人物的攻击模式较为特殊：他的附加攻击力可以拆分为n份（n>=2），这n份的乘积作为最终伤害值。游戏总监认为该人物过于超模（过于强大），要求对其附加攻击力增加上限限制。

现在给你最终伤害值的上限和该人物的附加攻击力，请判断该人物的实际最终伤害值是否会超出给出的最终伤害值上限。

输入描述

输入两个数值，第一个数值为最终伤害值上限，第二个数值为该人物的附加攻击力。
例如：2920 22
2920为最终伤害值的上限
22为该人物的附加攻击力

输出描述

输入true或者false
true表示超出上限
false表示未超出上限

补充说明

最终伤害值上限不会超过int最大值

示例 1

输入

1 2

输出

false

说明

最终伤害上限1
附加攻击力2
2=1+1
1*1=1
所以未超过上限

示例 2

输入

161 14

输出

true

说明

14=3+3+3+3+2
3*3*3*3*2=162>161
所以超过上限

题解

实际就是 343. 整数拆分 - 力扣（LeetCode）

• 解法1：动态规划

  • class Solution {
        public int integerBreak(int n) {
            int[] dp = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                int curMax = 0;
                for (int j = 1; j < i; j++) {
                    curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
                }
                dp[i] = curMax;
            }
            return dp[n];
        }
    }
    - 解法2 ：数学
    
      - ```java
        class Solution {
            public int integerBreak(int n) {
                if(n <= 3) return n - 1;
                int a = n / 3, b = n % 3;
                if(b == 0) return (int)Math.pow(3, a);
                if(b == 1) return (int)Math.pow(3, a - 1) * 4;
                return (int)Math.pow(3, a) * 2;
            }
        }
        
    

最佳工作任务安排

小友所在的部门在进行一系列复杂的开发项目。为了优化开发流程，部门要求工程师在不同的任务之间切换。每个任务有不同的执行时间，有些任务因为各种原因无法进行（标记为-1）。工程师可以在规定的跳跃范围内从一个任务跳到另一个任务，但每次执行任务需要消耗相应的时间。

你的目标是找到一个从任务列表开头到结尾的执行顺序，使得总执行时间最小。如果存在多个总执行时间相同的顺序，返回按索引值更小优先的顺序。如果无法到达最后一个任务，返回一个空数组。

规则

1.输入一个整数数组 tasks 表示任务执行时间，长度为 n。
2.输入一个整数 maxStep 表示单次切换任务的最大切换长度。
3.你从任务列表的第一个任务开始（tasks[0] 不是 -1）。
4.从任务 i 切换到任务 j，消耗的时间为 tasks[j]。
5.如果你当前位于任务 i，你只能跳到任务 i + k（满足 i + k <= n），其中 k 在范围 [1, maxStep] 内。
6.返回一个整数数组，包含你访问的任务索引顺序，使得总执行时间最小。如果存在多个总执行时间相同的顺序，返回索引值更小的顺序。

排序说明

如果存在多个总执行时间相同的顺序：
假设方案 p1 = [Pa1, Pa2, ..., Pax] 和方案 p2 = [Pb1, Pb2, ..., Pbx]。
如果在两个方案中第一个不同的索引 j 处，Pa[j] 小于 Pb[j]，则选择方案 p1。
如果所有索引都相同，但任务切换次数不同，则选择任务切换次数较少的一个方案。
提示：注意排序规则，如 1-2-3-4-5 和 1-4-5 , 假设两个方案所消耗的时间成本相同, 那么前面的方案更优。

输入描述

整数 N，代表任务 tasks 的长度
长度为 N 的数组 tasks 的各个元素
整数 M，代表每次切换任务的最大跳跃长度

输出描述

输出数组，代表总执行时间最短，并且索引值最小的执行方案

补充说明

1 <= tasks.length <= 1000
-1 <= tasks[i] <= 100
tasks[0] != -1
1 <= maxStep <= 100

示例 1

输入

5
1 2 4 -1 2
2

输出

1 3 5

示例 2

输入

5
1 2 4 -1 2
1

输出

[]

说明

无法到达最后一个任务，输出字符串”[]”

思路与代码（此代码为ac代码）

动态规划+路径回溯。

f[i]表示走到位置i的最小耗时是多少。转移方程为：f[i] = MIN(f[i-k] + task[i] )，迭代更新最小值即可。

这里需要使用fm 数组用于存储从哪个位置跳转到当前的位置。 对于每个位置 i，检查从 i - k 到达位置 i 的花费，并更新 f[i] 和 fm[i]。

最后， 从终点 N-1 开始回溯，使用 fm 数组来找到路径。将路径添加到 res 列表中。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int N = scanner.nextInt();
        int[] task = new int[N];
        for (int i = 0; i < N; i++) {
            task[i] = scanner.nextInt();
        }
        int M = scanner.nextInt();
        
        // 初始化 dp 数组
        final int INF = Integer.MAX_VALUE; // 使用 Integer.MAX_VALUE 代替 inf
        int[] f = new int[N];
        Arrays.fill(f, INF);
        f[0] = 0;
        
        int[] fm = new int[N];
        Arrays.fill(fm, -1);
        
        // 动态规划
        for (int i = 1; i < N; i++) {
            if (task[i] == -1) continue;
            for (int k = 1; k <= M; k++) {
                if (i - k < 0) break;
                if (f[i - k] + task[i] < f[i] && task[i - k] != -1) {
                    f[i] = f[i - k] + task[i];
                    fm[i] = i - k;
                }
            }
        }
        
        // 回溯找到路径
        List<Integer> res = new ArrayList<>();
        int index = N - 1;
        while (true) {
            if (index == 0) {
                res.add(1);
                break;
            }
            res.add(index + 1);
            index = fm[index];
        }
        
        // 输出结果
        Collections.reverse(res); // 反转列表以从起点到终点
        for (int r : res) {
            System.out.print(r + " ");
        }
        
        scanner.close();
    }
}

思考

我看出来的是动态规划，跟打家劫舍和爬楼梯很类似，但是没想出怎么记录路径

题解还带了路径回溯，从此真看出，我是个背书选手了。hhh

大众评分最高的一次旅程

小友是公司的文化大使，为了增加团队的凝聚力并激发大家的工作激情，他决定带着大家一起去旅游。

这次旅程包含了n个景点，编号1 ~ n ，每个景点都有一个大众评分，使用一维数组scores表示，其中scores[i]表示编号为i的(1<=i<=n)景点的大众评分。并且每个景点都有一个海拔高度，用一维数组heights表示，其中heights[j]表示编号为j的(1<=j<=n)景点的海拔高度。

由于员工年龄分布比较均匀，体力有限，这次旅程最多游览m个景点，并且在连续游览最多r个景点之后必须在休息亭休息，休息亭都是和景点在一块的，通过只包含0或1的一维数组rest表示，其中rest[k] = 1表示编号为k的(1<=k<=n)景点建有休息亭，0表示没有建休息亭 。此外，为了追求更高的视野，只有当景点的海拔严格大于之前参观过的所有景点时，你才能游览它。

请帮助小友设计一个最优的旅程线路，使得整个旅程当中能够获得最高的大众评分分数，请给出这个最高大众评分，以及旅游路线和休息方案。

输入描述

第一行输入3个整数n、m和r，含义如题干所述。
第二行输入n个整数组成scores数组，表示每个景点的大众评分。
第三行输入n个整数组成heights数组，表示每个景点的海拔高度。
第四行输入n个整数（0 or 1）组成rest数组，分别表示每个景点是否建有休息亭。

输出描述

第一行一个整数表示旅途获得的最高大众评分。
第二行输出一个二维数组routes表示最优旅游线路，由景点编号组成。
第三行输出一个二维数组stop表示旅途休息方案，其长度和routes数组一样，由0和1组成，其中stop[i] = 1表示景点routes[i]需要休息，0表示不需要休息。

补充说明

1 <= n <  9
0 <= m <=  n
0 <= r <=  n
0 <= scores[i] < 1000
0 <= heights[j] < 1000

注：如果存在多个最优旅游路线，请给出路线中所有景点编号组成的字符串按字典序最小的方案。例如，一共6个景点，编号分别为1 ~ 6，假设其中方案一路线3 -> 5 -> 4 和方案二路线 2 -> 6 -> 1均为最优路线，则方案二景点编号组成的字符串”261”字典序小于方案一”354”，请返回方案二的路线。

同理，休息方案如果存在多个，则取该休息方案中所有0和1组成的字符串按字典序最小的方案。例如，假设stop数组为[0,0]和[0,1]均为最优休息方案，则取[0,0]作为最优休息方案。

示例 1

输入

5 3 2
10 5 12 8 15
2 1 4 3 5
0 1 0 1 0

输出

35
4 3 5
1 0 0

说明

最高评分为35
最优路线为：景点4 -> 景点3 -> 景点5
休息方案为：在景点4休息，景点3和景点5都不休息

示例 2

输入

5 4 2
348 508 112 71 493
32 3 786 970 728
1 1 0 1 0

输出

1461
2 1 5 3
0 1 0 0

说明

最高评分为1461
最优路线为：景点2 -> 景点1 -> 景点5 -> 景点3
休息方案为：在景点2不休息，景点1休息，景点5和景点3都不休息

思路与代码（此代码为ac代码）

回溯。

题目的数据给出了提示，n<=10。那么我们可以使用较为暴力的解法来解决此问题。思路如下：递归地尝试选择每个景点，更新当前的路径和评分。检查是否需要休息亭，并根据需要进行休息，更新最优解和路径。注意，需要 比较两个列表的字典序，确定哪一个是字典序较小的。

Java

import java.util.*;

public class Main {
    private static int n, m, r;
    private static int[] scores, heights, rests;
    private static int ans = 0;
    private static List<Integer> res1 = new ArrayList<>();
    private static List<Integer> res2 = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        r = scanner.nextInt();
        
        scores = new int[n];
        heights = new int[n];
        rests = new int[n];
        
        for (int i = 0; i < n; i++) scores[i] = scanner.nextInt();
        for (int i = 0; i < n; i++) heights[i] = scanner.nextInt();
        for (int i = 0; i < n; i++) rests[i] = scanner.nextInt();
        
        scanner.close();
        
        List<Integer> path = new ArrayList<>();
        List<Integer> restPath = new ArrayList<>();
        Set<Integer> usd = new HashSet<>();
        
        backtrace(0, 0, usd, 0, path, restPath);
        
        System.out.println(ans);
        for (int i : res1) System.out.print((i + 1) + " ");
        System.out.println();
        for (int i : res2) System.out.print(i + " ");
        System.out.println();
    }
    
    private static void backtrace(int j, int cnt, Set<Integer> usd, int score, List<Integer> path, List<Integer> restPath) {
        if (ans < score) {
            ans = score;
            res1 = new ArrayList<>(path);
            res2 = new ArrayList<>(restPath);
        }
        if (ans == score) {
            if (compareLists(res1, path) > 0) {
                res1 = new ArrayList<>(path);
                res2 = new ArrayList<>(restPath);
            } else if (compareLists(res1, path) == 0 && compareLists(res2, restPath) > 0) {
                res2 = new ArrayList<>(restPath);
            }
        }
        
        if (cnt == m) return;
        
        boolean hasToRest = (j == r);
        
        for (int k = 0; k < n; k++) {
            if (usd.contains(k)) continue;
            if (!path.isEmpty() && heights[k] <= heights[path.get(path.size() - 1)]) continue;
            
            path.add(k);
            usd.add(k);
            
            if (!hasToRest) {
                // 还没必要休息
                if (rests[k] == 1) {
                    // 可以休息
                    restPath.add(1);
                    backtrace(0, cnt + 1, usd, score + scores[k], path, restPath);
                    restPath.remove(restPath.size() - 1);
                }
                // 不休息
                restPath.add(0);
                backtrace(j + 1, cnt + 1, usd, score + scores[k], path, restPath);
                restPath.remove(restPath.size() - 1);
            } else {
                // 一定要休息
                if (rests[k] == 1) {
                    restPath.add(1);
                    backtrace(0, cnt + 1, usd, score + scores[k], path, restPath);
                    restPath.remove(restPath.size() - 1);
                }
            }
            
            usd.remove(k);
            path.remove(path.size() - 1);
        }
    }
    
    private static int compareLists(List<Integer> list1, List<Integer> list2) {
        int size1 = list1.size();
        int size2 = list2.size();
        for (int i = 0; i < Math.min(size1, size2); i++) {
            if (!list1.get(i).equals(list2.get(i))) {
                return list1.get(i) - list2.get(i);
            }
        }
        return size1 - size2;
    }
}

我没想到是回溯，这个是我薄弱的一块，真的麻木

感悟

关于笔试方面的总结

公众号评价这场笔试是中等难度，也确实是，中等偏基础。

但是很不幸的是我基础不足。

这几天的算法学习

最近几天都照着灵神的动态规划题单在一步步学习，但我的动态规划还是一团糟。

leetcode总体刷题也才达到了300多而已，实在是不行啊，回忆之前看别人的算法攻略梯子，刷几百道就能在面试中算法差不多了，实际来说，这是有点偏颇的，因为这只是手撕的量，笔试的量真是完完全全的不够。

下一步学习算法的规划

其实基本没什么规划，就是刷刷题单，做做笔试真题，查漏补缺吧

也差不多是东边一块学一点，西边学一点吧

笔试可能不是很看重，但是我都这个学历了，能a多几道题，就多几道题吧。

找工作感悟

最近在boss投递工作真是找麻了，投了几百份简历，但还是连一个面试都没有，我不知道是计算机可悲，还是选择了我的计算机可悲。

首先说一下自己最近的投递吧，人工智能培训班。如下图所示

说实话，这个是实习僧在我投递一个之后给我推荐的，我就一键投递的。想想真是服了，过初筛的岗位，我印象中就两个，一个这个，一个是大数据的岗位，真是狗都不学Java啊。

25届这个时候真的还找这种普通实习吗，我很疑惑。

我真的怀疑这个是卖简历的。但是他后面把我删了，那就算了吧。

我们任然未知她的真实身份。

算是小小吐槽一下吧。

怀念大一的学习时光，没有认识到找工作的残酷，现在知道了，反而丧失了对计算机的兴趣。计算机算是我为数不多感兴趣的东西了，现在有了自己的电脑，写代码，搞软件，弄操作，已经快成为自己的习惯了，计算机是离不开的了。