leetcode Water and Jug Problem

leetcode Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

Operations allowed:

  • Fill any of the jugs completely.
  • Empty any of the jugs.
  • Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:

Example 2:

题目地址:leetcode Water and Jug Problem

题意: 给定两个杯子,它们分别能装x和y升水,求它们是否能恰好测量出z升的水。

思路:

题目可以表示为如下等式:

  • mx + ny = z
  • 若m,n>0说明往里面加水,若m,n <0则说明清空

如x=3,y=5 可以有  3 x  + (-1)y = 4 即 m=3 , n=-1 ,也就是说我们需要往3这个杯子装满3次,5这个杯子倒掉1次

  • 首先往3的杯子注满水,然后倒入倒入5    杯子情况为: 0,3
  • 接着把3的杯子注满水,在倒入5 ,杯子情况为  1,5
  • 接着把5的杯子倒掉, 把3的杯子装入5, 这样为 0,1
  • 接着把3的杯子注满水,倒入5, 这样0,4

可以参考  : http://www.math.tamu.edu/~dallen/hollywood/diehard/diehard.htm

本题中,若mx + ny = z 有解,则一定有z为GCD(x,y) 的整数倍,否则无解。

且需要满足条件 x + y >=z

 

C++

Java

Python

 

本题是leetcode 365 Water and Jug Problem 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Water and Jug Problem
本文地址:https://www.hrwhisper.me/leetcode-water-jug-problem/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *