「微软」2023 开刷 535 ~ 编码解码短 URL
IPFS
基本信息
- 题号:535
- 题厂:微软
- 难度系数:中
![](https://assets.matters.news/embed/f8d32422-cbce-42ce-a686-9d84aafceb93.png)
已知一个 URL,自定义「编码」「解码」算法,生成短 URL。原 URL 和生成的短 URL 可以编码解码查询……
例如 "https://leetcode.com/problems/design-tinyurl" 编码后输出 "http://tinyurl.com/4e9iAk" 为题目要求的短 URL 输入编码后的短 URL "http://tinyurl.com/4e9iAk",可以解码回原 URL —— "https://leetcode.com/problems/design-tinyurl"
背景介绍 - TinyUrl 「系统设计」入门经典题
在 TinyUrl 系统设计题中,我们需要设计一个数据库,存放 「Tiny Url - Origin Url」的对应表单;
同时还需要设计各种 component 让用户可以从万千数据行中迅速找到自己的 TinyUrl 再指向原装 Url;以及新用户如何创建「Tiny Url - Origin Url」的 entry;过期的 TinyUrl 如何从系统删除……问题 🤪;
在考试过程中,我们还需要和考官充分讨论系统需要 handle 的用户流量以及 Url 数量,来决定编码的长度。例如:XX 位 「0-9」「a-z」……粗略估算数据库可以提供 Url 存量……
但是,作为 TinyUrl 延伸出来的算法题,这里我们不需要考虑有多少用户,需要存放多少 Url……只需要保证编码解码的一致和唯一性即可……
解题思路
- 弄明白题目题目需求后,为了保证唯一性和一致型,很容易想到 HashMap 需要出场解题;
- 想到 HashMap 后,下一步需要思考如何保证 HashMap 里 key 的一致性。这里可以用常规的 random 方法随机生成,也可以直接 1 2 3 4 5……排下去
class Codec: # 初始两个 HashMap:encodeMap「longUrl,shortUrl」,decodeMap「shortUrl,longUrl」。 # 再创建一个 base url 备用…… def __init__(self): self.encodeMap = {} self.decodeMap = {} self.base = "http://tinyurl.com/" # 当检测到需要创建新的 TinyUrl 时,编码的 key 为当前 HashMap 长度➕ 1(最简单的一种编法🥴) def encode(self, longUrl: str) -> str: """Encodes a URL to a shortened URL. """ if longUrl not in self.encodeMap: url = self.base + str(len(self.encodeMap) + 1) self.encodeMap[longUrl] = url self.decodeMap[url] = longUrl return url else: return self.encodeMap[longUrl] # 解码非常简单…… def decode(self, shortUrl: str) -> str: """Decodes a shortened URL to its original URL. """ if shortUrl in self.decodeMap: return self.decodeMap[shortUrl] else: return "Url not found..."
Constraints
1 <= url.length <= 104
url is guranteed to be a valid URL.
测试
- 随便放几个去编码解码……
- ……
Big O
时间复杂度:O(1),HashMap 查找复杂度是 1 🥲
- 空间复杂度: O(n)算上创建了 HashMap 🥲
总结
- 刨除 TinyUrl 系统设计题目背景,本题的算法解题思路部分应该算简单档才是……
- 然鹅欲解此题,和有没有 TinyUrl 系统设计背景知识无关……
喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!