Maybe nlogn accepted Java solution?


  • 0
    W
      public class Solution {
    	int counter = 0;
    	
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        	Map<String, Var> map = new HashMap<>();
        	List<Node> list = flip(equations, values);
        	sort(list);
        	
            for (Node n : list) {
            	String x = n.pair1;
            	String y = n.pair2;
            	Double z = n.value;
            	
            	if (!map.containsKey(x) && !map.containsKey(y)) {
            		char unit = getUnit();
            		map.put(x, new Var(unit, z));
            		map.put(y, new Var(unit, 1.0));
            	} else if (map.containsKey(x) && map.containsKey(y)) {
            		System.out.println("Again?");
            	} else if (map.containsKey(x)) {
            		Var av = map.get(x);
            		char unit = av.unit;
            		double val = av.val;
            		Var cv = new Var(unit, val / z);
            		map.put(y, cv);
            	} else {
            		Var bv = map.get(y);
            		char unit = bv.unit;
            		double val = bv.val;
            		Var cv = new Var(unit, val * z);
            		map.put(x, cv);
            	}
            }
            
            double[] res = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
            	String[] pair = queries[i];
            	String x = pair[0];
            	String y = pair[1];
            	if (!map.containsKey(x) || !map.containsKey(y)) {
            		res[i] = -1.0;
            	} else {
            		Var vx = map.get(x);
            		Var vy = map.get(y);
            		if (vx.unit != vy.unit) {
            			res[i] = -1.0;
            		} else {
            			res[i] = vx.val / vy.val;
            		}
            	}
            }
            return res;
        }
        
        public char getUnit() {
        	char res = (char) ('a' + counter);
        	counter++;
        	return res;
        }
        
        private void sort(List<Node> list) {
        	Collections.sort(list, new Comparator<Node>() {
                @Override
                public int compare(Node n1, Node n2) {
                    return n1.pair1.compareToIgnoreCase(n2.pair1);
                }
            });
        }
        
        private List<Node> flip(String[][] equations, double[] values) {
        	List<Node> list = new ArrayList<>();
        	for (int i = 0; i < equations.length; i++) {
        		String[] pair = equations[i];
        		String x = pair[0];
        		String y = pair[1];
        		double z = values[i];
        		
        		int compare = x.compareTo(y); 
        		if (compare > 0) {
        			list.add(new Node(1 / z, y, x));
        		} else {
        			list.add(new Node(z, x, y));
        		}
        	}
        	return list;
        }
        
        private class Node {
        	double value;
        	String pair1;
        	String pair2;
        	public Node (double val, String pair1, String pair2) {
        		this.value = val;
        		this.pair1 = pair1;
        		this.pair2 = pair2;
        	}
        }
        
        private class Var {
        	char unit;
        	double val;
        	public Var (char unit, double val){
        		this.val = val;
        		this.unit = unit;
        	}
        }
    }
    

  • 0
    J

    I came back to the problem and found that this solution is wrong. The solution get accepted because the test case of lc is weak.
    Try test case:
    [ ["a","e"],["c", "d"], ["d", "e"]]
    [1.0, 1.0, 1.0]
    [["a","c"]]

    answer shoule be 1.000, but the solution output -1.000


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.