为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void async function () { // Write your code here let idx = 0; let userStar = {}; while(line = await readline()){ let tokens = line.split(' '); if (idx === 1) { userStar = tokens.reduce((pre, cur, idx) => { if (pre[cur]) { pre[cur].push(idx) return pre; }; pre[cur] = [idx]; return pre; }, {}); } if (idx > 2) { const start = parseInt(tokens[0]) - 1; const end = parseInt(tokens[1]) - 1; const starList = userStar[tokens[2]] ?? []; console.log(starList.filter(v => v >= start && v <= end).length) } idx++ } }()
let usernum=readline(); let user=readline().split('') var arr=[] for(var i=0;i<=user.length;i++){ if(i%2==0){ arr.push(user[i]) }else{ continue } } let q=readline() var fun=function(s,f,k){ let num=0; for(var i=s-1;i<f;i++){ if(arr[i]==k){ num++; continue }else{ continue } } print(num) } while(lines=readline()){ var liness = lines.split(''); var s = parseInt(liness[0]); var f = parseInt(liness[2]); var k = parseInt(liness[4]); fun(s,f,k); }
let n = Number(readline()); const user = readline().split(' ').map(Number); let map = new Map(); for(let i = 0; i < n; i++){ let current = []; if(map.has(user[i])){ current = map.get(user[i]).concat(i); map.set(user[i],current); } else { map.set(user[i], [i]) } } let q = Number(readline()); while(q){ let shot = readline().split(' ').map(Number); const begin = shot[0] - 1; const end = shot[1]; if (map.has(shot[2])){ const range = map.get(shot[2]) const count = range.filter(x => x>=begin && x<end).length; print(count) } else { print(0) } q--; }
const readline = require('readline'); /** * 主函数 */ async function main() { const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const info = await getInfo(rl); getLinesLikeCount(info.queryList, info.userLikes); rl.close(); } main(); /** * 获取所有的输入信息 */ async function getInfo(lineStream) { let userCount = 0; let userLikes = []; let queryCount = 0; const queryList = []; let lineNum = 0; return new Promise((resolve, reject) => { lineStream.on('line', (line) => { lineNum += 1; if (lineNum === 1) { return userCount = Number(line); } if (lineNum === 2) { return userLikes = line.split(' ').map(Number); } if (lineNum === 3) { return queryCount = Number(line); } queryList.push(line.split(' ').map(Number)); if (lineNum - 3 === queryCount) { resolve({ userLikes, queryList, }); } }); lineStream.on('error', reject); }); } /** * 查询数组处理 */ function getLinesLikeCount(queryList, userLikes) { const userLikeMap = {}; userLikes.forEach((like, index) => { if (!userLikeMap[like]) { userLikeMap[like] = []; } userLikeMap[like].push(index + 1); }); queryList.forEach((item) => { const count = getLineLikeCount(item, userLikeMap); console.log(count); }); } /** * 单条查询 */ function getLineLikeCount(queryItem, userLikeMap) { const [left, right, like] = queryItem; const likeMembers = userLikeMap[like]; if (!likeMembers) return 0; // likeMembers是一个有序数组,如果likeMembers数组不在left/right访问内,则直接返回0 if (likeMembers[0] > right || likeMembers[likeMembers.length - 1] < left) return 0; // 查找left、right最接近数字在likeMembers的位置 const leftIndex = quickFind(likeMembers, left, 1); const rightIndex = quickFind(likeMembers, right, -1); return rightIndex - leftIndex + 1; } /** * 二分查找,因为不是精确查找,所以加了一个direction表示查找的方向 * @param list 数组 * @param num 查找数组 * @param direction 查找方向,1表示查找向上查找最接近的数字,-1表示向下查找最接近的数字 */ function quickFind(list, num, direction) { let left = 0; let right = list.length - 1; let mid = 0; let val = 0; while (left <= right) { mid = Math.floor((right + left) / 2); val = list[mid]; if (val === num) return mid; // 完全匹配 if (val < num) { left = mid + 1; } else { right = mid - 1; }; } // 未能匹配到数字,开始做最接近匹配 // 如果想向上查找最接近的数字,并且最后一次比对的 list[mid] < num, 则选择 mid + 1 if (direction > 0 && val < num) return left; // left = mid + 1 // 如果想向下查找最接近的数字,并且最后一次比对的 list[mid] > num, 则选择 mid - 1 if (direction < 0 && val > num) return right; // right = mid - 1; // 这时候的 list[mid] 已经是最接近的数字了 return mid; }
//给前面的回答添加了点注释,方便阅读 let chaxunzuarr = []; //第一行输入,用户个数 let yonghushu = readline(), //第二行输入,用户对应喜好,转化为数组 xihaoduarr = readline().split(' '), //第三行输入,查询组数 chaxunzushu = readline(); //循环所有查询组,4行开始的所有行 for(let i = 0;i<chaxunzushu;i++){ //取得每行值,转为数组 chaxunzuarr[i] = readline().split(' '); } let arr = []; //遍历喜好度数组,将相同喜好度的下标添加进一个新数组 //样例添加完后生成arr=[,[0],[1],[2,3],,[4]] xihaoduarr.forEach((item,index) => { if(arr[item] == undefined){ arr[item] = []; } arr[item].push(index); }); //遍历查询组 for(let j = 0;j<chaxunzushu;j++){ //取得每行第一个数l,转化为下标-1 let start = chaxunzuarr[j][0] - 1, //取得每行第二个数r,转化为下标-1 end = chaxunzuarr[j][1] - 1, //取得每行第三个数k,喜好度 value = chaxunzuarr[j][2], //初始化结果用户个数 geshu = 0; if(arr[value] == undefined){ //下标数组为未定义时,无喜好度 console.log(0); }else{ //循环下标数组内元素,判断元素数组内元素是否处于标号间 arr[value].forEach(e=>{ if(e>=start && e<=end){ geshu++; } }) print(geshu); } }
不吹不黑,这题我做了至少5个小时。 JS代码如下:let chaxunzuarr = [];