用户喜好

详细解析：今日头条2018校招测试开发方向(第一、二、三、四批)编程题汇总 - 题解。

n = int(input())   #这道题用暴搜肯定超时，但是用Python的字典会非常简单

user_array = list(map(int,input().strip().split()))

user_dict = dict()            #创建一个字典
for i in range(len(user_array)):   #对应的键值是用户喜爱程度，value值是一个列表，对应相应的用户id
   if user_dict.__contains__(user_array[i]):
      user_array_list_i = list(user_dict[user_array[i]])
      user_array_list_i.append(i+1)
      user_dict[user_array[i]] = user_array_list_i
   else:
      user_array_list_i = []
      user_array_list_i.append(i+1)
      user_dict[user_array[i]] = user_array_list_i

q = int(input())

for i in range(q):
      query = list(map(int,input().strip().split()))
      start_index = query[0]
      end_index = query[1]
      k = query[2]

      if user_dict.__contains__(k):
          query_list = user_dict[k]    #通过键值找到这个喜爱程度对应所有的用户id

          count = 0

          for j in range(len(query_list)):
             if start_index <= query_list[j] <= end_index:
                 count += 1

          print(count)
      else:
          print(0)
   

	<?php



	// 已通过所有用例



	



	functiongetArrFromLine($pattern,$split,$num) {



	$arr= [];



	$p_str= "";



	for($i= 0; $i<$num; $i++) {



	if($i!= $num-1)



	{



	$p_str.= "{$pattern}{$split}";



	}



	else{



	$p_str.= "{$pattern}\n";



	}



	//$arr[$i] = null;



	}



	$paramters= [STDIN,$p_str];



	for($i= 0; $i<$num; $i++) {



	$paramters[$i+2] = &$arr[$i];



	}



	



	call_user_func_array('fscanf',$paramters);



	return$arr;



	}



	



	



	fscanf(STDIN, "%d",$users);



	$karr= getArrFromLine("%d"," ",$users);



	$kmap= [];



	for($i=0;$i<$users;$i++) {



	$k= $karr[$i];



	if(isset($kmap[$k]) && is_array($kmap[$k])) {



	array_push($kmap[$k],$i+1);



	}



	else{



	$kmap[$k] = [$i+1];



	}



	}



	



	//print_r($kmap);



	



	fscanf(STDIN, "%d",$groups);



	$res= [];



	for($i=0; $i<$groups; $i++) {



	$res[$i] = 0;



	list($start_id,$end_id,$k) = getArrFromLine("%d"," ",3);



	if(is_array($kmap[$k])) {



	foreach($kmap[$k] as$uid) {



	if($start_id<=$uid&& $uid<=$end_id)



	$res[$i]++;



	}



	}



	}



	



	foreach($resas$r) {



	echo$r,"\n";



	}



	



	?>

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, q, l, r, k;
    scanf("%d", &n);
    int a[n+1];
    map<int, vector<int>> mp;
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        mp[a[i]].push_back(i);
    }
    scanf("%d", &q);
    for(int i=0;i<q;i++){
        scanf("%d%d%d", &l, &r, &k);
        if(mp.find(k) == mp.end())
            puts("0");
        else{
            auto v = mp[k];
            auto ll = lower_bound(v.begin(), v.end(), l);
            auto rr = upper_bound(v.begin(), v.end(), r);
            printf("%ld\n", rr-ll);
        }
    }
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

	int n;
	cin >> n;
	unordered_map<int,vector<int>> kMapUser;
	for (int i = 0; i < n; i++) {
		int kValue;
		cin >> kValue;
		kMapUser[kValue].push_back(i+1);  //向量中的元素自动有序，这点很好
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int startUserIndex, endUserIndex, kvalue;
		cin >> startUserIndex >> endUserIndex >> kvalue;
		auto users = kMapUser[kvalue];
		auto low = lower_bound(users.begin(), users.end(), startUserIndex);
		auto high = upper_bound(users.begin(), users.end(), endUserIndex);
		cout << high - low << endl;
	}


	//system("Pause");
	return 0;
}

直接在数组中进行判断有几个的，但是不知道数据大的时候，牛客上怎么就ac了，有点奇怪

import java.util.Scanner;

/**
 * @Auther: xuzhangwang
 * @Description:
 */
