牛客网 - 企业笔试题.md

牛客网历年企业笔试题

字节跳动

字节跳动2018校招前端方向（第二批） 传送门

用户喜好

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。
假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，
我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。
因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。

输入描述：
输入：
第1行为n代表用户的个数
第2行为n个整数，第i个代表用户标号为i的用户对某类文章的喜好度
第3行为一个正整数q代表查询的组数
第4行到第（3+q）行，每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。
数据范围n <= 300000,q<=300000 k是整型

输出描述:
输出：一共q行，每行一个整数代表喜好值为k的用户的个数

示例：

输入：
5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3

输出：
1
0
2

说明：
样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

let n = parseInt(readline());
let arr = readline().split(' ').map(e => Number(e));
let q = parseInt(readline());
let xihaodu = [];
while(q>0){
  q--;
  xihaodu.push(readline().split(' ').map(e => Number(e)));
}
let res = [];
arr.forEach((item, index) => {
    if (res[item] == undefined){
        res[item]=[];
    }
    res[item].push(index);
})
xihaodu.forEach((item, index) => {
    let [l, r, k] = item;
    let count = 0;
    if (res[k] == undefined) {
        console.log(0)
    }else {
        res[k].forEach(e => {
            if (e>=l-1 && e<=r-1) {
                count++;
            }
        })
        print(count)
    }
})

手串

作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。
为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。
手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。
请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入描述:
第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 
接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。
接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)

输出描述:
一个非负整数，表示该手链上有多少种颜色不符需求。

示例1

输入
5 2 3
3 1 2 3
0
2 2 3
1 2
1 3

输出
2

说明
第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。
这里第2颗串珠是透明的。

let [n, m, c] = readline().trim().split(' ').map(e => parseInt(e));
let arr = [];
for (let i=0;i<n;i++){
  arr.push(readline().split(' ').map(e => parseInt(e)));
}
let res = [];
arr.forEach((item, index) => {
  if (item[0] > 0) {
    item.slice(1).forEach(e => {
      if(res[e]) {
        res[e].push(index+1);
      }else {
        res[e] = [index + 1];
      }
    })
  }
})
let count = 0;
res.forEach(item => {
  for(let i=0;i<item.length-1;i++){
    if(item[i+1]-item[i]<m){
      count++
      break;
    }
    if(item[0]-item[item.length-1]+n<m){ //因为手链是个环，所以最后一个要跟第一个做一下比较
      count++;
      break;
    }
  }
})
print(count)

字节跳动编程真题 传送门

ZJ1 附加题

题目描述
存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),
现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
    A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
    B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；

输入描述:
第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，
接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述:
输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。

示例1

输入
2
1 2

输出
4

说明
开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，
之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。

题解：

• 仔细分析 1<=pi<=i 知道用动态规划做。
• 记录第一次到达i为dp[i]，此时前面的所有门肯定是已经到达偶数次了
  • 因为传送只会后退，前进的唯一方式是偶数次到达并+1，不能跳跃
  • 所以到达i门前面所有门都走过并且经过偶数次（反正法也可以证明）
• dp[i]=dp[i-1]+第二次到达i-1 + 1
• 第一次到达i-1门后再走一步会回到p[i-1]，此时p[i-1]门到达奇数次，其他所有门到达偶数次
• 这和第一次到达p[i-1]门的情况完全相同，所以从p[i-1]门回到i-1门，需要dp[i-1]-dp[p[i-1]]
• 所以dp[i] = dp[i-1] + dp[i-1] - dp[p[i-1]] + 1 + 1
• dp[i] = 2 * dp[i-1] - dp[p[i-1]] + 2

let n = parseInt(readline());
let p = readline().split(' ').map(Number);
let dp = Array(n).fill(0); //dp[i]表示第一次到达i的步数为dp[i]
for(let i=1; i<=n; i++){
  dp[i] = ((2 * dp[i-1] % 1000000007 - dp[p[i-1] -1] + 1) + 1) % 1000000007;
}
console.log(dp[n])

ZJ16 数列的和

难度： 简单

题目描述
数列的定义如下：数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。

输入描述:
输入数据有多组，每组占一行，由两个整数n（n<10000）和m(m<1000)组成，n和m的含义如前所述。

输出描述:
对于每组输入数据，输出该数列的和，每个测试实例占一行，要求精度保留2位小数。

示例1

输入
81 4
2 2

输出
94.73
3.41

while(line = readline()) {
  let [n, m] = line.split(' ').map(Number);
  let sum = 0;
  for(let i=0; i<m; i++) {
    sum += n
    n = Math.sqrt(n);
  }
  print(sum.toFixed(2))
}

ZJ17 水仙花数

题目描述
春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：“水仙花数”是指一个三位数，
它的各位数字的立方和等于其本身，比如：153=1^3+5^3+3^3。 现在要求输出所有在m和n范围内的水仙花数。

输入描述:
输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。

输出描述:
对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，
如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开;如果给定的范围内不存在水仙花数，则输出no;每个测试实例的输出占一行。

示例1

输入
100 120
300 380

输出
no
370 371

