1.水壶问题

　

水壶

leetcode 水壶问题

---

难度 中等

---

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

• 装满任意一个水壶
• 清空任意一个水壶
• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例1: (From the famous "Die Hard" example)

输入: x = 3, y = 5, z = 4
输出: True

示例2:

输入: x = 2, y = 6, z = 5
输出: False

解题思路

这个问题当然很容易想到用

z=a*x+b*y（a，b均整数）表示啦,但是怎么用编程语言来描述这个公式呢？

我一开始想用x与y的差值来表示z，通过设置a与b的值

然而这种方法很naive，a与b的设置方式有成千上万种，设置起来十分麻烦，如果用穷举法，耗时长，还不一定找得到

我错误的原因是忘记了这一点，把a,b关系想的太简单，结果对a，b设置错误

错误的算法：选出x，y中的max与min，设置a=1自增（即a为整数）

在a*min<max情况下，如果abs(a*min-max)==z,则可以。

不知道怎么想的，a，b关系也太简单了吧，还是没有好好想想

后来从别人的文章中发现

如果z=a*x+b*y（a，b均整），x与y最大公约数为g，那么z一定是g的整数倍，即z%g=0！！

？？！

这不是小学初中就教过吗，

就算没教过，想想也知道

a*x=a*n*g,b*y=b*m*g,如果z=（a*n+b*m）g，那z可不就是g的整数倍吗

居然没想到，-_-||

g还不好求吗，辗转相除法的事

代码

class Solution {
public boolean canmeasureWater(int x, int y, int z) {
        return z == 0 || (x + y >= z && z % gcd(x, y) == 0);
    }
    int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}

总结

又浪费了几个小时，解法却这么简单，智商受到碾压

相关阅读

高并发下System.currentTimeMillis()并发问题以及优化

前言 在高并发场景下System.currentTimeMillis()并发问题严重，甚至比创建一个普通对象要耗时的多；在系统中有时候不可避免要打印一

物联卡之家：企业应用物联网仍然存在一些问题限制

企业仍然对投资物联网持谨慎态度，采用的关键因素会影响其效率和可用性。这并不不能够否定物联网在企业应用的价值，这只意味着供应商

拍拍微店开通流程及其他相关问题汇总

电商蓬勃发展的今天，让更多的人看到了中国市场巨大的需求和潜力，大而全的电商平台在几大企业近乎垄断的情况下做起来相当困难。对于

进程cpu占用99%排查,罪魁nanosleep的取值限制问题

文章目录背景代码模拟编译执行后输出结果分析结论背景 某天客户反馈程序cpu占用99%,要求分析出问题,经排查发现是由于nanosleep函

Windows文件及文件夹命名规则之admini~1≈administrat

最近自己对admini~1≈administrator产生了一个疑问，百度等搜索引擎都搜索了下都没有好答案，最后经过测试，总结得出一个结果Windows对