迭代所有最短长度字符串的算法？

我正在做一个URL缩短器，我想为每个给定的URL使用尽可能最短的字符串。每个网址将有不同的到期日期。迭代所有最短长度字符串的算法？

例如，让我们提交得到缩短为以下列表中的URL：

a, b, c, ..., z, 0 ..., 9, aa, ab, ac, ... a9, ba

然后说c到期，所以接下来的URL缩短为c，而不是bb，因为c较短并没有被采取。

什么样的数据结构对于追踪这个很好？

2016-04-27 Cisplatin

这是一个有趣的问题。你需要几个数据结构。这是我会做的。

1）哈希表，以短URL作为键，以及所有URL信息（完整URL，到期时间等）作为值。

2）过期网址的最小堆。这将允许您快速获取并重新使用可用的最短网址。

3）一个字符串，用于跟踪正在使用的最长的短URL。这样，如果没有过期时间较短的用户，可以快速生成新的URL。

4）有些东西要记录到期时间，所以你可以有效地过期URL。它可以是日期 - > ShortURL形式的哈希表，并具有有序的键，因此您可以轻松获取下一个到期的URL。

2016-04-28 00:01:40 Macondo2Seattle

我会使用一个优先级队列，其比较器有嵌套规则，第一个是空的或采取的标志，第二个是在字符串上。请记住，PQ会将您最热门的对象放在队列顶部。作为结果的对象应该是字符串名称和布尔标志的组合。

2016-04-28 00:02:37 mohsenmadi

中PQ是行不通的对于任何数量的参赛作品来说，都必须有一个限制。 – Cisplatin

不是我所知道的。 PQ是[unbounded]（https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html），除非它以编程方式设置为某个限制。 – mohsenmadi

你说得对，实际上有一个简单的方法。另一个问题是，如果添加了大量元素，那么他们永远处于PQ中，占用大量空间。我想我可以定期清除它们。 – Cisplatin

我会使用2堆。

当你需要一个新的URL，从堆1.当URL过期顶部拉出，从堆2拉URL，并将其插入到堆1

2016-04-28 00:52:06

回答