Vấn đề
Chúng tôi được yêu cầu viết một hàm JavaScript nhận một mảng các số nguyên không âm, arr, làm đối số đầu tiên và một Số nguyên, num, (num
Nhiệm vụ của hàm của chúng ta là chia mảng thành các mảng con liên tục không rỗng. Mảng phải được phân chia theo cách sao cho nó giảm thiểu tổng lớn nhất trong số các mảng con num này. Khi đó, hàm của chúng ta sẽ trả về tổng lớn nhất được tích lũy giữa các mảng con.
Ví dụ:nếu đầu vào của hàm là -
Sau đó, đầu ra phải là -
Mặc dù có bốn cách để chia mảng ban đầu thành các mảng con nhưng nếu chúng ta chia mảng thành hai nhóm [5, 1, 4] và [8, 7] thì hai nhóm này sẽ có tổng nhỏ nhất và lớn hơn trong hai nhóm này là 8 + 7 =15 mà hàm của chúng ta sẽ trả về.
Mã cho điều này sẽ là -
Ở đây, chúng tôi đã sử dụng Tìm kiếm nhị phân để kiểm tra xem chúng tôi có thể tìm thấy phân tách tốt nhất hay không.
Đầu ra trong bảng điều khiển sẽ là - const arr = [5, 1, 4, 8, 7];
const num = 2;
const output = 15;
Giải thích đầu ra
Ví dụ
const arr = [5, 1, 4, 8, 7];
const num = 2;
const splitArray = (arr = [], num = 1) => {
let max = 0;
let sum = 0;
const split = (arr, mid) => {
let part = 1;
let tempSum = 0;
for (let num of arr) {
if (tempSum + num > mid) {
tempSum = num;
part++;
} else {
tempSum += num;
}
}
return part;
};
for (let num of arr) {
max = Math.max(max, num);
sum += num;
};
let low = max;
let high = sum;
while (low < high) {
let mid = Math.floor((high+low)/2);
let part = split(arr, mid);
if (part > num) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
console.log(splitArray(arr, num)); Giải thích mã:
Đầu ra
15