#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
    }


  • 0

    const invertTree = (arr) => {
          var i = 1
          var newArr = [...arr.splice(0, 1).reverse()]
          while (i > 0) {
            newArr = [...newArr, ...arr.splice(0, Math.pow(2, i)).reverse()]
            if (arr.length <= 0) {
              break;
            }
            i++;
          }
          // newArr = newArr.filter(x=>x !== undefined)
          return newArr.filter(x=>x !== undefined)
        }
    

    这样写有问题么?为什么一直不对?我本地测试都没问题了啊.以下是错误信息

    Wrong Answer
    invertTree 应该能将反转过的二叉数还原


  • 0

     const invertTree = (tree) => {
      /* TODO */
    	let arr = [];
            let i = 0;
    while(tree.length>0){
      arr.push(...(tree.splice(0,Math.pow(2,i)).reverse()))
    	i++;
    }
    return arr;
    }
    

    为什么不对啊


  • 0

    const invertTree = (tree) => {
    /* TODO */
    let arr = [];
    let i = 0;
    while(tree.length>0){
    arr.push(...(tree.splice(0,Math.pow(2,i)).reverse()))
    i++;
    }
    return arr;
    }


  • 0

    const invertTree = (tree) => {
    /* TODO */
    let arr = [];
        let i = 0;
    while(tree.length>0){
    arr.push(...(tree.splice(0,Math.pow(2,i)).reverse()))
    i++;
    }
    return arr;
    }
    

    为什么不对啊


  • 0

    const invertTree = (tree) => {
      let depth = 0
      const res = []
    
      while (res.length < tree.length) {
        let end = 2 ** (depth + 1) - 1
        let breadth  = 2 ** depth
    
        let i = 0
    
        while (i < breadth) {
          res.push(tree[end - 1 - i])
    
          i += 1
        }
    
        depth += 1
      }
    
      return res
    }
    

  • 0

    function invertIndexXY(arr, x, y) {
        let tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
    function invertTree(arrTree) {
        if (!Array.isArray(arrTree)) return;
        let level = Math.trunc(Math.log2(arrTree.length + 1));
        for(let i = level; i > 0; i -= 1) {
            let levelLeftIndex = Math.pow(2, i - 1) - 1;
            let levelLength =  Math.pow(2, i - 1);
            for (let j = 0; j < levelLength/2; j += 1) {
                invertIndexXY(arrTree, j + levelLeftIndex, levelLength + levelLeftIndex - j - 1);
            }
        }
        return arrTree;
    }
    

  • 0

    主要是要通过数组先得到二叉树的最大层数, 然后再对每层reverse


登录后回复
 

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