2

这是一道面试题：

Imagine an alphabet of words. Example:
a ==> 1
b ==> 2
c ==> 3
.
z ==> 26
ab ==> 27
ac ==> 28
.
az ==> 51
bc ==> 52
and so on.

这样字符序列只需按升序排列（ab 有效，但 ba 无效）。给定任何单词，如果有效则打印其索引，否则打印 0。

Input Output
ab 27
ba 0
aez 441

注意：不允许暴力破解。这是问题的链接：http: //www.careercup.com/question?id=21117662

我可以将该解决方案理解为：

  • 总字数为 2^26 -1。
  • 对于给定的单词，大小小的单词首先出现。
  • 设 n 为单词的长度，
    • 大小小于 n 的单词总数为 C(26, 1) + C(26, 2) + ...+ C(26, n -1)
  • 然后计算在给定单词之前有多少个大小相同的单词
  • 两个数加一的和就是结果

参考：sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft

在示例解决方案中，我了解了作者如何计算大小小于 word.size() 的单词数。但是，在代码中，我不太确定如何找到与 word.size() 大小相同且出现在“word”之前的单词数。

准确地说，这一点：

char desirableStart;  
i = 0;
while( i < str.size()){     
    desirableStart = (i == 0) ? 'a' : str[i - 1] + 1;   

    for(int j = desirableStart; j < str[i]; ++j){
        index += NChooseK('z' - j, str.size() - i - 1);     // Choose str.size() - i - 1 in the available charset
    }

    i ++;
}

有人可以帮我理解这一点吗？谢谢。

4

2 回答 2

2

首先（您可能得到了这部分，但为了完整起见），该NChooseK函数计算二项式系数，即从一组n 个元素中选择k个元素的方法数。您的评论中提到了此功能，因此我将使用相同的符号。C(n, k)

由于字母是排序的而不是重复的，这正是创建问题中描述的n 个字母单词的方法的数量，所以这就是函数的第一部分让你处于正确位置的原因：

int index = 0;
int i = 1;

while(i < str.size()) {
    // choose *i* letters out of 26
    index += NChooseK(26, i);
    i++;
}

例如，如果您的输入是aez，这将获得单词 的索引yz，这是最后一个可能的 2 字母组合：C(26, 1) + C(26, 2) = 351。

此时，您有了n字母单词的初始索引，并且需要查看需要跳过多少个n字母单词组合才能到达单词的末尾。为此，您必须检查每个单独的字母并计算所有可能的字母组合，从前一个字母之后的一个字母（desirableStart代码中的变量）开始，并以正在检查的字母结尾。

例如，aez您将按以下方式进行：

  1. 获取最后 2 个字母的单词索引 ( yz)。
  2. 将 index 加一（这实际上是在代码末尾完成的，但在这里这样做以保持正确的位置更有意义）：现在我们在 index of abc.
  3. 第一个字母是a，不需要增加。你还在abc。
  4. 第二个字母是e，计算第二个字母的组合 from bto e。这将使您到达aef（请注意，这f是此示例中的第一个有效的第三个字符，并desirableStart会处理该问题）。
  5. 第三个字母是z，计算第三个字母的组合，从f到z。这会让你aez。

这就是代码的最后一部分所做的：

// get to str.size() initial index (moved this line up)
index ++;

i = 0;
while( i < str.size()) { 

    // if previous letter was `e`, we need to start with `f`
    desirableStart = (i == 0) ? 'a' : str[i - 1] + 1;   

    // add all combinations until you get to the current letter
    for (int j = desirableStart; j < str[i]; ++j) {

        char validLettersRemaining = 'z' - j;
        int numberOfLettersToChoose = str.size() - i - 1;
        index += NChooseK(validLettersRemaining, numberOfLettersToChoose);
    }

    i++;
}

return index;
于 2013-08-14T11:48:35.733 回答
0

相同大小的单词数的计算与较短单词的对应物之间没有区别。

您可能会被从 0 开始的 c 中数组的索引引入歧途。因此，尽管i < str.size()可能会提出其他建议，但该循环的最后一次迭代实际上计算了与计算其索引的单词大小相同的单词。

于 2013-08-14T10:11:10.520 回答