数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究JavaScript 中包含递增序列的二维数组的最长路径
递增序列
一个序列中的每个后续元素都大于或等于前一个元素的数字序列称为递增序列。
例如，
4, 6, 8, 9, 11, 14 is increasing sequence 3, 3, 3, 3, 3, 3, 3 is also an increasing sequence
问题
我们需要编写一个 JavaScript 函数，该函数将一个二维数字数组 arr 作为唯一参数。我们的函数应该找到并返回数组中包含仅递增数字的最长路径的长度。
例如，如果函数的输入为 -
const arr = [ [4, 5, 6], [4, 3, 7], [3, 3, 2] ];
则输出应为 -
const output = 4;
输出说明
因为最长的递增序列是 4、5、6、7。
示例
代码如下 -
const arr = [
[4, 5, 6],
[4, 3, 7],
[3, 3, 2]
];
const longestIncreasingPath = (arr = []) => {
let longest = 0;
let dp = Array(arr.length).fill(null).map(() =>
Array(arr[0].length).fill(1));
const backtracking = (row, col) => {
if (dp[row][col]!=1) return dp[row][col];
let dRow = [1,0,-1,0];
let dCol = [0,1,0,-1];
for (let i = 0;i<dRow.length;i++) {
let nR = row + dRow[i], nC = col+dCol[i];
if (nR >= 0 && nR < arr.length && nC >= 0 && nC < arr[0].length && arr[nR][nC] > arr[row][col]) {
dp[row][col] = Math.max(dp[row][col], 1 + backtracking(nR, nC))
};
};
return dp[row][col];
}
for (let i=0;i<arr.length;i++) {
for (let j=0;j<arr[0].length;j++) {
longest = Math.max(longest, backtracking(i, j));
};
};
return longest;
};
console.log(longestIncreasingPath(arr));代码说明
思路
这里我们使用了回溯深度优先搜索。
递归函数简单地返回给定行和列的最长递增路径
如果我们已经记录了某个位置的最长递增路径，那么我们可以直接返回它。
输出
控制台输出为 -
4
更新于: 2021年3月19日
268 次查看
广告