题目：复原IP地址，leetcode

题解： 第一眼看到这个题目时，我首先想到的是使用递归循环拆分，后面实现时发现ip格式比较固定，只需要将字符串拆分为四块。 说到分块问题就必须想到切蛋糕和割绳子的问题，这里ip地址又有点不同（无需考虑顺序），我们只需要在字符串中插入几个.。 这里就可以把问题简化成从字符串的空位中选择3个位置插入.，又回到了上一篇从m个数中选择n个数的组合

实现代码如下：

 // 0~10 
const s = '25525511135'
// 从m个数中选择n个数的组合
const test = function(m, n) {
  if (n < 1 || m < n) return []
  const result = []
  // 初始化选中下标
  let str = '1'.repeat(n) + '0'.repeat(m - n)
  result.push(str.split(''))
  while(str.indexOf('10') >= 0) {
    // 找到第一个10 替换成01
    const idx = str.indexOf('10')
    str = str.slice(0, idx) + '01' + str.slice(idx + 2)
    // 移动idx左边的到最左边
    let prefix = str.slice(0, idx)
    const oneArr = str.slice(0, idx).match(/[1]/g)
    if (oneArr && oneArr.length) {
      prefix = '1'.repeat(oneArr.length) + '0'.repeat(prefix.length - oneArr.length)
    }
    str = prefix + str.slice(idx)
    result.push(str.split(''))
  }
  return result
}
// 从字符串的间隔s.length - 1中选择3个位置放‘.’
const arr = test(s.length - 1, 3)
const ipValid = []
for(let i = 0; i < arr.length; i++) {
  const idxArr = arr[i].map((i, idx) => i == '1' ? (idx + 1) : 0).filter(i => i > 0)
  const ipArr = [s.slice(0, idxArr[0]), s.slice(idxArr[0], idxArr[1]), s.slice(idxArr[1], idxArr[2]), s.slice(idxArr[2])]
  // console.log(idxArr, ipArr)
  if (ipArr.every(ip => !ip.startsWith('0') && parseInt(ip) <= 255 && parseInt(ip) > 0)) {
    ipValid.push(ipArr.join('.'))
  }
}
console.log(ipValid)