数据结构手写题

掌握深拷贝、LRU 缓存、树形结构等常见数据结构操作

2. 深拷贝

难度: ⭐⭐⭐ | 梯队: 第一梯队 ✅ | 标签: 递归, WeakMap

题目描述

实现一个深拷贝函数，支持：

基本类型
对象和数组
循环引用
特殊对象（Date、RegExp、Map、Set）
Symbol 键

代码实现

javascript

/**
 * 深拷贝 - 完整版
 * @param {any} obj - 要拷贝的对象
 * @param {WeakMap} hash - 用于处理循环引用
 * @return {any}
 */
function deepClone(obj, hash = new WeakMap()) {
  // 处理 null 和非对象类型
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }

  // 处理循环引用
  if (hash.has(obj)) {
    return hash.get(obj);
  }

  // 处理 Date
  if (obj instanceof Date) {
    return new Date(obj.getTime());
  }

  // 处理 RegExp
  if (obj instanceof RegExp) {
    return new RegExp(obj.source, obj.flags);
  }

  // 处理 Map
  if (obj instanceof Map) {
    const clone = new Map();
    hash.set(obj, clone);
    obj.forEach((value, key) => {
      clone.set(deepClone(key, hash), deepClone(value, hash));
    });
    return clone;
  }

  // 处理 Set
  if (obj instanceof Set) {
    const clone = new Set();
    hash.set(obj, clone);
    obj.forEach((value) => {
      clone.add(deepClone(value, hash));
    });
    return clone;
  }

  // 处理数组和普通对象
  const clone = Array.isArray(obj) ? [] : {};
  hash.set(obj, clone);

  // 获取所有键（包括 Symbol）
  const keys = [
    ...Object.keys(obj),
    ...Object.getOwnPropertySymbols(obj)
  ];

  for (const key of keys) {
    clone[key] = deepClone(obj[key], hash);
  }

  return clone;
}

/**
 * 简易版深拷贝（面试快速手写）
 * 不支持：循环引用、特殊对象、Symbol
 */
function deepCloneSimple(obj) {
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }

  const clone = Array.isArray(obj) ? [] : {};

  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepCloneSimple(obj[key]);
    }
  }

  return clone;
}

/**
 * JSON 方法（最简单但有局限）
 * 不支持：函数、undefined、Symbol、循环引用、Date、RegExp
 */
function deepCloneJSON(obj) {
  return JSON.parse(JSON.stringify(obj));
}

示例调用

javascript

// 基础示例
const obj1 = { a: 1, b: { c: 2 } };
const cloned1 = deepClone(obj1);
console.log(cloned1.b !== obj1.b); // true（深拷贝）

// 循环引用
const circular = { a: 1 };
circular.self = circular;
const clonedCircular = deepClone(circular);
console.log(clonedCircular.self === clonedCircular); // true

// 特殊对象
const special = { date: new Date('2024-01-01'), regex: /hello/gi, map: new Map([['key', 'value']]) };
const clonedSpecial = deepClone(special);
console.log(clonedSpecial.date instanceof Date);  // true
console.log(clonedSpecial.date !== special.date); // true

// Symbol 键
const sym = Symbol('test');
const withSymbol = { [sym]: 'symbol value', a: 1 };
console.log(deepClone(withSymbol)[sym]); // 'symbol value'

复杂度分析

时间: O(n)，n 为对象中的属性总数
空间: O(n)，递归栈 + WeakMap

5. LRU 缓存

难度: ⭐⭐ | 梯队: 第二梯队 | 标签: 数据结构, Map LeetCode: 146. LRU 缓存

题目描述

设计一个 LRU (最近最少使用) 缓存，支持 get 和 put 操作，都是 O(1) 时间复杂度。

代码实现

javascript

/**
 * LRU Cache - 使用 Map（推荐）
 * JavaScript Map 自动维护插入顺序
 */
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  /**
   * 获取键值，访问后移到最新位置
   * @param {number} key
   * @return {number}
   */
  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;
  }

  /**
   * 设置键值，超出容量时淘汰最老的
   * @param {number} key
   * @param {number} value
   */
  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 删除最老的（Map 第一个元素）
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

