使用 JavaScript 在二进制字符串中查找最小翻转

Z时代
2024-01-10
分类：综合

单调递增的字符串：

如果一串“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));