为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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
public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] user = new int[n]; for (int i = 0; i < n; i++) { user[i] = sc.nextInt(); } int m = sc.nextInt(); while (m != 0){ int temp = 0; int l = sc.nextInt(); int r = sc.nextInt(); int k = sc.nextInt(); for (int i = l - 1; i < r; i++) { if (user[i] == k){ temp++; } } System.out.println(temp); m--; } } }
#include <iostream> using namespace std; const int N = 300001; int main() { int n; cin >> n; int a[N]; for (int i = 1; i <= n; i++) { cin >> a[i]; } int q; cin >> q; while (q--) { int l, r, k; cin >> l >> r >> k; int count = 0; for (int i = l; i <= r; i++) { if (a[i] == k) { count = count + 1; } } cout << count << endl; } return 0; }
let n = parseInt(readline()); let kArr = readline().split(' '); let kObj = {}; // 存k值的对应下标数组 for (let i = 0; i < n; i++) { kObj[kArr[i]] = kObj[kArr[i]] ? kObj[kArr[i]] : []; kObj[kArr[i]].push(i); } let count = readline(); while(count--) { let arr = readline().split(' '); let l = arr[0]; let r = arr[1]; let k = arr[2]; let res = 0; for (let i in kObj[k]) { // 直接搜索k值对应数组里在[l, r]范围内的个数 if (kObj[k][i] >= l-1 && kObj[k][i] <= r-1) { res++; } } console.log(res) }
import java.util.Scanner; public class Main{ public static void main(String[] args) { // 5 // 1 2 3 3 5 // 3 // 1 2 1 // 2 4 5 // 3 5 3 Scanner scanner = new Scanner(System.in); int numPerson = scanner.nextInt(); int[] arrInterest = new int[numPerson]; for(int i = 0; i < numPerson; i++){ arrInterest[i] = scanner.nextInt(); } int numQuery = scanner.nextInt(); int[] leftBorder = new int[numQuery]; int[] rightBorder = new int[numQuery]; int[] interestQuery = new int[numQuery]; for(int i = 0; i < numQuery; i++){ leftBorder[i] = scanner.nextInt(); rightBorder[i] = scanner.nextInt(); interestQuery[i] = scanner.nextInt(); } for(int i = 0; i< numQuery; i++){ int count = 0; for(int j = leftBorder[i] - 1; j <= rightBorder[i] - 1; j++){ if(interestQuery[i] == arrInterest[j]) count++; } System.out.println(count); } } }
importbisect n =int(input()) levels =list(map(int, input().split())) assertlen(levels) ==n k2i ={} fori inrange(n): ifnotlevels[i] ink2i: k2i[levels[i]] =[i+1] else: k2i[levels[i]].append(i+1) # print(k2i) q =int(input().strip()) for_ inrange(q): l, r, k =list(map(int, input().split())) ifk notink2i: print(0) continue count =0 id_l =bisect.bisect_left(k2i[k], l) id_r =bisect.bisect_right(k2i[k], r) fori inrange(id_l, min(id_r +1, len(k2i[k]))): ifl <=k2i[k][i] <=r: count +=1 print(count)倒排索引字典+二分查找边界
if __name__ == "__main__": n = int(input()) if n < 0 and n > 300000: print("输入有误") like = list(map(int, input().split())) q = int(input()) if q < 0 and q > 300000: print("输入有误") para = [] for i in range(q): para.append(list(map(int, input().split()))) for i in range(q): l = para[i][0] r = para[i][1] k = para[i][2] ans = 0 for j in range(l-1, r): if like[j] == k: ans += 1 print(ans) 为啥超时了1ms。。。 |
java语言能过吗?50%通过率,题解也是50%通过率 import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s=new Scanner(System.in); ArrayList<String> in=new ArrayList<String>(); while(s.hasNextLine()){ in.add(s.nextLine()); } int num=Integer.parseInt(in.get(0)); String[] people=in.get(1).split(" "); String q=in.get(2); String[] row; int count=0; for(int i=3;i<in.size();i++){ count=0; row=in.get(i).split(" "); for(int j=Integer.parseInt(row[0])-1;j<Integer.parseInt(row[1]);j++){ if(row[2].equals(people[j])){ count++; } } System.out.println(count); } } }
import java.util.*; public class Main { public static int binaryFind(UserPre[] sortedListUserPre,int l, int r, int k){ if(l>r){ return -1; }else if(l==r){ if(sortedListUserPre[l].prefer==k){ return l; }else{ return -1; } }else{ int m=(l+r)/2; if(sortedListUserPre[m].prefer<k){ l=m+1; } else if(sortedListUserPre[m].prefer==k){ return m; } else{ r=m-1; } return binaryFind(sortedListUserPre,l,r,k); } } public static void main(String[] args){ int userNum; int q; Scanner sc=new Scanner(System.in); //输入用户数 userNum=sc.nextInt(); if(userNum<=0||userNum>=300000){ return; } //输入用户喜爱值 UserPre[] prefNums=new UserPre[userNum]; for(int i=0;i<userNum;i++){ prefNums[i]=new UserPre(i+1,sc.nextInt()); } Arrays.sort(prefNums,new UserCompare()); //查询列表 q=sc.nextInt(); if(q<=0||q>=300000){ return; } Query[] listQuery=new Query[q]; for(int i=0;i<q;i++){ Integer[] nums=new Integer[3]; nums[0]=sc.nextInt(); nums[1]=sc.nextInt(); nums[2]=sc.nextInt(); if(nums[0]<0||nums[0]>userNum|| nums[1]<0||nums[1]>userNum|| nums[0]>nums[1]){ return; } listQuery[i]=new Query(nums[0],nums[1],nums[2]); } //遍历查询列表得到结果 for(Query query:listQuery){ int findResult=binaryFind(prefNums,0,userNum-1,query.k); //若没找到查询的k值退出 if(findResult<0){ return; } //找到k值的部分,首先往左边找是不是在区间内 int count=0; for(int i=findResult;i>0;i--){ if(prefNums[i-1].prefer==query.k){ if(prefNums[i-1].num>=query.l&&prefNums[i-1].num<=query.r){ count++; } }else{ break; } } //找到k值的部分,再往右边找是不是在区间内 for(int i=findResult+1;i<=userNum;i++){ if(prefNums[i-1].prefer==query.k){ if(prefNums[i-1].num>=query.l&&prefNums[i-1].num<=query.r){ count++; } }else{ break; } } System.out.println(count); } } } class UserPre{ int num; int prefer; UserPre(int num,int prefer){ this.num=num; this.prefer=prefer; } } class UserCompare implements Comparator<UserPre> { @Override public int compare(UserPre o1, UserPre o2) { return o1.prefer-o2.prefer; } } class Query{ int l; int r; int k; Query(int l,int r, int k){ this.l=l; this.r=r; this.k=k; } }
N = int(input()) U = map(int, input().split(' ')) Q = int(input()) T = {} for idx, val in enumerate(U): if val not in T: T[val] = 0 T[val] |= 1<<idx for i in range(Q): L, R, V = map(int, input().split(' ')) if V not in T: print(0) continue R = (1<<R) - 1 R ^= (1<<L-1) - 1 R &= T[V] print(bin(R).count('1'))不知道为啥我这个也显示越界了。。。
import sys nums = [] try: while True: c = sys.stdin.readline() if c == '': break nums.append(list(map(int,c.split(' ')))) except: pass scores = nums[1] num = nums[3:] result = [] if nums[0] == 0: print(0) break for i in num: tmp = 0 j = i[0]-1 while j < i[1]: if scores[j] == i[2]: tmp+=1 j+=1 print(tmp)自测的时候用给的例子通过了,但是提交运行的时候显示越界了,为什么呢
//思路是按用户偏好值进行排序,搜索时当偏好值相同且用户编号在查询区间即搜索成功,最后以查询成功的偏好值向用户区间两侧进行 //搜索,统计所有符合要求的用户,C++代码如下: //提交时间:2019-03-14 语言:C++ 运行时间: 424 ms 占用内存:6620K 状态:答案正确#include <iostream>#include <vector>#include <algorithm>using namespace std;struct User{int no;int prefer;};struct Query{int l;int r;int k;};bool cmp_user(User &a, User &b){return a.prefer < b.prefer;}class Solution{public:void binary(vector<User> & user, Query & q, int & qn, int l, int r){if(l > r) return;if(l == r){if(user[l].prefer == q.k){qn = l;}return;}int m = (l + r)/2;if(user[m].prefer == q.k) {qn = m;return;}if(q.k > user[m].prefer) return binary(user, q, qn, m+1, r);return binary(user, q, qn, l, m-1);}vector<int> fun(vector<User> & user, vector<Query> &query){int qn, l, r;sort(user.begin(), user.end(), cmp_user);vector<int> res(query.size(), 0);for(int i = 0; i < query.size(); i++){qn = -1;binary(user, query[i], qn, 0, user.size()-1);if(qn != -1){for(l = qn; l >= 0 && user[l].prefer == query[i].k; l--){if(user[l].no >= query[i].l && user[l].no <= query[i].r) res[i]++;}for(r = qn+1; r < user.size() && user[r].prefer == query[i].k; r++){if(user[r].no >= query[i].l && user[r].no <= query[i].r) res[i]++;}}}return res;}};int main(void){int un, qn;vector<User> user;vector<Query> query;vector<int> res;User x;Query y;cin >> un;for(int i = 0; i < un; i++){cin >> x.prefer;x.no = i+1;user.push_back(x);}cin >> qn;for(inti = 0; i < qn; i++){cin >> y.l >> y.r >> y.k;query.push_back(y);}class Solution s;res = s.fun(user, query);for(int i = 0; i < res.size(); i++) cout << res[i] << endl;return 0;}