#75 最高产的猪


  • 0
    administrators

    我们用一个 HTML 结构来表示一头猪的子子孙孙:

    <div class="pig">
      <div class="pig">
        <div class="pig">
          <div class="pig"></div>
        </div>
        <div class="pig">
          <div class="pig"></div>
        </div>
        <div class="pig">
          <div class="pig"></div>
        </div>
      </div>
      <div class="pig">
        <div class="pig"></div>
        <div class="pig"></div>
      </div>
      <div class="pig">
        <div class="pig">
          <div class="pig"></div>
          <div class="pig"></div>
          <div class="pig"></div>
          <div class="pig"></div>
          <div class="pig"></div>
        </div>
      </div>
    </div>
    

    每个 DOM 节点都是一头猪,子节点就是这头猪的孩子。

    请你完成一个函数 findMostProductivePigChildrenCount 它接受一个 DOM 节点作为参数,返回一个数组。存放同代猪最高产的猪的孩子的数量。例如:

    1:          o
    2:    o     o     o
    3:  o o o  o o    o
    4:  o o o       ooooo 
    

    上面的结果是 [3, 3, 5, 0],解释如下:

    第一代猪有三个孩子,所以数组第一项是 3。

    第二代的三头猪中,第一头猪生了 3 个,第二头猪生了 2 个,第三头猪生了 1 个。最高产的是第一头猪,它的孩子数是 3,所以数组第二项为 3。

    第三代的前三头猪都有一个后代,中间两头猪绝后,而最后一头猪惊人地生出了 5 头猪。这一代最高产的猪的孩子数是 5,所以数组项是 5。

    最后一代无后,所以是 0。


  • 0

    @ScriptOJ 可以帮我看一下哪个用例出错了吗


  • 0
    administrators

    @myboy

    <div class="pig"></div>
    

    应该是这个。应该会返回 [0]


  • 0

    @ScriptOJ 本地是[0]啊


  • 0
    administrators

    @myboy 你的解法调用之间会互相影响。你试一下调用两次,两次结果是不一样的。


  • 0

    这里考察的应该是广度优先遍历数组

    const findMostProductivePigChildrenCount = (dom) => {
      const result = []
      
      function find(pigs, result) {
        let most = 0 //当代猪最高产的小猪数量
        let piggies = [] //当代猪的后一代
        
        for(let p of pigs) {
          if(p.childElementCount) {
            piggies.push(...p.children)
            if(p.childElementCount > most) {
              most = p.childElementCount
            }
          }
        }
        result.push(most)
        if(piggies.length) {
          //继续搜索下一代
          find(piggies, result)
        }
      }
      
      find([dom], result)
      
      return result
    }
    

    前端表单验证工具 https://github.com/WLDragon/SMValidator


  • 0

    效率有丁点小低,代码有点小简的解决方案

    const findMostProductivePigChildrenCount = (dom) => {
      let a = [...dom.children]
      let b = [dom.children.length]
      while (a.length) {
          let c = []
          b.push(Math.max(...a.map(v => v.children.length)))
          a.forEach(v => {
              c.push(...v.children)
          })
          a = c
      }
      return b
    }
    

登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待