163 lines
5.7 KiB
Markdown
163 lines
5.7 KiB
Markdown
# 毎日一题 - 水壶问题
|
||
|
||
## 信息卡片
|
||
|
||
* 时间：2019-09-15
|
||
* 题目链接：https://leetcode-cn.com/problems/water-and-jug-problem/
|
||
* tag：`Math`
|
||
## 题目描述
|
||
```
|
||
给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。
|
||
```
|
||
|
||
## 参考答案
|
||
|
||
1.数学分析解答
|
||
|
||
上面的问题是一个特例，我们可以抽象为[leetcode-365-水壶问题](https://leetcode-cn.com/problems/water-and-jug-problem/)。
|
||
```
|
||
有两个容量分别为 x升 和 y升 的水壶（壶1，壶2）以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
|
||
```
|
||
|
||
解题核心思路（x < y，即壶1容量小于壶2，x == y的情况后面讨论）：
|
||
|
||
1. 将壶2倒满，往壶1倒入至满。
|
||
2. 若壶1满，记录当前壶2中新水量。壶1倒出，将壶2中剩余的继续往壶1中倒入；（当壶1满，继续此操作，并记录当前壶2中新水量nw， 若此新水量已被记录，则）。
|
||
3. 若出现壶1不满时（即此时壶2必空），重复操作1。
|
||
|
||
开辟一个新数组nws记录所有新水量，对任意nws[i]，可构造的水量为nws[i]，nws[i]+x，nws[i]+y。
|
||
|
||
（其实不需要新数组，因为数学上可以证明新水量的值循环周期呈现，故可以使用一个临时变量cur，当cur==x为终止条件）
|
||
|
||
数学证明新水量nw值是循环周期的：
|
||
|
||
|
||
个别特殊情况考虑：
|
||
|
||
- x == z || y == z; **true**
|
||
- x == 0 || x+y < z; **false**
|
||
- x+y == z || z == 0; **true**
|
||
|
||
```c++
|
||
class Solution {
|
||
public:
|
||
bool canMeasureWater(int x, int y, int z) {
|
||
if(x > y) return canMeasureWater(y, x, z);
|
||
if(x == z || y == z) return true;
|
||
if(x == 0 || x+y < z) return false;
|
||
if(x+y == z || z == 0) return true;
|
||
int cur = y - x;
|
||
while(cur != x){
|
||
if(cur == z) return true;
|
||
if(cur > x){
|
||
if(cur + x == z) return true;
|
||
cur = cur - x;
|
||
}
|
||
else{
|
||
if(cur + y == z || cur + x == z) return true;
|
||
cur = y - x + cur;
|
||
}
|
||
}
|
||
return false;
|
||
}
|
||
};
|
||
```
|
||
|
||
2.BFS
|
||
|
||
不仅可以计算是否能获取 z 升水，而且可以获得最少多少操作可获取 z 升水。（缺点，无法通过，因为需要太大的空间，需要申请一个三维数组记录状态）
|
||
|
||
核心思想就是状态转移问题：
|
||
|
||
壶0（x+y），壶1（x），壶2（y），壶0是本是无限大水池，同理于定义为大小为x+y的壶。用bfs的思想，使用一个队列记录所有新的状态。
|
||
|
||
对于任意状态（c，a，b），状态转移就是：
|
||
|
||
- 若c不为0，将壶0倒水入壶1或壶2；若a不为0，将壶1倒水入壶0或壶2；若b不为0，将壶2倒水入壶0或壶1；
|
||
- 记录每个新状态，并入队，若此状态访问过则不入队。
|
||
|
||
特殊情况考虑同1。
|
||
|
||
```c++
|
||
class Solution {
|
||
public:
|
||
struct state{
|
||
int nums[3];
|
||
state(int xy, int x, int y){
|
||
nums[0] = xy;
|
||
nums[1] = x;
|
||
nums[2] = y;
|
||
}
|
||
};
|
||
|
||
state pour_water(state cur, int src, int det, int size[]){
|
||
state ans = cur;
|
||
int need_w = size[det] - cur.nums[det];
|
||
if(need_w <= cur.nums[src]){
|
||
ans.nums[det] += need_w;
|
||
ans.nums[src] -= need_w;
|
||
}
|
||
else{
|
||
ans.nums[det] += ans.nums[src];
|
||
ans.nums[src] = 0;
|
||
}
|
||
return ans;
|
||
}
|
||
|
||
bool canMeasureWater(int x, int y, int z) {
|
||
if(x > y) return canMeasureWater(y, x, z); //
|
||
if(x == z || y == z) return true;
|
||
if(x == 0 || x+y < z) return false;
|
||
if(x+y == z || z == 0) return true;
|
||
int visited[x+y+1][x+1][y+1];
|
||
int water_size[3] = {x+y, x, y};
|
||
memset(visited, 0, sizeof(visited));
|
||
state cur(x+y, 0, 0);
|
||
queue<state> q;
|
||
q.push(cur);
|
||
int step = 0;
|
||
while(!q.empty()){
|
||
int size = q.size();
|
||
while(size){
|
||
state temp(0, 0, 0);
|
||
cur = q.front();
|
||
if(cur.nums[1] + cur.nums[2] == z) return true;
|
||
visited[cur.nums[0]][cur.nums[1]][cur.nums[2]] = 1;
|
||
q.pop();
|
||
if(cur.nums[0] != 0){
|
||
temp = pour_water(cur, 0, 1, water_size);
|
||
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
|
||
q.push(temp);
|
||
temp = pour_water(cur, 0, 2, water_size);
|
||
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
|
||
q.push(temp);
|
||
}
|
||
if(cur.nums[1] != 0){
|
||
temp = pour_water(cur, 1, 2, water_size);
|
||
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
|
||
q.push(temp);
|
||
temp = pour_water(cur, 1, 0, water_size);
|
||
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
|
||
q.push(temp);
|
||
}
|
||
if(cur.nums[2] != 0){
|
||
temp = pour_water(cur, 2, 1, water_size);
|
||
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
|
||
q.push(temp);
|
||
temp = pour_water(cur, 2, 0, water_size);
|
||
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
|
||
q.push(temp);
|
||
}
|
||
size--;
|
||
}
|
||
step++;
|
||
}
|
||
return false;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 优秀解答
|
||
|
||
>暂缺
|