最长公共子序列（Longest Common Subsequence LCS）

[HerokunTan]

第 59 题：给定两个数组，写一个方法来计算它们的交集。
当我第一眼看到这个问题的时候，我脑袋是空白的，空白的原因是问题的“数组”与“交集”同时出现，脑中的概念顿时模糊...
但随后，对这个问题脑子突然蹦出很多不同的答案...

问题：第 59 题：给定两个数组，写一个方法来计算它们的交集。
问题例题答案：例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。

既然有“交集”出现，那肯定得有"集合"吧...(我应该不是杠精)
集合的概念百度一下：数学集合

看两条集合的性质：
1.确定性：每一个对象都能确定是不是某一集合的元素，没有确定性就不能成为集合，例如“个子高的同学”“很小的数”都不能构成集合。这个性质主要用于判断一个集合是否能形成集合。
2.互异性：集合中任意两个元素都是不同的对象。如写成{1，1，2}，等同于{1，2}。互异性使集合中的元素是没有重复，两个相同的对象在同一个集合中时，只能算作这个集合的一个元素。

看到互异性的定义：数学中的“1”在自然数集合{N}中是唯一的。
但是在我们本题数组中的“1”我的理解并不是唯一的，“1”可以是nums[0]下标为0的“1”，也可以是nums[1]下标为1的“1”。
所以这里有把“数组”偷换成“集合”的味道了...，所以概念有点模糊...

粗暴的理解：找到一个算一个

const intersect = (nums1, nums2) => {
  const map = {}
  const res = []
  for (let n of nums1) {
    if (map[n]) {
      map[n]++
    } else {
      map[n] = 1
    }
  }
  for (let n of nums2) {
    if (map[n] > 0) {
      res.push(n)
      map[n]--
    }
  }
  return res
}

intersect([1,2,2,1],[2,1,2])  // 输出[2, 1, 2]
intersect([1,2,2,1],[2,2,3,1,1])  // 输出[2, 2, 1, 1]

理解为真正的集合

let intersect  = function(arr1,arr2){
    let a = new Set(arr1);
    let b = new Set(arr2);
    return Array.from(new Set([...a].filter(x => b.has(x))));
}
intersect([1,2,2,1,444,3],[2,1,2,3])  // 输出[1,2,3]

最长公共子序列

可参考:1143. 最长公共子序列

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
 const m = text1.length
 const n = text2.length
 const dp = []

//初始化全部为0
 for(let i=0;i<=m;i++){
    dp[i] = new Array(n+1).fill(0)
 }
 for(let i = 1;i<=m;i++){
     for(let j =1;j<=n;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[m][n]
};

但是这里的实现只是输出了“最长公共子序列”的长度
并没有实现输出所有的“最长公共子序列“的序列

如：s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}
最长公共子序列有两个： {3,4,6,7,8}，{3,5,7,7,8}

学习来源：

动态规划 最长公共子序列 过程图解
LCS 算法：Javascript 最长公共子序列

ps：现在每每看到“司徒正美” 四个字就想着要早点休息，保护颈椎。缅怀！