使用 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