while(line = readline()) {
  let [m, n] = line.split(' ').map(Number);
  let res = [];
  for (let num=m; num<=n; num++) {
    // 下面三个都必须加parseInt强转，不知道什么原因，知道的朋友可以在GitHub的Issues里告知我一下
    let bai = parseInt(num / 100);
    let shi = parseInt(num % 100 / 10);
    let ge = parseInt(num % 100 % 10);
    let sum = bai ** 3 + shi ** 3 + ge ** 3;
    if (sum === num){
      res.push(num);
    }
  }
  if(res.length){
    console.log(res.join(' '));
  }else{
    console.log('no');
  }
}

ZJ19 万万没想到之抓捕孔连顺

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

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

输出
4

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

示例2

输入
5 19
1 10 20 30 50

输出
1

说明
可选方案 (1, 10, 20)

// 双指针法
let [N, D] = readline().split(' ').map(Number);
let pos = readline().split(' ').map(Number);
let count = 0;
let [L, R] = [0, 2];
while (L+2 <= R && R < N) {
  if (pos[R] - pos[L] <= D) {
    while (R < N && pos[R] - pos[L] <= D) {
      R++;
    }
    R--;
    let n = R - L;
    if (n >= 2) {
      count += n * (n - 1) / 2;
    }
    L++;
  }
}
console.log(count % 99997867)

ZJ20 雀魂启动

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

总共有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

输出
9

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


示例2

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

输出
4 7

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


示例3

输入
1 1 1 2 2 2 3 3 3 5 7 7 9

输出
0

说明
来任何牌都无法和牌

备注:
请不要根据自己的常识为题目增加未提及的条件
对于20%的数据，保证和牌时一定是4个刻子+雀头的形式

let arr = readline().split(' ').map(Number);
let account = Array(9).fill(0);
arr.forEach(e=>account[e-1]++);
let arrRemain = account.map(e => 4-e); // 记录剩余牌的次数
let ishu = (nums) => {
  let len = nums.length;
  if (len === 0)return true; 
  let count = 0;
  nums.forEach(e => e === nums[0] && count++)
  // nums最前面的数字至少2个相同，将2个数字作为雀头；递归判断剩下的数字
  if (count>=2 && len%3!==0 && ishu(nums.slice(2))) return true;
  // nums最前面的数字至少三个相同，将3个数字作为刻子；递归判断剩下的数字
  if(count>=3 && ishu(nums.slice(3))) return true;
  // nums最前面的数字只出现了1次，在nums数组里找到比这个数字大1和大2的数字组成顺子；递归判断剩余的数字
  let [n, m] = [nums[0] + 1, nums[0] + 2];
  if (nums.indexOf(n) !== -1 && nums.indexOf(m) !== -1) {
    // 去掉这个顺子
    nums.splice(0, 1); // 去掉顺子的第1个数字
    nums.splice(nums.indexOf(n), 1); // 去掉顺子的第2个数字
    nums.splice(nums.indexOf(m), 1); // 去掉顺子的第3个数字
    return ishu(nums);
  }
  return false;
}
let res = [];
for(let i=1; i<=9; i++) {
  let nums = arr.slice();
  if (arrRemain[i-1] <=0) continue; // 剩余的牌中没有这个数字
  nums.push(i)
  nums.sort((a, b) => a - b);
  ishu(nums) && res.push(i);
}
res.length > 0 ? console.log(res.join(' ')) : console.log(0);

腾讯2020校园招聘 传送门

1. 压缩算法

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述:
输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:
输出一个字符串，代表解压后的字符串。

示例1
输入
HG[3|B[2|CA]]F

输出
HGBCACABCACABCACAF

说明
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

let s = readline().trim();
let decode = (s) => {
  // x, y, z会找到最内层的一组方括号 [|]
  let [i, x, y, z] = [0, -1, -1, -1];
  while (i < s.length) {
    if (s[i] === '[') {
      x = i;
    }
    else if(s[i] === '|') {
      y = i;
    }
    else if (s[i] === ']'){
      z = i;
      break;
    }
    i++
  }
  if (x !== -1 && y !== -1 && z !== -1) {
    let times = s.slice(x+1, y);
    let sub = s.slice(y+1, z);
    let decode_s = s.slice(0, x) + sub.repeat(times) + s.slice(z+1);
    return decode(decode_s);
  }else{
    return s;
  }
}
print(decode(s));

2. 逛街

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述:
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;


输出描述:
输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。

示例1
输入
6
5 3 8 3 2 5

输出
3 3 5 4 4 4

说明
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

let n = parseInt(readline());
let w = readline().split(' ').map(Number);
let left = []; //从左往右看能看到的楼数 借助单调递增栈
let right = [];//从右往左看能看到的楼数 借助单调递减栈
let total = [];
// 单调递减栈
let stack = [];
for(let i = n-1; i>=0; i--) { // 从右往左遍历
  right[i] = stack.length;
  while(stack.length && stack[0] <= w[i]) { //栈顶的元素如果小于当前遍历的数，就把栈顶元素弹出
    stack.shift();
  }
  stack.unshift(w[i]);
}
// 单调递增栈
stack = [];
for(let i=0; i<n; i++) { // 从左往右遍历
  left[i] = stack.length;
  total[i] = left[i] + right[i] + 1; // +1是加的自身的一栋楼
  while(stack.length && stack[stack.length - 1]<=w[i]) { //栈顶的元素如果小于当前遍历的数，就把栈顶元素弹出
    stack.pop();
  }
  stack.push(w[i]);
}
print(total.join(' '));