字节笔试题（含答案）

- 日理万妓 2022-10-16 11:25 282阅读 0赞

[个人博客][Link 1]欢迎访问

> 总结不易，如果对你有帮助，请点赞关注支持一下  
> 微信搜索**程序dunk**，关注公众号，获取博主的数据结构与算法的代码笔记

### 目录 ###

*  2019春招研发部分编程题
 *   *  万万没想到之聪明的编辑(AC)
     *   *  思路
         *  代码
     *  万万没想到之抓捕孔连顺(AC)
     *   *  思路
         *  注意
         *  代码
         *   *  方法一
             *  方法二
     *  雀魂启动！(AC)
     *   *  思路
         *  代码
     *  特征提取(AC)
     *   *  思路
         *  代码
     *  毕业旅行问题(TLE，50%)
     *   *  思路
         *  递归
     *  找零(AC)
     *   *  思路
         *  代码
     *  机器人跳跃问题（AC）
     *   *  思路
         *  代码
 *  5.30更新
 *   *  寻找最大的子字符串（AC）
     *   *  代码
     *  象棋（AC）
     *   *  代码
     *  最大快乐值（10%）
     *   *  递归

# 2019春招研发部分编程题 #

> 试题链接：[字节跳动2019春招研发部分编程题汇总][2019]

## 万万没想到之聪明的编辑(AC) ##

我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：

\\1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello

\\2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello

\\3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！

……

万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……

请听题：请实现大锤的自动校对程序

**输出描述:**

N行，每行包括一个被修复后的字符串。

**输入例子1:**

2
    helloo
    wooooooow

**输出例子1:**

woow

### 思路 ###

> 一开始没有想出来，最后拆分问题，将一道题拆为两道题来做，先过滤掉AAA问题，再处理AABBCC问题O(n)

### 代码 ###

import java.util.*;
    
    public class Main { 
    
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            for(int i = 0; i < N; i++) { 
                String str = in.next();
                String res = handler(str);
                System.out.println(res);
            }
        }
    
        //先处理三个的情况，在处理AABBCC的情况
        private static String handler(String str) { 
            StringBuilder builder = new StringBuilder();
            char[] chars = str.toCharArray();
            char pre = ' ';
            int count = 1;
            for(char ch : chars) { 
                if (ch == pre) { 
                    count++;
                    continue;
                } else { 
                    if (count >= 2) { 
                        builder.append(pre);
                        count = 1;
                    }
                    pre = ch;
                    builder.append(ch);
                }
            }
            if (count >= 2)
                builder.append(pre);
            chars = builder.toString().toCharArray();
            builder = new StringBuilder();
            boolean flag = false;
            int n = chars.length;
            for (int i = 0; i < n; i++) { 
                builder.append(chars[i]);
                if (i + 1 < n && chars[i] == chars[i + 1]) { 
                    if (flag) { 
                        flag = false;
                    } else { 
                        flag = true;
                        builder.append(chars[i]);
                    }
                    i++;
                } else { 
                    flag = false;
                }
            }
            return builder.toString();
        }
    
    }

## 万万没想到之抓捕孔连顺(AC) ##

我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议

\\1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。

\\2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。

我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！

……

万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！

请听题：给定N（可选作为埋伏点的建筑物数）、D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。

注意：

\\1. 两个特工不能埋伏在同一地点

\\2. 三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用

**输入描述:**

第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
    
    第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）

**输出描述:**

一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模

**输入例子1:**

4 3
    1 2 3 4

**输出例子1:**

### 思路 ###

> 数学题：只要right - left <= D 那么它能够组成的站位就是right - left - 1加到1（等差数列求和），遍历left，为了优化时间，没有采用遍历，通过二分查找直接找到left + D的最小值

### 注意 ###

> **注意：一定要用long，亲测，使用int 只能过80%**

### 代码 ###

#### 方法一 ####

