当前位置: 首页 > news >正文

[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]之间&#xff0c; 是:是否加水(加水y,用掉x,是否在[l,r]之间)(不加水y,用掉x,是否在[l,r]之间)先尝试加水&#xff0c;如…...

《华为数据之道》读书笔记六---面向自助消费的数据服务建设

七、从结果管理到过程管理&#xff0c; 从能“看”到能“管” 1、数据赋能业务运营 数字化运营旨在利用数字化技术获取、管理和分析数据&#xff0c;从而为企业的战略决策与业务运营提供可量化的、科学的支撑。 数字化运营归根结底是运营&#xff0c;旨在推动运营效率与能力的…...

go语言day18 reflect反射

Golang-100-Days/Day16-20(Go语言基础进阶)/day19_Go语言反射.md at master rubyhan1314/Golang-100-Days (github.com) 7-19 接口&#xff1a;底层实现_哔哩哔哩_bilibili 一、interface接口 接口类型内部存储了一对pair(value,Type) type interface { type *Type // 类型信…...

理解 Objective-C 中 `+load` 方法的执行顺序

理解 Objective-C 中 load 方法的执行顺序 在 Objective-C 中&#xff0c;load 方法是在类或分类被加载到内存时调用的。它在程序启动过程中非常早的阶段执行&#xff0c;用于在类或分类被加载时进行一些初始化工作。理解 load 方法的执行顺序对于编写可靠的 Objective-C 代码…...

C++:类和对象2

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

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 接口&#xff0c;既可以是 GET 请求&#xff0c;也可以是 POST请求&#xff0c;也可以通过在搜索 URL 中指定索引来限制范围。 _search 接口有两种请求方法&#xff0c;一种是基于 URI 的请求方式&#xff0c;另一种是基于…...

Pytest之parametrize()实现数据驱动

一、Pytest之parametrize()实现数据驱动 方法: pytest.mark-parametrize(argsname,args_value) args_name:参数名称&#xff0c;用于将参数值传递给函数 args value:参数值:(列表和字典列表&#xff0c;元组和字典元组)&#xff0c;有n个值那么用例执行n次 第一种用法&#xf…...

关于鸿蒙系统前景

鸿蒙系统的前景看起来非常乐观。‌ 鸿蒙系统以其全新的分布式架构和快速运行速度&#xff0c;‌展现了其独特的优势。‌它没有历史包袱&#xff0c;‌可以轻量前进&#xff0c;‌这一点在开发适配上具有明显优势。‌此外&#xff0c;‌鸿蒙系统的最大优势在于其“万物互联”的…...

针对datax-web 中Swagger UI接口未授权访问

application.yml 添加以下配置 实现访问doc.html 以及/v2/api-docs 接口时需要进行简单的校验 swagger:basic:enable: trueusername: adminpassword: 12345 配置重启后再进行相关访问则需要输入用户名和密码...

生成式AI如何帮助小型企业高效运营?

即使只有几家或几十家店的小规模生意&#xff0c;也可以利用AI技术来提升效率。不管企业组织规模如何&#xff0c;未来可能会有新的工作流程需要适应。就像计算机编程一样&#xff0c;我们需要将业务逻辑拆解成多个可管理的小任务&#xff0c;并设计它们之间的协同关系。这样&a…...

2024最新网络安全自学路线,内容涵盖3-5年技能提升

01 什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防两面…...

Postman API测试数据生成秘籍:技巧与实践

Postman API测试数据生成秘籍&#xff1a;技巧与实践 在API测试过程中&#xff0c;生成合适的测试数据是确保测试覆盖率和准确性的关键步骤。Postman作为流行的API开发和测试工具&#xff0c;提供了多种方法来生成和管理测试数据。本文将深入探讨Postman中API测试数据生成的技…...

【接口自动化_07课_Pytest+Excel+Allure完整框架集成_下】

目标&#xff1a;优化框架场景 1. 生成对应的接口关联【重点】 2. 优化URL基础路径封装【理解】 3. 利用PySQL操作数据库应用【理解】--- 怎么用python连接数据库、mysql 4. 通过数据库进行数据库断言【重点】 5. 通过数据库进行关联操作【重点】 一、接口关联&#xff1a…...

Java开发之反射与动态代理

#来自ゾフィー&#xff08;佐菲&#xff09; 1 反射&#xff08;Reflect&#xff09; 运行期间&#xff0c;获取类的信息&#xff0c;进行一些操作。 运行时构造类的对象。运行时获取类的成员变量和方法。运行时调用对象的方法&#xff08;属性&#xff09;。 2 Class 类 Cla…...

实习日志1之大模型相关知识概览

一、RAB 1、介绍&#xff08;提供检索和生成&#xff09; RAG&#xff0c;全称为Retrieval-Augmented Generation&#xff0c;中文可以翻译为"检索增强生成"&#xff0c;也有人说是召回增强生成。这是一种结合了检索和生成两种机器学习方法的新型框架&#xff0c;主…...

华为嵌入式面试题及参考答案(持续更新)

目录 详细讲TCP/IP协议的层数 材料硬度由什么决定? SD3.0接口电压标准 晶振市场失效率 RS232-C的硬件接口组成 详细讲眼图的功能 局域网传输介质有哪几类? 详细讲OSI模型 NMOS与PMOS的区别 I2C和SPI的区别 Static在C语言中的用法 堆栈和队列的区别 数组的时间复…...

Java二十三种设计模式-装饰器模式(7/23)

装饰器模式&#xff1a;动态扩展功能的灵活之选 引言 装饰器模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;用于在不修改对象自身的基础上&#xff0c;通过添加额外的职责来扩展对象的功能。 基础知识&#xff0c;java设计模式总体来说设计…...

正则表达式与文本处理

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

Python | Leetcode Python题解之第283题移动零

题目&#xff1a; 题解&#xff1a; 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编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...