2024.1.28力扣每日一题——水壶问题
2024.1.28
- 题目来源
- 我的题解
- 方法一 深度搜索(DFS)/广度搜索(BFS)
- 方法二 数学
题目来源
力扣每日一题;题序:365
我的题解
方法一 深度搜索(DFS)/广度搜索(BFS)
首先对题目进行建模。观察题目可知,在任意一个时刻,此问题的状态可以由两个数字决定:X 壶中的水量,以及 Y 壶中的水量。
在任意一个时刻,我们可以且仅可以采取以下几种操作:
把 X 壶的水灌进 Y 壶,直至灌满或倒空;
把 Y 壶的水灌进 X 壶,直至灌满或倒空;
把 X 壶灌满;
把 Y 壶灌满;
把 X 壶倒空;
把 Y 壶倒空。
因此,本题可以使用深度优先搜索来解决。搜索中的每一步以 cap1, cap2 作为状态,即表示 X 壶和 Y 壶中的水量。在每一步搜索时,我们会依次尝试所有的操作,递归地搜索下去。这可能会导致我们陷入无止境的递归,因此我们还需要使用一个哈希结合(HashSet)存储所有已经搜索过的 cap1, cap2 状态,保证每个状态至多只被搜索一次。但是由于数据量问题,导致递归空间不足,因此最终使用广度优先实现。
时间复杂度:O(xy),状态数最多有 (x+1)(y+1)种,对每一种状态进行深度优先搜索的时间复杂度为 O(1),因此总时间复杂度为 O(xy)。
空间复杂度:O(xy),由于状态数最多有 (x+1)(y+1) 种,哈希集合中最多会有 (x+1)(y+1) 项,因此空间复杂度为 O(xy)。
//未使用哈希函数进行优化,直接将两个杯子的值构建字符串,利用字符串类重写了哈希函数的特点保证集合中出现的内容唯一。public boolean canMeasureWater(int x, int y, int z) {if (x + y < z) {return false;}if (x == z || y == z || x + y == z) {return true;}Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{0, 0});Set<Long> seen = new HashSet<>();while (!queue.isEmpty()) {int[] state = queue.poll();int remain_x = state[0], remain_y = state[1];if (seen.contains(hash(state))) {continue;}seen.add(hash(state));if (remain_x == z || remain_y == z || remain_x + remain_y == z) {return true;}// 把 X 壶灌满。queue.offer(new int[]{x, remain_y});// 把 Y 壶灌满。queue.offer(new int[]{remain_x, y});// 把 X 壶倒空。queue.offer(new int[]{0, remain_y});// 把 Y 壶倒空。queue.offer(new int[]{remain_x, 0});// 把 X 壶的水灌进 Y 壶,直至灌满或倒空。queue.offer(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});// 把 Y 壶的水灌进 X 壶,直至灌满或倒空。queue.offer(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});}return false;}
//使用哈希函数进行优化,自定义哈希函数。
public boolean canMeasureWater(int x, int y, int z) {if (x + y < z) {return false;}if (x == z || y == z || x + y == z) {return true;}Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{0, 0});Set<Long> seen = new HashSet<>();while (!queue.isEmpty()) {int[] state = queue.poll();int remain_x = state[0], remain_y = state[1];if (seen.contains(hash(state))) {continue;}seen.add(hash(state));if (remain_x == z || remain_y == z || remain_x + remain_y == z) {return true;}// 把 X 壶灌满。queue.offer(new int[]{x, remain_y});// 把 Y 壶灌满。queue.offer(new int[]{remain_x, y});// 把 X 壶倒空。queue.offer(new int[]{0, remain_y});// 把 Y 壶倒空。queue.offer(new int[]{remain_x, 0});// 把 X 壶的水灌进 Y 壶,直至灌满或倒空。queue.offer(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});// 把 Y 壶的水灌进 X 壶,直至灌满或倒空。queue.offer(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});}return false;}private long hash(int[] state) {return (long) state[0] * 1000001 + state[1];}
方法二 数学
数学理论看:官方题解
时间复杂度:O(log(min(x,y))),取决于计算最大公约数所使用的算法的时间复杂度
空间复杂度:O(1)
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {if(jug1Capacity+jug2Capacity<targetCapacity)return false;if(jug1Capacity==0||jug2Capacity==0)return targetCapacity==0||jug1Capacity+jug2Capacity==targetCapacity;return targetCapacity%gcd(jug1Capacity,jug2Capacity)==0;
}
public int gcd(int x,int y){int z=x%y;while(z!=0){x=y;y=z;z=x%y;}return y;
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~
相关文章:
2024.1.28力扣每日一题——水壶问题
2024.1.28 题目来源我的题解方法一 深度搜索(DFS)/广度搜索(BFS)方法二 数学 题目来源 力扣每日一题;题序:365 我的题解 方法一 深度搜索(DFS)/广度搜索(BFSÿ…...
orin nx 安装paddlespeech记录
nx配置: 模块 版本说明 CPU 8核 内存 16G Cuda版本 11.4 Opencv版本 4.5.4 Tensorrt版本 5.1 Cudnn版本 8.6.0.166 Deepstream版本 6.2 Python版本 3.8 算力 100T 安装paddlepaddle: 去飞桨官网下载jetpack版本的:下…...
系统架构设计师-21年-上午答案
系统架构设计师-21年-上午答案 更多软考资料 https://ruankao.blog.csdn.net/ 1 ~ 10 1 前趋图(Precedence Graph)是一个有向无环图,记为:→{(Pi,Pj)|Pi must complete before Pj may strat},假设系统中进程P{P1,P2,P3…...
外包干了10个月,技术退步明显...
先说一下自己的情况,大专生,18年通过校招进入武汉某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...
树莓派Pico入门
文章目录 1. Pico概述1.1 微处理器1.2 GPIO引脚1.3 MicroPython优点 2. 硬件准备2.1 购买清单2.2 软件需求 3. 安装MicroPython3.1下载固件3.2把固件安装到硬件里3.3补充 4. 第一个程序5. 验证运行效果6. 扩展应用 1. Pico概述 1.1 微处理器 ARM Cortex-M0 (频率 133MHz) 1.…...
yolov8使用旋转框自己做数据集检测
主要在数据集制作,训练的步骤和目标检测是一样的 1.数据集标注主要使用rolabelimg工具,这个工具不能在线安装 得下载源代码 然后运行 标注好数据保存会是一个xml文件 2.把xml文件转换成dota的xml文件,然后把dota的xml文件转换成dota的txt文件…...
docker重建镜像
DockerFile如下: FROM k8s-registry.qhtx.local/base/centos7-jdk8-haitong0704RUN yum -y update && yum install -y python3-devel && yum install -y python36 RUN mv /usr/bin/python /usr/bin/python_old RUN ln -s /usr/bin/python3 /usr/bi…...
【Linux】vim的基本操作与配置(上)
Hello everybody!今天我们要进入vim的讲解了。学会了vim,咱们就可以在Linux系统上做一些简单的编程啦! 那么废话不多说,咱们直接进入正题! 1.初识vim vim是一款多模式的文本编辑器,可以对一个文件进行编辑操作。 它一共有三个模…...
幻兽帕鲁怎么样?好玩? Mac版的玩《幻兽帕鲁》也很简单,只需三个步骤
幻兽帕鲁怎么样 幻兽帕鲁是一款集合了多种游戏元素的游戏,它巧妙地融合了《方舟:生存进化》的野外生存挑战、《荒野之息》的开放世界探索、《魔兽世界》的多元角色互动以及宝可梦的精灵捕捉与培养等经典游戏元素。游戏的核心系统是「帕鲁」捕获,你可以让…...
002集——统一码(Unicode)及ASCII码详解
统一码(Unicode),它也叫万国码、单一码,是计算机科学领域里的一项业界标准,包括字符集、编码方案等。Unicode是为了解决传统的字符编码方案的局限而产生的,它为每种语言中的每个字符设定了统一并且唯一的二进制编码,以…...
下载、安装Jenkins
进入官网 下载Jenkins https://www.jenkins.io 直接点击Download 一般是下长期支持版 因为它是java写的,你要运行它(Jenkins.war)肯定要有java环境 有两种方式去运行它,一种是下载Tomcat(是很经典的java容器或者jav…...
python flask 魔术方法
魔术方法作用_init_对象的初始化方法_class_返回对象所属的类_module_返回类所在的模块_mro_返回类的调用顺序,可以找到其父类(用于找父类)_base_获取类的直接父类(用于找父类)_bases_获取父类的元组,按它们…...
2024清洁能源、环境与智慧城市国际研讨会(ISCEESC2024)
2024清洁能源、环境与智慧城市国际研讨会(ISCEESC2024) 会议简介 2024年清洁能源、环境与智慧城市国际研讨会(ISCEESC2024)将在中国丽江举行。本次会议主要围绕清洁能源、环境和智慧城市等研究领域,旨在为该研究领域的专家学者提供一个国际…...
Postgres与DynamoDB:选择哪个数据库
启动新项目时需要做出的决定之一是使用哪个数据库。如果您使用的是Django这样的包含电池的框架,那么没有理由再三考虑。选择一个受支持的数据库引擎,就可以了。另一方面,如果你使用像FastAPI或Flask这样的微框架,你需要自己做出这…...
【ELK】logstash快速入门
1.概述 1.1.什么是logstash? 之前我们聊了es,并且用docker搭建了一个eskibana的环境。es目前最普遍的用法是用来存储日志的,然后结合kibana对日志做一些可视化的工作。既然要收集日志,就面临着一个问题: 各个系统的…...
SQL sever2008中创建用户并赋权
一、创建数据库dream CREATE DATABASE dream; 二、创建登录用户XZS 法一:使用SSMS创建 通过查询 sys.syslogins 系统视图来确定当前登录是否具有系统管理员权限。执行以下查询语句: SELECT name, isntname FROM sys.syslogins WHERE sysadmin 1;选…...
SpringBoot2-Jwt
1.官网 jwt.io/libraries 2.选jose4j pom <dependency><groupId>org.bitbucket.b_c</groupId><artifactId>jose4j</artifactId><version>0.9.4</version> </dependency> 3.创建jwt工具 public class JwtUtil {private stat…...
2、安全开发-Python-Socket编程端口探针域名爆破反弹Shell编码免杀
用途:个人学习笔记,欢迎指正! 目录 主要内容: 一、端口扫描(未开防火墙情况) 1、Python关键代码: 2、完整代码:多线程配合Queue进行全端口扫描 二、子域名扫描 三、客户端,服务端Socket编程通信cmd命…...
Python 套接字详解:与网络通信的温柔邂逅
网络世界,犹如一片无垠的海洋,充满了无限的可能性和无尽的探索。而在这个浩瀚的网络宇宙中,Python 语言以其简洁优雅、功能丰富而备受青睐。在 Python 的世界里,有一个神奇的工具,它就像是一座桥梁,将不同的…...
如何在Linux系统中安装MySQL
要在Linux系统中安装MySQL,您可以使用系统的包管理工具。以下是一些常见的Linux发行版的安装命令: 1. **Ubuntu/Debian:** bash sudo apt-get update sudo apt-get install mysql-server 2. **Fedora:** bash sudo dnf install mysql-server 3. **Cent…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
