Example
var wishlist = [
{name: "Mini Puzzle", size: "small", clatters: "yes", weight: "light"},
{name: "Toy Car", size: "medium", clatters: "a bit", weight: "medium"},
{name: "Card Game", size: "small", clatters: "no", weight: "light"}
];
var presents = [
{size: "medium", clatters: "a bit", weight: "medium"},
{size: "small", clatters: "yes", weight: "light"}
];
guessGifts(wishlist, presents); // must return ["Toy Car", "Mini Puzzle"]
怎么实现guessGifts这个功能,codewars遇到的题目,自己写了一半天没写出来。
我想说明一下,wishlist.length和presents.length的个数未知,并且里面的键值对也是未知的,循环遍历的话要嵌套好几层,有没有其他更简单的办法?
document.addEventListener('DOMContentLoaded', function(){
var ret = document.getElementById('ret');
guesss(ret, wishlist, presents);
});
var wishlist = [
{name: "Mini Puzzle", size: "small", clatters: "yes", weight: "light"},
{name: "Toy Car", size: "medium", clatters: "a bit", weight: "medium"},
{name: "Card Game", size: "small", clatters: "no", weight: "light"}
],
presents = [
{size: "medium", clatters: "a bit", weight: "medium"},
{size: "small", clatters: "yes", weight: "light"}
],
guesss = function(elem, list, require){
var str = '无',
list = list || [],
require = require || [],
serialKey = function(item){
return [item.size, item.clatters, item.weight].join(', ');
};
if(elem && require.length > 0 && list.length > 0){
var listMap = {};
list.forEach(function(item){
var key = serialKey(item),
val = item.name;
listMap[key.toLowerCase()] = val;
});
require.forEach(function(item){
var key = serialKey(item),
val = listMap[key.toLowerCase()];
if(val){
if(str === '无'){
str = '';
}
str += '<p>Gift is: '+ val +'<br> Key is: '+ key +'</p>';
}
});
}
elem.innerHTML = str;
};
http://codepen.io/interjc/pen/ZQrNRz?editors=0010
写完了才发现和要求不是很一致,囧
题目以presents的顺序返回名称,现在这个以wishlist的顺序返回
有空再改吧。
'use strict';
describe('guess gift test', function(){
function guessGifts(wishlist, presents) {
return wishlist.filter(anyone_matcher(presents)).map(giftName);
}
function anyone_matcher(presents) {
return function (gift) {
return presents.some(matcher(gift));
}
}
function matcher(gift) {
return function (present) {
for (var field in present) {
if (gift[field] !== present[field]) return false;
}
return true;
}
}
function giftName(gift) { return gift.name; }
// tests start here
it("should return empty array if none wish or presents", function() {
expect(guessGifts([], [])).toEqual([]);
});
it("should return matched 1 filed gift with 1 criteria", function() {
expect(guessGifts([{name:'g1'}], [{name:'g1'}])).toEqual(['g1']);
expect(guessGifts([{name:'g1'},{name:'g2'}], [{name:'g1'}])).toEqual(['g1']);
expect(guessGifts([{name1:'g1'},{name1:'g2'}], [{name1:'g2'}])).toEqual([undefined]);
});
it("should return matched gifts with criterias", function() {
var wishlist = [
{name:'g1', size: 'small', wight: 'light'},
{name:'g2', size: 'medium', wight: 'light'}
];
var presents = [
{size: 'medium', wight: 'light'}
];
expect(guessGifts(wishlist, presents)).toEqual(['g2']);
});
it("should return matched gifts with more than 1 criterias", function() {
var wishlist = [
{name: 'Mini Puzzle', size: 'small', clatters: 'yes', weight: 'light'},
{name: 'Toy Car', size: 'medium', clatters: 'a bit', weight: 'medium'},
{name: 'Card Game', size: 'small', clatters: 'no', weight: 'light'}
];
var presents = [
{size: 'medium', clatters: 'a bit', weight: 'medium'},
{size: 'small', clatters: 'yes', weight: 'light'}
];
expect(guessGifts(wishlist, presents)).toEqual(['Mini Puzzle', 'Toy Car']);
});
});
提问者这是要问什么?
如果是要大量处理的话,把size, clatters, weight拼成一个属性value,再做一点映射。譬如:
size: 'small' -> 0 'medium' -> 1 'large' -> 2 //and so on ...
clatters: 'no' -> 0 'a bit' -> 1 'yes' -> 2
weight: 'light' -> 0 'medium' -> 1 'heavy' -> 2 ...
那么'Card Game'对应的value就是 000 .
这样wishlist就像一个map,每一个name(key)对应一个value,然后presents里面全存的都是value,然后你就
根据这个value去找对应的key就行了,只不过这个key不一定是唯一的。
至于是要先把wishlist全部预处理还是用到了某一个name再处理这一条的内容再缓存,就看你的需求了。
var wishlist = [
{name: "Mini Puzzle", size: "small", clatters: "yes", weight: "light"},
{name: "Toy Car", size: "medium", clatters: "a bit", weight: "medium"},
{name: "Card Game", size: "small", clatters: "no", weight: "light"}
];
var presents = [
{size: "medium", clatters: "a bit", weight: "medium"},
{size: "small", clatters: "yes", weight: "light"}
];
function guessGifts(wish, present){
var dict = {};
var ret = [];
// normalize special key
var normalize = function(v){
return JSON.stringify({
size: v.size,
clatters: v.clatters,
weight: v.weight
});
};
wish.forEach(function(v){
var key = normalize(v);
dict[key] = v.name;
});
present.forEach(function(v){
var key = normalize(v);
if ( dict[key] ) {
ret.push(dict[key]);
}
});
return ret;
}
guessGifts(wishlist, presents); // must return ["Toy Car", "Mini Puzzle"]
给一个比较傻的方法,把属性转成string再比较 :)
var result = [];
var presentsString = [];
for (var p of presents) {
presentsString.push(JSON.stringify(p))
}
for (var v of wishlist) {
var name = v.name;
delete v.name;
for (var pp of presentsString) {
if (JSON.stringify(v) === pp) result.push(name);
}
}
console.log(result);
从2个数组的关系以及返回结果来看,应该就是presents中的属性与wishlist中的后三个属性相同,然后取wishlist中的name组成数组作为返回结果。因此我想到的解决方案如下:
转换wishlist的结构如下
var wishlistC = [
{
name: "Mini Puzzle",
info: {
...
}
},
...
];
比较
wishlistC[i].info
与presents[n]
,如果他们相等,则取到wishlistC[i].name
,然后组成数组返回。
思路很简单,这里有一个比较麻烦的地方就是如何比较2个对象相同,因此这边自己定义了一个方法用来比较
这里实现的这个方法比较健全,如果仅仅只是为了满足题主的问题,只需要遍历一下presents中的属性,能够在wishlist中找到并相等即可。有点类似楼上某位同学的fit方法
// 比较2个内容是否相等,他们可以是数组,对象,字符串,数字等
function equal(objectA, objectB) {
// 如果类型不同,不等
if (typeof objectA != typeof objectB) {
return false;
}
// array
if (objectA instanceof Array && objectB instanceof Array) {
if (objectA.length != objectB.length) {
return false;
};
var tagArray = true;
for(var i=0; i<objectA.length; i++) {
if (typeof objectA[i] != typeof objectB[i]) {
tagArray = false;
return tagArray;
};
if (typeof objectA[i] == 'number' || typeof objectA[i] == 'string') {
if (objectA[i] != objectB[i]) {
tagArray = false;
return tagArray;
};
} else {
tagArray = arguments.callee(objectA[i], objectB[i]);
}
return tagArray;
}
}
// object
if (objectA instanceof Object && objectB instanceof Object) {
var result = true,
lengthA = 0,
lengthB = 0;
for(var item in objectA) {
if (typeof objectA[item] == 'number' || typeof objectA == 'string') {
if (objectA[item] != objectB[item]) {
result = false;
return result;
};
} else {
if (!arguments.callee(objectA[item], objectB[item])) {
result = false;
return result;
};
}
lengthA ++;
}
for(var item in objectB) {
lengthB ++;
}
if (lengthA != lengthB) {
result = false;
};
return result;
};
return objectA == objectB;
}
那么接下来就比较简单了
function guessGifts(wishlist, presents) {
var wishlistC = [];
for(var i = 0; i<wishlist.length; i++) {
var demo = {
name: wishlist[i].name,
info: {}
};
for(var n in wishlist[i]) {
if (n != 'name') {
demo.info[n] = wishlist[i][n];
};
}
wishlistC.push(demo);
}
console.log(wishlistC);
var result = [];
for(var i in wishlistC) {
for(var m in presents) {
if (equal(wishlistC[i].info, presents[m])) {
result.push(wishlistC[i].name);
};
}
}
return result;
};
看了楼上的回答,这里解释一下为什么一定要比较对象相等,而不是为了降低时间复杂度比较拼接的字符串或者其他形式。因为对象中,属性的位置是没有顺序问题的,直接比较对象会更加灵活而满足需求。
因此总的来说,无论怎么转换,比较对象内容相等在我看来是不可避免的一步。
时间复杂度O(n+m)
function guessGifts(wishlist, presents) {
let re = [], wt = [],
size = {small: 1, medium: 2, large: 3 },
clatters = {no: 10, 'a bit': 20, yes: 30 },
weight = {light: 100, medium: 200, heavy: 300 }
for(item of wishlist) {
let w = size[item.size] + clatters[item.clatters] + weight[item.weight]
if(!wt[w]) {
wt[w] = []
}
wt[w].push(item.name)
}
for(item of presents) {
let w = size[item.size] + clatters[item.clatters] + weight[item.weight]
if(wt[w]) {
re = [...re, ...wt[w]]
delete wt[w]
}
}
return re
}
过了之后看了一下其他人的答案。。。虽然用全了特性,但是效率低,但是毕竟是javascript,谁在意性能呢;)
楼主,这是要根据关键字weight来关键字来关联两组数据???
var guessGifts = function (wishlist, presents) {
'use strict'
return presents.map(function(giftInfo) {
for(var i = 0; i < wishlist.length; i++) {
if(fit(wishlist[i], giftInfo)) {
return wishlist[i].name;
}
}
});
}
function fit(gift, giftInfo) {
'use strict'
for (var p in giftInfo) {
if(gift[p] !== giftInfo[p])
return false;
}
return true;
}
简单实现 时间复杂度o(n*m)。用到了ES5的数组map方法。在nodejs 5.3下测试通过。考虑到了不固定属性名。
一个比较懒的写法
function guessGifts(type1,type2){
var lastArr=[];
type1.forEach(function(item){
type2.forEach(function(subitem,index){
var k=0;
for(var i in subitem){
k++;
if(!item.hasOwnProperty(i) || item[i]!==subitem[i]){ break;}
if(k===type2.length) lastArr.push(item["name"]);
}
});
});
return lastArr;
}
下面时间复杂度为n²
function guessGifts (arr1, arr2) {
// 首先遍历数组2,找出条件
var keys = arr2.map(function (ele) {
var arr = [];
var keys = Object.keys(ele);
for (var i = 0, len = keys.length; i < len; i++) {
arr[i] = ele[keys[i]];
}
return arr;
});
// 根据条件数组筛选
var result = arr1.filter(function (ele) {
for (var i = 0, len = keys.length; i < len; i++) {
if (keys[i].indexOf(ele.clatters) !== -1 &&
keys[i].indexOf(ele.size) !== -1 &&
keys[i].indexOf(ele.weight) !== -1) {
return true;
}
}
return false;
});
// 取出筛选后数组的name
result = result.map(function (ele) {
return ele.name;
});
return result;
}
wishlist.length和presents.length的个数未知,并且里面的键值对也是未知的
var wishlist = [
{name: "Mini Puzzle", size: "small", clatters: "yes", weight: "light"},
{name: "Toy Car", size: "medium", clatters: "a bit", weight: "medium"},
{name: "Card Game", size: "small", clatters: "no", weight: "light"}
];
var presents = [
{size: "medium", clatters: "a bit", weight: "medium"},
{size: "small", clatters: "yes", weight: "light"}
];
function guessGifts(wishlist,presents){
var someWish=wishlist[0];
var keys=[];
for(var prop in someWish){
if(someWish.hasOwnProperty(prop)){
keys.push(prop);
}
}
var somePresent;
var matchScores={};
for(var i= 0,presentLengt=presents.length;i<presentLengt;i++){
somePresent=presents[i];
keys.forEach(function(key){
if(somePresent[key]){
wishlist.forEach(function(item,index){
if(item[key]===somePresent[key]){
//console.log('match value:%s presend:%d wishlist:%d',somePresent[key],i,index);
if(!matchScores[i+'_'+index]){
matchScores[i+'_'+index]={
score:0,
wishIndex:index
};
}
matchScores[i+'_'+index].score=matchScores[i+'_'+index].score+1;
}
});
}
});
}
var resut=[];
for(prop in matchScores){
if(matchScores.hasOwnProperty(prop)){
resut.push(matchScores[prop]);
}
}
resut.sort(function(itemA,itemB){
return itemB.score-itemA.score;
});
console.log(resut.slice(0,presents.length).map(function(item){
if(wishlist[item.wishIndex].name){
return wishlist[item.wishIndex].name;
}else{
return wishlist[item.wishIndex];
}
}));
}
guessGifts(wishlist, presents); // must return ["Toy Car", "Mini Puzzle"]
O(n)搞之,先遍历presents,把要求的东西存到一个标记数组里面,key可以设置为(size: "medium", clatters: "a bit", weight: "medium",key怎么存自己搞定),value为1,保证唯一,然后扫一下wishlist数组,看生成的key是否在标记数组里面,如果在则输出。尽提供思路。
最终版本
var guessGifts = function(wishlist, presents) {
var result = [];
_.each(presents, function(item) {
result.push(_.pluck(_.filter(wishlist, item), 'name'));
});
return _.flatten(result);
};
下面的内容为前面的版本
导入lodash插件,然后就简单了
var result = _.filter(wishlist, function(item) {
return _.some(presents, function(v) {
return v.size == item.size && v.weight == item.weight && v.clatters == item.clatters;
});
});
console.log(result);
简单版本
var result =[];
_.each(presents,function(item){
result.push(_.filter(wishlist,item));
});
console.log(result);
我也试个,尽量用一个for:
function guessGifts( wishlist, presents){
var gifts = newWishList = [];
for( var key in wishlist ){
var name = wishlist[key].name;
delete wishlist[key].name;
presents.filter(function( gift ){
if(JSON.stringify( gift ) === JSON.stringify( wishlist[key] )){
gifts.push( name );
}
});
}
return gifts;
}
var guessGift = guessGifts( wishlist, presents );
console.log( guessGift ); // ["Toy Car", "Mini Puzzle"]