import java.util.*;
    
    public class Main { 
    
       public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            int D = in.nextInt();
            int[] locations = new int[N];
            for(int i = 0; i < N ; i++) { 
                locations[i] = in.nextInt();
            }
            Arrays.sort(locations);
            long count = 0;
            for (int i = 0; i < N - 2; i++) { 
                int j = binarySearch(locations, locations[i] + D);
                if (j - i < 2) break;
                //System.out.println(locations[i] + " " + j);
                //注意：这里一定要用long，否则结果不正确
                long sum = j - i - 1;
                count += (1 + sum) * sum / 2;
            }
            System.out.println(count %= 99997867);
        }
    
        private static int binarySearch(int[] locations, int t) { 
            int l = 0;
            int r = locations.length;
            int mid;
            while(l < r) { 
                mid = l + r >> 1;
                if(locations[mid] >= t) { 
                    r = mid;
                } else { 
                    l = mid + 1;
                }
            }
            l = l >= locations.length ? locations.length - 1 : l;
            return locations[l] > t ? l - 1 : l;
        }
    
    }

#### 方法二 ####

import java.util.*;
    
    public class Main { 
        private int mod = 99997867;
    
        private void sln() { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt(), D = sc.nextInt();
            long cnt = 0;
            if (N <= 2) { 
                System.out.println(-1);
                return;
            }
            int[] locs = new int[N];
            for (int i = 0; i < N; i++) { 
                locs[i] = sc.nextInt();
            }
            sc.close();
            int left = 0, right = 2;
            while (right < N) { 
                if (locs[right] - locs[left] > D) left++;
                else if (right - left < 2) right++;
                else { 
                    cnt += calC(right - left);
                    right++;
                }
            }
            cnt %= mod;
            System.out.println(cnt);
        }
    
        private long calC(long num) { 
            return num * (num - 1) / 2;
        }
    
    
        public static void main(String[] args) { 
            new Main().sln();
        }
    }

## 雀魂启动！(AC) ##

小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。

于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

1.  总共有36张牌，每张牌是1~9。每个数字4张牌。
2.  你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌

*  14张牌中有2张相同数字的牌，称为雀头。
 *  除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）

例如：

1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌

1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌

1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。

现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。

**输入描述:**

输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。

**输出描述:**

输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0

**输入例子1:**

1 1 1 2 2 2 5 5 5 6 6 6 9

**输出例子1:**

**例子说明1:**

可以组成1,2,6,7的4个刻子和9的雀头

**输入例子2:**

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

**输出例子2:**

4 7

**例子说明2:**

用1做雀头，组123,123,567或456,789的四个顺子

### 思路 ###

> 本题考查的是回溯法，由于数据的规模非常小(n<=9)，所以递归不会很深。
> 
> 思路： 已有13张牌，我们从剩余的牌中依次从1到9选择一张牌作为第14张牌，然后判断是否已经构成胡牌。
> 
> 判断胡牌思路：从1到9中选择一个数字作为雀头，然后判断剩余的数字是否包含4个三张牌

### 代码 ###

import java.util.*;
    
    public class Main { 
    
        private static int[]arr = new int[13];
        private static int[] count;
    
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
    
    
            count = new int[9];
            for (int i = 0; i < arr.length; i++) { 
                arr[i] = scanner.nextInt();
                ++count[arr[i]-1];
            }
    
    
            int winCount = 0;
            // 选择1到9中的一个作为第14张牌，然后判断是否胡牌
            for (int i = 1 ; i <= 9; i++) { 
                if(count[i-1]<4){ 
                    ++count[i-1];
                    if(win()){ 
                        ++winCount;
                        System.out.print(i + " ");
                    }
                    --count[i-1];
                }
            }
            if(winCount==0){ 
                System.out.println(0);
            }
        }
    
        public static boolean win() { 
            // 从1到9 中选择一个作为雀头, 然后判断剩余的牌是否构成4对
            for (int i = 1; i <= 9; i++) { 
                if (count[i - 1] < 2) { 
                    continue;
                }
                count[i - 1] -= 2;
                if (hasTriples(4)) { 
                    count[i - 1] += 2;
                    return true;
                }
                count[i - 1] += 2;
            }
            return false;
        }
    
        public static boolean hasTriples(int n) { 
            if (n == 0) return true;
            // 1到9，每一张牌尝试三张或顺子
            for (int i = 1; i <= 9; i++) { 
                if (count[i - 1] >= 3) { 
                    count[i - 1] -= 3;
                    boolean subHasTriples = hasTriples(n - 1);
                    count[i - 1] += 3;
                    if (subHasTriples) return true;
                }
                if (i <= 7 && count[i - 1] > 0 && count[i] > 0 && count[i + 1] > 0) { 
                    --count[i - 1];
                    --count[i];
                    --count[i + 1];
                    boolean subHasTriples = hasTriples(n - 1);
                    ++count[i - 1];
                    ++count[i];
                    ++count[i + 1];
                    if (subHasTriples) { 
                        return true;
                    }
                }
            }
            return false;
        }
    
    }

