python算法与数据结构朋友圈与水杯实验题分析实例
目录
- 算法与数据结构实验题-朋友圈
- 实验任务
- 数据输入
- 数据输出
- 输入示例
- 输出示例
- 代码实现
- 效果展示
- 算法与数据结构实验题-水杯
- 实验任务
- 数据输入
- 数据输出
- 输入示例
- 输出示例
- 代码实现
- 效果展示
算法与数据结构实验题-朋友圈
实验任务
朋友圈是由若干个人组成的集体，已知现在有n个人(1到n)，然后给你m个关系x y，表示x和y是朋友，假设朋友的朋友也是朋友，求这n个人中最大的朋友圈人数。
数据输入
输入第一行为一个正整数n,m。
接下来有m行，每行有两个正整数 x 和 y ，表示 x 和 y 是朋友
60%的数据 1<=n,m<=100.
100%的数据1<=n<=100000.
数据输出
输出n个人中最大的朋友圈人数。
输入示例
3 2
1 2
2 3
输出示例
3
代码实现
rel=int (input().split()[1])
my_list=[]
ne=0
while rel:
rel-=1
flag=0
my_set=set()
my_cont=[int (n) for n in input().split()]
for n in range(len(my_list)):
if my_cont[0] in my_list[n]:
my_list[n].add(my_cont[1])
flag=1
ne=n
continue
if (my_cont[1] in my_list[n]) and flag==0:
my_list[n].add(my_cont[0])
flag = 1
break
elif (my_cont[1] in my_list[n]) and flag==1:
my_list[n]=my_list[n].union(my_list[ne])
my_list.remove(my_list[ne])
if flag==0:
my_set.add(my_cont[0])
my_set.add(my_cont[1])
my_list.append(my_set)
ans=0
for n in my_list:
ans=max(ans,len(n))
print(ans)
tips：union返回一个新的集合，需要赋值
效果展示
算法与数据结构实验题-水杯
实验任务
有n个水杯叠放在一起
从上到下，编号由1开始一直到n，容量ai不一定满足也依次增大的关系，如果i号杯子存的水超过了它的容量，则会像i+1号水杯流，以此类推
现在给你两个操作
操作一： 1 x y 给x号杯子加y容量的水
操作二： 2 x 查询x杯子里有多少水。
数据输入
输入第一行为一个正整数n
接下来n个元素，表示第i个水杯的容量
接着输入操作的个数q
接下来q行操作。
60%的数据 1<=n<=100,1<=q<=100,1<=ai,y<=100.
100%的数据1<=n<=100000,1<=q<=100000,1<=ai,y<=1000000000.
数据输出
对于每个操作二，输出对应的值。
输入示例
2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2
输出示例
4
5
8
代码实现
def action(x,n):
while n>0 and x<=num:
if my_cup[x]>=n:
my_cup[x]-=n
n=0
else:
n-=my_cup[x]
my_cup[x] = 0
x+=1
num=int (input())
my_cup=[int (n) for n in input().split()]
old=my_cup.copy()
act=int (input())
while act:
act-=1
cont=[int (n) for n in input().split()]
if cont[0]==1:
action(cont[1]-1,cont[2])
if cont[0]==2:
print(old[cont[1]-1]-my_cup[cont[1]-1])
注释：这里的old列表需要用到copy函数进行浅拷贝操作（没有出现嵌套所以不同考虑深拷贝），若是直接赋值则会导致my_cup改变时old也跟着改变。本代码输出为实时输出
效果展示
到此这篇关于python算法与数据结构实验题分析实例的文章就介绍到这了,更多相关python算法与数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Python数据结构与算法中的队列详解(2)
目录 传土豆 总结 传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景.考虑这样一个游戏:传土豆.在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆.在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏. 重复上述过程,直到只剩下一个成员. 我们将针对传土豆游戏实现通用的模拟程序.该程序接受一个名字列表和一个用于计数的常量 num ,并且返回最后剩下的那个人的名字. 我们使用队列来模拟一个环.即假设握着土豆的人位于队列的头部.在模拟传土豆的过程中,程序将这个人
-
Python数据结构与算法之链表,无序链表详解
目录 我们首先来构造节点. 节点(Node)的类构建完毕后,接下来我们开始构建整个链表(LinkList)的类. 那么我们还需要一个方法来判断链表头的指向. 接下来我们构建链表节点的添加方法. 实现length方法(计算链表中节点的个数/链表长度) 实现search方法(搜索链表中的某个节点) 实现remove方法(移除链表中的某个节点) 代码汇总 总结 链表是一系列元素的集合,这些元素的内存是散乱的. 无序链表则是一系列逻辑无序元素的集合,只是通过链表数据结构连接起来.虽然这些元素整体来看是散
-
Python数据结构树与算法分析
目录 1.示例 2.术语及定义 3.实现 3.1 列表之列表 3.2节点与引用 4.二叉树的应用 4.1解析树 4.2树的遍历 5.利用二叉堆实现优先级队列 6.二叉搜索树 6.1搜索树的实现 7.平衡二叉搜索树(AVL树) 1.示例 树的一些属性: 层次性:树是按层级构建的,越笼统就越靠近顶部,越具体则越靠近底部. 一个节点的所有子节点都与另一个节点的所有子节点无关. 叶子节点都是独一无二的. 嵌套 2.术语及定义 节点:树的基础部分.节点的名字 → 键,附加信息 → 有效载荷. 边:两个节点
-
Python数据结构与算法中的栈详解
目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总
-
Python数据结构与算法的双端队列详解
目录 什么是双端队列 用Python实现双端队列 运用双端队列构建回文检测器 总结 什么是双端队列 双端队列是与队列类似的有序集合.它有一前.一后两端,元素在其中保持自己的位置.与队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制.新元素既可以被添加到前端,也可以被添加到后端.同理,已有的元素也能从任意一端移除.某种意义上,双端队列可以是栈和队列的结合. 值得注意的是,尽管双端队列有栈和队列的很多特性,但是它并不要求按照这两种数据结构分别规定的LIFO原则和FIFO原则操作元素.具
-
python算法与数据结构朋友圈与水杯实验题分析实例
目录 算法与数据结构实验题-朋友圈 实验任务 数据输入 数据输出 输入示例 输出示例 代码实现 效果展示 算法与数据结构实验题-水杯 实验任务 数据输入 数据输出 输入示例 输出示例 代码实现 效果展示 算法与数据结构实验题-朋友圈 实验任务 朋友圈是由若干个人组成的集体,已知现在有n个人(1到n),然后给你m个关系x y,表示x和y是朋友,假设朋友的朋友也是朋友,求这n个人中最大的朋友圈人数. 数据输入 输入第一行为一个正整数n,m. 接下来有m行,每行有两个正整数 x 和 y ,表示 x 和
-
python算法与数据结构之冒泡排序实例详解
一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的
-
python算法与数据结构之单链表的实现代码
=一.链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是
-
JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解
本文实例讲述了JS中的算法与数据结构之二叉查找树(Binary Sort Tree).分享给大家供大家参考,具体如下: 二叉查找树(Binary Sort Tree) 我们之前所学到的列表,栈等都是一种线性的数据结构,今天我们将学习计算机中经常用到的一种非线性的数据结构--树(Tree),由于其存储的所有元素之间具有明显的层次特性,因此常被用来存储具有层级关系的数据,比如文件系统中的文件:也会被用来存储有序列表等. 在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的
-
Android仿微信朋友圈全文、收起功能的实例代码
前言 一般在社交APP中都有类似朋友圈的功能,其中发表的动态内容很长的时候不可能让它全部显示.这里就需要做一个仿微信朋友圈全文.收起功能来解决该问题.在网上看到一个例子-->http://www.jb51.net/article/105251.htm,写的很不错,但是有个bug,他这个Demo只有在条目固定的时候才正常,当增加.删除条目的时候会出现全文.收起显示混乱的问题.原因是他使用了固定的position作为key来保存当前显示的状态.这篇文章在他的基础上进行优化. 效果图 具体代码 (详细
-
Python爬虫爬取微信朋友圈
接下来,我们将实现微信朋友圈的爬取. 如果直接用 Charles 或 mitmproxy 来监听微信朋友圈的接口数据,这是无法实现爬取的,因为数据都是被加密的.而 Appium 不同,Appium 作为一个自动化测试工具可以直接模拟 App 的操作并可以获取当前所见的内容.所以只要 App 显示了内容,我们就可以用 Appium 抓取下来. 1. 本节目标 本节我们以 Android 平台为例,实现抓取微信朋友圈的动态信息.动态信息包括好友昵称.正文.发布日期.其中发布日期还需要进行转换,如日期
-
Python实现的数据结构与算法之双端队列详解
本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe
-
Python实现的数据结构与算法之队列详解
本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队
-
Python实现的数据结构与算法之基本搜索详解
本文实例讲述了Python实现的数据结构与算法之基本搜索.分享给大家供大家参考.具体分析如下: 一.顺序搜索 顺序搜索 是最简单直观的搜索方法:从列表开头到末尾,逐个比较待搜索项与列表中的项,直到找到目标项(搜索成功)或者 超出搜索范围 (搜索失败). 根据列表中的项是否按顺序排列,可以将列表分为 无序列表 和 有序列表.对于 无序列表,超出搜索范围 是指越过列表的末尾:对于 有序列表,超过搜索范围 是指进入列表中大于目标项的区域(发生在目标项小于列表末尾项时)或者指越过列表的末尾(发生在目标项
-
Python实现的数据结构与算法之快速排序详解
本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中