关于javascript:JS-教练我想做习题14

???? 前言

大家好呀，我是毛小悠，能够叫我二毛，在家中排行老二，是一名前端开发工程师。

本系列文章旨在通过练习来进步 JavaScript 的能力，一起欢快的做题吧。????????????

以下每道题，二毛我都有尝试做一遍。倡议限时训练，比方限定为半小时，如果半小时内想不进去，能够联合文章开端的参考答案来思考。

能够在下方评论区留言或者加我的微信：code\_maomao。期待你的到来。

求关注求点赞 ????\~~~????????????

???? 题目 1：最小门路单位

您会失去一个由随机数组成的正方形，如下所示：

var square = [[1,2,3],
    [4,8,2],
    [1,5,3]];

您的工作是计算从左上角到给定坐标的最小总成本。您只能向右或向下挪动。

在下面的示例中，最小门路为：

var square = [[1,2,3],
    [_,_,2],
    [_,_,3]];

总共给出 11 个。包含开始和完结地位。

留神：坐标标记为程度 x 和垂直 y。

习题代码：

function minPath(grid, x, y) {}

???? 题目 2：二叉树遍历

给定二叉树的根节点（但不肯定是二叉搜寻树），编写三个函数，这些函数将按 pre-order,order 和 post-order 打印树。

节点具备以下属性：

var data; // A number or string.
Node left; // Undefined if there is no left child.
Node right; // Undefined if there is no right child.

一棵树的构造如下：

data Tree a = Nil | Node (Tree a) a (Tree a)

pre-order 意味着咱们
1.）访问根。
2.）遍历左侧子树（左侧节点）
3.）遍历右侧子树（右侧节点）。

按 order 程序示意咱们
1.）遍历左侧子树（左侧节点）
2.）拜访根。
3.）遍历右侧子树（右侧节点）。

post-order 订单意味着咱们
1.）遍历左侧子树（左侧节点）
2.）遍历右侧子树（右侧节点。）
3.）拜访根。

假如咱们有三个节点。

var a = new Node("A");
var b = new Node("B");
var c = new Node("C");

a.left = b;
a.right = c;

而后，preOrder（a）应该返回 [“A”，“B”，C“]
inOrder（a）应该返回 [”B“，”A“，”C“]
postOrder（a）应该返回 [”B“，“C”，A“]

如果咱们这样做会怎么？

var d = new Node("D");
c.left = d;

preOrder（a）应该返回 [“A”，“B”，“C”，“D”]
inOrder（a）应该返回 [“B”，“A”，“D”，“C”]
postOrder（a）应该返回 [“B”，“D”，“C”，“A”]

习题代码：

/*
A Node has the following properties:
var data; // A number or string.
Node left; // Undefined if there is no left child.
Node right; // Undefined if there is no right child.
*/

// 1.) Root node, 2.) traverse left subtree, 3.) traverse right subtree.
function preOrder(node)
{
}

// 1.) Traverse left subtree, 2.) root node, 3.) traverse right subtree.
function inOrder(node)
{
}

// 1.) Traverse left subtree, 2.) traverse right subtree, 3.) root node.
function postOrder(node)
{}

答案

???? 题目 1 的答案

参考答案 1：

function minPath(grid, x, y) {const [X, Y] = [0, 1];
  const row = new Array(x+1).fill(0);
  for (let i = 0; i <= y; ++i) {row[0] += grid[i][0];
    for (let j = 1; j <= x; ++j) {if (i === 0) { }
      if (i === 0) {row[j] = row[j-1] + grid[i][j];  
      } else {row[j] = Math.min(row[j-1], row[j]) + grid[i][j];
      }
    }
  }
  return row.pop();}

参考答案 2：

function minPath(grid, x, y) {grid = grid.map(row => row.slice());
  let row, col;
  for (row = y - 1; row >= 0; row--)
    grid[row][x] += grid[row + 1][x];
  for (col = x - 1; col >= 0; col--)
    grid[y][col] += grid[y][col + 1];
  for (row = y - 1; row >= 0; row--)
    for (col = x - 1; col >= 0; col--)
      grid[row][col] += Math.min(grid[row + 1][col], grid[row][col + 1]);
  return grid[0][0];
}

参考答案 3：

const minPath = (() => {const croppedCopy = (grid, x, y) => {const copy = [];
    for (let row = 0; row <= y; row++) {copy.push(grid[row].slice(0, x + 1))
    }
    return copy;
  };
  
  const processGrid = (grid) => {
    
    const maxRow = grid.length;
    const maxCol = grid[0].length;
  
    let row, col, current;
    
    for (col = 1; col < maxCol; col++) {grid[0][col] += grid[0][col - 1];
    }
    
    for (row = 1; row < maxRow; row++) {grid[row][0] += grid[row - 1][0];
    }
    
    for (row = 1; row < maxRow; row++) {for (col = 1; col < maxCol; col++) {current = grid[row][col];
        grid[row][col] = Math.min(current + grid[row - 1][col], current + grid[row][col - 1]);
      }
    }
  };

  return (grid, x, y) => {grid = croppedCopy(grid, x, y);
    processGrid(grid);
    return grid[y][x];
  };
  
})();

