最长上升子序列、零钱兑换、链表中倒数第 K 个节点

最长递增子序列

题目描述

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3, 6, 2, 7] 是数组 [0, 3, 1, 6, 2, 2, 7] 的子序列。

示例：

输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]

输出：4

解释：最长递增子序列是 [2, 3, 7, 101]，因此长度为 4。

思路 1：动态规划

定义 dp[i] 为以 nums[i] 为结尾的最长子序列长度

题解

ts
function lengthOfLIS(nums: number[]): number {
  let dp = new Array(nums.length).fill(1);

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(1, ...dp);
}

思路 2：贪心 + 二分查找

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 lis[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，lis[1] = nums[0]。

因为 lis 总是在递增的基础上替换更小的数，所以 d 始终是递增的。根据 d 数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。

则整个算法流程为：设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i] 时：

如果 nums[i] > lis[len]，则直接加入到 lis 数组末尾，并更新 len = len + 1；
否则，在 lis 数组中二分查找，找到第一个比 nums[i] 小的数 lis[k]，并更新 lis[k + 1] = nums[i]。

直觉理解：lis 维护的是 “最优接续方式”。

如果 nums[i] 比 lis 末尾大，我们直接加进去，延长 LIS。
如果 nums[i] 不能延长 LIS，就找到 lis 里最小的、比它大的数，把它替换掉。这样未来如果有更大的数，它仍然可以接在 lis 后面。但 lis 长度不会变，保证 LIS 长度正确。

题解

ts
function lengthOfLIS(nums: number[]): number {
  let lis: number[] = [];

  for (let num of nums) {
    let left = 0,
      right = lis.length;

    while (left < right) {
      let mid = Math.floor((left + right) / 2);

      if (lis[mid] >= num) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }

    if (left < lis.length) {
      lis[left] = num;
    } else {
      lis.push(num);
    }
  }

  return lis.length;
}

零钱兑换

题目描述

给定一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

可以认为每种硬币的数量是无限的。

示例：

输入：coins = [1, 2, 5], amount = 11

输出：3

解释：11 = 5 + 5 + 1

思路 1：动态规划（自底向上）

ts
function coinChange(coins: number[], amount: number): number {
  const dp: number[] = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 组成 0 元需要 0 枚硬币

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

思路 2：记忆化搜索（动态规划 - 自顶向下）

注意：

仅当 rem !== -1 时才更新 minCount
dp 返回的 result 必须是 minCount === Infinity ? -1 : minCount，不能直接返回 minCount

ts
function coinChangeMemo(coins: number[], amount: number): number {
  const memo = new Map<number, number>();

  function dp(rem: number): number {
    if (rem === 0) {
      return 0;
    }
    if (rem < 0) {
      return -1;
    }
    if (memo.has(rem)) {
      return memo.get(rem)!;
    }

    let minCount = Infinity;
    for (const coin of coins) {
      const res = dp(rem - coin);
      if (res !== -1) {
        minCount = Math.min(minCount, res + 1);
      }
    }

    const result = minCount === Infinity ? -1 : minCount;
    memo.set(rem, result);

    return result;
  }

  return dp(amount);
}

链表中倒数第 K 个节点

题目描述

给定一个头节点为 head 的链表用于记录一系列编号，请查找并返回倒数第 k 个编号。

示例：

输入：head = [2, 4, 7, 8], k = 1

输出：8

思路：快慢指针

ts
function trainingPlan(head: ListNode | null, k: number): ListNode | null {
  let l = head,
    r = head;

  for (let i = 0; i < k; i++) {
    l = l.next;
  }

  while (l) {
    l = l.next;
    r = r.next;
  }

  return r;
}