乐趣区

关于后端:面试高频题源于场景八股文的算法题

jiezi

题目形容

这是 LeetCode 上的 535. TinyURL 的加密与解密 ，难度为 中等。

Tag :「哈希表」、「模仿」

TinyURL 是一种 URL 简化服务，比方：当你输出一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的 URL http://tinyurl.com/4e9iAk。

请你设计一个类来加密与解密 TinyURL。

加密和解密算法如何设计和运作是没有限度的，你只须要保障一个 URL 能够被加密成一个 TinyURL，并且这个 TinyURL 能够用解密办法复原成本来的 URL。

实现 Solution 类：

  • Solution() 初始化 TinyURL 零碎对象。
  • String encode(String longUrl) 返回 longUrl 对应的 TinyURL。
  • String decode(String shortUrl) 返回 shortUrl 本来的 URL。题目数据保障给定的 shortUrl 是由同一个零碎对象加密的。

示例：

输出：url = "https://leetcode.com/problems/design-tinyurl"

输入："https://leetcode.com/problems/design-tinyurl"

解释：Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后失去的 TinyURL。string ans = obj.decode(tiny); // 返回解密后失去的本来的 URL。

提醒：

  • $1 <= url.length <= 10^4$
  • 题目数据保障 url 是一个无效的 URL

模仿 + 哈希表

对于每个 longUrl 咱们都在「大写字母 / 小写字母 / 数字」中随机 $k = 6$ 位作为其映射标识，这须要应用一个哈希表 tiny2Origin 进行记录。

同时了避免雷同的 longUrl 屡次调用，确保 encode 服务的「幂等性」，咱们再额定建设哈希表 origin2Tiny 来记录原串和映射标识的对应关系。

Java 代码：

public class Codec {Map<String, String> origin2Tiny = new HashMap<>(), tiny2Origin = new HashMap<>();
    String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
    String prefix = "https://acoier.com/tags/";
    int k = 6;
    Random random = new Random();
    public String encode(String longUrl) {while (!origin2Tiny.containsKey(longUrl)) {char[] cs = new char[k];
            for (int i = 0; i < k; i++) cs[i] = str.charAt(random.nextInt(str.length()));
            String cur = prefix + String.valueOf(cs);
            if (tiny2Origin.containsKey(cur)) continue;
            tiny2Origin.put(cur, longUrl);
            origin2Tiny.put(longUrl, cur);
        }
        return origin2Tiny.get(longUrl);
    }
    public String decode(String shortUrl) {return tiny2Origin.get(shortUrl);
    }
}

Python 代码：

class Codec:
    def __init__(self):
        self.origin_to_tiny = {}
        self.tiny_to_origin = {}
        self.k = 6
        self.prefix = 'https://acoier.com/tags/'
        self.ss = string.ascii_letters + string.digits

    def encode(self, longUrl: str) -> str:
        while longUrl not in self.origin_to_tiny.keys():
            cur = ''.join([self.ss[random.randint(0,len(self.ss) - 1)] for _ in range(self.k)])
            if cur in self.tiny_to_origin.keys():
                continue
            self.tiny_to_origin[cur] = longUrl
            self.origin_to_tiny[longUrl] = cur
        return self.origin_to_tiny[longUrl]
        
    def decode(self, shortUrl: str) -> str:
        return self.tiny_to_origin[shortUrl]
  • 工夫复杂度：encode 操作复杂度为 $O(C + L)$，其中 $C = 6$ 为短串长度，$L$ 为传入参数 longUrl 的长度（存入哈希表须要计算 longUrl 哈希值，该过程须要遍历 longUrl）；decode 操作复杂度为 $O(C)$，其中 $L$ 为传入参数 shortUrl 的长度，该长度固定为 prefix 长度加 $6$
  • 空间复杂度：$O(K \times L)$，其中 $K$ 为调用次数，$L$ 为均匀 longUrl 长度

对于应用「自增 id」的答疑

群里有同学问到为啥要应用「哈希存储映射关系」的形式，而不是用「自增 id」的形式，感觉可能是一部分同学的独特纳闷，这里对立答复一下。

其中两点较为致命的弊病是：

  1. 应用「自增 id」更容易被枚举；

    （再补充，提出原问题的好奇宝宝又问了另外一个问题）对于被枚举的害处：粗略来说会导致安全性降落，被攻打的可能性大大加强。因为可枚举意味着，不能光靠 URL 特定发放来确保安全。

    联合具体场景来说，假如某个流动日期生成了短 URL 的流动链接，只有特定用户能够拜访，可枚举意味着竞品只须要大略晓得你自增 id 以后在什么范畴即可拿到流动链接，即便流动链接做了鉴权，也能通过攻打伎俩导致服务申请数量突增，影响实在的流动用户应用。

    或者这个场景并不致命，竞品要拿到流动链接有很多形式，未必是通过枚举短 URL 来做到。

    但另外一个场景则是致命的，就是可枚举会导致应用短 URL 服务的「验证服务」生效。

    例如某个服务会通过「邮件 / 短信」发送短 URL 链接，让用户通过点击短 URL 来验证是否为某个「邮箱 / 手机号」的拥有者，短 URL 可枚举，意味着只须要晓得以后自增 id 大略范畴，就可通过枚举的形式拜访到实在的验证地址，从而实现「不收到某个邮件 / 短信」也能够通过验证的目标。

  2. 相比于应用「哈希存储映射关系」的形式，不好重用：
举个🌰，例如映射关系都是 $7$ 天过期，每天会产生了 $10$ 个短 URL，当进行到第 $8$ 天，此时 `id` 曾经自增到 $71$，同时第一天产生的短 URL 已过期，然而实现上，咱们不好将 `id` 进行回拨（须要思考当重用数字用完后要回到 $71$ 的地位）。也就是说，发现而且重用某些数字段（过期的 `id`）会为“自增”带来困扰，而引入「重用池」则违反了抉择自增计划的初衷。但「哈希存储映射关系」要实现重用则是简略的，如果随机产生的短 URL 发生冲突，只须要间接回绝进行重试即可，一旦产生短 URL 无抵触，则能够间接应用。同时因为随机通常遵从某种散布，咱们毋庸引入「过期工夫戳」等信息，即可达到「某个短 URL 在应用后的一段时间后，都不会被随机到（不会在过期后就被迅速重用）」的作用，这一点能够通过调大 $k$ 值来进一步保障。

防杠申明：当然，如果你只是在单纯的做算法题，就当我没说 🤣

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.535 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版