l3-004 肿瘤诊断 (30 分)
时间: 2023-04-15 10:00:37 浏览: 68
l3-004 肿瘤诊断是指通过各种医学检查手段,对患者是否患有肿瘤进行诊断和判断。肿瘤是一种常见的疾病,早期发现和诊断对于治疗和预后都有很大的影响。常见的肿瘤诊断手段包括影像学检查、病理学检查、血液学检查等。在诊断过程中,医生需要综合分析患者的病史、体征、检查结果等多方面的信息,做出准确的诊断和治疗方案。
相关问题
l3-002 特殊堆栈 (30 分)
题目描述
本题要求实现一个特殊堆栈,除了常规的入栈和出栈操作外,还需要支持以下操作:
peek:取出栈顶元素,但是不弹出;
min:返回当前栈中的最小值;
max:返回当前栈中的最大值。
输入格式
输入第一行给出一个正整数 N(≤10^5),是操作数。以下 N 行每行包含一个操作指令,格式如下:
push key:将 key 插入堆栈;
pop:弹出栈顶元素;
peek:取出栈顶元素,但是不弹出;
min:返回当前栈中的最小值;
max:返回当前栈中的最大值。
这里假设堆栈中没有重复元素,且输入保证不会出现不合法的操作。
输出格式
对于每个 min 和 max 操作,输出该操作返回的值,如果堆栈为空则输出 ERROR。
输入样例
10
push 3
push 2
push 1
max
pop
max
pop
max
pop
max
输出样例
3
2
3
1
ERROR
算法1
(单调栈) $O(n)$
首先,我们需要一个普通的栈来实现入栈和出栈操作。
然后,我们需要维护一个单调递减的栈,来实现最小值的查询。每次入栈时,如果当前元素小于等于栈顶元素,就将其入栈。否则,我们需要将栈顶元素弹出,直到栈顶元素小于等于当前元素,再将当前元素入栈。
同理,我们也需要维护一个单调递增的栈,来实现最大值的查询。
对于 peek 操作,我们只需要返回栈顶元素即可。
时间复杂度
每个元素最多入栈一次,出栈一次,查询一次最小值和最大值,因此总时间复杂度为 $O(n)$。
C++ 代码
算法2
(双向队列) $O(n)$
我们可以使用双向队列来维护最小值和最大值。队列中的元素是一个二元组,第一个元素是值,第二个元素是该值在栈中的出现次数。
每次入栈时,我们需要将该元素插入到双向队列中。同时,我们需要维护队列的单调性。对于最小值队列,我们需要保证队列中的元素是单调递增的。对于最大值队列,我们需要保证队列中的元素是单调递减的。
每次出栈时,我们需要将该元素从双向队列中删除。同时,我们也需要更新队列的单调性。
对于 min 和 max 操作,我们只需要返回最小值队列和最大值队列的队首元素即可。
时间复杂度
每个元素最多入队一次,出队一次,查询一次最小值和最大值,因此总时间复杂度为 $O(n)$。
C++ 代码
l3-003 社交集群 (30 分)
社交集群是指一群人在社交网络上形成的紧密联系的群体。这些人通常有共同的兴趣爱好、职业、地理位置等特征,通过社交网络平台进行交流和互动。社交集群的形成可以促进人们之间的交流和合作,也可以为企业和组织提供更精准的营销和推广渠道。同时,社交集群也存在一些问题,如信息过滤、信息泄露等,需要注意保护个人隐私和信息安全。