Giả sử, chúng ta được yêu cầu viết một hàm nhận một mảng làm đầu vào và trả về phần tử tối đa của mảng chứa không quá hai số khác nhau. Nếu chúng tôi kiểm tra chặt chẽ vấn đề này, điều này liên quan đến việc kiểm tra một mảng con ổn định và lặp lại trên mảng ban đầu.
Do đó, thuật toán cửa sổ trượt rất thích hợp cho việc này. Mã để giải quyết vấn đề này thông qua thuật toán cửa sổ trượt sẽ là -
Ví dụ
const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1,
1, 8, 8];
const map = {
length: 0
};
let required = [];
for(start = 0, end = 0; end <= arr.length; ){
if(map.length > 2){
if(map[arr[start]] === 1){
delete map[arr[start]];
map.length --;
}else{
map[arr[start]]--;
};
start++;
}else{
if(end - start > required.length){
required = arr.slice(start, end);
};
if(map[arr[end]]){
map[arr[end]]++;
}else{
map[arr[end]] = 1;
map.length++;
}
end++;
}
}
console.log(required); Chúng tôi duy trì một bản đồ để lưu trữ số lượng các ký tự khác biệt tại bất kỳ điểm nào trong mảng và so sánh độ dài của mảng con dài nhất tại mỗi lần lặp, khi số ký tự phân biệt vượt quá 2, chúng tôi trượt mảng sang phải tìm kiếm mảng ổn định tiếp theo.
Đầu ra
Đầu ra trong bảng điều khiển sẽ là -
[ 1, 8, 1, 1, 1, 1, 8, 1, 1, 8, 8 ]