public class Main {
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            arr[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int k = sc.nextInt();
            check(arr, l, r, k);
        }
    }

    private static void check(int[] arr, int l, int r, int k) {
        int ans = 0;
        for (int i = l; i <= r; i++) {
            if (arr[i] == k) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

	
	

		#include <stdio.h>
	

	

		int main() {
	

	

		  int n, q, low, high, key, cnt, i;
	

	

		  scanf("%d", &n);
	

	

		  int likes[n];
	

	

		  for (i=0; i<n; ++i)
	

	

		    scanf("%d", &likes[i]);
	

	

		  scanf("%d", &q);
	

	

		  while (q--) {
	

	

		    cnt = 0;
	

	

		    scanf("%d %d %d", &low, &high, &key);
	

	

		    for (i=low-1; i<high; ++i)
	

	

		      if (likes[i] == key)
	

	

		        cnt++;
	

	

		    printf("%d\n", cnt);
	

	

		  }
	

	

		  return 0;
	

	

		}
	

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    vector<int> users(n);
    for(int i = 0; i < n; cin >> users[i++]);
    int q; cin >> q;
    vector<int> l(q), r(q), k(q);
    for(int i = 0; i < q; cin >> l[i] >> r[i] >> k[i++]);
    
    map<int, vector<int>> mp;
    for(int i = 0; i < n; ++i)
        mp[users[i]].push_back(i+1);
    
    vector<int> res(q, 0);
    for(int i = 0; i < q; ++i) {
        if(mp.count(k[i]) == 0)
            continue;
        auto pos = mp[k[i]];
        auto low = lower_bound(pos.begin(), pos.end(), l[i]);
        auto up  = upper_bound(pos.begin(), pos.end(), r[i]);
        res[i] = up - low;
    }
    
    for(int i = 0; i < q; ++i)
        cout << res[i] << endl;
}

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n;    cin>> n;
    int user[n];    memset(user, 0, n*4);
    for(int i=0; i<n;i++) cin>> user[i];
    int q;    cin>> q;
    int request[q][3];
    for(int i=0; i<q;i++){
        for(int j=0; j<3;j++)
            cin>> request[i][j];
    }

    vector<int> res;
    for(int i=0; i<q;i++){
        int left = request[i][0], right=request[i][1], key = request[i][2];
        int num=0;
        for(int j=left-1; j<=right-1 ;j++){
            if(user[j] == key){
                num++;
            }
        }
        res.push_back(num);
 
    }
        
    for(auto it: res) cout<< it<<endl;
    
    return 0;
}

这道题时间限制不太行啊，我暴力也过了 (1049ms)

#include 
using namespace std;
int n, p;
int T[300005];
void solve(int l, int r, int k) {
    int cnt = 0;
    for(int i = l; i <= r; ++i) {
        if(T[i] == k) ++cnt;
    } 
    printf("%d\n", cnt);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &T[i]);
    scanf("%d",&p);
    for(int  i = 0; i < p; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        solve(l, r, k);
    }
}

再来一个二分的解法，这个不如上面的快（2110ms），应该和测试用例过有关。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <map>
using namespace std;
int n, q;
int T[300005];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &T[i]);
    }
    map<int, vector<int>> t;
    scanf("%d", &q);
    for(int i = 0; i < q; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        if(t.find(k) == t.end()) {
            t[k] = vector<int>();
            for(int i = 0; i < n; ++i)
                if(T[i] == k)  {
                    t[k].push_back(i+1);
            //        cout << "insert " << i << endl;
                }
        }
        auto low = lower_bound(t[k].begin(), t[k].end(), l);
        auto up  = upper_bound(t[k].begin(), t[k].end(), r);
        printf("%d\n", up - low);

    }
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            Map<Integer,Node> map=new HashMap<>();
           int n=sc.nextInt();
           for(int i=0;i<n;i++){
               int val=sc.nextInt();
               if(map.containsKey(val))
                    map.put(val,map.get(val).add(i+1));
               else
                   map.put(val,new Node(i+1));
           }
           int q=sc.nextInt();
           for(int i=0;i<q;i++){
              int l=sc.nextInt();
              int r=sc.nextInt();
              int k=sc.nextInt();
              if(!map.containsKey(k)){
                  System.out.println(0);
              }else{
                  System.out.println(map.get(k).getSize(l,r));
              }
           } 
       } 
        sc.close();
    }
} 
class Node{
    private TreeSet<Integer> set;
    public Node(int index){
        set=new TreeSet<>();
        set.add(index);
    }
    public Node add(int index){
        set.add(index);
        return this;
    }
    
    public int getSize(int l,int r){
       return set.subSet(l,true,r,true).size();
    }
}