2 篇博文 含有标签「数据结构」

// ① 去重 —— O(n)
const unique = [...new Set([1, 1, 2, 3, 3])];        // [1, 2, 3]

// ② 扁平化 —— O(n)（含所有元素）
const flat = [1, [2, [3, [4]]]].flat(Infinity);        // [1, 2, 3, 4]
// 手写版（递归，面试爱考）
function flatten(arr) {
  return arr.reduce(
    (acc, cur) => Array.isArray(cur) ? acc.concat(flatten(cur)) : acc.concat(cur),
    [],
  );
}

// ③ 翻转 —— O(n)
const rev = [1, 2, 3].reverse();                        // [3, 2, 1]

function isValid(s) {
  const stack = [];
  const map = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch in map) {
      if (stack.pop() !== map[ch]) return false;   // 遇到右括号，必须匹配栈顶
    } else {
      stack.push(ch);                               // 左括号入栈
    }
  }
  return stack.length === 0;
}

console.log(1);                 // 同步
Promise.resolve().then(() => console.log(2));  // 微任务
setTimeout(() => console.log(3));              // 宏任务
// 输出：1 → 2 → 3

function reverseList(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;   // 先记住下一个
    cur.next = prev;         // 反转指针
    prev = cur;
    cur = next;
  }
  return prev;
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;        // 走一步
    fast = fast.next.next;   // 走两步
    if (slow === fast) return true;   // 有环必相遇
  }
  return false;
}

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];   // 找到了之前存的另一半
    map.set(nums[i], i);                             // 记下"当前值 → 下标"
  }
  return [];
}

class LRUCache {
  constructor(capacity) { this.capacity = capacity; this.cache = new Map(); }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const value = this.cache.get(key);
    this.cache.delete(key);                // ① 先删掉旧的
    this.cache.set(key, value);            // ② 再插回去 → 排到"最新"位置
    return value;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);   // 更新也先删旧的
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value); // 淘汰队头
    }
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();          // key → 链表节点
    this.head = this.tail = null;  // 双向链表头尾
  }
  _detach(node) {                  // O(1) 从链表摘掉 node
    if (node.prev) node.prev.next = node.next; else this.head = node.next;
    if (node.next) node.next.prev = node.prev; else this.tail = node.prev;
  }
  _pushToTail(node) {              // O(1) 把 node 放到队尾
    node.prev = this.tail; node.next = null;
    if (this.tail) this.tail.next = node; else this.head = node;
    this.tail = node;
  }
  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    this._detach(node);
    this._pushToTail(node);        // 顶到最新
    return node.value;
  }
  put(key, value) {
    if (this.map.has(key)) this._detach(this.map.get(key));
    const node = { key, value, prev: null, next: null };
    this.map.set(key, node);
    this._pushToTail(node);
    if (this.map.size > this.capacity) {
      this.map.delete(this.head.key);   // 淘汰队头
      this._detach(this.head);
    }
  }
}

// 前序：根 → 左 → 右（递归版，最好写）
function preorder(root, res = []) {
  if (!root) return res;
  res.push(root.val);
  preorder(root.left, res);
  preorder(root.right, res);
  return res;
}

// 前序（迭代版，用栈）——面试官常让你把递归改成迭代
function preorderIter(root) {
  const res = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    res.push(node.val);
    stack.push(node.right, node.left);   // 先压右，后压左 → 弹出来先左
  }
  return res;
}

function levelOrder(root) {
  const res = [];
  if (!root) return res;
  const queue = [root];
  while (queue.length) {
    const size = queue.length;        // 先记下这一层有几个节点
    const level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = [], right = [];
  for (let i = 1; i < arr.length; i++) {
    (arr[i] < pivot ? left : right).push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

[10, 9, 100].sort();            // [10, 100, 9] ← 按字符串排的坑
[10, 9, 100].sort((a, b) => a - b);  // [9, 10, 100] ✅

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;      // 取中位
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function deepClone(obj, seen = new Map()) {
  if (obj === null || typeof obj !== 'object') return obj;   // 基础类型直接返回
  if (seen.has(obj)) return seen.get(obj);                    // 处理循环引用！
  const res = Array.isArray(obj) ? [] : {};
  seen.set(obj, res);
  for (const key of Object.keys(obj)) {
    res[key] = deepClone(obj[key], seen);
  }
  return res;
}

// 层次 1：纯递归 —— O(2^n)，指数爆炸，n 稍大就卡死 ❌
function climb1(n) {
  if (n <= 2) return n;
  return climb1(n - 1) + climb1(n - 2);
}

// 层次 2：记忆化（自顶向下）—— O(n) ✅
function climb2(n, memo = {}) {
  if (n <= 2) return n;
  if (memo[n] !== undefined) return memo[n];
  return (memo[n] = climb2(n - 1, memo) + climb2(n - 2, memo));
}

// 层次 3：自底向上滚动数组（真正的 DP）—— O(n) 时间 O(1) 空间 ✅
function climb3(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, max = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {      // 窗口里有重复 → 右移 left 直到没有
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

function isPalindrome(s) {
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++; r--;
  }
  return true;
}