刷题笔记合集🔗

API集群负载统计

问题描述

小柯负责一个产品的 RESTful API 集合，该集合部署在服务器集群的多个节点上。最近，团队对客户端访问日志进行了采集，需要统计各个 API 的访问频次，根据热点信息在服务器节点之间做负载均衡，现在需要实现热点信息统计查询功能。

RESTful API 是由多个层级构成，层级之间使用 / 连接，如 /A/B/C/D 这个地址，A 属于第一级，B 属于第二级，C 属于第三级，D 属于第四级。

现在负载均衡模块需要知道给定层级上某个名字出现的频次，未出现过用 0 表示，需要实现这个功能。

输入格式

第一行为 ，表示访问历史日志的条数，。

接下来 行，每一行为一个 RESTful API 的 URL 地址，约束地址中仅包含英文字母和连接符 /，最大层级为 10，每层级字符串最大长度为 10。

最后一行为层级 和要查询的关键字。

输出格式

输出给定层级上，关键字出现的频次，使用完全匹配方式（大小写敏感）。

样例输入

5
/huawei/computing/no/one
/huawei/computing
/huawei
/huawei/cloud/no/one
/huawei/wireless/no/one
2 computing

5
/huawei/computing/no/one
/huawei/computing
/huawei
/huawei/cloud/no/one
/huawei/wireless/no/one
4 two

样例输出

2

0

数据范围

• 
• 最大层级为 10
• 每层级字符串最大长度为 10

题解

这道题本质上是一个关于数据结构的模拟题，需要对 RESTful API 的结构进行解析和统计。

题目要求我们统计不同层级上各个关键字出现的频次。一个直观的数据结构是使用一个数组，其中数组的索引表示层级，每个元素是一个映射表（哈希表/字典），用于存储该层级上各个关键字出现的次数。

解题步骤：

1. 初始化一个表示不同层级的数组，数组中的每个元素是一个映射表
2. 遍历每条日志记录（URL）
3. 将URL按照"/"分割成不同的层级组件
4. 对于每个层级的组件，在对应层级的映射表中增加该组件的计数
5. 最后根据给定的层级和关键字，查询对应层级的映射表中该关键字的计数，如果不存在则返回0

需要注意的是：

• URL 分割后，第一个元素通常是空字符串（因为URL以"/"开头），所以实际的层级要对应到正确的索引
• 需要处理查询层级超出统计范围的情况
• 大小写敏感，需要精确匹配

这种方法的时间复杂度为 ，其中 是日志条数， 是平均每条URL包含的层级数。对于给定的数据范围（，最大层级为10），这个复杂度是完全可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取日志条数
n = int(input())

# 初始化各层级关键字频次统计
level_counts = []

# 处理每条URL日志
for _ in range(n):
    url = input()
    components = url.split('/')
    
    # 遍历各层级
    for level, comp in enumerate(components):
        # 确保level_counts有足够的元素
        while len(level_counts) <= level:
            level_counts.append({})
        
        # 更新该层级上该关键字的计数
        level_counts[level][comp] = level_counts[level].get(comp, 0) + 1

# 读取查询信息
query = input().split()
target_level = int(query[0])
target_key = query[1]

# 检查层级是否超出范围
if target_level >= len(level_counts):
    print(0)
else:
    # 查询并输出频次
    result = level_counts[target_level].get(target_key, 0)
    print(result)

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <st