Javascript 的最长递增子序列问题

Question

我为最长递增子序列生成了这段代码：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列为[2,3,7,101]，因此长度为4

var lengthOfLIS = function(nums) {
  if (nums.length === 0) return 0;
  let result = 1;
  const LISEndAt = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    LISEndAt[i] = Math.max(1,
      ...LISEndAt.slice(0, i).map((item, j) => {
        return nums[i] > nums[j] ? item + 1 : 0
      }));

    result = Math.max(LISEndAt[i], result);
  }
  
  return result;
}

let nums = [7,7,7,7,7,7,7];

console.log(lengthOfLIS(nums));

谁能帮我理解这一行：

LISEndAt[i] = Math.max(1,...LISEndAt.slice(0, i).map((item, j)

three dots 的意义是什么，我们知道 map 生成键值对，map 和 slice 一起做什么？

Answer 1

澄清

在我解释您所询问的行的作用之前，有几件事需要弄清楚。

`...`

... 是 spread syntax 扩展给定的可迭代对象（数组索引、对象 key-value 对等）。这是一个示例，其中现有数组用于创建包含更多元素的新数组：

const first = [1, 2, 3];
const second = [...first, 4, 5, 6];
console.log(second);
/* returns [1, 2, 3, 4, 5, 6] */

在您的示例中，它用于向 Math.max() 函数提供多个参数。这是一个例子：

const candidates = [1, 5, 6, 2, 4];
const largest = Math.max(...candidates);
console.log(largest);
/* returns 6 */

数组#map

Array#map 不会创建 key/value 对。相反，它通过对原始数组中的每个元素执行操作来创建一个新数组。这是一个通过将原始数组中的每个项目加倍来创建新数组的示例：

const original = [1, 2, 3];
const doubled = original.map(i => i * 2);
console.log(doubled);
/* returns [2, 4, 6] */

您还可以访问原始数组中每一项的索引：

const alphabet = ['A', 'B', 'C'];
const positions = alphabet.map((letter, index) => index);
console.log(positions);
/* returns [0, 1, 2] */

数组#slice

Array#slice 创建一个新数组，该数组是从提供的起始索引到（但不包括）提供的结束索引的原始数组的子集。这是一个从现有数组的前三项创建新数组的示例：

const superset = [1, 2, 3, 4, 5, 6];
const subset = superset.slice(0, 3);
console.log(subset);
/* returns [1, 2, 3] */

你的问题

考虑到所有这些，让我们看一下包含您的行的循环：

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
const LISEndAt = new Array(nums.length).fill(1);
/* [1, 1, 1, 1, 1, 1, 1, 1] */

for (let i = 1; i < nums.length; i++) {
    LISEndAt[i] = Math.max(1,
        ...LISEndAt.slice(0, i).map((item, j) => {
            return nums[i] > nums[j] ? item + 1 : 0;
        }));
}

LISEndAt 随 for-loop 的每次迭代而更新。每次，下一个索引计算为：

1 中任意元素的最大值：
LISEndAt 的子集，从 0 到 for-loop 的当前迭代，修改者为：
map 中的一些比较，其中 returns 是：
正在修改的当前索引处的项目加一或：
零。

如果我们在您的循环中添加一些日志记录，您可以看到这会按顺序发生：

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
const LISEndAt = new Array(nums.length).fill(1);
console.log(`original: ${JSON.stringify(LISEndAt)}`);

for (let i = 1; i < nums.length; i++) {
  const subset = LISEndAt.slice(0, i);
  console.log(`sliced: [${subset.join(', ')}]`);
  const someArray = subset.map((item, j) => {
    console.log(`comparing ${nums[i]} > ${nums[j]} ? ${item + 1} : 0`);
    return nums[i] > nums[j] ? item + 1 : 0;
  });
  console.log(`taking max of 1, ${JSON.stringify(...someArray)}`);
  LISEndAt[i] = Math.max(1, ...someArray);
  console.log(`iteration ${i}: ${JSON.stringify(LISEndAt)}`);
}

Javascript 的最长递增子序列问题

Longest Increasing Subsequence Problem with Javascript

javascript

data-structures

ecmascript-6

澄清

`...`

数组#map

数组#slice

你的问题