如何在从第一步到最后一步的二维数组中找到所有可能的路径，其中每一步的值都大于前一步？
如何在从第一步到最后一步的二维数组中找到所有可能的路径，其中每一步的值都大于前一步？
提问于 2020-07-20 04:48:51
到目前为止，我得到的代码只找到了两个可能的路径。我怎么才能把它们都找出来呢？
有效路径的一个示例是，从第一个数组[1, 32]开始。选择一个数字作为步长，如32。
看看下面的下一个数组：[11, 21, 24, 27, 35, 37, 65]。有效的步骤应该是这些数字中的任何一个大于您当前的步骤。所以35、37和65都是有效的步骤。
然后继续构建路径，按顺序(从上到下)逐步到其他数组，直到到达最后一个数组。
'use strict';
const matrix = [
[1, 32],
[11, 21, 24, 27, 35, 37, 65],
[17, 22, 25, 51, 57, 63],
[18, 56]
];
function findPaths(arrays) {
const paths = [];
for (let i = 0; i < arrays[0].length; i++) {
const path = [arrays[0][i]];
for (let j = 1; j < arrays.length; j++) {
for (let y = 0; y < arrays[j].length; y++) {
if (path[Math.max(0, path.length - 1)] < arrays[j][y]) {
path.push(arrays[j][y]);
break;
}
}
}
paths.push(path);
}
return paths;
}
const result = findPaths(matrix);
console.log(result); // [ [ 1, 11, 17, 18 ], [ 32, 35, 51, 56 ] ]
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-07-20 05:01:29
我解决了。这不是最有效的解决方案，但我正在努力。
const data = [
[1, 32],
[11, 21, 24, 27, 35, 37, 65],
[17, 22, 25, 51, 57, 63],
[18, 56]
];
function findPaths(arrays) {
const paths = [];
const maxPaths = arrays.reduce((total, arr) => total *= arr.length || total, 1);
for (let x = 0; x < maxPaths; x++) {
for (let i = 0; i < arrays[0].length; i++) {
const path = [arrays[0][i]];
for (let j = 1; j < arrays.length; j++) {
for (let y = 0; y < arrays[j].length; y++) {
if (path[Math.max(0, path.length - 1)] < arrays[j][y]) {
if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {
path.push(arrays[j][y]);
break;
}
}
}
}
paths.push(path);
}
}
return paths.filter(path => path.length == arrays.length).sort();
}
const result = findPaths(data);
console.log(result);
/*
[
[ 1, 11, 17, 18 ], [ 1, 11, 17, 56 ],
[ 1, 11, 22, 56 ], [ 1, 11, 25, 56 ],
[ 1, 11, 51, 56 ], [ 1, 21, 22, 56 ],
[ 1, 21, 25, 56 ], [ 1, 21, 51, 56 ],
[ 1, 24, 25, 56 ], [ 1, 24, 51, 56 ],
[ 1, 27, 51, 56 ], [ 1, 35, 51, 56 ],
[ 1, 37, 51, 56 ], [ 32, 35, 51, 56 ],
[ 32, 37, 51, 56 ]
]
*/
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62988827
复制相关文章
相似问题
社区富文本编辑器全新改版！诚邀体验～
全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验
腾讯云开发者