/**
 * LRU Cache - 双向链表实现（面试常考）
 * get/put 都是 O(1)
 */
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCacheLinkedList {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // key -> Node

    // 虚拟头尾节点
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * 从链表中移除节点
   */
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  /**
   * 插入到头部（最新位置）
   */
  _insertToHead(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    const node = this.cache.get(key);
    // 移到头部
    this._remove(node);
    this._insertToHead(node);
    return node.value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this._remove(node);
      this._insertToHead(node);
    } else {
      if (this.cache.size >= this.capacity) {
        // 删除尾部（最老）
        const oldest = this.tail.prev;
        this._remove(oldest);
        this.cache.delete(oldest.key);
      }
      const newNode = new Node(key, value);
      this.cache.set(key, newNode);
      this._insertToHead(newNode);
    }
  }
}

示例调用

javascript

// 基础示例
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));  // 1
cache.put(3, 3);            // 淘汰 key 2
console.log(cache.get(2));  // -1 (已淘汰)
console.log(cache.get(3));  // 3

// get 后再 put（访问顺序影响淘汰）
const cache2 = new LRUCache(2);
cache2.put(1, 1);
cache2.put(2, 2);
cache2.get(1);              // 1 变成最新
cache2.put(3, 3);           // 淘汰 2
console.log(cache2.get(2)); // -1
console.log(cache2.get(1)); // 1

// 更新已存在的键
const cache3 = new LRUCache(2);
cache3.put(1, 1);
cache3.put(1, 10);
console.log(cache3.get(1)); // 10

复杂度分析

时间: O(1) get/put
空间: O(capacity)

9. 省市区平级转树状

难度: ⭐⭐ | 梯队: 第二梯队 | 标签: 递归, Map

题目描述

服务端返回的省市区、组织架构、菜单权限等通常是 [{id, parentId, name, ...}] 平级结构，前端 Cascader、Tree 组件需要树状结构。实现将平级列表转为树状结构的函数。

输入：平级数组，每项含 id、parentId（根节点为 null/0/undefined）输出：树状数组，每项含 children 子节点数组

代码实现

javascript

/**
 * 平级列表转树状结构
 * @param {Array} list - 平级数据 [{id, parentId, name, ...}]
 * @param {Object} options - 配置项
 * @param {string} options.idKey - id 字段名，默认 'id'
 * @param {string} options.parentKey - parentId 字段名，默认 'parentId'
 * @param {string} options.childrenKey - 子节点字段名，默认 'children'
 * @param {*} options.rootValue - 根节点的 parentId 值，默认 null
 * @return {Array}
 */
function listToTree(list, options = {}) {
  const {
    idKey = 'id',
    parentKey = 'parentId',
    childrenKey = 'children',
    rootValue = null,
  } = options;

  if (!list || list.length === 0) return [];

  const map = new Map();
  const roots = [];

  // 第一遍：建立 id -> 节点 映射，并初始化 children
  for (const item of list) {
    const node = { ...item, [childrenKey]: [] };
    map.set(node[idKey], node);
  }

  // 第二遍：根据 parentId 挂到父节点
  for (const item of list) {
    const node = map.get(item[idKey]);
    const parentId = item[parentKey];

    if (parentId === rootValue || parentId === undefined) {
      roots.push(node);
    } else {
      const parent = map.get(parentId);
      if (parent) {
        parent[childrenKey].push(node);
      } else {
        // 父节点不存在（数据不完整），作为根节点
        roots.push(node);
      }
    }
  }

  return roots;
}

示例调用

javascript

// 省市区数据
const flatList = [
  { id: 1, parentId: null, name: '广东省' },
  { id: 2, parentId: null, name: '浙江省' },
  { id: 11, parentId: 1, name: '广州市' },
  { id: 12, parentId: 1, name: '深圳市' },
  { id: 111, parentId: 11, name: '天河区' },
];

