Java just calculate without DFS/BFS


  • 0
    W

    Given a / b = 2.0, b / c = 3.0.

    For input a / b = 2.0, we can make a = 2, b = 1
    For input b / c = 3.0, cause we know b = 1, so c = 1/3

    If you have all values, you can calculate easily.

    Given a / b = 3, e / f = 2, b / e = 4

    For input a / b = 3, as above, we can make a = 3, b = 1
    For input e / f = 2, we can not make f = 1, e = 2 cause we do not know the relationship between b and f.

    So we introduce a list of base

    make a = 3 * base1, b=base1
    make e = 2 * base2, f = base2
    cause b / e = 4, base1 = 4 * 2 * base2, so we know the realtionship between base1 and base2.

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Node> map = new HashMap<>();
        Map<Integer, List<String>> bases = new HashMap<>();
        for (int i = 0; i < values.length; i++) {
          String a = equations[i][0], b = equations[i][1];
          Node aNode = map.get(a), bNode = map.get(b);
          if (Objects.isNull(aNode) && Objects.isNull(bNode)) {
            map.put(a, new Node(values[i], bases.size()));
            map.put(b, new Node(1d, bases.size()));
            bases.put(bases.size(), Lists.newArrayList(a, b));
          } else if (Objects.nonNull(aNode) && Objects.nonNull(bNode)) {
            if (aNode.base == bNode.base) continue;
            double val = values[i] * bNode.val;
            bases.get(aNode.base).stream().map(s -> map.get(s)).forEach(node -> {
              node.val *= val;
              node.base = bNode.base;
            });
            bases.get(bNode.base).addAll(bases.remove(aNode.base));
          } else if (Objects.isNull(aNode)) {
            map.put(a, new Node(bNode.val * values[i], bNode.base));
            bases.get(bNode.base).add(a);
          } else {
            map.put(b, new Node(aNode.val / values[i], aNode.base));
            bases.get(aNode.base).add(b);
          }
        }
        int i = 0;
        double[] result = new double[queries.length];
        for (String[] query : queries) {
          String a = query[0], b = query[1];
          Node aNode = map.get(a), bNode = map.get(b);
          if (Objects.isNull(aNode) || Objects.isNull(bNode) || aNode.base != bNode.base) result[i++] = -1d;
          else result[i++] = aNode.val / bNode.val;
        }
        return result;
      }
    
      class Node {
        public double val;
        public int base;
        public Node(double val, int base) {
          this.val = val;
          this.base = base;
        }
      }

Log in to reply
 

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