时间戳

首页 > 解决方案 > 获取每个项目的完整依赖项列表，当最初为每个项目指定一个级别的子依赖项和父依赖项时

javascript - 获取每个项目的完整依赖项列表，当最初为每个项目指定一个级别的子依赖项和父依赖项时

问题描述

我的数据结构如下所示：

const items = [
  { id: '1', subItems: ['2', '3'], majorItems: ['4'] },
  { id: '4', subItems: ['1'], majorItems: [] },
  { id: '2', subItems: ['5'], majorItems: ['1'] },
  { id: '5', subItems: [], majorItems: ['2'] },
  { id: '3', subItems: [], majorItems: ['1'] },
]

例子

我需要将此结构转换为这种形式：

const result = {
  '1': ['2','3','5'],
  '4': ['1','2','3','5'],
  '2': ['5'],
  '5': [],
  '3': []
}

你能帮我找到解决这个问题的最佳算法吗？

标签： javascriptalgorithm

解决方案

您可以使用执行 DFS 遍历和记忆的递归函数来避免重复工作：

function createList(items) {
    let map = new Map(items.map(item => [item.id, item.subItems]));
    let memo = new Map;

    function recur(id, tab="") {
        let result = memo.get(id);
        if (!result) {
            result = [...map.get(id)];
            memo.set(id, result = [...result, ...result.flatMap(recur)]);
        }
        return result;
    }

    return Object.fromEntries(items.map(({id}) => [id, recur(id)]));
}

// demo
const items = [
  { id: '1', subItems: ['2', '3'], majorItems: ['4'] },
  { id: '4', subItems: ['1'], majorItems: [] },
  { id: '2', subItems: ['5'], majorItems: ['1'] },
  { id: '5', subItems: [], majorItems: ['2'] },
  { id: '3', subItems: [], majorItems: ['1'] },
];

console.log(createList(items));

请注意，结果对象的键按其数字顺序迭代/显示。这是 ECMAScript 指定的行为。

推荐阅读