陈恒承

与 1 共舞

问题描述:对于给定正整数 n,计算长度为 n 的 0-1 字符串中有多少个与 1 共舞的数字。
与 1 共舞 ：每个 0 左边必须要有一个 1 与其相邻

如：

• n=3, 生成的字符串组合有 000,001,010,011,100,101,110,111。与 1 共舞的 有 110 111，101.

• n=1 , 组合 0,1 与 1 共舞的 1

我们通过构造组合发现如下规律

       000
  100    010   001
 110 101   011
111

可以看到它的构造是有规律的，以 000 为根，进行广度优先遍历。横向遍历，纵向递归。

横向遍历：直到 变化到最后一位
纵向递归：一上一次替换之后的字符串为基础，保持已经替换的，开始从未替换的开始，直到变化到最后一位

与 1 共舞的条件也容易：

遍历组合，如果当前是 0 且 前一位是 0，那么不是，或者 如果当前位 0，且第一位为 0，那么不是 与一共舞的组合

function outputWithOneUnitBody(n) {
  let initStrArr = new Array(n).fill(0);
  // console.log(initStrArr);
  insteadOfStr(initStrArr, 0, n);
}
function insteadOfStr(strArr, changeIndex, n) {
  if (changeIndex === n) {
    return;
  } else {
    for (let h = changeIndex; h < n; h++) {
      let replaceStr = strArr.concat();
      replaceStr.splice(h, 1, 1);
      // 只要判断，1的右边是0 就可以了
      // if (replaceStr[h + 1] === 0) {
      //   console.log(replaceStr);
      // }
      if (isWithOne(replaceStr)) {
        console.log(replaceStr);
      }
      insteadOfStr(replaceStr, h + 1, n); // 替换
    }
  }
}

function isWithOne(arr) {
  for (let i = 0; i < arr.length; i++) {
    if ((arr[i] === 0 && i === 0) || (arr[i] === 0 && arr[i - 1] === 0)) {
      return false;
    }
  }

  return true;
}

// console.log(isWithOne([1, 0, 0]));

generateCompose(5);

总结

应该是求二进制数的过程去判断才对，我这个想法太直接了，只是实现了而已，完全不考虑什么算法复杂度