Chúng tôi được yêu cầu viết một hàm JavaScript để xác định có bao nhiêu cách khác nhau mà chúng tôi có thể xóa một nhóm giá trị khỏi một trình tự, giữ nguyên trình tự ban đầu theo thứ tự (ổn định) và đảm bảo chỉ xóa một giá trị phiên bản khỏi chuỗi ban đầu.
Ví dụ - Nếu mảng trình tự là -
const arr = [1, 2, 1, 3, 1, 4, 4];
Và mảng được xóa là -
const arr2 = [1, 4, 4];
Sau đó, có ba cách khả thi để làm điều này mà không làm gián đoạn thứ tự của các phần tử -
1 --> [2, 1, 3, 1] 2 --> [1, 2, 3, 1] 3 --> [1, 2, 1, 3]
Do đó, hàm của chúng ta sẽ xuất ra 3 cho các chuỗi này. Mã cho điều này sẽ là -
Ví dụ
const arr = [1, 2, 1, 3, 1, 4, 4];
const arr2 = [1, 4, 4];
const possibleRemovalCombinations = (original, part) => {
const sorter = (a, b) => a - b;
part.sort(sorter);
let place = [];
part.forEach(el => {
place[el] = []
});
original.forEach((el, index) => {
if(place[el]){
place[el].push(index);
}
});
let connection = part.map(el => place[el].slice());
for(let i = 1; i < connection.length; i++){
if (part[i - 1] != part[i]){
continue;
}
let left = connection[i - 1][0];
while(connection[i][0] <= left){
connection[i].shift();
};
};
for (let i = connection.length - 2; i >= 0; i--) {
if(part[i] != part[i + 1]){
continue;
}
let right = connection[i + 1][connection[i + 1].length - 1];
while(connection[i][connection[i].length - 1] >= right){
connection[i].pop();
};
};
const combineArray = (step, prev, combination) => {
for (let i = 0; i < connection[step].length; i++) {
let curr = connection[step][i];
if(prev >= curr && original[prev] == original[curr]){
continue;
}
if(step + 1 == connection.length){
combinations.push(combination.concat([curr]))
}
else {
combineArray(step + 1, curr, combination.concat([curr]));
};
};
};
let combinations = [], res = [];
combineArray(0, -1, []);
for (let i = 0; i < combinations.length; i++) {
let copy = original.slice();
combinations[i].forEach(el => copy[el]);
res[i] = copy.filter(el => el !== undefined);
};
return res.length;
};
console.log(possibleRemovalCombinations(arr, arr2)); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
3