javascript - 最长连续历史记录问题

Question

我遇到了这个难题，并试图解决它，然而，我不能让它运行！
我很难找到合适的数据结构来存储用户点击。
问题：
编写一个函数，将两个用户的浏览历史记录作为输入，然后
返回出现在两者中的最长连续URL序列。
样本输入：
用户0=[“/start”，“/pink”，“/register”，“/orange”，“/red”，“a”]
用户1=[“/start”、“/green”、“/blue”、“/pink”、“/register”、“/orange”、“/one/two”]
样本输出：
[“/pink”、“/register”、“/orange”]
这是我的尝试：

function findContiguousHistory(u1, u2) {
    const res = {}; // { 1: ['/start'], 3: ['/pink', '/register', '/orange']}
    let count = 0;
    let temp = [];
  
    for(let i=0; i<u1.length; i++){
      for(let j=0; j<u2.length; j++){
        const curA = u1[i];
        const curB = u2[j];
  
        if(curA === curB) {
          temp.push(curA); // pink
          break; // continue;
        } else {
          res[temp.length] = temp;
          temp = [];// reset the array.
        }
      } 
    }
        
    const max = Math.max.apply(this, Object.keys(res)); // 3
  
    return res[max]; // ['/pink', '/register', '/orange']
  }
  
  const user0 = ["/start", "/pink", "/register", "/orange", "/red", "a"];
  const user1 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"];
  
  console.log(findContiguousHistory(user0, user1));

我在试着看看如何解决这个问题任何帮助都将不胜感激。

Answer 1

这是一个动态规划问题。在下面的解决方案中，我创建了二维数组来跟踪最长的匹配子序列，直到每个点最后，结果将显示在二维数组的右下角。下面是代码：

   

    function Create2DArray(rows) {
      var arr = [];
    
      for (var i=0;i<rows;i++) {
         arr[i] = [];
      }
    
      return arr;
    }
    
    function lcs(a , b, m, n) {
      var arr = Create2DArray(m+1);
    
      for(i = 0; i <= m; i++) {
        for(j = 0; j <= n; j++) {
          if(i == 0 || j == 0)
            arr[i][j] = 0
          else if(a[i-1] == b[j-1])
            arr[i][j] = arr[i-1][j-1] + 1;
          else
            arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1])
        }
      }
    
      return arr[m][n];
    }
    
    const user0 = ["/pink", "/register", "/orange", "/red", "a", "/start"];
    const user1 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"];
    
    console.log(lcs(user0, user1, user0.length, user1.length));