## 特征提取(AC) ##

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x\_1=x\_2 and y\_1=y\_2，那么这俩是同一个特征。

因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。

现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。

**输入描述:**

第一行包含一个正整数N，代表测试用例的个数。
    
    每个测试用例的第一行包含一个正整数M，代表视频的帧数。
    
    接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2>
    所有用例的输入特征总数和<100000
    
    N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。
    特征取值均为非负整数。

**输出描述:**

对每一个测试用例，输出特征运动的长度作为一行

**输入例子1:**

1
    8
    2 1 1 2 2
    2 1 1 1 4
    2 1 1 2 2
    2 2 2 1 4
    0
    0
    1 1 1
    1 1 1

**输出例子1:**

### 思路 ###

> 哈希表存储前一个的特征数组，对比当前特征，相同的，数量 + 1，不同的删除前一个哈希表的特征数组，保留当前哈希表

### 代码 ###

import java.util.*;
    
    public class Main { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int maxLen = 1;
            int N = in.nextInt();
            while (N > 0) { 
                int M = in.nextInt();
                Map<int[], Integer> preMap = new HashMap<>();
                while(M > 0) { 
                    int F = in.nextInt();
                    Map<int[], Integer> curMap = new HashMap<>();
                    for(int i = 0; i < F; i++) { 
                        int[] nums = new int[2];
                        nums[0] = in.nextInt();
                        nums[1] = in.nextInt();
                        curMap.put(nums, 1);
                        for(int[] keys : preMap.keySet()) { 
                            if (keys[0] == nums[0] && keys[1] == nums[1]) { 
                                int len = preMap.get(keys) + 1;
                                curMap.put(nums, len);
                                maxLen = maxLen > len ? maxLen : len;
                            }
                        }
                    }
                    preMap = curMap;
                    M--;
                }
                N--;
            }
            System.out.println(maxLen);
        }
    
    }

## 毕业旅行问题(TLE，50%) ##

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

**输入描述:**

城市个数n（1<n≤20，包括北京）
    
    城市间的车票价钱 n行n列的矩阵 m[n][n]

**输出描述:**

最小车费花销 s

**输入例子1:**

4
    0 2 6 5
    2 0 4 4
    6 4 0 2
    5 4 2 0

**输出例子1:**

### 思路 ###

> 最先想到了dfs递归，但是，显而易见，递归超时了，尝试了dp，没推出来，有没有大佬讲解一下

### 递归 ###

import java.util.*;
    
    //DFS
    public class Main { 
    
        public static int minPay = Integer.MAX_VALUE;
        public static int n;
    
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            n = in.nextInt();
            int[][] tickets = new int[n][n];
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++) { 
                for(int j = 0; j < n; j++) { 
                    tickets[i][j] = in.nextInt();
                }
            }
            list.add(0);
            dfs(tickets, 0, list, 0);
            System.out.println(minPay);
        }
    
        private static void dfs(int[][] tickets, int now, List<Integer> list, int pay) { 
            if (list.size() == n) { 
                pay += tickets[now][0];
                minPay = Math.min(minPay, pay);
                return;
            }
            for(int i = 0; i < n; i++) { 
                if(list.contains(i)) continue;
                List<Integer> curList = new ArrayList<>(list);
                if (pay + tickets[now][i] > minPay) return;
                curList.add(i);
                dfs(tickets, i,curList, pay + tickets[now][i]);
            }
        }
    
    }