const tree = listToTree(flatList);
console.log(JSON.stringify(tree, null, 2));
// [{ id: 1, name: '广东省', children: [{ id: 11, name: '广州市', children: [...] }, ...] }, ...]

// 自定义字段名
const menuList = [
  { code: 'm1', pcode: '', label: '系统管理' },
  { code: 'm2', pcode: 'm1', label: '用户管理' },
];
console.log(listToTree(menuList, { idKey: 'code', parentKey: 'pcode', childrenKey: 'items', rootValue: '' }));

// 空数组
console.log(listToTree([])); // []

复杂度分析

时间: O(n)，两次遍历
空间: O(n)，Map 存储所有节点

11. 对象扁平化与反扁平化

难度: ⭐⭐ | 梯队: 第三梯队 | 标签: 递归, 字符串

题目描述

扁平化：将嵌套对象 {user: {name: 'a', addr: {city: 'b'}}} 转为 {'user.name': 'a', 'user.addr.city': 'b'}，常用于表单校验、提交数据
反扁平化：将扁平对象还原为嵌套结构

代码实现

javascript

/**
 * 对象扁平化
 * @param {Object} obj - 嵌套对象
 * @param {string} prefix - 键前缀，递归用
 * @param {Object} result - 结果对象，递归用
 * @return {Object}
 */
function flattenObject(obj, prefix = '', result = {}) {
  if (obj === null || typeof obj !== 'object') {
    if (prefix) result[prefix] = obj;
    return result;
  }

  // 数组按索引展开：arr.0, arr.1
  if (Array.isArray(obj)) {
    obj.forEach((item, index) => {
      flattenObject(item, `${prefix}[${index}]`, result);
    });
    return result;
  }

  for (const key of Object.keys(obj)) {
    const newPrefix = prefix ? `${prefix}.${key}` : key;
    flattenObject(obj[key], newPrefix, result);
  }

  return result;
}

/**
 * 对象反扁平化（支持 a.b.c 和 arr[0] 格式）
 * @param {Object} flatObj - 扁平对象 {'a.b.c': 1, 'tags[0]': 'x'}
 * @return {Object}
 */
function unflattenObject(flatObj) {
  const result = {};

  for (const key of Object.keys(flatObj)) {
    // 解析 'a.b[0].c' 为 ['a', 'b', 0, 'c']，'tags[0]' 为 ['tags', 0]
    const parts = key.split('.').flatMap((p) => {
      const match = p.match(/^(\w+)\[(\d+)\]$/);
      return match ? [match[1], parseInt(match[2], 10)] : [p];
    });

    let current = result;

    for (let i = 0; i < parts.length - 1; i++) {
      const part = parts[i];
      const nextPart = parts[i + 1];
      const nextIsNum = typeof nextPart === 'number';

      if (!(part in current)) {
        current[part] = nextIsNum ? [] : {};
      }
      current = current[part];
    }

    const lastKey = parts[parts.length - 1];
    current[lastKey] = flatObj[key];
  }

  return result;
}

/**
 * 简化版反扁平化（仅支持 a.b.c 形式，不含数组）
 */
function unflattenObjectSimple(flatObj) {
  const result = {};

  for (const key of Object.keys(flatObj)) {
    const parts = key.split('.');
    let current = result;

    for (let i = 0; i < parts.length - 1; i++) {
      const part = parts[i];
      if (!(part in current)) {
        current[part] = {};
      }
      current = current[part];
    }
    current[parts[parts.length - 1]] = flatObj[key];
  }

  return result;
}

示例调用

javascript

// 扁平化
const nested = {
  user: { name: 'Alice', addr: { city: '广州' } },
  tags: ['a', 'b'],
};
console.log(flattenObject(nested));
// { 'user.name': 'Alice', 'user.addr.city': '广州', 'tags[0]': 'a', 'tags[1]': 'b' }

