【JavaScript】LeetCode：91-95

文章目录

• 91 不同路径
• 92 最小路径和
• 93 最长回文子串
• 94 最长公共子序列
• 95 编辑距离

91 不同路径

• 动态规划
• dp[i][j]：从[0, 0]到[i, j]的路径条数。
• dp[i][j] = 从[0, 0]到[i, j]上面一格的路径条数 + 从[0, 0]到[i, j]左边一格的路径条数。
• 初始化：因为第一行的格子只能由左侧格子向右移动到达，第一列的格子只能上面格子向下移动到达，所以第一行和第一列均初始化为1。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = Array(m).fill(Array(n).fill(0));
    for(let i = 0; i < m; i++){
        dp[i][0] = 1;
    }
    for(let j = 0; j < n; j++){
        dp[0][j] = 1;
    }
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
};

92 最小路径和

• 动态规划
• dp[i][j]：从[0, 0]到[i, j]的最小路径和。
• dp[i][j] = min(到[i, j]上面一格的最小路径和, 到[i, j]左边一格的最小路径和) + [i, j]的值。
• 初始化：第一行为从[0, 0]到[0, j]的累加和，第一列为从[0, 0]到[i, 0]的累加和。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let m = grid.length;
    let n = grid[0].length;
    let dp = Array(m).fill(0).map(() => Array(n).fill(0));
    dp[0][0] = grid[0][0];
    for(let i = 1; i < m; i++){
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for(let j = 1; j < n; j++){
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
};

93 最长回文子串

• 中心扩展法
• 遍历字符串，以每个字符(i)为中心，向左(left)右(right)扩展。
• 情况一：回文串中的元素个数为奇数，此时left = right = i。
• 情况二：回文串中的元素个数为偶数，此时left = i，right = i + 1。
• 不断更新最长回文子串的长度和起始位置。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res_len = 0;
    let res_start = 0;
    for(let i = 0; i < s.length; i++){
        let left = i;
        let right = i;
        while(left >= 0 && right < s.length && s[left] == s[right]){
            if(right - left + 1 > res_len){
                res_len = right - left + 1;
                res_start = left;
            }
            left--;
            right++;
        }

        left = i;
        right = i + 1;
        while(left >= 0 && right < s.length && s[left] == s[right]){
            if(right - left + 1 > res_len){
                res_len = right - left + 1;
                res_start = left;
            }
            left--;
            right++;
        }
    }
    return s.slice(res_start, res_start + res_len);
};

94 最长公共子序列

• 动态规划
• dp[i][j]：text1[0, i - 1]和text2[0, j - 1]的最长公共子序列的长度。
• 初始化：第一行和第一列其中一个字符串为空串，最长公共子序列的长度为0，因此初始化为0。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let dp = Array(text1.length + 1).fill(0).map(() => Array(text2.length + 1).fill(0));
    for(let i = 1; i <= text1.length; i++){
        for(let j = 1; j <= text2.length; j++){
            if(text1[i - 1] == text2[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]);
            }
        }
    }
    return dp[text1.length][text2.length];
};

95 编辑距离

• 动态规划
• dp[i][j]：word1[0, i - 1]转换为word2[0, j - 1]的最少操作次数。
• 若word1[i - 1] != word1[j - 1]，则对应三种操作方式：删除、添加和替换。
  删除：word1[0, i - 2]转换为word2[0, j - 1]的最少操作次数 + 1(word1删除word1[i - 1])。
  添加：word1[0, i - 1]转换为word2[0, j - 2]的最少操作次数 + 1(word1添加word2[j - 1])。
  替换：word1[0, i - 2]转换为word2[0, j - 2]的最少操作次数 + 1(word1[i - 1]替换为word2[j - 1])。
• 初始化：第一行和第一列其中一个字符串为空串，最少操作次数为另一个非空串的元素数，因此初始化为i和j。

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let dp = Array(word1.length + 1).fill(0).map(() => Array(word2.length + 1).fill(0));
    for(let i = 0; i <= word1.length; i++){
        dp[i][0] = i;
    }
    for(let j = 0; j <= word2.length; j++){
        dp[0][j] = j;
    }
    for(let i = 1; i <= word1.length; i++){
        for(let j = 1; j <= word2.length; j++){
            if(word1[i - 1] == word2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
    }
    return dp[word1.length][word2.length];
};