共计 6281 个字符,预计需要花费 16 分钟才能阅读完成。
???? 前言
大家好呀,我是毛小悠,能够叫我二毛,在家中排行老二,是一名前端开发工程师。
本系列文章旨在通过练习来进步 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] : [];
???? 后序
本系列会定期更新的,题目会由浅到深的逐步提高。
求关注求点赞 ????~~????????????
能够关注我的公众号: 前端毛小悠 。欢送浏览