字节跳动18年后端方向笔试真题

发表于 | 更新于 | 分类于
本文字数： 4.9k | 阅读时长 ≈ 4 分钟

字跳18年后端方向

🥇用户喜好

题目描述

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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的用户的个数

问题分析

这题的题目很长，容易把人弄晕。给了一个数组，其中索引i对应的值代表员工编号为i的喜好值val；然后给一个查询条件，员工编号的范围[l, r],以及喜好值k，判断在这个范围内有多少喜好值为k的员工。我们输出打印员工的人数即可。

看到这题，就觉得简直不能更简单了好么！用一个数组把员工的喜好值存起来，再用一个for循环遍历索引为[left,right]中的喜好值即可。无奈理想很丰满，现实很骨感，一提交运行就给你一个50%的通过率，原因是超时。可能是员工的人数过多，但喜好值呢，是一个比较固定的范围。

因此想办法改进，很直观的方法是用一个map把喜好和员工编号对应起来，每次查询找到喜好值为k的所有员工，员工的编号是有序的，二分查找所有在范围内的员工即可。二分查找时，找到大于等于员工编号左边界的最小值，和小于等于员工编号的最大值，根据二者的差值求出员工数目。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.*;

/**
 * @author zhen
 */
public class Main {
    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      HashMap<Integer, List<Integer>> map = new HashMap<>();
      //将喜好为k的员工放在一起
      for(int i=1; i<=N; i++){
        int k = in.nextInt();
        //这种输入方法可以记一下，一个key对应一个列表的情况
        List<Integer> tmp = map.getOrDefault(k, new ArrayList<>());
        tmp.add(i);
        map.put(k, tmp);        
      }
      int q = in.nextInt();
      int res = 0;
      for(int i=0;i<q;i++){
        int left = in.nextInt();
        int right = in.nextInt();
        int target = in.nextInt();
        if(map.containsKey(target)){
          List<Integer> list = map.get(target);
          //把Integer类型传进去
          Integer[] array = list.toArray(Integer[0]);
          int start = lowerBound(array, target);
          int end = upperBound(array, target);
          if(start != -1 && end != -1){
            res = end - start +1;
          }                   
        }else{
          res = 0;
        }
        System.out.println(res);
      }      
    }
  //找到大于等于target的最小值
  private static int lowerBound(Integer[] array, int target){
    int l = 0;
    int r = array.length-1;
    while(l <= r){
      int mid = (r-l)/2+l;
      if(target <= array[mid]){
        r = mid-1;
      }else{
        l = mid+1;
      }
    }
    if(l < array.length && array[l] >= target){
      return l;
    }else{
      return -1;
    }
  }
  //找到小于等于target的最大值
  private static int upperBound(Integer[] array, int target){
    int l = 0;
    int r = array.length-1;
    while(l <= r){
      int mid = (r-l)/2+l;
      if(target >= array[mid]){
        l = mid+1;
      }else{
        r = mid-1;
      }
    }
    if(r >= 0 && array[r] <= target){
      return r;
    }else{
      return -1;
    }
  }
}

🥈手串

题目描述

作为一个手串艺人，有金主向你订购了一条包含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)

输出描述

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

问题分析

这个题目也很绕，搞得人看不明白就对了。我一度觉得自己智商有问题。给一个手串，手串上有n个珠子，总共有c种颜色，每个珠子可能由0种或多种颜色组成，规则为连续m个珠子中出现了至少两次则这种颜色不符合要求。

我们把题目转换一下，有一个数组，索引i指的是颜色i，每个里面放的是所有出现了的珠子位置，然后判断每个颜色里面的珠子是否是符合要求的。

注意：这里要输出的是有多少种颜色不符合需求，因此每种颜色只要出现了一组不符合要求的位置就可以退出了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int C = in.nextInt();
        List<Integer>[] position = new List<>[C+1];
        for(int i=1;i<=C;i++){
           position[i] = new ArrayList<>();          
        }
        for(int i=0; i<N;i++){
          int c= in.nextInt();
          for(int j=0; j<c;j++){
            position[j].add(i);
          }
        }
      	int count = 0;
      	for(int i=1 ; i<=C;i++){
          //手链是环形
          	if(position[i].get(0)+N-position[position[i].size()-1] < M){
              count++;
              continue;
            }
            for(int j=0;j<position[i].size()-1;i++){
              if(position[i].get(j+1) - position[i].get[j] < M){
                count++;
                break;
              }
            }
        }
      System.out.println(count);      
    }
}