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] : [];

?后序

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

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

可以关注我的公众号：前端毛小悠。欢迎阅读