用户喜好
（java实现）
题目描述：
为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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的用户的个数
示例1：
输入
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
问题分析：
思路一：直接暴力法，容易超时。故需要考虑其他算法。
但是有个问题，如果把查询那一部分单独写成函数（如思路一实现2.0）却可以通过，不写成函数（1.0），反而过不了？目前还没搞清楚是为什么。
比较图片中的第一、第二行：从运行结果可以看出，第一行（2.0）运行状态是“答案正确”，第二行（1.0）却运行超时。从占用内存方面来看，第一行（2.0）占用“157068K”，相比于第二行（1.0）的“31340K”来说，增加将近5倍的内存（也可能是函数的调用、查找，使用到了栈，故消耗的内存比较大）。
思路二：符号表应用，把喜好值作为key，对应该喜好值的人的集合作为value
比如查询5的时候，直接找到所有喜好值为5的人的集合，遍历集合中哪些人在范围内。
使用：Map<Integer,List<integer>></integer>
相关知识：
Map<Integer,List<integer>> userLike = new HashMap<>();</integer>
List<Integer> list = userLike.get(key);
if (list!=null)
{
for (Integer val : list)
{
if (val>=left && val<=right)
count++;
}
}参考代码：
思路一实现（1.0）：
import java.util.*;
public class Main {
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
while (input.hasNext())
{
int n = input.nextInt();
int[] userLike = new int[n+1];
for (int i=1; i<=n; i++)
{
userLike[i] = input.nextInt();
}
int m = input.nextInt();
for (int i=0; i<m; i++)
{
int left = input.nextInt();
int right = input.nextInt();
int key = input.nextInt();
int count = 0;
for (int j=left; j<=right; j++)
{
if (key == userLike[j])
count++;
}
System.out.println(count);
}
}
}
}思路一实现（2.0）：
import java.util.*;
public class Main {
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] userLike = new int[n+1];
for (int i=1; i<=n; i++)
{
userLike[i] = input.nextInt();
}
int m = input.nextInt();
int left, right, key;
int[] res = new int[m];
for (int i=0; i<m; i++)
{
left = input.nextInt();
right = input.nextInt();
key = input.nextInt();
res[i] = check(left,right,key,userLike);
}
for (int i=0; i<m; i++)
{
System.out.println(res[i]);
}
}
public static int check(int left, int right, int key, int[] userLike)
{
int count = 0;
for (int j=left; j<=right; j++)
{
if (key == userLike[j])
count++;
}
return count;
}
}思路二实现：
import java.util.*;
import java.util.List;
public class Main {
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int n = input.nextInt();
Map<Integer,List<Integer>> userLike = new HashMap<>();
int key = 0;
for (int i=1; i<=n; i++)
{
key = input.nextInt();
if (!userLike.containsKey(key))
{
List<Integer> list = new LinkedList<>();
list.add(i);
userLike.put(key, list);
}
else
{
List<Integer> list = userLike.get(key);
list.add(i);
}
}
int m = input.nextInt();
int left, right, count;
for (int i=0; i<m; i++)
{
left = input.nextInt();
right = input.nextInt();
key = input.nextInt();
count = 0;
List<Integer> list = userLike.get(key);
if (list!=null)
{
for (Integer val : list)
{
if (val>=left && val<=right)
count++;
}
}
System.out.println(count);
}
}
}
投递字节跳动等公司9个岗位