遍历所有最短字符串的算法？

Question

我正在制作一个URL缩短器，并希望为每个给定的URL使用尽可能短的字符串。每个URL都将有不同的过期日期。

例如，我们提交的URL将被缩短为以下列表：

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

然后，假设c过期了，那么下一个URL应该缩短为c而不是bb，因为c更短且未被占用。

哪种数据结构适合跟踪这个呢？

- Cisplatin

Answer 1

这是一个有趣的问题。你需要几个数据结构来解决它。以下是我的做法：

1）哈希表，以短网址为键，以所有URL信息（完整URL、过期时间等）为值。

2）一个过期URL的最小堆。这将使您能够快速获取并重用可用的最短URL。

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

4）某种方式来跟踪过期时间，以便您可以有效地使URL过期。它可以是哈希表，形式为日期->短URL，具有有序键，因此您可以轻松地获取下一个过期的URL。

- TotoroTotoro

Answer 2

我会使用一个优先队列，其比较器具有嵌套规则。第一条规则是检查是否为空或已被占用的标志，第二条规则是字符串。请记住，PQ将您最需要的对象保持在队列顶部。因此，您的对象应该是字符串名称和布尔标志的组合。

- mohsenmadi

---

一个优先队列无法处理任意数量的条目，必须有一个限制。 - Cisplatin

据我所知没有。除非程序上设置了某个限制，否则PQ是无界的。 - mohsenmadi

其实你是对的，有一个简单的方法可以解决这个问题。但另一个问题是，如果添加了大量元素，它们将永远存在于PQ中，占用大量空间。我想我可以定期清除它们。 - Cisplatin

这取决于应用程序。如果维护了一个简单的计数器来跟踪过期的URL，则PQ只能增长到一定的限制。一旦过期的URL数量超过限制，我们就可以删除/轮询对象。 - mohsenmadi

Answer 3

我会使用两个堆。

1. 一个最小堆用于未使用的URL，其中最小值是URL。
2. 一个最小堆用于已使用的URL，其中最小值是自1970年1月1日以来的秒数（长整型值）。

当您需要新的URL时，请从堆1的顶部获取。当URL过期时，请从堆2中获取URL并将其插入堆1。

- James Oravec