java - 扁平化字典的采访Q

Question

有这个面试题。

写一个函数来展平字典数组example_input:
example_input= [{a:{b:{c:{d:'e'}}}}, {a:{b:{c:{d:{e:'f'}}}}}]
example_output: [{a_b_c_d:'e'}, {a_b_c_d_e:'f'}]

1. 如何在 java 中对该输入进行建模？
2. 如何用 Java 解决这个问题。

上面的输入可以映射到什么样的数据结构？

class Node {
   String s;
   Node node;
}

我尝试使用这个 Node 类，它会导致 {node:{node:{node:{s:'value'} 而不是 {a:{b:{c :{d:'e'}}}}.

Answer 1

不要忘记字典是一对 (key, value) 的集合，具有键唯一的不变性。所以你可以将它们表示为:

class Dict {
    List<Pair> pairs;
}

Pair 在哪里

class Pair {
    String key;
    Dict value;
}

或者如果你想要更一般的概念:

class Pair<T> {
    T key;
    Dict value;
}

请注意，您可以将单个值表示为一个 Pair 的 Dict，值为 null。然后你的展平功能无效

Dict flatten(Dict dict) {
    Dict new_dict = new Dict();
    for (Pair pair : dict.pairs) {
        if (pair.value == null)
            new_dict.pairs.add(pair);
        else
            new_dict.pairs.addAll(combine(pair.key, flatten(pair.value)));
    }
}

List<Pair> combine(String key, Dict value) { //here value is a flattened dict
    List<Pair> pairs = new ArrayList<Pair>();
    for (Pair pair : value.pairs) {
        pairs.add(new Pair(key + "_" + pair.key, pair.value));
    }
    return pairs;
}