山东城建设计院网站,cdr平面设计教程,阿里云邮箱企业邮箱,产品推广方案ppt有一个水壶容量或者两个水壶加起来总容量为目标容量
总共有八种选择#xff1a;第一种倒满x,第二种倒满y,第三种清空x,第四种清空y,第五种x 倒给 y y能装满 #xff0c;第六种 x 倒给 y x倒完, 。。。。
这里用深度遍历#xff0c;时间超时
class Solution {public boole…有一个水壶容量或者两个水壶加起来总容量为目标容量
总共有八种选择第一种倒满x,第二种倒满y,第三种清空x,第四种清空y,第五种x 倒给 y y能装满 第六种 x 倒给 y x倒完, 。。。。
这里用深度遍历时间超时
class Solution {public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {//深度递归//用一个visited map来判断 当前情况是否能成功因此只需要置为false一次即可不需要反复操作//存储水量涉及到判断重写写一个类来存储State state new State(0, 0);ArrayListState states new ArrayList();return dfs(jug1Capacity,jug2Capacity,targetCapacity,state,states);}private boolean dfs(int jug1Capacity, int jug2Capacity, int targetCapacity, State state, List states) {if (states.contains(state))return false;states.add(state);//结束条件if (state.x 0 || state.y 0 || state.x jug1Capacity || state.y jug2Capacity)return false;if (state.x targetCapacity || state.y targetCapacity || state.x state.y targetCapacity)return true;//总共有八种情况//第一种倒满x,第二种倒满y,第三种清空x,第四种清空y,第五种x 倒给 y y能装满 第六种 x 倒给 y x倒完, 。。。。if (dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(jug1Capacity,state.y),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x, jug2Capacity),states)||dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(0, state.y),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x, 0),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x - (jug2Capacity - state.y), jug2Capacity),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(0, state.y state.x),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(jug1Capacity, state.y - (jug1Capacity - state.x)),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x state.y, 0),states))return true;return false;}
}class State{int x;int y;public State(int x, int y) {this.x x;this.y y;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;State state (State) o;return x state.x y state.y;}Overridepublic int hashCode() {return Objects.hash(x, y);}
}
