7

我在准备考试时遇到了以下问题：

想象一个单词的字母表。例子：

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

任何有关如何解决此问题的指示将不胜感激。

4

2 回答 2

7

让我给你一些提示：

  • 你能找到一个给定长度的单词数量的公式k吗？
  • 现在确定一个长度k和一个字母l。它们以多少字k开头l？

提示：帕斯卡三角形。如果您需要更多提示，http ://en.wikipedia.org/wiki/Combinadic可以提供帮助。如果您需要一些实现，您可以从（Python 语言）中定义的 rank 函数中获得灵感https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py

于 2013-07-16T17:41:37.350 回答
2
  1. 确保输入仅为字母。没有就失败。
  2. 根据字符串长度减 1 设置循环。
  3. 从下一个中“减去”字符串中第一个字母的值。如果该值为零或正数，则完成，因为字符串不升序，因此返回 0。
  4. 通过一次一个字母地向上移动字符串来重复检查下一个字母。
  5. 如果你到最后，它是一个升序字符串。

公平地说，我没有提到如何计算指数值的算法，只是退出案例。但它为您提供了一个正确方向的开始，并且计算指数将遵循相同的框架。

更多信息：

从第一个字母开始向上数。当您点击“z”时，重置为下一个有效字符串并继续计数 - >“aa”失败不要计算它。添加到下一个，这里是“ab”。一旦你点击“az”，尝试“ba” - 失败，继续添加字母，直到你得到一个有效的字符串“bc”并重新开始计数。它就像一个向上计数的里程表。

该死的慢，但它应该可以工作，因为它是您手动执行的操作以获得答案。

顺便说一句，@hivert 暗示了一个更优雅的解决方案，几乎可以立即计算......

于 2013-07-16T17:39:14.513 回答