LeetCode 535. 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_map<int, string> db;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));
如果长url的长度为n,此算法中,encode方法的时间复杂度为O(n),空间复杂度为O(n);decode方法的时间复杂度为O(1),空间复杂度为O(1)。
解法二:哈希生成,选两个合适的质数k1_11=1117,k2_22=109^99+7,使用以下方法计算长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_map<int, string> db;unordered_map<string, int> urlToKey;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));
如果长url的长度为n,此算法中,encode方法的时间复杂度为O(n),在数据量远小于10e9+7的情况下,哈希冲突很少发生,空间复杂度为O(n);decode方法的时间复杂度为O(1),空间复杂度为O(1)。
计算字符串的哈希时,类似于计算一个数字,如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_distribution<int> 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_map<int, string> db;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));
如果长url的长度为n,此算法中,encode方法的时间复杂度为O(n),空间复杂度为O(n);decode方法的时间复杂度为O(1),空间复杂度为O(1)。
相关文章:
LeetCode 535. TinyURL 的加密与解密
TinyURL 是一种 URL 简化服务, 比如:当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时,它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。 加密和解密算法如何设计和运作是没有限…...
【c++】类和对象2—构造函数、析构函数、拷贝构造函数
文章目录构造函数和析构函数构造函数的分类及调用拷贝构造函数调用时机构造函数调用规则深拷贝与浅拷贝构造函数和析构函数 c利用了构造函数和析构函数解决上述问题,这两个函数将会被编译器自动调用,完成对象初始化和清理工作。对象的初始化和清理工作是…...
[C++关键字] const/constexpr
文章目录const/constexpr[^1]const 与 宏const 与 类const 与 指针const 其他constexpr (C11之后)referenceconst/constexpr1 尽可能的使用constexpr对于不变的变量,尽量用const修饰 const 与 宏 const vs define的比较:define只是字符的替换…...
FPGA电源电流参数
一、FPGA里各个电源释义 VCCINT VCCINT是FPGA芯片的内核电压,是用来给FPGA内部的逻辑门和触发器上的电压。即芯片的晶体管开关是有核心电压提供。当内部逻辑工作时钟速率越高,使用逻辑资源越多,则核心电压供电电流会更大,可高达几…...
【Git】Git下载安装与使用(一)
目录 1. 前言 1.1 什么是Git 1.2 使用Git能做什么 2. Git概述 2.1 Git简介 2.2 Git下载与安装 3. Git代码托管服务 3.1 常用的Git代码托管服务 3.2 码云代码托管服务 1. 前言 1.1 什么是Git Git是一个分布式版本控制工具,主要用于管理开发过程中的源代码…...
刷题记录:牛客NC20545[HEOI2012]采花
传送门:牛客 题目描述: 题目较长,此处暂略 输入: 5 3 5 1 2 2 3 1 1 5 1 2 2 2 2 3 3 5 输出: 2 0 0 1 0总结一下题意,就是求区间[l,r][l,r][l,r]出现次数大于1的花的种类数. 考虑使用主席树或者离线树状数组的方法来解决.由于数据加强的原因,导致主席树在本题中是不能完美通…...
每日学术速递2.21
CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.T2I-Adapter: Learning Adapters to Dig out More Controllable Ability for Text-to-Image Diffusion Models 标题:T2I-Adapter:学习Adapter,为…...
网络安全之认识挖矿木马
一、什么是挖矿木马? 比特币是以区块链技术为基础的虚拟加密货币,比特币具有匿名性和难以追踪的特点,经过十余年的发展,已成为网络黑产最爱使用的交易媒介。大多数勒索病毒在加密受害者数据后,会勒索代价高昂的比特币…...
OpenCV实战——基于分水岭算法的图像分割
OpenCV实战——基于分水岭算法的图像分割0. 前言1. 分水岭算法2. 分水岭算法直观理解3. 完整代码相关链接0. 前言 分水岭变换是一种流行的图像处理算法,用于快速将图像分割成同质区域。分水岭变换主要基于以下思想:当图像被视为拓扑浮雕时,均…...
YOLOv8模型调试记录
前言 新年伊始,ultralytics 公司在 2023 年 1月 10 号开源的 YOLOv5 的下一个重大更新版本,目前支持图像分类、物体检测和实例分割任务,在还没有开源时就收到了用户的广泛关注。 值得一提的是,在博主的印象中,YOLO系…...
算法刷题打卡第97天:删除字符串两端相同字符后的最短长度
删除字符串两端相同字符后的最短长度 难度:中等 给你一个只包含字符 a,b 和 c 的字符串 s ,你可以执行下面这个操作(5 个步骤)任意次: 选择字符串 s 一个 非空 的前缀,这个前缀的所有字符都相…...
WebGPU学习(3)---使用IndexBuffer(索引缓冲区)
现在让我们将 IndexBuffer 与 VertexBuffer 一起使用。演示示例 1.准备索引数据 我们用 Uint16Array 类型来准备索引数据。我们将矩形的4个点放到 VertexBuffer 中,然后根据三角形绘制顺序,组织成 0–1–2 和 0–2–3 的结构。 const quadIndexArray …...
Java代码加密混淆工具有哪些?
在Java中,代码加密混淆工具可以帮助开发者将源代码进行加密和混淆处理,以增加代码的安全性和保护知识产权。以下是一些流行的Java代码加密混淆工具: 第一款:ProGuard:ProGuard ProGuard:ProGuard…...
华为OD机试 - 高效的任务规划(Python) | 机试题+算法思路+考点+代码解析 【2023】
高效的任务规划 题目 你有 n 台机器编号为1-n,每台都需要完成一项工作, 机器经过配置后都能独立完成一项工作。 假设第i台机器你需要花 Bi 分钟进行设置, 然后开始运行,Ji分钟后完成任务。 现在,你需要选择布置工作的顺序,使得用最短的时间完成所有工作。 注意,不能同…...
ChatGPT写程序如何?
前言ChatGPT最近挺火的,据说还能写程序,感到有些惊讶。于是在使用ChatGPT有一周左右后,分享一下用它写程序的效果如何。1、对于矩阵,把减法操作转换加法?感觉不错的,能清晰介绍原理,然后写示例程…...
编译链接实战(9)elf符号表
文章目录符号的概念符号表探索前面介绍了elf文件的两种视图,以及两种视图的各自几个组成部分:elf文件有两种视图,链接视图和执行视图。在链接视图里,elf文件被划分成了elf 头、节头表、若干的节(section)&a…...
React合成事件的原理是什么
事件介绍 什么是事件? 事件是在编程时系统内发生的动作或者发生的事情,而开发者可以某种方式对事件做出回应,而这里有几个先决条件 事件对象 给事件对象注册事件,当事件被触发后需要做什么 事件触发 举个例子 在机场等待检票…...
Arduino-交通灯
LED交通灯实验实验器件:■ 红色LED灯:1 个■ 黄色LED灯:1 个■ 绿色LED灯:1 个■ 220欧电阻:3 个■ 面包板:1 个■ 多彩杜邦线:若干实验连线1.将3个发光二极管插入面包板,2.用杜邦线…...
【论文笔记】Manhattan-SDF == ZJU == CVPR‘2022 Oral
Neural 3D Scene Reconstruction with the Manhattan-world Assumption 本文工作:基于曼哈顿世界假设,重建室内场景三维模型。 1.1 曼哈顿世界假设 参考阅读文献:Structure-SLAM: Low-Drift Monocular SLAM in Indoor EnvironmentsIEEE IR…...
好消息!Ellab(易来博)官方微信公众号开通了!携虹科提供专业验证和监测解决方案
自1949年以来,丹麦Ellab一直通过全球范围内的验证和监测解决方案,协助全球生命科学和食品公司优化和改进其流程的质量。Ellab全面的无线数据记录仪,热电偶系统,无线环境监测系统,校准设备,软件解决方案等等…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
