[OJ]水位线问题,1.采用回溯法(深度优先遍历求解)2.采用广度优先遍历求解
1.深度优先遍历
'''
使用回溯法,深度优先遍历利用栈先进后出的特点,在加水控制水量失败时,
回到最近一次可对水进行加水与否的位置1.对于给定水量k,是否在[l,r]之间,
是:是否加水(加水y,用掉x,是否在[l,r]之间)(不加水y,用掉x,是否在[l,r]之间)先尝试加水,如果不满足条件,则回溯到之前位置
否:报错
'''
class SStack(object):def __init__(self): # 初始化栈为空列表self.items = []def is_empty(self): # 判断栈是否为空,返回布尔值return self.items == []def peek(self): # 返回栈顶元素return self.items[len(self.items) - 1]def size(self): # 返回栈的大小return len(self.items)def push(self, item): # 把新的元素堆进栈里面(入栈)self.items.append(item)def pop(self): # 把栈顶元素丢出去(出栈)return self.items.pop()def main():# code herek,l,r,t,x,y=map(int,input().split(" "))ControlWaterAmount(k,l,r,t,x,y)def ControlWaterAmount(k,l,r,t,x,y):dirs=[0,y]assert l<=k<=r#创建栈st=SStack()#标记当前日期的水量 k#入口和方向0、时间t的序对入栈st.push((k,0,t))while not st.is_empty():#走不通时回退#取栈顶及检查方向pos,nxt,t=st.pop()#依次检查未检查的方向,算出下一方向for i in range(nxt,2):if l<=pos<=r:#当前时刻的偏移量为y(是否加水) nextpos=pos+dirs[i]if nextpos>r:break#到达程序出口if l<=pos<=r and t==0:print('Yes')#遇到未探索的新方向if l<=pos<=r :#标记当前时间 t#原位置、下一方向、时间t 入栈st.push((pos,i+1,t))#标记当前日期的水量 nextposnextpos=nextpos-x #新位置入栈st.push((nextpos,0,t-1))#退出内层循环,下次迭代将以新栈顶作为当前位置继续breakprint('No')if __name__ == '__main__':main();
提交测评结果:
原因分析:
当输入的时间t足够大时,会维持一个占内存极大的栈,栈中保存 t到1天的数据,造成超内存。
2.采用广度优先遍历
'''
以队列存储可以探索的位置。利用队列先进先出的特点,
实现在每个分支上同时进行搜索路径,直到找到出口。
广度优先遍历
'''
class SQueue(object):"""实现一个队列"""def __init__(self):self.__list = []def enqueue(self, elem):"""入队"""self.__list.append(elem)def dequeue(self):"""出队"""return self.__list.pop(0)def is_empty(self):return not self.__listdef size(self):"""队列的大小"""return len(self.__list)def ControlWaterAmount_queue(k,l,r,t,x,y):dirs=[0,y]path=[] #存水量的变化#path.append(k)qu=SQueue()#标记当前日期的水量 k#开始水量、开始时间入队qu.enqueue((k,t))while not qu.is_empty():#当队列中还有候选水量时pos,t=qu.dequeue()#取出下一水量和时间for i in range(2):#检查每种水量的情况if l<=pos<=r:nextpos=pos+dirs[i]if nextpos>r:continueif l<=pos<=r and t==0: #到达程序入口#path.append(pos)print('Yes')if l<=pos<=r:#找到新的探索方向#标记当前日期的水量 nextposnextpos=nextpos-xqu.enqueue((nextpos,t-1))#新水量入队print('No')def main():# code herek,l,r,t,x,y=map(int,input().split(" "))#ControlWaterAmount(k,l,r,t,x,y)ControlWaterAmount_queue(k,l,r,t,x,y)if __name__ == '__main__':main();
原因分析:当输入的时间t足够大时,会出现2^t次情况,每种情况都需要进行判断,会消耗大量的时间,直接导致超时
参考内容
相关文章:

[OJ]水位线问题,1.采用回溯法(深度优先遍历求解)2.采用广度优先遍历求解
1.深度优先遍历 使用回溯法,深度优先遍历利用栈先进后出的特点,在加水控制水量失败时, 回到最近一次可对水进行加水与否的位置1.对于给定水量k,是否在[l,r]之间, 是:是否加水(加水y,用掉x,是否在[l,r]之间)(不加水y,用掉x,是否在[l,r]之间)先尝试加水,如…...

《华为数据之道》读书笔记六---面向自助消费的数据服务建设
七、从结果管理到过程管理, 从能“看”到能“管” 1、数据赋能业务运营 数字化运营旨在利用数字化技术获取、管理和分析数据,从而为企业的战略决策与业务运营提供可量化的、科学的支撑。 数字化运营归根结底是运营,旨在推动运营效率与能力的…...

