[leedcode][JAVA][365][BFS]

【问题描述】

有两个容量分别为 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

【解答思路】

1. 广度优先遍历BFS

• set 确保情况不重复
• queue 遍历所有情况

public boolean canMeasureWater_BFS(int x, int y, int z) {if (z < 0 || z > x + y) {return false;}Set<Integer> set = new HashSet<>();Queue<Integer> q = new LinkedList<>(); //巧妙过度q.offer(0); //遍历所有情况 第一次 x,y入队列while (!q.isEmpty()) {int n = q.poll(); //巧妙限制条件！if (n + x <= x + y && set.add(n + x)) {q.offer(n + x);}if (n + y <= x + y && set.add(n + y)) {q.offer(n + y);}if (n - x >= 0 && set.add(n - x)) {q.offer(n - x);}if (n - y >= 0 && set.add(n - y)) {q.offer(n - y);}if (set.contains(z)) {return true;}}return false; }

2.数学方法 最大公约数

public boolean canMeasureWater(int x, int y, int z) {if (z == 0) return true;if (x + y < z) return false;int big = Math.max(x, y);int small = x + y - big;if (small == 0) return big == z;//最大公约数 while (big % small != 0) {int temp = small;small = big % small;big = temp;}return z % small == 0; }

【总结】

1. 想清楚所有可能，列小点实现，善用容器，巧用边界

2. Queue操作

• add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
• remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
• element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
• offer 添加一个元素并返回true 如果队列已满，则返回false
• poll 移除并返问队列头部的元素 如果队列为空，则返回null
• peek 返回队列头部的元素 如果队列为空，则返回null
• put 添加一个元素 如果队列满，则阻塞
• take 移除并返回队列头部的元素

3.Collections

Set 和List 都继承了Conllection,Map没有
Collection接口的方法：

• boolean add(Object o) :向集合中加入一个对象的引用
• void clear() :删除集合中所有的对象，即不再持有这些对象的引用
• boolean isEmpty() :判断集合是否为空
• boolean contains(Object o): 判断集合中是否持有特定对象的引用
• Iterartor iterator() : 返回一个Iterator对象，可以用来遍历集合中的元素
• boolean remove(Object o):从集合中删除一个对象的引用
• int size() :返回集合中元素的数目
• Object[] toArray() :返回一个数组，该数组中包括集合中的所有元素
• 关于：Iterator() 和toArray() 方法都用于集合的所有的元素，前者返回一个Iterator对象，后者返回一个包含集合中所有元素的数组。
  Iterator接口声明了如下方法:
• hasNext(): 判断集合中元素是否遍历完毕，如果没有，就返回true
• next() :返回下一个元素
• remove():从集合中删除上一个有next()方法返回的元素。
  Set 的 add()方法是如何判断对象是否已经存放在集合中？

boolean isExists=false;Iterator iterator=set.iterator();while(it.hasNext()) {String oldStr=it.next();if(newStr.equals(oldStr)){isExists=true;}

总结

以上是生活随笔为你收集整理的[leedcode][JAVA][365][BFS]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。