本文主要是介绍力扣365-水壶问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
水壶问题
题目链接
解题思路
- 假设两个水壶分别为A,B,容量为a,b;想要凑出C升的水
- 将A,B两壶看作一个整体
- 那么,这个整体只存在四种操作+a,-a,+b,-b;
- +a:就是将A壶装满
- -a:就是将A壶清空
- +b:就是将B壶装满
- -b:就是将B壶清空
- 想要凑出C升的水壶,需要满足
xa+yb=c
- 即我们需要对A壶进行x次操作,对B壶进行y次操作,使得可以凑出C升的水
- 要想使得
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-水壶问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!