算法（四十一）

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

输出例子1:

1
0
2

例子说明1:

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

方法一

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n_user = sc.nextInt();
        int[] user_like = new int[n_user];
        for(int i=0; i< n_user; i++){
            user_like[i] = sc.nextInt();
        }

        int search = sc.nextInt();
        int[][] search_group = new int[search][3];
        for(int j=0; j<search; j++){
            for(int k=0; k<3; k++){
                search_group[j][k] = sc.nextInt();
            }
        }


        //执行函数
        ArrayList<Integer> list = new ArrayList<>();
        for(int j=0; j<search; j++){
            int l = search_group[j][0];
            int r = search_group[j][1];
            int k = search_group[j][2];
            int num =0;
            for(int i1=l; i1<=r; i1++){
                if(user_like[i1-1] == k){
                    num++;
                }
            }
            list.add(num);
        }

        for(int i2=0; i2<search; i2++){
            System.out.println(list.get(i2));
        }
    }
}

方法二

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int user = sc.nextInt();

Map<Integer, List<Integer>> map = new HashMap<>();

for (int i = 1; i <= user; i++) {

int fav = sc.nextInt();

if (!map.containsKey(fav)) {

List<Integer> list = new ArrayList<>();

list.add(i);

map.put(fav, list);

} else {

List<Integer> list = map.get(fav);

list.add(i);

}

int group = sc.nextInt();

for (int i = 0; i < group; i++) {

int a = sc.nextInt();

int b = sc.nextInt();

int k = sc.nextInt();

int sum = 0;

List<Integer> list = map.get(k);

if (list != null) {

for (int j = 0; j < list.size(); j++) {

if (list.get(j)>=a&&list.get(j)<=b) {

sum++;

}

System.out.println(sum);

}

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

输出例子1:

例子说明1:

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

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int c=sc.nextInt();
int res=0;
Map<Integer,ArrayList<Integer>> map=new HashMap<>();
for(int i=1;i<n+1;i++){
int diversity=sc.nextInt();
if(diversity==0){
continue;
}
for(int j=diversity;j>0;j--){
int color=sc.nextInt();
if(map.containsKey(color)){
ArrayList<Integer> list=map.get(color);
list.add(i);
}
else{
ArrayList<Integer> list=new ArrayList<>();
list.add(i);
map.put(color, list);
}
}
}
for(int i=1;i<=50;i++){
if(map.containsKey(i)){
c--;
ArrayList<Integer> li=map.get(i);
Iterator<Integer> ltr=li.iterator();
int fir=ltr.next();
int now=fir;
int pre;
while(ltr.hasNext()){
pre=now;
now=ltr.next();
if((now-pre)<m&&(li.size()-now+fir)<m){
res++;
break;
}
}
if(c==0){
break;
}
}
}
System.out.println(res);
}
}