go语言day18 reflect反射
Golang-100-Days/Day16-20(Go语言基础进阶)/day19_Go语言反射.md at master rubyhan1314/Golang-100-Days (github.com) 7-19 接口:底层实现_哔哩哔哩_bilibili 一、interface接口 接口类型内部存储了一对pair(value,Type) type interface { type *Type // 类型信…...
理解 Objective-C 中 `+load` 方法的执行顺序
理解 Objective-C 中 load 方法的执行顺序 在 Objective-C 中,load 方法是在类或分类被加载到内存时调用的。它在程序启动过程中非常早的阶段执行,用于在类或分类被加载时进行一些初始化工作。理解 load 方法的执行顺序对于编写可靠的 Objective-C 代码…...

C++:类和对象2
1.类的默认成员函数 默认成员函数就是用户没有显示实现编译器会自动生成的成员函数称为默认成员函数。一个类,我们在不写的情况下编译器会默认生成6个默认成员函数,分别是构造函数,析构函数,拷贝构造函数,拷贝赋值运算…...

Docker安装kkFileView实现在线文件预览
kkFileView为文件文档在线预览解决方案,该项目使用流行的spring boot搭建,易上手和部署,基本支持主流办公文档的在线预览,如doc,docx,xls,xlsx,ppt,pptx,pdf,txt,zip,rar,图片,视频,音频等等 官方文档地址:https://kkview.cn/zh-cn/docs/production.html 一、拉取镜像 do…...

ElasticSearch(四)— 数据检索与查询
一、基本查询语法 所有的 REST 搜索请求使用_search 接口,既可以是 GET 请求,也可以是 POST请求,也可以通过在搜索 URL 中指定索引来限制范围。 _search 接口有两种请求方法,一种是基于 URI 的请求方式,另一种是基于…...
Pytest之parametrize()实现数据驱动
一、Pytest之parametrize()实现数据驱动 方法: pytest.mark-parametrize(argsname,args_value) args_name:参数名称,用于将参数值传递给函数 args value:参数值:(列表和字典列表,元组和字典元组),有n个值那么用例执行n次 第一种用法…...
关于鸿蒙系统前景
鸿蒙系统的前景看起来非常乐观。 鸿蒙系统以其全新的分布式架构和快速运行速度,展现了其独特的优势。它没有历史包袱,可以轻量前进,这一点在开发适配上具有明显优势。此外,鸿蒙系统的最大优势在于其“万物互联”的…...

针对datax-web 中Swagger UI接口未授权访问
application.yml 添加以下配置 实现访问doc.html 以及/v2/api-docs 接口时需要进行简单的校验 swagger:basic:enable: trueusername: adminpassword: 12345 配置重启后再进行相关访问则需要输入用户名和密码...
生成式AI如何帮助小型企业高效运营?
即使只有几家或几十家店的小规模生意,也可以利用AI技术来提升效率。不管企业组织规模如何,未来可能会有新的工作流程需要适应。就像计算机编程一样,我们需要将业务逻辑拆解成多个可管理的小任务,并设计它们之间的协同关系。这样&a…...

2024最新网络安全自学路线,内容涵盖3-5年技能提升
01 什么是网络安全 网络安全可以基于攻击和防御视角来分类,我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术,而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域,都有攻与防两面…...
Postman API测试数据生成秘籍:技巧与实践
Postman API测试数据生成秘籍:技巧与实践 在API测试过程中,生成合适的测试数据是确保测试覆盖率和准确性的关键步骤。Postman作为流行的API开发和测试工具,提供了多种方法来生成和管理测试数据。本文将深入探讨Postman中API测试数据生成的技…...

【接口自动化_07课_Pytest+Excel+Allure完整框架集成_下】
目标:优化框架场景 1. 生成对应的接口关联【重点】 2. 优化URL基础路径封装【理解】 3. 利用PySQL操作数据库应用【理解】--- 怎么用python连接数据库、mysql 4. 通过数据库进行数据库断言【重点】 5. 通过数据库进行关联操作【重点】 一、接口关联:…...

Java开发之反射与动态代理
#来自ゾフィー(佐菲) 1 反射(Reflect) 运行期间,获取类的信息,进行一些操作。 运行时构造类的对象。运行时获取类的成员变量和方法。运行时调用对象的方法(属性)。 2 Class 类 Cla…...

实习日志1之大模型相关知识概览
一、RAB 1、介绍(提供检索和生成) RAG,全称为Retrieval-Augmented Generation,中文可以翻译为"检索增强生成",也有人说是召回增强生成。这是一种结合了检索和生成两种机器学习方法的新型框架,主…...
华为嵌入式面试题及参考答案(持续更新)
目录 详细讲TCP/IP协议的层数 材料硬度由什么决定? SD3.0接口电压标准 晶振市场失效率 RS232-C的硬件接口组成 详细讲眼图的功能 局域网传输介质有哪几类? 详细讲OSI模型 NMOS与PMOS的区别 I2C和SPI的区别 Static在C语言中的用法 堆栈和队列的区别 数组的时间复…...

Java二十三种设计模式-装饰器模式(7/23)
装饰器模式:动态扩展功能的灵活之选 引言 装饰器模式(Decorator Pattern)是一种结构型设计模式,用于在不修改对象自身的基础上,通过添加额外的职责来扩展对象的功能。 基础知识,java设计模式总体来说设计…...

正则表达式与文本处理
目录 一、正则表达式 1、正则表达式定义 1.1正则表达式的概念及作用 1.2、正则表达式的工具 1.3、正则表达式的组成 2、基础正则表达式 3、扩展正则表达式 4、元字符操作 4.1、查找特定字符 4.2、利用中括号“[]”来查找集合字符 4.3、查找行首“^”与行尾字符“$”…...

Python | Leetcode Python题解之第283题移动零
题目: 题解: class Solution:def moveZeroes(self, nums: List[int]) -> None:n len(nums)left right 0while right < n:if nums[right] ! 0:nums[left], nums[right] nums[right], nums[left]left 1right 1...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...