Javascript常见算法（二）【学习】
动态规划
-
斐波那契数列：
经典的动态规划问题，每个数是前两个数的和。
斐波那契数列（Fibonacci sequence）是一个非常著名的数列，其中每个数是前两个数的和，序列以0和1开始。在JavaScript中，有多种方式可以实现斐波那契数列，下面是一些常见的方法：
方法1：递归
递归是实现斐波那契数列最直接的方式，但它对于较大的数字来说效率很低，因为它会重复计算很多相同的值。
function fibonacciRecursive(n) { if (n <= 1) return n; return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
} console.log(fibonacciRecursive(10)); // 输出: 55方法2：动态规划（使用数组）
为了避免递归中的重复计算，我们可以使用动态规划。这种方法通过存储已经计算过的值来避免重复计算。
function fibonacciDP(n) { if (n <= 1) return n; let fibArray = [0, 1]; for (let i = 2; i <= n; i++) { fibArray[i] = fibArray[i - 1] + fibArray[i - 2]; } return fibArray[n];
} console.log(fibonacciDP(10)); // 输出: 55方法3：动态规划（不使用额外空间）
如果你想要进一步优化空间使用，可以不使用数组，而只保留前两个值。
function fibonacciIterative(n) { if (n <= 1) return n; let a = 0, b = 1, sum; for (let i = 2; i <= n; i++) { sum = a + b; a = b; b = sum; } return b;
} console.log(fibonacciIterative(10)); // 输出: 55方法4：使用生成器
如果你想要一个可以逐个生成斐波那契数列中数字的方法，可以使用生成器。
function* fibonacciGenerator() { let a = 0, b = 1; while (true) { yield a; [a, b] = [b, a + b]; }
} const fibGen = fibonacciGenerator();
for (let i = 0; i < 10; i++) { console.log(fibGen.next().value); // 输出斐波那契数列的前10个数字
}
生成器：JavaScript：4分钟学会生成器函数_哔哩哔哩_bilibili
在JavaScript中，生成器（Generators）是一种特殊的函数，它可以暂停执行和恢复执行，并且可以通过yield关键字返回多次。生成器函数使用function*声明，而不是普通的function声明。生成器非常适合于处理异步操作或需要逐步生成值的场景。
基本用法
生成器函数返回一个迭代器对象，这个对象包含next(), return(), throw()等方法。调用next()方法会使生成器函数执行到下一个yield表达式，并返回包含value和done属性的对象。value是yield表达式的结果（如果没有yield表达式，则为undefined），done是一个布尔值，表示生成器是否已经完成执行。
示例
下面是一个简单的生成器函数示例，它逐个生成数字1到3
function* generateNumbers() { yield 1; yield 2; yield 3;
} const gen = generateNumbers(); console.log(gen.next()); // { value: 1, done: false }
console.log(gen.next()); // { value: 2, done: false }
console.log(gen.next()); // { value: 3, done: false }
console.log(gen.next()); // { value: undefined, done: true }异步生成器
从ES2018开始，JavaScript引入了异步生成器（Async Generators），允许生成器处理异步操作。异步生成器函数使用async function*声明，并且可以在yield关键字后面跟上一个Promise。
异步生成器示例
async function* asyncGenerator() { yield Promise.resolve(1); yield Promise.resolve(2); yield Promise.resolve(3);
} const asyncGen = asyncGenerator(); async function run() { for await (const value of asyncGen) { console.log(value); // 依次打印 1, 2, 3 }
} run();在这个示例中，asyncGenerator是一个异步生成器函数，它逐个yield出解析为数字的Promise。在run函数中，我们使用for await...of循环来遍历这个异步生成器，它能够自动处理每个yield的Promise，并在每个Promise解决后打印其值。
-
最长公共子序列（LCS）：
寻找两个序列共有的最长子序列的问题。
在JavaScript中，最长公共子序列（Longest Common Subsequence, LCS）是一个在计算机科学中常见的问题。它旨在找到两个序列共有的最长子序列的长度（或具体序列），这里的子序列不需要在原序列中连续出现，但保持相对顺序。
以下是一个用动态规划方法解决LCS问题的JavaScript示例，这个示例将计算并返回两个字符串的最长公共子序列的长度：
function longestCommonSubsequence(str1, str2) { // 创建一个二维数组来保存子问题的解 // dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度 const dp = new Array(str1.length + 1).fill(null).map(() => new Array(str2.length + 1).fill(0)); // 填充 dp 数组 for (let i = 1; i <= str1.length; i++) { for (let j = 1; j <= str2.length; j++) { if (str1[i - 1] === str2[j - 1]) { // 如果当前字符相等，则当前位置的最长公共子序列长度等于左上方位置加一 dp[i][j] = dp[i - 1][j - 1] + 1; } else { // 如果当前字符不相等，则取左边和上边的最大值 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // dp[str1.length][str2.length] 存储了最长公共子序列的长度 return dp[str1.length][str2.length];
} // 示例
console.log(longestCommonSubsequence("AGGTAB", "GXTXAYB")); // 输出 4，因为最长公共子序列是 "GTAB" 或 "GTAY"如果你想要获取具体的最长公共子序列（而不仅仅是长度），则需要对上述算法进行一些修改，以追踪构建LCS的字符。这通常涉及到记录如何达到每个dp[i][j]值（例如，通过回溯或使用额外的空间来存储决策）。
以下是一个修改后的版本，用于获取具体的最长公共子序列：
function longestCommonSubsequenceRecursive(str1, str2, i, j, memo = {}) { if (i === 0 || j === 0) return ''; if (memo[i] && memo[i][j] !== undefined) return memo[i][j]; if (str1[i - 1] === str2[j - 1]) { memo[i][j] = str1[i - 1] + longestCommonSubsequenceRecursive(str1, str2, i - 1, j - 1, memo); } else { const left = longestCommonSubsequenceRecursive(str1, str2, i - 1, j, memo); const up = longestCommonSubsequenceRecursive(str1, str2, i, j - 1, memo); if (left.length > up.length) { memo[i][j] = left; } else { memo[i][j] = up; } } return memo[i][j];
} function longestCommonSubsequence(str1, str2) { return longestCommonSubsequenceRecursive(str1, str2, str1.length, str2.length);
} // 示例
console.log(longestCommonSubsequence("AGGTAB", "GXTXAYB")); // 输出 "GTAB" 或 "GTAY"（取决于递归的分支选择）注意：第二个版本使用了递归和记忆化（memoization）来避免重复计算，这在实际应用中可以显著提高效率，特别是当输入字符串很长时。然而，它使用了额外的空间来存储中间结果。