## 找零(AC) ##

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LFGJxxIY-1622381470834)(https://uploadfiles.nowcoder.com/files/20190308/311069\_1552040949258\_equation?tex=N%20(0%20%3C%20N%20%5Cle%201024)\])的商品，请问最少他会收到多少硬币？

**输入描述:**

一行，包含一个数N。

**输出描述:**

一行，包含一个数，表示最少收到的硬币数。

**输入例子1:**

200

**输出例子1:**

### 思路 ###

> 很明显是完全背包问题
> 
> 但是，不用dp，也能做，尽量拿大的硬币，拿不了的再拿小的

### 代码 ###

import java.util.*;
    
    public class Main { 
    
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            int money = 1024 - N;
            int count = 0;
            int[] coins = { 64, 16, 4, 1};
            for(int coin : coins) { 
                int i = money / coin;
                count += i;
                money -= i * coin;
            }
            System.out.println(count);
        }
    
    }

## 机器人跳跃问题（AC） ##

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。

起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。

游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？

**输入描述:**

第一行输入，表示一共有 N 组数据.
    
    第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度

**输出描述:**

输出一个单独的数表示完成游戏所需的最少单位的初始能量

**输入例子1:**

5
    3 4 3 2 4

**输出例子1:**

**输入例子2:**

3
    4 4 4

**输出例子2:**

**输入例子3:**

3
    1 6 4

**输出例子3:**

### 思路 ###

> 数学题，推导式
> 
> e(k + 1) = e(k) + e(k) - H(k + 1)  
> e(k) = (H(k + 1) + e(k + 1)) / 2

### 代码 ###

import java.util.*;
    
    public class Main{ 
        public static void main(String[] args){ 
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            double[] tower = new double[N];
            for(int i = 0; i < N; i++) { 
                tower[i] = (double)in.nextDouble();
            }
            //e(k + 1) = e(k) + e(k) - H(k + 1)
            //e(k) = (H(k + 1) + e(k + 1)) / 2
            double e = 0;
            for(int i = N - 1; i >= 0; i--) { 
                e = (e + tower[i]) / 2;
            }
            System.out.println((int)Math.ceil(e));
        }
    }

# 5.30更新 #

> 5.30字节Byte Camp-计算机软件工程方向笔试

## 寻找最大的子字符串（AC） ##

1、包含字符串所有字母

2、长度最短，如果有长度相同的，则选择最左边的

输入

abbbccaabc

输出

3,4

> 说明：abb`bcca` 和 c`caab`c两种满足要求，取左边的

### 代码 ###

public class Main { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            String s = in.next();
            char[] chars = s.toCharArray();
            Set<Character> set = new HashSet<>();
            for(char ch : chars) { 
                set.add(ch);
            }
            int minSize = Integer.MAX_VALUE;
            Set<Character> subSet = new HashSet<>();
            int minBegin = 0;
            int begin = 0;
            int i = 0;
            while(i < chars.length){ 
                subSet.add(chars[i]);
                if (subSet.size() == set.size()) { 
                    if (i - begin + 1 < minSize) { 
                        minBegin = begin;
                        minSize = i - begin + 1;
                    }
                    begin = begin + 1;
                    subSet = new HashSet<>();
                    i = begin;
                } else { 
                    i++;
                }
            }
            System.out.println(minBegin + "," + minSize);
        }
    }

## 象棋（AC） ##

A、B两个同学下象棋

B：马在一处，将在一处，且不能动。

A：在(0,0)只能向右上走，（先上在右45°或者先右再上45°），问有几种走法吃掉B的将

*  过程中不能被吃
 *  做的路径上不能有阻碍，比如先向上再向右45°，如果B的马在A的马的上方，则A的马不能这样走

输入

2 2 6 3

输出

> 说明 B的马在(2,2)将在(6,3)，A的马只有1中走法可吃掉B的将

### 代码 ###