参考答案 4：

function minPath(grid, x, y) {const result = [...Array(grid.length).keys()].map(i => Array(grid.length).fill(0));
    result[0][0] = grid[0][0];

    for (let i = 1; i <= x; i++) {result[0][i] = grid[0][i] + result[0][i - 1];
    }
    for (let i = 1; i <= y; i++) {result[i][0] = grid[i][0] + result[i - 1][0];
    }

    for (let i = 1; i <= y; i++) {for (let j = 1; j <= x; j++) {result[i][j] = grid[i][j] + Math.min(result[i - 1][j], result[i][j - 1])
        }
    }
    return result[y][x];
}

参考答案 5：

function minPath(grid, x, y) {let minPaths = []
  let i, j;
  for (i = 0; i < grid.length; i++) {minPaths.push([])
    for (j = 0; j < grid[0].length; j++) {if (i == 0 && j == 0) {minPaths[i][j] = grid[i][j]
      } else if (j == 0) {minPaths[i][j] = minPaths[i-1][j] + grid[i][j]
      } else if (i == 0){minPaths[i][j] = minPaths[i][j-1] + grid[i][j]
      } else {minPaths[i][j] = Math.min(minPaths[i-1][j] + grid[i][j], minPaths[i][j-1] + grid[i][j])
      }

      if (i == y && j == x) {break}
    }
  }
  
  return minPaths[y][x]
}

???? 题目 2 的答案

参考答案 1：

/*
A Node has the following properties:
var data; // A number or string.
Node left; // Undefined if there is no left child.
Node right; // Undefined if there is no right child.
*/

// 1.) Root node, 2.) traverse left subtree, 3.) traverse right subtree.
function preOrder(node)
{if (node == undefined) {return [];
  }
  return [node.data].concat(preOrder(node.left)).concat(preOrder(node.right));
}

// 1.) Traverse left subtree, 2.) root node, 3.) traverse right subtree.
function inOrder(node)
{if (node == undefined) {return [];
  }
  return inOrder(node.left).concat(node.data).concat(inOrder(node.right));
}

// 1.) Traverse left subtree, 2.) traverse right subtree, 3.) root node.
function postOrder(node)
{if (node == undefined) {return [];
  }
  return postOrder(node.left).concat(postOrder(node.right)).concat([node.data]);
}

参考答案 2：

function preOrder(node) {return node == null || node.data == null ? [] : [node.data].concat(preOrder(node.left)).concat(preOrder(node.right));
}
function inOrder(node) {return node == null || node.data == null ? [] : inOrder(node.left).concat(node.data).concat(inOrder(node.right));
}
function postOrder(node) {return node == null || node.data == null ? [] : postOrder(node.left).concat(postOrder(node.right)).concat(node.data);
}

参考答案 3：

/*
A Node has the following properties:
var data; // A number or string.
Node left; // Undefined if there is no left child.
Node right; // Undefined if there is no right child.
*/
function traversal(node, path, res){return path.reduce(function(res, nodeName){
    var subnode;
    switch(nodeName) {
      case 'root':
        res.push(node.data);
        break;
      default:
        subnode = node[nodeName];
        if (subnode) {traversal(subnode, path, res);
        }
    }
    return res;
  }, res)
}

// 1.) Root node, 2.) traverse left subtree, 3.) traverse right subtree.

function preOrder(node)
{return traversal(node, ['root', 'left', 'right'], []);
}

// 1.) Traverse left subtree, 2.) root node, 3.) traverse right subtree.
function inOrder(node)
{return traversal(node, ['left', 'root', 'right'], []);
}

// 1.) Traverse left subtree, 2.) traverse right subtree, 3.) root node.
function postOrder(node)
{return traversal(node, ['left', 'right', 'root'], []);
}

参考答案 4：

function Node(value) {
  this.data = value;
  this.left = null;
  this.right = null;
}

function preOrder(node, values) {values = values || [];
  if (node) {values.push(node.data);
    values = preOrder(node.left, values);
    values = preOrder(node.right, values);
  }
  return values;
}

function inOrder(node, values) {values = values || [];
  if (node) {values = inOrder(node.left, values);
    values.push(node.data);
    values = inOrder(node.right, values);
  }
  return values;
}

function postOrder(node, values) {values = values || [];
  if (node) {values = postOrder(node.left, values);
    values = postOrder(node.right, values);
    values.push(node.data);
  }
  return values;
}

参考答案 5：

const preOrder = n => n ? [n.data, ...preOrder(n.left), ...preOrder(n.right)] : [];
const inOrder = n => n ? [...inOrder(n.left), n.data, ...inOrder(n.right)] : [];
const postOrder = n => n ? [...postOrder(n.left), ...postOrder(n.right), n.data] : [];

???? 后序

本系列会定期更新的，题目会由浅到深的逐步提高。

求关注求点赞 ????~~????????????

能够关注我的公众号： 前端毛小悠 。欢送浏览