有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升水。
你允许:
•装满任意一个水壶•清空任意一个水壶•从一个水壶向另外一个水壶倒水,直到装满或者倒空
示例 1: (From the famous *"Die Hard"* example[2])
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
首先我们要明确一点,每次操作仅仅会让桶中水的总量增加 x或增加 y,减少或减少 y。
因为在题目给定的条件下,两个桶不存在都有水并且都不满的情况,换言之,操作后,两个桶中水至少一个是空或者满。再者,我们分析易知:对一个不满的桶加水是没有什么意义的,为什么呢?因为给一个不满的桶加水其实就相当于将该桶初始化为满桶水;同理将一个未装满水桶的水倒掉也没有意义。
通过分析我们还能得出,两桶水的总量是否能满足给定的z是取决于x、y两桶容量的差值,也就是说差的制造是通过反复将大桶中的水倒入小桶产生的,整个操作描述如下:
1.往 y 壶倒水
2.把 y 壶的水倒入 x 壶 3.如果 y 壶不为空,那么 x 壶肯定是满的,把 x 壶倒空,然后再把 y 壶的水倒入 x 壶 4.重复以上操作直至某一步时 x 壶进行了 m 次倒空操作,y 壶进行了 n 次倒水操作。
由贝祖定理可得:mx+ny=z,当且仅当z是x、y最大公约数的倍数时,成立,因此,我们只需找出x、y最大公约数即可。
/**
* @param {number} x
* @param {number} y
* @param {number} z
* @return {boolean}
*/
var canMeasureWater = function(x, y, z) {
if (x + y < z) {
return false;
}
if (x === 0 || y === 0) {
return (z === 0) || (x + y === z);
}
return (z % calcGcd(x, y)) === 0;
};
function calcGcd(a, b) {
if (b === 0) {
return a;
}
return calcGcd(b, a % b);
}
key是虚拟节点的唯一id,通过可以能够更快更准确找到更新前对应的虚拟节点。
Vue
和React
都是通过diff算法对比新旧虚拟树节点差异,然后更新节点。当新旧节点对比不一致时,会根据节点的key去找寻旧节点,如果未找到则表明为新的节点,反之会进行复用。
针对这个问题我们应该辩证看待,并不是说书写key一定是好的,一定是提升性能的。
如果是简单列表,且列表只是单纯数据展示,无相关状态的更改,则可不使用key,这样在数据更新重新渲染时会更快,因为会跳过key的检索与复用逻辑
不管何时,都要求列表必须带key,大家阅读过React
都会发现,在commit阶段,更新操作通过复用来提升性能,这样虽然会有额外性能开销,但是对比频繁的DOM更新,还是能接受的。
[1]
365. 水壶问题: https://leetcode-cn.com/problems/water-and-jug-problem/
[2]
*"Die Hard"* example: https://www.youtube.com/watch?v=BVtQNK_ZUJg
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!