字节跳动2020春招笔试 - 研发岗位（Java、C++、大数据）

Dear 丶 2022-11-27 09:00 145阅读 0赞

### 目录 ###

*  前言
 *  一、万万没想到之聪明的编辑
 *   *  方法：常规方法，主要考察逻辑思维
 *  二、万万没想到之抓捕孔连顺
 *   *  方法：双指针（窗口滑动）
 *  三、雀魂启动！
 *   *  方法：递归（回溯法）
 *  四、特征提取
 *   *  方法：双hashMap

# 前言 #

如果能过字节的笔试，那应该没什么笔试能难倒你了，祝所有秋招的同学offer拿到手软

> 如果你从本文中学习到丝毫知识，那么请您点点**关注、点赞、评论和收藏**  
> 大家好，我是[爱做梦的鱼][Link 1]，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：[爱做梦的鱼https://zihao.blog.csdn.net/][https_zihao.blog.csdn.net]，微信公众号、微信视频号为[【程序猿干货铺】][Link 2]，qq交流群为：[1107710098][]，  
> ![程序猿干货铺][Image 1]

# 一、万万没想到之聪明的编辑 #

时间限制： C/C++ 1秒，其他语言2秒
    空间限制： C/C++ 32M，其他语言64M

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

1.  三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
2.  两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
3.  上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！  
……  
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……

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

**输入描述:**

第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。
    后面跟随N行，每行为一个待校验的字符串。

**输出描述:**

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

**输入例子1:**

2
    helloo
    wooooooow

**输出例子1:**

hello
    woow

## 方法：常规方法，主要考察逻辑思维 ##

**代码**

import java.util.Scanner;
    
    public class First { 
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            for (int i = 0; i < N; i++) { 
                String string = sc.next();
                int pointer = 0;
                StringBuilder ans = new StringBuilder();
                int last = 0;
                while (pointer < string.length()) { 
                    char temp = string.charAt(pointer);
                    int cnt = 0;
                    while (pointer < string.length() && temp == string.charAt(pointer)) {  //求同一个字母相连了几个
                        pointer++;
                        cnt++;
                    }
                    if (cnt > 2) //1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
                        cnt = 2;
                    else if (cnt == 2 && last == 2)   //2.两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
                        cnt = 1;
                    last = cnt;
    // cnt= Math.min(cnt, 2);
                    for (int j = 0; j < cnt; j++)
                        ans.append(temp);
                }
                System.out.println(ans);
            }
            sc.close();
        }
    }

# 二、万万没想到之抓捕孔连顺 #

时间限制：C/C++ 1秒，其他语言2秒
    空间限制：C/C++ 128M，其他语言256M

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

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:**

**例子说明1:**

可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

**输入例子2:**

5 19
    1 10 20 30 50

**输出例子2:**

**例子说明2:**

可选方案 (1, 10, 20)

## 方法：双指针（窗口滑动） ##

**注意**

1.  一看见取模，小心数据大小范围

**代码**

import java.util.Scanner;
    
    public class Second4 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int D = sc.nextInt();
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) { 
                arr[i] = sc.nextInt();
            }
            sc.close();
            // 固定窗口的末尾位置,这样就可以保证窗口移动过程不会出现重复，因为下一次判断至少和上次的末尾位置不一样。
            // 然后从末尾位置的前面选取两个位置，加上末尾正好三个位置
            int start = 0;
            long ans = 0;
            for (int end = 2; end < N; end++) { 
                while (start < end && (arr[end] - arr[start]) > D) { 
                    start++;
                }
                long nums = end - start;
                ans += nums * (nums - 1) / 2 ; //nums个中取两个位置，我们末尾的位置固定了，所以只需要去它前面找两个位置
            }
            System.out.println(ans% 99997867);
        }
    }

# 三、雀魂启动！ #

时间限制：C/C++ 1秒，其他语言2秒
    
    空间限制：C/C++ 32M，其他语言64M

小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。  
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

总共有36张牌，每张牌是1~9。每个数字4张牌。  
你手里有其中的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的四个顺子

**输入例子3:**

1 1 1 2 2 2 3 3 3 5 7 7 9

**输出例子3:**

**例子说明3:**

来任何牌都无法和牌

## 方法：递归（回溯法） ##

本题考查的是回溯法，由于数据的规模非常小(n<=9)，所以递归不会很深。

1.  从最小的数字开始尝试，如果把其当成雀头成员，该数字划掉两个，并看余下的数字能否划空
2.  如果是刻子成员，该数字划掉三个，并查看余下数字能否划空
3.  如果是顺子成员，划掉该值 a ,a+1,a+2，并查看余下数字能否划空

如果上述三种尝试都无法划空数组，说明存在数字无法是 雀头、刻子、顺子的成员， 即无法胡牌。

