Tìm số lần lật bit tối thiểu trong chuỗi nhị phân dùng JavaScript

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

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

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một chuỗi nhị phân str làm đối số duy nhất. Chúng ta có thể lật bất kỳ '0' thành '1' hoặc '1' thành '0'. Hàm phải trả về số lần lật tối thiểu để chuỗi trở thành đơn điệu tăng.

Ví dụ, nếu đầu vào là:

Đầu vào

const str = '00110';

Đầu ra

const output = 1;

Giải thích

Vì nếu lật '0' cuối cùng thành '1', ta được chuỗi '00111'.

Ví dụ

Dưới đây là mã thực hiện:

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

Kết quả

1