淄博网站制作高端营销,wordpress七牛云图床,wordpress 侧 悬浮插件,淄博seo排名TinyURL 是一种 URL 简化服务#xff0c; 比如#xff1a;当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时#xff0c;它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。
加密和解密算法如何设计和运作是没有限…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 104 题目数据保证 url 是一个有效的 URL
解法一可将长url存入数据库中id为自增主键每次存放后会得到数据库中一个自增长的id然后将带有该id的url作为短url
class Solution {
public:Solution () {id 0;}// Encodes a URL to a shortened URL.string encode(string longUrl) {db[id] longUrl;string shortUrl string(http://tinyurl.com/) to_string(id);id;return shortUrl;}// Decodes a shortened URL to its original URL.string decode(string shortUrl) {int idStartIdx shortUrl.rfind(/) 1;int id stoi(shortUrl.substr(idStartIdx, shortUrl.size() - idStartIdx));return db[id];}private:int id;unordered_mapint, string db;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));如果长url的长度为n此算法中encode方法的时间复杂度为On空间复杂度为Ondecode方法的时间复杂度为O1空间复杂度为O1。
解法二哈希生成选两个合适的质数k1_111117k2_22109^997使用以下方法计算长url的哈希值 然后encode函数将哈希值和长url存入数据库并返回含有哈希值的短url。decode函数可根据短url中的哈希值从数据库中取出长url。
当发生哈希冲突时采用线性探测再散列的方法将key加1直到没有冲突。相同的长url的哈希值相同哈希冲突可能会频繁发生为避免这一点我们使用一个额外的哈希表记录从长url到哈希值的映射。
const long long k1 1117;
const long long k2 1e9 7;class Solution {
public:// Encodes a URL to a shortened URL.string encode(string longUrl) {if (urlToKey[longUrl] 0) {return string(http://tinyurl.com/) to_string(urlToKey[longUrl]);}int key 0, base 1;for (char c : longUrl) {int key (key c * base) % k2;int base (base * k1) % k2;}while (db.find(key) ! db.end()) {key (key 1) % k2;}db[key] longUrl;return string(http://tinyurl.com/) to_string(key);}// Decodes a shortened URL to its original URL.string decode(string shortUrl) {int idStartIdx shortUrl.rfind(/) 1;int id stoi(shortUrl.substr(idStartIdx, shortUrl.size() - idStartIdx));return db[id];}private:unordered_mapint, string db;unordered_mapstring, int urlToKey;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));如果长url的长度为n此算法中encode方法的时间复杂度为On在数据量远小于10e97的情况下哈希冲突很少发生空间复杂度为Ondecode方法的时间复杂度为O1空间复杂度为O1。
计算字符串的哈希时类似于计算一个数字如1234它等于1 * 10³ 2 * 10² 3 * 10 4 * 1。
解法三随机生成随机生成一个key如果key已存在则继续生成直到出现不存在的key
class Solution {
public:// Encodes a URL to a shortened URL.string encode(string longUrl) {default_random_engine e(time(0));uniform_int_distributionint u(0, INT_MAX);int key u(e);while (db.find(key) ! db.end()) {key u(e);}db[key] longUrl;return string(http://tinyurl.com/) to_string(key);}// Decodes a shortened URL to its original URL.string decode(string shortUrl) {int idStartIdx shortUrl.rfind(/) 1;int id stoi(shortUrl.substr(idStartIdx, shortUrl.size() - idStartIdx));return db[id];}private:unordered_mapint, string db;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));如果长url的长度为n此算法中encode方法的时间复杂度为On空间复杂度为Ondecode方法的时间复杂度为O1空间复杂度为O1。
