LRU 缓存、数组中的第 K 个最大元素、最长回文子串

LRU 缓存

题目描述

请设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。

• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出：

[null, null, null, 1, null, -1, null, -1, 3, 4]

解释：

tsCopy
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

思路

1. 注意要先在类里声明成员变量，用 private 标识。

2. map 的容量用 map.size 获得。

3. 最久未使用的 key 通过 cache.keys().next().value 获得。

题解

tsCopy
class LRUCache {
  private size: number;
  private cache: Map<number, number>;

  constructor(capacity: number) {
    this.size = capacity;
    this.cache = new Map();
  }

  get(key: number): number {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    }
    return -1;
  }

  put(key: number, value: number): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
      this.cache.set(key, value);
      return;
    }
    if (this.cache.size >= this.size) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

数组中的第 K 个最大元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例:

输入: [3,2,1,5,6,4], k = 2

输出: 5

思路：维护一个小顶堆

如何维护：

1. 创建一个 heap 数组模拟小顶堆。顶端元素下标为 0，则若父节点下标是 n，子节点下标便是 2n + 1 和 2n + 2（可以用 0, 1, 2 类比）

2. 创建一个 swap 函数，用于交换 a 和 b 下标代表的数字，便于后续交换父子节点

3. 创建一个 up 函数。若 idx === 0 则直接返回；否则比较父子节点。若 comparator(f, s) > 0，则 swap 父子，然后递归调用 up 函数冒泡到父节点下标继续 swap

4. 创建一个 down 函数，各自处理两个子节点，判断左右子节点哪个更小，再让父节点跟最小的子节点交换

5. 创建一个 peak 函数，用于获取并移除顶端元素。先通过 heap[0] 获取顶端元素，然后再用 peak.pop() 获得最后一个元素，把它放在顶端，然后从 0 下标开始 down

6. 创建一个 insert 函数，用于插入新元素。新元素直接 push 到 heap 数组末尾，然后从它的下标 heap.size() 处开始 up

7. 在 solution 函数里，我们就可以在 nums.lenth 的范围里循环，一边 insert nums[i]，一边判断当容量大于 k 时 peak 顶端最小的元素出来。

因为第 k 个大数应当是大数里最小的，大于 k 这个容量的小数都被移除了，剩下的这个堆顶元素就应该是第 k 大的

特别注意

1. 求父节点下标：const f = (i - 1) >> 1

2. insert 方法里的下标是 this.size() - 1，别忘了 -1

3. comparator(this.heap[f], this.heap[i]) > 0，注意这里比较的应该是值 heap[i]，而不是直接传下标 i

4. down 里需要判断左右子节点哪个更小，再跟那个节点交换。不能两个都交换

题解

tsCopy
function findKthLargest(nums: number[], k: number): number {
  const h = new Heap((a, b) => a - b);

  for (let i = 0; i < nums.length; i++) {
    h.insert(nums[i]);
    if (h.size() > k) {
      h.peak();
    }
  }

  return h.peak();
}

class Heap {
  private heap: number[];
  private comparator: (a: number, b: number) => number;

  constructor(comparator: (a: number, b: number) => number) {
    this.heap = [];
    this.comparator = comparator;
  }

  size(): number {
    return this.heap.length;
  }

  swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  up(i: number): void {
    if (i === 0) return;
    const f = (i - 1) >> 1;
    if (this.comparator(this.heap[f], this.heap[i]) > 0) {
      this.swap(f, i);
      this.up(f);
    }
  }

  down(i: number): void {
    const l = 2 * i + 1,
      r = 2 * i + 2;
    let smallest = i;

    if (
      l < this.size() &&
      this.comparator(this.heap[l], this.heap[smallest]) < 0
    ) {
      smallest = l;
    }
    if (
      r < this.size() &&
      this.comparator(this.heap[r], this.heap[smallest]) < 0
    ) {
      smallest = r;
    }
    if (smallest !== i) {
      this.swap(i, smallest);
      this.down(smallest);
    }
  }

  peak(): number | undefined {
    if (this.size() === 0) return undefined;
    const first = this.heap[0];
    const last = this.heap.pop();
    if (this.size() > 0) {
      this.heap[0] = last!;
      this.down(0);
    }
    return first;
  }

  insert(value: number): void {
    this.heap.push(value);
    this.up(this.size() - 1);
  }
}

最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。

示例：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

思路 1：中心扩展法

遍历字符串中的每一个字符，并以该字符为中心向两边扩展，直到无法形成回文

需要考虑回文长度是奇数（中心只有一个）或偶数（中心有两个）的情况

题解

tsCopy
function longestPalindrome(s: string): string {
  let max = 0,
    start = 0;

  const solution = (left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }

    const maxLen = right - left - 1;
    if (maxLen > max) {
      max = maxLen;
      start = left + 1;
    }
  };

  for (let i = 0; i < s.length; i++) {
    solution(i, i);
    solution(i, i + 1);
  }

  return s.substring(start, start + max);
}

思路 2：动态规划

核心思想：如果 s[i + 1:j - 1] 是回文，并且 s[i] === s[j]，则 s[i:j] 也是回文。

状态转移方程：定义 dp[i][j] 标识 s[i:j] 是否是回文

边界条件：

• 单个字符一定是回文：dp[i][j] === true

• 两个相同的相邻字符是回文：若 s[i] === s[i+1]，则 dp[i][i + 1] = true

• 三个及以上的字符串是回文：若 s[i] === s[j] 且 dp[i + 1][j - 1] === true，则 dp[i][j] = true

注意：

1. len > 2 这里的边界条件。外循环是先循环 len，让 len 从 3 开始一直到 n的情况；内循环是循环字符串开始的下标 i，i 的终止条件是 i <= n - len，而 j 的对应取值是 i + len - 1（因为 len = j - 1 + 1）

2. 初始的 max 应该是 1，因为至少存在单个字符，使得它成为一个长度为 1 的回文串

3. 在 len = 2 的情况下也要更新 start 和 max

题解

tsCopy
function longestPalindrome(s: string): string {
  let max = 1,
    start = 0,
    n = s.length;

  if (n < 2) {
    return s;
  }

  let dp = Array.from({ length: n }, () => new Array(n).fill(false));

  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      max = 2;
    }
  }

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        max = len;
      }
    }
  }

  return s.substring(start, start + max);
}