3

我在一次采访中被问到这个问题。假设你有一个有序的字典,并且给定了一个无序字符列表——你将如何按优先顺序排列这些字符?该词典包含保证出现所有 26 个字符的单词。但是,请注意字典的大小可能是任何值。字典可能只有几个单词,并且每个字符可能没有单独的部分,例如,以a;开头的单词可能没有部分。尽管a将作为另一个词的一部分出现,例如“bat”。

字典可能是“有序的”(/sarcasm),例如“zebra”、“apple”、“cat”、“crass”,如果给定列表 { a, z, r},正确的顺序是 { z, a, r}. 由于字典中“zebra”在“apple”之前,所以我们知道z在之前a出现。由于“apple”在“cat”之前,我们知道a在之前c。因为“cat”在“crass”之前,我们知道出现a在 之前r。这个排序离开c并且r存在不确定性,但是由于字母列表是 { a, z, r},我们知道解决方案是 { z, a, r}。

4

3 回答 3

11

使用有 26 个顶点的有向图,每个顶点代表一个字符。从顶点 A 到顶点 B 的边意味着在字母表中 B 在 A 前面。

第一步是建立这样一个只有顶点但没有边的图。

其次,您逐字扫描输入字典。并将每个单词与前一个单词进行比较。您应该为您扫描的每个单词找到一个确切的关​​系。所以你在这个图中添加了一条边。假设字典是正确的,应该没有冲突。

完成字典后,您通过以下方式输出字母表

  1. 选择一个随机顶点,遍历它的路径,直到找到一个不指向任何东西的字符。这是字母表中的第一个字符。输出它并从图中删除它。
  2. 继续执行 1 直到所有顶点都被删除。

编辑:为了更好地解释这个算法,让我们在你的样本输入上运行它。

输入:{“斑马”、“苹果”、“猫”、“粗鲁”}

单词 0 和单词 1,我们马上就知道 z 在 a 之前,所以我们做一条边 a->z

单词 1 和单词 2,我们立即知道 a 在 c 之前,所以我们再做一条边 c->a

Word 2 和 Word 3,第一个字母是相同的“c”,但第二个字母不同,所以我们知道 a 在 r 之前,所以我们有另一个边 r->a

现在所有的单词都读完了。通过随机选择一个顶点来输出顺序(比如我们选择 c),然后我们在图中有 c->a->z。输出 z 并从图中删除 z(将其标记为 NULL)。现在选择另一个(假设我们选择 r),然后我们在图中找到 r->a。我们输出 a 并从图中删除 a。现在我们选择另一个(假设我们再次选择 c),没有找到路径,所以我们只输出 c 并删除它。现在我们选择最后一个,r,又没有路径了,所以我们输出r并删除它。由于删除了所有顶点,因此算法完成。

输出为 z、a、c、r。“c”和“r”的顺序是随机的,因为我们从输入中并不真正知道它们的关系。

于 2012-04-24T20:45:22.900 回答
1

从“zebra”<“apple”<“cat”<“crass”的事实来看,导出每个字符关系的最有效方法是让一个循环考虑所有单词的第 N 个字符,其中 N 最初为 0,产生关系“z”<“a”<“c”。该循环可以递归地提取具有相同前缀的单词组的第(N + 1)个字符的关系(即位置<= N的文本)。这样做是为了N == 1 具有相同前缀的“cat”和“crass”产生关系“a”<“r”。

我们可以在二维x < y真值数组中表示已知关系。

y\x a b c...r...z
a   -   N   N   Y
b     -
c   Y   -       Y
r   Y       -
z   N   N       -

The brute force approach is to iterate over all pairs of characters in the input list (i.e. {a, z, r} -> az, ar, zr) looking up the table for a<z, a<r, z<r: if this is ever false, then swap the characters and restart the whole she-bang. When you make it through the full process without having had to swap any more characters, the output is sorted consistently with the rules. This is a bit like doing a bubble sort.

为了加快速度,我们可以更主动地在表格中填充隐含关系的单元格:例如,我们知道“z”<“a”<“c”和“a”<“r”,所以我们推断“ z" < "r"。我们可以通过遍历上面的“naive”表来找到我们所知道的关于每个字符的所有信息(例如那个z<az<c)——然后遍历我们对 a 和 c 的了解。为避免树过深,您可以像这样只遵循一级间接,然后重复直到表稳定。

于 2012-04-25T08:44:00.410 回答
-3

根据您描述问题的方式,您的示例不正确。你的答案应该是{z,r,a}。然而,这可能是,下面是解决问题的代码。您可以修改它以返回与我设想的不同的订单{z,r,a}

Set<Character> charPrecedence(List<String> dictionary, char[] letters){
    Set<Character> result = new HashSet<Character>();
    //since your characters are the 26 letters instead of the 256 chars
    // a bit vector won't do; you need a map or set
    Set<Character> alphabets = new HashSet<Character>();
    for(char c: letters)
       alphabets.add(c);

    //now get to work
    for(String word: dictionary){
       if(alphabets.isEmpty()) return result;
       for(char c: word.toCharArray()){
          if(alphabets.remove(c))
           result.add(c);
       }
    }
    //since the dictionary is guaranteed to contain all the 26 letters,
    //per the problem statement, then at this point your work is done.
    return result;
}

最佳情况 O(1); 最坏情况 O(n) 其中 n 是字典中的字符数,即一个特定字母只出现一次,并且是您检查的最后一个字符。

于 2012-04-24T23:15:16.360 回答