Tre*_*est 12 javascript algorithm
考虑这个嵌套的日期和名称数组:
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
]
如何识别那些不按顺序排列的日期.我不在乎日期重复,或跳过,我只是需要那些不按顺序.即,我应该回来:
results = [
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-15', 'namex'],
['1980-12-23', 'name2'],
]
('Namex'不太明显,但它不是列表的一般顺序.)
这似乎是最长增长子序列(LIS)问题的变化,但需要注意的是序列中可能有重复的日期,但不应该向后退一步.
使用案例:我已对记录进行了排序和记录,需要找到日期为"可疑"的日期 - 可能是输入错误 - 标记为检查.
NB1:我使用的是直接的Javascript而不是框架.(我在节点,但我正在寻找一个无包装的解决方案,所以我可以理解发生了什么...)
这是Rosetta Code LIS的改编版,用于定制getElement和compare功能.我们可以根据您的特定需求优化比较和元素获取功能.
function f(arr, getElement, compare){
function findIndex(input){
var len = input.length;
var maxSeqEndingHere = new Array(len).fill(1)
for(var i=0; i<len; i++)
for(var j=i-1;j>=0;j--)
if(compare(getElement(input, i), getElement(input, j)) && maxSeqEndingHere[j] >= maxSeqEndingHere[i])
maxSeqEndingHere[i] = maxSeqEndingHere[j]+1;
return maxSeqEndingHere;
}
function findSequence(input, result){
var maxValue = Math.max.apply(null, result);
var maxIndex = result.indexOf(Math.max.apply(Math, result));
var output = new Set();
output.add(maxIndex);
for(var i = maxIndex ; i >= 0; i--){
if(maxValue==0)break;
if(compare(getElement(input, maxIndex), getElement(input, i)) && result[i] == maxValue-1){
output.add(i);
maxValue--;
}
}
return output;
}
var result = findIndex(arr);
var final = findSequence(arr, result)
return arr.filter((e, i) => !final.has(i));
}
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
];
console.log(f(fDates, (arr, i) => arr[i][0], (a,b) => a >= b));此解决方案尝试获取所有有效序列并返回用于过滤部分的longes序列.
它通过迭代给定的数组并检查值是否可以构建序列来工作.如果给出了一个值,哪个部分结果具有有效的前导,则该数组将附加该值.如果没有进行回溯并且使用有效的前任搜索序列.
Run Code Online (Sandbox Code Playgroud)act. array value 7 3 4 4 5 1 23 7 comment ----- ------------------------ --------------------------- 7 7 add array with single value 3 7 keep 3 add array with single value 4 7 keep 3 4 add value to array 4 7 keep 3 4 4 add value to array 5 7 keep 3 4 4 5 add value to array 1 7 keep 3 4 4 5 keep 1 add array with single value 23 7 23 add value to array 3 4 4 5 23 add value to array 1 23 add value to array 7 7 23 keep 7 7 fork above, filter for smaller or equal and add value 3 4 4 5 23 keep 3 4 4 5 7 fork above, filter for smaller or equal and add value 1 23 keep 1 7 fork above, filter for smaller or equal and add value
function longestSequences(array, getValue = v => v) {
return array
.reduce(function (sub, value) {
var single = true;
sub.forEach(function (s) {
var temp;
if (getValue(s[s.length - 1]) <= getValue(value)) {
s.push(value);
single = false;
return;
}
// backtracking
temp = s.reduceRight(function (r, v) {
if (getValue(v) <= getValue(r[0])) {
r.unshift(v);
single = false;
}
return r;
}, [value]);
if (temp.length !== 1 && !sub.some(s => s.length === temp.length && s.every((v, i) => getValue(v) === getValue(temp[i])))) {
sub.push(temp);
}
});
if (single) {
sub.push([value]);
}
return sub;
}, [])
.reduce(function (r, a) {
if (!r || r[0].length < a.length) {
return [a];
}
if (r[0].length === a.length) {
r.push(a);
}
return r;
}, undefined);
}
function notInSequence(array, getValue = v => v) {
var longest = longestSequences(array, getValue);
return array.filter((i => a => a !== longest[0][i] || !++i)(0));
}
var array = [7, 3, 4, 4, 5, 1, 23, 7, 8, 15, 9, 2, 12, 13],
fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
usuallyFailingButNotHere = [['2015-01-01'], ['2014-01-01'], ['2015-01-02'], ['2014-01-02'], ['2015-01-03'], ['2014-01-03'], ['2014-01-04'], ['2015-01-04'], ['2014-01-05'], ['2014-01-06'], ['2014-01-07'], ['2014-01-08'], ['2014-01-09'], ['2014-01-10'], ['2014-01-11']],
test2 = [['1975-01-01'], ['2015-02-03'], ['2015-02-04'], ['2015-02-04'], ['2015-02-05'], ['1929-03-12'], ['2023-07-01'], ['2015-02-07'], ['2015-02-08']];
console.log(longestSequences(array));
console.log(notInSequence(array));
console.log(notInSequence(fDates, a => a[0]));
console.log(longestSequences(usuallyFailingButNotHere, a => a[0]));
console.log(notInSequence(usuallyFailingButNotHere, a => a[0]));
console.log(longestSequences(test2, a => a[0]));
console.log(notInSequence(test2, a => a[0]));.as-console-wrapper { max-height: 100% !important; top: 0; }