leetcode 中等(设计)：[146, 155, 208, 211, 284, 304, 307, 341, 355, 380]

• 146. LRU 缓存
• 155. 最小栈
• 208. 实现 Trie (前缀树)
• 211. 添加与搜索单词 - 数据结构设计
• 284. 顶端迭代器
• 304. 二维区域和检索 - 矩阵不可变
• 307. 区域和检索 - 数组可修改
• 341. 扁平化嵌套列表迭代器
• 355. 设计推特
• 380. O(1) 时间插入、删除和获取随机元素

146. LRU 缓存

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
};
LRUCache.prototype.get = function (key) {
  if (this.map.has(key)) {
    let value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }
  return -1;
};

LRUCache.prototype.put = function (key, value) {
  this.map.delete(key);
  this.map.set(key, value);
  if (this.map.size > this.capacity) {
    this.map.delete(this.map.keys().next().value);
  }
};

155. 最小栈

var MinStack = function () {
  this.data = [];
};

MinStack.prototype.push = function (val) {
  this.data.push(val);
};
MinStack.prototype.pop = function () {
  this.data.pop();
};
MinStack.prototype.top = function () {
  return this.data[this.data.length - 1];
};
MinStack.prototype.getMin = function () {
  return Math.min(...this.data);
};

208. 实现 Trie (前缀树)

var Trie = function () {
  this.data = {};
};

Trie.prototype.insert = function (word) {
  this.data[word] = word;
};

Trie.prototype.search = function (word) {
  return !!this.data[word];
};

Trie.prototype.startsWith = function (prefix) {
  for (const key in this.data) {
    if (this.data[key].startsWith(prefix)) {
      return true;
    }
  }
  return false;
};

211. 添加与搜索单词 - 数据结构设计

var WordDictionary = function () {
  this.data = {};
};

WordDictionary.prototype.addWord = function (word) {
  if (!this.data[word.length]) {
    // 键为单词长度，值为同长度的单词集合
    this.data[word.length] = [];
  }
  this.data[word.length].push(word);
};

WordDictionary.prototype.search = function (word) {
  const len = word.length;
  if (!this.data[len]) return false;
  if (!word.includes(".")) return this.data[len].includes(word); // 普通字符串，直接从等长单词集合中查找即可

  // 否则是正则表达式，先创建正则表达式对象
  const reg = new RegExp(word);
  return this.data[len].some((item) => reg.test(item));
};

284. 顶端迭代器

var PeekingIterator = function (iterator) {
  this.data = [];
  while (iterator.hasNext()) this.data.push(iterator.next());
  this.index = 0;
  this.size = this.data.length;
};

PeekingIterator.prototype.peek = function () {
  return this.data[this.index];
};

PeekingIterator.prototype.next = function () {
  return this.data[this.index++];
};

PeekingIterator.prototype.hasNext = function () {
  return this.index < this.size;
};

304. 二维区域和检索 - 矩阵不可变

var NumMatrix = function (matrix) {
  this.data = matrix;
};

NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  let sum = 0;
  for (let i = row1; i <= row2; i++) {
    for (let j = col1; j <= col2; j++) {
      sum += this.data[i][j];
    }
  }
  return sum;
};

307. 区域和检索 - 数组可修改

var NumArray = function (nums) {
  this.data = nums;
};
NumArray.prototype.update = function (index, val) {
  this.data[index] = val;
};
NumArray.prototype.sumRange = function (left, right) {
  let sum = 0;
  for (let i = left; i <= right; i++) {
    sum += this.data[i];
  }
  return sum;
};

341. 扁平化嵌套列表迭代器

// 方法一：
var NestedIterator = function (nestedList) {
  this.list = [];
  this.traverse(nestedList);
};
NestedIterator.prototype.traverse = function (arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i].isInteger()) {
      this.list.push(arr[i].getInteger()); // 是Integer
    } else {
      this.traverse(arr[i].getList()); // 是List，递归调用
    }
  }
};
NestedIterator.prototype.hasNext = function () {
  return this.list.length > 0;
};
NestedIterator.prototype.next = function () {
  return this.list.shift();
};

// 方法二：
var NestedIterator_1 = function (nestedList) {
  this.list = nestedList
    .toString()
    .split(",")
    .filter((val) => {
      return val != "";
    });
};
NestedIterator_1.prototype.toString = function () {
  if (this.isInteger()) {
    return this.getInteger() + "";
  } else {
    return this.getList().toString();
  }
};
NestedIterator_1.prototype.hasNext = function () {
  return this.list.length > 0;
};
NestedIterator_1.prototype.next = function () {
  return this.list.shift();
};

355. 设计推特

var Twitter = function () {
  this.tweets = {};
  this.user = {};
  this.time = 0;
};
Twitter.prototype.postTweet = function (userId, tweetId) {
  if (!this.tweets[userId]) {
    this.tweets[userId] = [];
  }
  this.tweets[userId].push({ tweetId, twitTime: this.time++ });
};

Twitter.prototype.getNewsFeed = function (userId) {
  let followsId = Array.from(this.user[userId] || {});
  followsId.push(userId);
  const allTwitters = followsId
    .reduce((prev, next) => prev.concat(this.tweets[next] || []), [])
    .sort((a, b) => b.twitTime - a.twitTime)
    .map((item) => item.tweetId);
  return Array.from(new Set(allTwitters)).slice(0, 10);
};

Twitter.prototype.follow = function (followerId, followeeId) {
  if (!this.user[followerId]) {
    this.user[followerId] = new Set();
  }
  this.user[followerId].add(followeeId);
};
Twitter.prototype.unfollow = function (followerId, followeeId) {
  if (this.user[followerId]) {
    this.user[followerId].delete(followeeId);
  }
};

380. O(1) 时间插入、删除和获取随机元素

var RandomizedSet = function () {
  this.data = new Set();
};

RandomizedSet.prototype.insert = function (val) {
  if (this.data.has(val)) {
    return false;
  } else {
    this.data.add(val);
    return true;
  }
};

RandomizedSet.prototype.remove = function (val) {
  return this.data.delete(val);
};

RandomizedSet.prototype.getRandom = function () {
  let random = Math.floor(Math.random() * this.data.size);
  return Array.from(this.data)[random];
};