#53 你会被谷歌拒绝吗?


  • 0
    administrators

    Max Howell 参加了谷歌的面试,出题人竟然要求 Max Howell 在白板上作出解答,Max Howell 当然愤怒地拒绝了,回家以后马上在微博上跟我们分享他的吐槽:

    Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

    看来在白板上作出反转二叉树的解答并不容易呢?那么在 ScriptOJ 有上 OJ 系统会不会更方便一些呢?

    假如有这样一个二叉树,

              4
            /   \
          3      2
        /  \    / \
      7     1  2   3
     / \   /   
    6   5 9
    

    使用广度优先的原则用数组的表示就是 [4, 3, 2, 7, 1, 2, 3, 6, 5, 9, null, null, null, null, null],二叉树中的空位用 null 表示。

    进行反转以后会变成

              4
            /   \
          2      3
        /  \    /  \
      3     2  1     7
                \   /  \  
                 9 5    6
    

    使用广度优先的原则用数组的表示就是 [4, 2, 3, 3, 2, 1, 7, null, null, null, null, null, 9, 5, 6]

    请实现函数 invertTree,它接受一个表示二叉树的数组,返回表示这个反转二叉树的数组。

    请注意,提交后提示中显示的 1,2,3,,,4,5 表示的是 1, 2, 3, null, null, 4, 5


  • 0
    administrators

    这道题刚想出,厉害了。


  • 2

    分享一下做题的思路,抓住两点, 1.给出的数组是广度优先遍历的结果。 2. 给出的数组是满二叉树的结果。


  • 4

    这破题根本不用正经求解的。。。

    const invertTree = tree => tree.reduce((p, c, i) => {
      const ti = (i + 1).toString(2).length
      p[ti] = p[ti] || []
      p[ti].push(c)
      return p
    }, []).map(x => x.reverse()).reduce((p, c) => [...p, ...c], [])
    

  • 0

    @ScriptOJ
    const invertTree = (tree) => {
    /* TODO */
    var newTree = [];
    var k = 0;

    for(var i = 0; Math.pow(2, i) < tree.length; i ++)
    {
    var currArr = [];

    currArr = tree.slice(k, k + Math.pow(2, i));
    currArr.reverse();
    for(var j = 0; j < currArr.length; j ++)
    {
      newTree.push(currArr[j]);
    }
    k += Math.pow(2, i);
    

    }
    return newTree;
    }
    这样写有什么问题吗?为什么一直说length undefined?


  • 0

    const invertTree = (tree) => {
    let i = 1;
    if(tree.length<1)
    return [];
    let newTree = [tree[0]];
    while(Math.pow(2,i)<=tree.length+1){
    newTree.push(...tree.slice(Math.pow(2, i)-1,Math.pow(2, i+1)-1).reverse());
    i++;
    }
    return newTree;
    }


  • 0

    const invertTree = (tree) => {
      let count = 1
      let lastIndex = 0
      let reverseTree = []
      while(lastIndex < (tree.length+count)){
        reverseTree = reverseTree.concat(tree.slice(lastIndex,lastIndex+count).reverse())
        lastIndex += count
        count = count * 2
      }
      return reverseTree
    }
    

  • 0

    @ScriptOJ const invertTree = tree=> {
    let ret = []
    for(let cur=1; tree.length > cur; cur<<=1) {
    let mask = cur - 1
    for(let x=0; x < cur; ++x)
    ret.push(tree[mask+(mask^x)])
    }
    return ret
    }


登录后回复
 

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