**代码**

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Third { 
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int[] state = new int[9], helpArr = new int[9];
            ArrayList<Integer> res = new ArrayList<>();
            for (int i = 0; i < 13; i++) { 
                int num = sc.nextInt();
                state[num - 1]++; //构建出state数组表示每一张牌的数量
            }
            for (int i = 0; i < 9; i++) {  //抓取下一张牌，1-9
                if (state[i] < 4) {  //如果抓了一张牌导致某个数字超过4，那么错误
                    int num = i + 1;
                    System.arraycopy(state, 0, helpArr, 0, 9); //复制数组
                    helpArr[i]++;
                    if (canHu(helpArr, 14, false)) res.add(num);
                }
            }
            if (res.isEmpty())
                System.out.println(0);
            else { 
                StringBuilder sbf = new StringBuilder();
                sbf.append(res.get(0));
                for (int i = 1; i < res.size(); i++) { 
                    sbf.append(" ");
                    sbf.append(res.get(i));
                }
                System.out.println(sbf.toString());
            }
        }
    
        /** * 判断是否可以和牌 * @param arr 表示每一张牌的数量的数组，index+1代表牌的小，比如arr[0]存放的是1的个数 * @param total 现在剩下的牌的数量 * @param hasHead 有无雀头 * @return */
        private static boolean canHu(int[] arr, int total, boolean hasHead) { 
            if (total == 0)  // 剩下的牌为0，表明牌可以找到雀头，刻子和顺子（找到了就删掉了，所以数量不断变小）
                return true;
            if (!hasHead) {  // 1. 先判断有无雀头
                for (int i = 0; i < 9; i++) { 
                    if (arr[i] >= 2) { 
                        arr[i] -= 2;
                        if (canHu(arr, total - 2, true)) return true;
                        arr[i] += 2;
                    }
                }
                return false;
            } else { 
                for (int i = 0; i < 9; i++) { 
                    if (arr[i] > 0) {  //找刻子和顺子，先找哪个无所谓
                        if (arr[i] >= 3) {  //刻子：刻子的意思是相同数字的3个数字牌（例如111,777）
                            arr[i] -= 3;
                            if (canHu(arr, total - 3, true)) return true;
                            //和牌失败，得把拿掉的牌加回来
                            arr[i] += 3;
                        }
                        if (i + 2 < 9 && arr[i + 1] > 0 && arr[i + 2] > 0) {  //顺子的意思是递增的连续3个数字牌（例如234,567等）
                            arr[i]--;
                            arr[i + 1]--;
                            arr[i + 2]--;
                            if (canHu(arr, total - 3, true)) return true;
                            //和牌失败，得把拿掉的牌加回来
                            arr[i]++;
                            arr[i + 1]++;
                            arr[i + 2]++;
                        }
                    }
                }
            }
            return false;
        }
    }

# 四、特征提取 #

时间限制：C/C++ 1秒，其他语言2秒
    
    空间限制：C/C++ 32M，其他语言64M

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的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:**

特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3

## 方法：双hashMap ##

import java.util.HashMap;
    import java.util.Scanner;
    
    public class Fourth { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            for (int i = 0; i < N; ++i) { 
                HashMap<String, Integer> map = new HashMap<>();
                HashMap<String, Integer> temp_map = new HashMap<>();
                int M = sc.nextInt();
                int max = 1;
                for (int j = 0; j < M; ++j) { 
                    temp_map.clear();
    // System.out.println(temp_map);
                    int n = sc.nextInt();
                    for (int k = 0; k < n; ++k) { 
                        int x = sc.nextInt();
                        int y = sc.nextInt();
                        String key = x + "-" + y; //如果 x + “ ”+ y那么特征（1，11）和（11，1）无法区分
                        //使用的是map而不是temp_map，这是本算法核心，
                        //如果上一帧中存在一样的特征，那么我们的num在上一次记录的vlue（特征数=帧数，因为每个特征在每个帧就出现一次）基础上加1
                        //如果上一帧中不存在，则我们num为1，也就是从这次帧开始记录这个特征连续出现到几个帧
                        int num = map.getOrDefault(key, 0) + 1;
                        temp_map.put(key, num);
                        max = Math.max(num, max);
    // System.out.println("temp_men: " + temp_map);
                    }
                    map.clear();
                    map.putAll(temp_map);
    // System.out.println("men: " + map);
                }
                if (max <= 1) { 
                    System.out.println(1);
                } else { 
                    System.out.println(max);
                }
    
            }
            sc.close();
    
        }
    }

[Link 1]: https://blog.csdn.net/weixin_43124279
[https_zihao.blog.csdn.net]: https://zihao.blog.csdn.net/
[Link 2]: https://s1.ax1x.com/2020/06/11/tHUSvq.png
[1107710098]: https://s1.ax1x.com/2020/06/26/NroKrd.jpg
[Image 1]: