leetcode 刷题 log day 53

• 1143. 最长公共子序列
  【思路】分别遍历两个数组，如果元素相等，长度 +1，长度不相等，就比较两个数组的前一个元素哪个最长公共子序列长。

  var longestCommonSubsequence = function(text1, text2) {
      let dp = new Array(text1.length + 1).fill().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];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

• 1035. 不相交的线
  【思路】线就是两数相等，不相交就是按顺序来，本质和上一道题一样～

var maxUncrossedLines = function(nums1, nums2) {
    let dp = new Array(nums1.length + 1).fill().map(() => Array(nums2.length + 1).fill(0));

    for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j<= nums2.length; j++) {
            if(nums1[i - 1] === nums2[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[nums1.length][nums2.length];
};
1
2
3
4
5
6
7
8
9
10
11

• 53. 最大子序和（动态规划）
  【思路】dp[i] 代表到第 i 个元素为止最大的子序列和。计算 dp[i] 时考虑两种情况：上一个的和加上现在的元素（dp[i] = dp[i - 1] + nums[i]）或者从当前元素开始计算（dp[i] = nums[i]），取两种情况的最大值即可。

  // 贪心
  var maxSubArray = function(nums) {
      let res = -Infinity, count = 0;
      for (let i = 0; i < nums.length; i++){
          count += nums[i];
          if (count > res) res = count;
          if (count < 0) count = 0;  // 如果总和小于 0 了，就下一个位置开始重新计和
      }
      return res;
  };
  
  // 动规
  let maxSubArray = function(nums) {
    let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
  
    for (let i = 1; i < nums.length; i++) {
      dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
  
    return Math.max(...dp);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

参考代码随想录：https://www.programmercarl.com/