美团前端题目一，子序列选取
题目的要求：找到权值最大的序列中最长子序列的长度
思路：滑动窗口。利用map存放子序列的权重和，以及该权重对应的最长子序列的长度。如果权重为0，那么保存当前权重及子串长度。然后重开一个窗口，直到遇到 0 或者 退出。
const a = [2, 0, 1, 1, 2]
// const str = 'abcd'
console.log(a);
let len = 0;
let left = 0;
let right = 0;
let weight = 1;
const m = new Map();
// 从不为0的第一个数开始
while (a[left] === 0) {
left++;
right++;
}
for (; right < a.length; right++) {
if (a[right] === 0) {
len = right - left;
m.set(weight, (m.get(weight) > len ? m.get(weight) : len))
weight = 1;
len = 0;
left = right;
// 找到不为 0的数，重新开始算权重
while (a[left] === 0) {
left++;
right++;
}
}
weight *= a[right];
// console.log('weight', weight);
}
if (right - left > len) {
len = right - left;
m.set(weight, (m.get(weight) > len ? m.get(weight) : len))
}
let maxWeight = 0;
for (k of m) {
if (k[0] > maxWeight) {
maxWeight = k[0]
len = k[1]
}
}
console.log(m);
console.log(len);
console.log(''); 
查看18道真题和解析
投递字节跳动等公司8个岗位 >