Vấn đề
Chúng tôi được yêu cầu viết một hàm JavaScript nhận một mảng chuỗi, arr, được tạo thành chỉ bằng 0 và 1 làm đối số đầu tiên.
Hàm nhận hai số là đối số thứ hai và thứ ba, m và tương ứng. Nhiệm vụ của hàm của chúng ta là tìm bao nhiêu chuỗi từ mảng arr có thể được tạo bằng cách sử dụng tối đa m 0 và n 1.
Ví dụ:nếu đầu vào của hàm là -
const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3;
Sau đó, kết quả đầu ra phải là -
const output = 4;
Giải thích đầu ra:
Có tổng cộng 4 chuỗi có thể được tạo thành bằng cách sử dụng 5 số 0 và 3 số 1, đó là -
“10,”0001”,”1”,”0”
Ví dụ
Mã cho điều này sẽ là -
const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3; const findAllStrings = (arr = [], m = 1, n = 1) => { const getCount = str => str.split('').reduce((acc, cur) => { cur === '0' ? acc.zeros++ : acc.ones++; return acc; }, {zeros:0, ones:0}); const dp = Array.from({length: m+1}, () => Array(n+1).fill(0)); for(let i = 0; i < arr.length; i++) { const {zeros, ones} = getCount(arr[i]); for(let j = m; j >= zeros; j--) { for(let k = n; k >= ones; k--) { dp[j][k] = Math.max(dp[j-zeros][k-ones]+1, dp[j][k]); } } } return dp[m][n] }; console.log(findAllStrings(arr, m, n));
Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
4