从嵌套字典列表中提取每层最大值的名称

核心算法

核心思想是将列表转化为树的解析过程。利用递归函数 compMx 遍历树结构，并使用辅助函数 best 比较节点，找出最佳节点（最深层级或相同层级下数值最大）。

代码实现

def best(a, b):
    """
    比较两个节点，返回更佳的节点。
    比较标准：层级更深者胜出，若层级相同，则数值更大者胜出。
    """
    if a is None:
        return b
    if a[1] < b[1]:
        return b
    if a[1] == b[1] and a[2] < b[2]:
        return b
    return a

def compMx(L, start=0):
    """
    递归函数，用于遍历树结构，找到每个节点的最佳子节点。
    """
    lv = L[start]['level']
    L[start]['mx'] = (L[start]['name'], lv, L[start]['number'])  # 初始化最佳节点信息
    i = start + 1
    while i < len(L):
        if L[i]['level'] <= lv:
            return i
        j = compMx(L, i)  # 递归调用，处理子节点
        L[start]['mx'] = best(L[start]['mx'], L[i]['mx'])  # 更新最佳节点信息
        if j < 0:
            break
        i = j
    return -1

# 执行主要逻辑
compMx(list_of_dicts)
# 提取指定层级（例如 level=1）的最佳节点名称
result = [d['mx'][0] for d in list_of_dicts if d['level'] == 1]
print(result)  # 输出: ['C', 'H']

代码解析

1. best(a, b) 函数: 此函数用于比较两个节点 a 和 b，并返回“更佳”的节点。比较的标准是首先比较节点的层级（level），层级更深的节点更佳。如果两个节点的层级相同，则比较它们的数值（number），数值更大的节点更佳。
2. compMx(L, start=0) 函数: 这是一个递归函数，用于遍历列表 L，并为每个节点确定其子树中的“最佳”节点。
   • lv = L[start]['level']: 获取当前节点的层级。
   • L[start]['mx'] = (L[start]['name'], lv, L[start]['number']): 初始化当前节点的 mx 属性，该属性用于存储当前节点及其子树中的最佳节点信息。mx 是一个元组，包含节点名称、层级和数值。
   • i = start + 1: 从当前节点的下一个节点开始遍历。
   • while i < len(L): 循环遍历后续节点，直到列表结束。
   • if L[i]['level'] <= lv: 如果当前节点的层级小于或等于起始节点的层级，则表示当前节点不是起始节点的子节点，返回当前节点的索引 i，以便在上一层递归中继续遍历。
   • j = compMx(L, i): 递归调用 compMx 函数，处理当前节点的子节点。
   • L[start]['mx'] = best(L[start]['mx'], L[i]['mx']): 将当前节点的 mx 属性更新为其自身和其子节点中的最佳节点。
   • if j < 0: break: 如果 compMx(L, i) 返回 -1，表示当前节点没有子节点，结束循环。
   • i = j: 将 i 更新为 j，以便在下一轮循环中处理下一个子节点。
   • return -1: 如果循环结束，返回 -1，表示当前节点没有兄弟节点。
3. 主程序:
   • compMx(list_of_dicts): 调用 compMx 函数，对列表进行处理，为每个节点添加 mx 属性。
   • result = [d['mx'][0] for d in list_of_dicts if d['level'] == 1]: 使用列表推导式，提取所有层级为 1 的节点的 mx 属性中的节点名称，并将结果存储在 result 列表中。
   • print(result): 输出结果。

注意事项

NameGPT名称生成器

免费AI公司名称生成器，AI在线生成企业名称，注册公司名称起名大全。

0

查看详情

• 该算法修改了原始列表，添加了 mx 属性。如果需要保留原始数据，请先复制列表。
• 算法假设列表中的节点是按照树的深度优先顺序排列的。
• 可以根据需要修改代码，提取其他层级的最佳节点。

总结

本文介绍了一种使用递归方法从嵌套字典列表中提取特定层级最大值的方法。该方法通过将列表转化为树的解析过程，利用递归函数遍历树结构，并使用辅助函数比较节点，最终找到最佳节点。该方法具有较高的灵活性和可扩展性，可以应用于各种需要处理层级关系数据的场景。

以上就是从嵌套字典列表中提取每层最大值的名称的详细内容，更多请关注php中文网其它相关文章！