public class Main { 
        public static int[][] isSafe;
        public static int count = 0;
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int x = in.nextInt();
            int y = in.nextInt();
            int top = in.nextInt();
            int right = in.nextInt();
            int m = top + 1;
            int n = right + 1;
            isSafe = new int[30][30];
            //0表示安全
            //1表示有障碍
            //-1表示危险
            //3代表终点
            isSafe[x][y] = 1;
            if ((x + 2) < m) { 
                if(y + 1 < n) isSafe[x + 2][y + 1] = -1;
                if(y - 1 >= 0) isSafe[x + 2][y - 1] = -1;
            }
            if ((x - 2) >= 0) { 
                if(y + 1 < n) isSafe[x - 2][y + 1] = -1;
                if(y - 1 >= 0) isSafe[x - 2][y - 1] = -1;
            }
            if ((y + 2) < n) { 
                if(x + 1 < m) isSafe[x + 1][y + 2] = -1;
                if(x - 1 >= 0) isSafe[x - 1][y + 2] = -1;
            }
            if ((y - 2) >= 0) { 
                if(x + 1 < m) isSafe[x + 1][y - 2] = -1;
                if(x - 1 >= 0) isSafe[x - 1][y - 2] = -1;
            }
            /*for(int[] res : isSafe) { System.out.println(Arrays.toString(res)); }*/
            dfs(0, 0, top, right);
            System.out.println(count);
        }
    
        private static void dfs(int x, int y, int top, int right) { 
            if(x == top && y == right) { 
                count++;
                return;
            }
            if (x >= top || y >= right) return;
            if (x <= top && y <= right && isSafe[x][y] == -1) return;
            if (isSafe[x + 1][y] != 1)
                dfs(x + 2, y + 1, top, right);
            if (isSafe[x][y + 1] != 1)
                dfs(x + 1, y + 2, top, right);
        }
    }

## 最大快乐值（10%） ##

D、E、F三种服装，每个员工选择不同的服装会有不同的快乐值，不能和自己的直系领导撞衫

输出最大的员工快乐值总和

输入

3
    1 2 9
    3 2 1
    2 1 3
    0  	1
    1   2

输出

> 说明：第一行 输入N代表有N个员工，下面的 2 - N行分别是第i个员工获取D、E、F三件服装的不同快乐值，每位员工除了第0号大领导外，有且只有一个直系领导，第N + 1到第2N行输入A,B表示B的直系领导是A，输出14最大快乐值为14，分别对应，0号员工选F，1号员工选E，2号员工选D的最大情况。

### 递归 ###

public class Main { 
        public static Map<Integer, Integer> map;
        public static int[][] nums;
        public static int maxHappy = Integer.MIN_VALUE;
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            nums = new int[N][3];
            for(int i = 0; i < N; i++) { 
                for(int j = 0 ; j < 3; j++) { 
                    nums[i][j] = in.nextInt();
                }
            }
            map = new HashMap<>();
            for(int i = N + 1; i < N * 2; i++) { 
                int leader = in.nextInt();
                int emp = in.nextInt();
                map.put(emp, leader);
            }
            int[] count = new int[N];
            Arrays.fill(count, -1);
            for(int i = 0; i < 3; i++) { 
                count[0] = i;
                dfs(1, nums[0][i], count);
            }
            System.out.println(maxHappy);
        }
    
        private static void dfs(int index, int happy, int[] count) { 
            if (index == count.length) { 
                System.out.println(Arrays.toString(count) + " " + happy);
                maxHappy = Math.max(maxHappy, happy);
                count[index - 1] = -1;
                return;
            }
            for(int i = 0; i < 3; i++) { 
                count[index] = i;
                int leader = map.getOrDefault(index, -1);
                if (count[0] != i) { 
                    if (leader != -1 && count[leader] != i) { 
                        dfs(index + 1, happy + nums[index][i], count);
                    }
                } else { 
                    dfs(index + 1, happy, count);
                }
            }
        }
    }

> 总结：有点可惜，最后一题花费了大量的时间，不了解牛客的报错形式，提示通过10%，答案错误，自己以为是答案的问题，其实是递归超时了，时间应该放在递归剪枝或者记忆化搜索上，但是自己却把时间全部放在的答案的修正上，尽管最后一个小时没改个啥。

> 后面会不断更新新的试题…

[Link 1]: http://www.dunkcode.cn/
[2019]: https://www.nowcoder.com/test/16516564/summary