解决百度笔试题：数组区间重叠与序列排序问题

"这篇资料包含了历年百度笔试题，旨在帮助求职者准备面试，同时也适合学习编程的人员。题目涵盖数组处理、序列分析以及好友关系管理等多个方面，要求解题者提供高效的算法和代码实现，并进行复杂性分析。" 首先，我们来详细分析第一个题目。该题目要求编写一个函数`foo`，计算两个无符号整数数组`a1`和`a2`所代表的区间之间的重叠部分的长度。数组中的元素是对区间边界的描述，例如，数组`a1`表示区间 `[0,1]`, `[3,6]`, `[10,20]`等。要找到重叠部分，我们可以采用双指针法。初始化两个指针，分别遍历两个数组，比较当前指针对应的区间是否有交集，如果有，累加重叠长度。关键点在于处理区间重叠和边界条件。以下是可能的代码实现： ```cpp size_t foo(unsigned int *a1, size_t al1, unsigned int *a2, size_t al2) { size_t overlap = 0; int i = 0, j = 0; while (i < al1 && j < al2) { if (a1[i * 2] <= a2[j * 2] && a2[j * 2] < a1[i * 2 + 1]) { // a2在a1内 overlap += a1[i * 2 + 1] - a2[j * 2] + 1; j++; } else if (a2[j * 2] < a1[i * 2]) { // a2左移 j++; } else { // a1左移 i++; } } return overlap; } ``` 此算法的时间复杂度为O(min(al1, al2))，因为最多只遍历两个数组中较短的一个。空间复杂度为O(1)，因为我们仅使用了常量级别的额外空间。 接下来是第二个题目，目标是统计一个整数序列中违反顺序的配对数量。可以通过一次遍历来解决，每次遍历遇到比前一个元素大的数字时，增加计数。关键在于如何有效地处理重复元素。以下是可能的代码实现： ```python def count_disorder(seq): disorder_count = 0 prev_num = float('-inf') for num in seq: if num > prev_num: disorder_count += 1 prev_num = num return disorder_count // 2 # 一对捣乱分子被计算了两次，所以除以2 # 读取文件并计算总数 with open('in', 'r') as f_in, open('out', 'w') as f_out: total_pairs = 0 for line in f_in: seq = list(map(int, line.strip().split(','))) total_pairs += count_disorder(seq) f_out.write(str(total_pairs)) ``` 这个算法的时间复杂度为O(n)，其中n为序列中的元素数量，因为每个元素都被检查一次。空间复杂度为O(1)，除了输入序列的临时存储，没有使用额外的空间。 最后，第三个题目涉及到在线好友系统的管理。由于好友关系是单向的，我们需要维护两个数据结构：一个是每个用户的ID列表，另一个是每个ID对应的好友列表。对于添加好友、删除好友、查找好友数量等操作，可以使用哈希表或字典来快速访问。具体实现细节会根据实际需求和语言特性而变化。 以上是针对百度笔试题目的解析，包括算法设计、代码实现和复杂性分析。这些题目旨在考察编程基础、问题解决能力和数据结构与算法的理解。