视频网站开发的视频放在哪,网络科技有限公司的简介,公司在百度做网站找谁,工装哪家装修公司好有一个水壶容量或者两个水壶加起来总容量为目标容量
总共有八种选择#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);}
}
