Tìm số lần lật nhỏ nhất trong một chuỗi nhị phân bằng JavaScript

Chuỗi tăng đơn điệu:

Chuỗi số '0 và' 1 sẽ tăng đơn điệu nếu nó bao gồm một số số '0 (có thể là 0), theo sau là một số số' 1 (cũng có thể là 0)

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy chuỗi nhị phân, str, làm đối số đầu tiên và duy nhất.

Chúng ta có thể lật bất kỳ từ ‘0’ nào sang ‘1’ hoặc bất kỳ từ ‘1’ nào thành ‘0’ có trong chuỗi. Hàm của chúng ta sẽ trả về số lần lật nhỏ nhất để làm cho S tăng đơn điệu.

Ví dụ:nếu đầu vào của hàm là

Đầu vào

const str = '00110';

Đầu ra

const output = 1;

Giải thích đầu ra

Bởi vì nếu chúng ta lật ‘0’ cuối cùng thành ‘1’, chúng ta sẽ chỉ còn lại chuỗi ‘00111’.

Ví dụ

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