前几天头条前端编程题讨论
放上题目和代码~感觉我都是暴力没有技巧~请有更好解法的dalao们交流
[编程题|25分] 手串
时间限制：1秒
空间限制：65536K
题目描述
作为一个手串艺人，有金主向你订购了一条包含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
输入
5 2 3
3 1 2 3
0
2 2 3
1 2
1 3
输出
2
说明
第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。
这里第2颗串珠是透明的。
、、、、、、、、、、、、、、、、、、、、、、、、、
我的代码
/**
* Created by CBB on 2017/9/10.
*/
var readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal:false
});
var n = -1;// 初始状态为负数，表示还没开始读取
var arr =[];
var cur_line = 0;
var m =0;
var color =0;
var len =0;
rl.on('line', function(line){ // javascript每行数据的回调接口
if (n<0) { // 测试用例第一行读取n
n = Number(line.trim().split(" ")[0]);
m = Number(line.trim().split(" ")[1]);
color = Number(line.trim().split(" ")[2]);
} else {
// 矩阵数据读取
var tokens = line.split(' ');
// 题目逻辑求和，边读取边计算
arr.push(tokens);
// 记录当前读取的行数
cur_line += 1;
}
// 读取行数结束，如果确定只有一行额外的数据输入，也可以通过cur_line === 1来判断
if (n === cur_line) {
// 输出结果
var res= ans(arr,color,m);
console.log(res);
// 重新初始化相关变量
n = -1;
arr =[]
cur_line = 0;
m=0;
color =0;
}
});
function ans(arr,color,m){
if(arr == null || arr==[]){
return 0
}
//hua dong chuang kou
var obj ={};
var m = m-1;
for(var j =0;j<m;j++){
arr.push(arr[j]);
}
for(var h =0;h<(arr.length-m);h++){
arr[h].shift();
for(var z=0;z<arr[h].length;z++){
arr[h][z] = Number(arr[h][z]);
}
}
var originlen = arr.length-m;
m +=1;
for(var h =0;h<originlen;h++){
var tmpobj={};
for(var z=0;z<m;z++) {
for (var k = 0; k < arr[h + z].length; k++) {
var tmparr = arr[h + z][k];
if (!tmpobj[arr[h + z][k]]) {
tmpobj[arr[h + z][k]] = 1;
} else {
if (!obj[arr[h + z][k]]) {
obj[arr[h + z][k]] = 1;
}
}
}
}
}
var count =0;
for(i in obj){
if(obj[i] == 1){
count ++;
}
}
return count;
}
[编程题|25分] 用户喜好
时间限制：3秒
空间限制：262144K
题目描述
为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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
输入
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
、、、、、、、、、、
我的代码
/**
* Created by CBB on 2017/9/10.
*/
/**
* Created by CBB on 2017/9/10.
*/
var readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal:false
});
var n = -1;// 初始状态为负数，表示还没开始读取
var arr =[];
var q =0;
var query =[];
var cur_line =0;
rl.on('line', function(line){ // javascript每行数据的回调接口
if (n<0) { // 测试用例第一行读取n
n++
} else {
if(cur_line ==1)
{
arr = line.split(' ');
}else if(cur_line ==2){
q = Number(line.trim());
}else{
query.push(line.split(" "));
}
}
cur_line += 1;
// 读取行数结束，如果确定只有一行额外的数据输入，也可以通过cur_line === 1来判断
if ((q+3) === cur_line) {
var res = result(arr,query,q);
for(var i=0;i<arr.length;i++){
console.log(res[i]);
}
// 重新初始化相关变量
n = -1;// 初始状态为负数，表示还没开始读取
arr =[];
q =0;
query =[];
cur_line =0;
}
});
function result(arr,query,q){
for(var i=0;i<arr.length;i++){
arr[i] =Number(arr[i]);
}
var res =[];
for(var i=0;i<q;i++){
var l = Number(query[i][0]);
var r = Number(query[i][1]);
var tmpArr = [];
copyArr(arr,tmpArr,l-1,r-1);
tmpArr.sort(function(a,b){
return a-b;
})
var key =Number(query[i][2]);
var index = binary_search(tmpArr,key);
var count =0;
if(index!=undefined){
count++;
var left =index-1;
var right =index+1;
while(left>=0){
if(tmpArr[left]==key){
count++
}else{
break;
}
left--;
}
while(right<tmpArr.length)
{
if(tmpArr[left]==key){
count++
}else{
break;
}
right++;
}
}
res.push(count);
}
return res;
}
function copyArr(arr1,arr2,l,r){
for(var i=l;i<=r;i++){
arr2.push(arr1[i]);
}
}
function binary_search(arr, key) {
var low = 0,
high = arr.length - 1;
while(low <= high){
var mid = parseInt((high + low) / 2);
if(key == arr[mid]){
return mid;
}else if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid -1;
}else{
return -1;
}
}
};
希望能看到其他的思路~~~~
投递小红书等公司9个岗位