力扣365-水壶问题

本文主要是介绍力扣365-水壶问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

水壶问题

题目链接

解题思路

1. 假设两个水壶分别为A,B,容量为a，b；想要凑出C升的水
2. 将A,B两壶看作一个整体
3. 那么，这个整体只存在四种操作+a，-a，+b，-b；
4. +a：就是将A壶装满
5. -a：就是将A壶清空
6. +b：就是将B壶装满
7. -b：就是将B壶清空
8. 想要凑出C升的水壶，需要满足xa+yb=c
9. 即我们需要对A壶进行x次操作，对B壶进行y次操作，使得可以凑出C升的水
10. 要想使得xa+yb=c成立，由裴蜀定理知道，要使的a和b的最大公约数可以整除c

class Solution {
public:int gcd(int a,int b){return b ? gcd(b,a % b) : a;}bool canMeasureWater(int a, int b, int c) {if(c > a + b) return false;return !c || c % gcd(a,b) == 0;}
};

这篇关于力扣365-水壶问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---