133. Clone Graph
我们也可以使用 BFS 来遍历图，使用队列 queue 进行辅助，还是需要一个 HashMap 来建立原图结点和克隆结点之间的映射。先克隆当前结点，然后建立映射，并加入 queue 中，进行 while 循环。在循环中，取出队首结点，遍历其所有 neighbor 结点，若不在 HashMap 中，我们根据 neigbor 结点值克隆一个新 neighbor 结点，建立映射，并且排入 queue 中。然后将 neighbor 结点在 HashMap 中的映射结点加入到克隆结点的 neighbors 数组中即可
Map.containsKey() :是否含有key
Map.get(key) : 获取key对应的value
class Solution {
public Node cloneGraph(Node node) {
if(node == null) return null;
Map<Node, Node> map = new HashMap<>();
Node newNode = new Node(node.val, new ArrayList<>());
map.put(node, newNode);
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while(!queue.isEmpty()){
Node cur = queue.poll();
for(Node nei : cur.neighbors){
if(!map.containsKey(nei)){
map.put(nei, new Node(nei.val, new ArrayList<>()));
queue.add(nei);
}
map.get(cur).neighbors.add(map.get(nei));
}
}
return newNode;
}
}399. Evaluate Division
用有向图的方法做，先存入图中，再用DFS遍历。
Map.keySet() : 获取map对应的所有的key值。
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> g = new HashMap<>();
buildGraph(g, equations, values);
double[] res = new double[queries.size()];
Arrays.fill(res, -1.0);
int index = 0;
for(List<String> q : queries){
String a = q.get(0);
String b = q.get(1);
if(!g.containsKey(a) || !g.containsKey(b)){
index++;
continue;
}else{
dfs(g, a, b, res, index, new HashSet<>(), 1.0);
index++;
}
}
return res;
}
private void dfs(Map<String, Map<String, Double>> g, String a, String b, double[] res,
int index, Set<String> visited, double tmp){
visited.add(a);
if(g.get(a) == null || g.get(a).size() == 0){
return;
}
if(g.get(a).containsKey(b)){
res[index] = g.get(a).get(b) * tmp;
return;
}
for(String next : g.get(a).keySet()){
if(visited.contains(next)) continue;
dfs(g, next, b, res, index, visited, g.get(a).get(next)*tmp);
}
}
private void buildGraph(Map<String, Map<String, Double>> g, List<List<String>> equations, double[] values){
int index = 0;
for(List<String> e : equations){
String a = e.get(0);
String b = e.get(1);
g.putIfAbsent(a, new HashMap<>());
g.putIfAbsent(b, new HashMap<>());
g.get(a).put(b, values[index]);
g.get(b).put(a, 1.0 / values[index]);
index++;
g.get(a).put(a, 1.0);
g.get(b).put(b, 1.0);
}
}
}223. Rectangle Area
尝试先找出所有的不相交的情况，只有四种，一个矩形在另一个的上下左右四个位置不重叠，这四种情况下返回两个矩形面积之和。其他所有情况下两个矩形是有交集的，这时候只要算出长和宽，即可求出交集区域的大小，然后从两个矩型面积之和中减去交集面积就是最终答案。求交集区域的长和宽也不难，由于交集都是在中间，所以横边的左端点是两个矩形左顶点横坐标的较大值，右端点是两个矩形右顶点的较小值，同理，竖边的下端点是两个矩形下顶点纵坐标的较大值，上端点是两个矩形上顶点纵坐标的较小值。之前是可以直接将 sum1 和 sum2 加起来的，可以后来OJ搞了些恶心的 test case，使得直接把 sum1 和 sum2 相加会溢出，所以只好分开了，若两个矩形有重叠，那么返回的时候也不能让 sum1 和 sum2 直接相加，中间一定要先减去重叠部分才行
class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int sum1 = (C - A) * (D - B), sum2 = (H - F) * (G - E);
if(E >= C || F >= D || B >= H || A >= G) return sum1 + sum2;
return sum1 - (Math.min(G, C) - Math.max(A, E)) * (Math.min(D, H) - Math.max(B, F)) + sum2;
}
}