#53 你会被谷歌拒绝吗?


  • 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


  • 0

    这样写感觉挺简单的,先拆分再倒序再合并

    const invertTree = (tree) => {
       let num = 0, len = 0, point = 0, arr = [];
       while (len < tree.length) {
           point = len;
           len += 2**num;
           arr = arr.concat(tree.slice(point, len).reverse());
           num++;
       }
       return arr;
    }

  • 0

    BFS:: 先右节点index,再左节点index
    const invertTree = (tree) => {
      if (!Array.isArray(tree) || tree.length <= 1) {
        return tree;
      }
      let ans = [];
      let q = [0];
      while (q.length > 0) {
        let nodeIndex = q.shift();
        ans.push(tree[nodeIndex]);
        //left = 2n + 1; right = 2n + 2
        let left = 2 * nodeIndex + 1;
        let right = 2 * nodeIndex + 2;
        if (right < tree.length) {
          q.push(right);
        }
        if (left < tree.length) {
          q.push(left)
        }
      }
      return ans;
    }
    

  • 0

    0_1549438422034_#53 你会被谷歌拒绝吗?.png
    看来我是个老实人...


登录后回复
 

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