为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
数据范围: , , , 每组查询满足 ,查询的喜好值满足
为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Map<Integer, List<Integer>> m = new HashMap<>(); for (int i = 1; i <= n; ++i) { int k = in.nextInt(); m.computeIfAbsent(k, e -> new ArrayList<>()).add(i); } int q = in.nextInt(); while (q-- != 0) { int left = in.nextInt(), right = in.nextInt(), k = in.nextInt(); List<Integer> ls = m.getOrDefault(k, new ArrayList<>()); int res = 0; for (int i: ls) { if (i >= left && i <= right) res++; } System.out.println(res); } } }
import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n, q, i, l, r, k; n = scan.nextInt(); HashMap<Integer, ArrayList<Integer>> map = new HashMap<>(); for (i = 0; i < n; i++) { k = scan.nextInt(); ArrayList<Integer> list; if (!map.containsKey(k)) { list = new ArrayList<>(); list.add(i + 1); map.put(k, list); } else { list = map.get(k); list.add(i + 1); map.put(k, list); } } q = scan.nextInt(); for (i = 0; i < q; i++) { l = scan.nextInt(); r = scan.nextInt(); k = scan.nextInt(); int sum = 0; if (map.containsKey(k)) { ArrayList<Integer> list = map.get(k); // list是有序的 也可以用二分查找 for (Integer o : list) { if (o >= l) { if (o > r) break; else sum++; } } System.out.println(sum); } else System.out.println(0); } } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int[] favo= new int[n]; //存储喜好值 for(int i=0;i<n;i++){ favo[i]=scan.nextInt(); } //准备查询 int q=scan.nextInt(); int[] res=new int[q];//存放结果 //Queue<Integer> res= new LinkedList<>(); //查询几次循环几次 for(int i=0;i<q;i++){ int count=0; int low=scan.nextInt(); int high=scan.nextInt(); int target=scan.nextInt(); res[i]=check(low,high,target,favo); } for(Integer x:res){ System.out.println(x); } } //单独摘出来就不会超时,放进main就超时 public static int check(int low,int high,int target,int[] favo){ int count=0; for(int m=low;m<=high;m++){ if(favo[m-1]==target){ count++; } } return count; } }
import java.util.Arrays; import java.util.Scanner; public class Solution1 { /* 输入: * 5 * 1 2 3 3 5 * 3 * 1 2 1 * 2 4 5 * 3 5 3 *输出: 1 0 2 */ public static void main(String[] args) { //输入5 Scanner input = new Scanner(System.in); //创建一个大小为5的数组 int length1 = input.nextInt(); int[] arr1 = new int[length1]; //输入该数组的值 Scanner input2 = new Scanner(System.in); String str1 = input2.nextLine(); String[] arrStr1 = str1.split(" "); for (int i=0;i<arrStr1.length;i++){ arr1[i] = Integer.parseInt(arrStr1[i]); } //输入x int length2 = input.nextInt(); //创建一个大小为x,3的二维数组 int[][] arr2 = new int[length2][3]; //输入该数组的值 for (int i=0;i<arr2.length;i++){ Scanner input3 = new Scanner(System.in); String str2 = input3.nextLine(); String[] arrStr2 = str2.split(" "); for (int j=0;j<3;j++){ arr2[i][j] = Integer.parseInt(arrStr2[j]); } } //假设现在得到一维数组 //int[] arr1 = {1,2,3,3,5}; //假设现在得到的二维数组 //int[][] arr2 = {{1,2,1},{2,4,5},{3,5,3}}; int[] arr3 = new int[length2]; for (int i=0;i<arr2.length;i++){ int count = getCount(arr1, arr2[i]); arr3[i] = count; } for (int i : arr3) { System.out.println(i); } } /** * * @param arr1 1,2,3,3,5 * @param arr2 二维数组的第几行 * @return */ public static int getCount(int[] arr1,int[] arr2){ //count1,count2分别记录两个数在一维数组中重复次数 int count1=0; int count2=0; //若有一个为0,则返回0,否则返回较大值 Arrays.sort(arr1); for (int i=0;i<arr1.length;i++){ if (arr2[1]==arr1[i]){ count1++; } } for (int i=0;i<arr1.length;i++){ if (arr2[2]==arr1[i]){ count2++; } } if (count1==0 || count2==0){ return 0; }else { if (count1>count2){ return count1; }else { return count2; } } } }
为什么他会数组越界呢??我测试用例明明没问题啊
import java.util.HashMap; import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { try (Scanner scanner = new Scanner(System.in)) { // 用户个数 int userCount = scanner.nextInt(); // key表示fav值,value表示fav位置 Map<Integer, List<Integer>> favMap = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < userCount; i++) { int num = scanner.nextInt(); if (favMap.containsKey(num)) { favMap.get(num).add(i + 1); } else { List<Integer> li = new ArrayList<Integer>(); li.add(i + 1); favMap.put(num, li); } } // 测试组个数 int testCount = scanner.nextInt(); // 结果集 int[] results = new int[testCount]; for (int i = 0; i < testCount; i++) { int min = scanner.nextInt(); int max = scanner.nextInt(); int testFav = scanner.nextInt(); if (favMap.containsKey(testFav)) { for (Integer favIndex : favMap.get(testFav)) { if (min <= favIndex && favIndex <= max) { results[i]++; } } } } // 输出结果集 for (int i = 0; i < testCount; i++) { System.out.println(results[i]); } } catch (Exception e) { // TODO: handle exception } } }
符号表应用,把喜好值作为key,对应该喜好值的人的集合作为value
比如查询5的时候,直接找到所有喜好值为5的人的集合,遍历集合中哪些人在范围内。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int[] fav=new int[n];
for(int i=0;i<n;i++){
fav[i]=scan.nextInt();
}
Map<Integer,List<Integer>> map=new HashMap<>();
for(int i=0;i<n;i++){
int key=fav[i];
int value=i+1;
if(!map.containsKey(key)){
List<Integer> list=new LinkedList<>();
list.add(value);
map.put(key,list);
}else{
List<Integer> list=map.get(key);
list.add(value);
}
}
int m=scan.nextInt();
Queue<Integer> queue=new LinkedList<>();
for(int i=0;i<m;i++){
int lo=scan.nextInt();
int hi=scan.nextInt();
int des=scan.nextInt();
List<Integer> list=map.get(des);
int count=0;
if(list!=null){
for(Integer integer:list){
if(integer>=lo&&integer<=hi){
count++;
}
}
}
queue.add(count);
}
for(Integer integer:queue){
System.out.println(integer);
}
}
}
大佬们,帮忙看看哪里有问题,系统提示答案错误,但测试用例给不出来,能帮忙看看什么问题吗?
import java.util.*;
public class Main {
public static List<Integer[]> querys(int [] weights, List<Integer[]> qs){
List<Integer[]> ans = new ArrayList<>();
Map<Integer,Integer[]> *** = new HashMap<>();
Integer i, w, l, r, c;
Integer[] line;
for (Integer[] query: qs){
i = query[0];
l = query[1];
r = query[2];
w = query[3];
if (***.containsKey(w)) line = ***.get(w);
else if (weights[l] == w) ***.put(w, line = new Integer[]{l, l, 1});
else ***.put(w, line = new Integer[]{l, l, 0});
c = line[2];
for(int j = line[0]; j < l; j++){
if (weights[j] == w) c--;
}
for(int j = line[1] + 1; j <= r; j++){
if (weights[j] == w) c++;
}
line[0] = l;
line[1] = r;
line[2] = c;
ans.add(new Integer[]{i, c});
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
//数组下标不从0开始难受
int[] weights = new int[n + 1];
for (int i = 1; i <= n; i++) weights[i] = sc.nextInt();
int q = sc.nextInt(), l, r, w;
List<Integer[]> qs = new ArrayList<>(q);
for (int i = 1; i <= q; i++){
l = sc.nextInt();
r = sc.nextInt();
w = sc.nextInt();
qs.add(new Integer[]{i, l, r, w});
}
//排序 保证查询区间一直向后移动
qs.sort(Comparator.comparing((Integer[] integers) -> integers[1]).thenComparing((integers) -> integers[2]));
List<Integer[]> ans = querys(weights, qs);
//按编号返回结果
ans.sort(Comparator.comparing((Integer[] integers) -> integers[0]));
for(Integer[] a : ans) System.out.println(a[1]);
}
sc.close();
}
}