当前位置: 首页 > 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...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

MeanFlow:何凯明新作,单步去噪图像生成新SOTA

1.简介 这篇文章介绍了一种名为MeanFlow的新型生成模型框架&#xff0c;旨在通过单步生成过程高效地将先验分布转换为数据分布。文章的核心创新在于引入了平均速度的概念&#xff0c;这一概念的引入使得模型能够通过单次函数评估完成从先验分布到数据分布的转换&#xff0c;显…...