做sgs认证的公司网站,浪琴女士手表网站,西宁市网站建设公司推荐,优秀学习网站LeetCode 第365题#xff1a;水壶问题
#x1f4d6; 文章摘要
本文详细解析LeetCode第365题水壶问题#xff0c;这是一道数学和广度优先搜索问题。文章提供了基于数学和BFS的两种解法#xff0c;包含C#、Python、C三种语言实现#xff0c;配有详细的算法分析…LeetCode 第365题水壶问题 文章摘要
本文详细解析LeetCode第365题水壶问题这是一道数学和广度优先搜索问题。文章提供了基于数学和BFS的两种解法包含C#、Python、C三种语言实现配有详细的算法分析和性能对比。适合想要提升数学思维和搜索算法的读者。
核心知识点 数学、广度优先搜索、最大公约数、状态搜索 难度等级 中等 推荐人群 具有基础算法知识想要提升数学思维的程序员
题目描述
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶从而可以得到恰好 z升 的水
如果可以最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许
装满任意一个水壶清空任意一个水壶从一个水壶向另外一个水壶倒水直到装满或者倒空
示例
示例 1
输入x 3, y 5, z 4
输出True
解释我们可以先装满5升的水壶然后倒3升到3升的水壶中此时5升水壶中剩余2升水。然后倒空3升水壶将5升水壶中的2升水倒入3升水壶中。最后装满5升水壶此时5升水壶中有5升水3升水壶中有2升水总共7升水。然后从5升水壶中倒出1升水到3升水壶中此时5升水壶中有4升水3升水壶中有3升水总共7升水。所以我们可以得到4升水。示例 2
输入x 2, y 6, z 5
输出False
解释我们无法得到5升水。提示
0 x 10^60 y 10^60 z 10^6
解题思路
本题可以使用数学或BFS解决 数学解法 使用贝祖定理判断z是否能被x和y的最大公约数整除 BFS解法 使用队列进行状态搜索记录已访问的状态枚举所有可能的操作
时间复杂度
数学解法O(log(min(x,y)))BFS解法O(xy)
空间复杂度
数学解法O(1)BFS解法O(xy) 算法流程演示 图解思路
数学解法
步骤操作说明1计算gcd(x,y)使用辗转相除法2判断z%gcd0判断是否有解3判断zxy判断是否可行
BFS状态转移
状态操作新状态(a,b)装满x(x,b)(a,b)装满y(a,y)(a,b)倒空x(0,b)(a,b)倒空y(a,0)(a,b)x倒入y(max(0,ab-y),min(y,ab))(a,b)y倒入x(min(x,ab),max(0,ab-x))
代码实现
C# 实现
public class Solution {public bool CanMeasureWater(int x, int y, int z) {if (z 0) return true;if (x y z) return false;return z % GCD(x, y) 0;}private int GCD(int a, int b) {while (b ! 0) {int temp b;b a % b;a temp;}return a;}
}Python 实现
class Solution:def canMeasureWater(self, x: int, y: int, z: int) - bool:if z 0:return Trueif x y z:return Falsedef gcd(a, b):while b:a, b b, a % breturn areturn z % gcd(x, y) 0C 实现
class Solution {
public:bool canMeasureWater(int x, int y, int z) {if (z 0) return true;if (x y z) return false;return z % gcd(x, y) 0;}private:int gcd(int a, int b) {while (b) {int temp b;b a % b;a temp;}return a;}
};执行结果
C# 实现
执行用时36 ms内存消耗14.8 MB
Python 实现
执行用时28 ms内存消耗13.2 MB
C 实现
执行用时0 ms内存消耗5.9 MB
性能对比
语言执行用时内存消耗特点C0 ms5.9 MB执行效率最高内存占用最小Python28 ms13.2 MB代码简洁内存占用适中C#36 ms14.8 MB类型安全内存占用较大
代码亮点 使用数学方法优雅解决 处理边界情况和特殊情况 使用辗转相除法计算最大公约数 代码结构清晰易于维护
常见错误分析 未处理z0的情况 未处理xyz的情况 最大公约数计算错误 整数溢出
解法对比
解法时间复杂度空间复杂度优点缺点数学解法O(log(min(x,y)))O(1)高效实现简单需要数学知识BFS解法O(xy)O(xy)直观易于理解效率较低
相关题目
LeetCode 365. 水壶问题 - 中等LeetCode 279. 完全平方数 - 中等LeetCode 322. 零钱兑换 - 中等 系列导航 算法专题合集 - 查看完整合集 关注合集更新点击上方合集链接关注获取最新题解目前已更新第365题。 互动交流
感谢大家耐心阅读到这里希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助请 点个赞让更多人看到这篇文章 收藏文章方便后续查阅复习 关注作者获取更多高质量算法题解 评论区留言分享你的解题思路或提出疑问
你的支持是我持续分享的动力 一起进步算法学习路上不孤单欢迎一起交流学习 互动交流
感谢大家耐心阅读到这里希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助请 点个赞让更多人看到这篇文章 收藏文章方便后续查阅复习 关注作者获取更多高质量算法题解 评论区留言分享你的解题思路或提出疑问
你的支持是我持续分享的动力 一起进步算法学习路上不孤单欢迎一起交流学习
