การสร้างสตริงโดยใช้ 0 และ 1 ใน JavaScript

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของสตริง arr ซึ่งสร้างโดยใช้ 0 และ 1 เป็นอาร์กิวเมนต์แรกเท่านั้น

ฟังก์ชันใช้ตัวเลขสองตัวเป็นอาร์กิวเมนต์ที่สองและสาม m และตามลำดับ หน้าที่ของฟังก์ชันของเราคือค้นหาจำนวนสตริงจากอาร์เรย์ arr ที่สามารถสร้างได้โดยใช้ค่าสูงสุด m 0s และ n 1s

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

const arr = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;

จากนั้นผลลัพธ์ควรเป็น −

const output = 4;

คำอธิบายผลลัพธ์:

มีทั้งหมด 4 สายที่สามารถเกิดขึ้นได้โดยใช้ 5 0s และ 3 1s ซึ่งก็คือ −

“10,”0001”,”1”,”0”

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

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));

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

4