資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告