ค้นหาการพลิกขั้นต่ำในสตริงไบนารีโดยใช้ JavaScript

การเพิ่มสตริงแบบโมโนโทน:

สตริงของ '0 และ '1' จะเพิ่มขึ้นอย่างซ้ำซากจำเจ หากประกอบด้วยจำนวนหนึ่งของ '0 (อาจเป็น 0) ตามด้วยจำนวน '1' (อาจเป็น 0)

ปัญหา

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

เราสามารถพลิก '0' เป็น '1' หรือ '1' เป็น '0' ใดก็ได้ที่อยู่ในสตริง ฟังก์ชันของเราควรคืนค่าจำนวนการพลิกขั้นต่ำเพื่อทำให้ S เพิ่มขึ้นอย่างซ้ำซากจำเจ

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

ป้อนข้อมูล

const str = '00110';

ผลผลิต

const output = 1;

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

เพราะถ้าเราพลิก '0' สุดท้ายเป็น '1' เราจะเหลือสตริง '00111'

ตัวอย่าง

const str = '00110';
const countFlips = (str = '') => {
   const map = {}
   const helper = (index, prev) => {
      map[index] = map[index] || {}
      if (map[index][prev] !== undefined) {
         return map[index][prev]
      }
      if (index >= str.length) {
         return 0
      }
      if (prev === '0') {
         if (str[index] === '0') {
            map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1)
      } else {
         map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1)
      }
      } else if (str[index] === '0') {
         map[index][prev] = helper(index + 1, '1') + 1
      } else {
         map[index][prev] = helper(index + 1, '1')
      }
         return map[index][prev]
      }
   return helper(0, '0')
};
console.log(countFlips(str));

ผลลัพธ์

1