// 反扁平化
const flat = { 'user.name': 'Alice', 'user.addr.city': '广州', 'a.b.c': 1 };
console.log(unflattenObjectSimple(flat));
// { user: { name: 'Alice', addr: { city: '广州' } }, a: { b: { c: 1 } } }

// 空对象
console.log(flattenObject({})); // {}
console.log(unflattenObjectSimple({})); // {}

复杂度分析

时间: O(n)，n 为键值对总数
空间: O(d)，d 为最大嵌套深度（递归栈）

12. 树形结构查找路径

难度: ⭐⭐ | 梯队: 第三梯队 | 标签: DFS, 回溯

题目描述

在文件树、菜单树中，根据节点 id 查找从根到该节点的路径，用于面包屑展示或 Cascader 回显。树结构为 {id, children: [...]}。

代码实现

javascript

/**
 * 树形结构查找路径
 * @param {Array} tree - 树状数据
 * @param {*} targetId - 目标节点 id
 * @param {Object} options - 配置
 * @param {string} options.idKey - id 字段名，默认 'id'
 * @param {string} options.childrenKey - 子节点字段名，默认 'children'
 * @return {Array} - 路径节点数组，未找到返回 []
 */
function findTreePath(tree, targetId, options = {}) {
  const { idKey = 'id', childrenKey = 'children' } = options;

  const path = [];

  function dfs(nodes, target, currentPath) {
    if (!nodes || nodes.length === 0) return false;

    for (const node of nodes) {
      const newPath = [...currentPath, node];

      if (node[idKey] === target) {
        path.push(...newPath);
        return true;
      }

      const children = node[childrenKey];
      if (children && children.length > 0) {
        if (dfs(children, target, newPath)) {
          return true;
        }
      }
    }
    return false;
  }

  dfs(tree, targetId, []);
  return path;
}

/**
 * 仅返回 id 路径（用于 Cascader 的 value）
 */
function findTreePathIds(tree, targetId, options = {}) {
  const path = findTreePath(tree, targetId, options);
  const { idKey = 'id' } = options;
  return path.map((node) => node[idKey]);
}

/**
 * 查找路径（不包含目标节点，仅祖先）
 */
function findTreeAncestors(tree, targetId, options = {}) {
  const path = findTreePath(tree, targetId, options);
  return path.slice(0, -1);
}

示例调用

javascript

const tree = [
  {
    id: 1,
    name: '广东省',
    children: [
      {
        id: 11,
        name: '广州市',
        children: [
          { id: 111, name: '天河区', children: [] },
          { id: 112, name: '越秀区', children: [] },
        ],
      },
      { id: 12, name: '深圳市', children: [] },
    ],
  },
  { id: 2, name: '浙江省', children: [] },
];

// 查找天河区路径
console.log(findTreePath(tree, 111));
// [广东省节点, 广州市节点, 天河区节点]

// 仅 id 路径（Cascader value）
console.log(findTreePathIds(tree, 111)); // [1, 11, 111]

// 面包屑（不含当前节点）
console.log(findTreeAncestors(tree, 111).map((n) => n.name)); // ['广东省', '广州市']

// 不存在的节点
console.log(findTreePath(tree, 999)); // []

复杂度分析

时间: O(n)，n 为树节点总数
空间: O(h)，h 为树高（递归栈 + 路径数组）

数据结构手写题 ​

2. 深拷贝 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

5. LRU 缓存 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

9. 省市区平级转树状 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

11. 对象扁平化与反扁平化 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

12. 树形结构查找路径 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

数据结构手写题

2. 深拷贝

题目描述

代码实现

示例调用

复杂度分析

5. LRU 缓存

题目描述

代码实现

示例调用

复杂度分析

9. 省市区平级转树状

题目描述

代码实现

示例调用

复杂度分析

11. 对象扁平化与反扁平化

题目描述

代码实现

示例调用

复杂度分析

12. 树形结构查找路径

题目描述

代码实现

示例调用

复杂度分析