本文概述
- C ++
- Java
- Python3
需要注意的重要一件事是, 长网址也应该可以从短网址中唯一地识别出来。所以我们需要一个
双射函数
一个简单的解决方案可能是哈希。使用哈希函数将长字符串转换为短字符串。在散列中, 可能是冲突(2个长URL映射到相同的短URL), 并且我们需要为每个长URL唯一的短URL, 以便我们可以返回长URL。
一种更好的解决方案是使用存储在数据库中的整数id并将该整数转换为最多6个字符长的字符串。这个问题基本上可以看作是一个基本转换问题, 其中我们有一个10位数字的输入数字, 我们想将其转换为6个字符长的字符串。
以下是有关URL中可能字符的一项重要观察。
URL字符可以是以下之一
1)小写字母[a]到[z], 共26个字符
2)大写字母[A至Z], 共26个字符
3)数字[‘ 0’ 到’ 9’ ], 共10个字符
一共有26 + 26 + 10 = 62个可能的字符。
因此, 任务是将十进制数转换为以62为基数的数字。
要获取原始的长URL, 我们需要在数据库中获取URL ID。可以使用以62为底的十进制转换获得id。
C ++
//C++ program to generate short url from integer id and
//integer id back from short url.
#include<
iostream>
#include<
algorithm>
#include<
string>
using namespace std;
//Function to generate a short url from integer ID
string idToShortURL( long int n)
{
//Map to store 62 possible characters
char map[] = "abcdefghijklmnopqrstuvwxyzABCDEF"
"GHIJKLMNOPQRSTUVWXYZ0123456789" ;
string shorturl;
//Convert given integer id to a base 62 number
while (n)
{
//use above map to store actual character
//in short url
shorturl.push_back(map[n%62]);
n = n/62;
}//Reverse shortURL to complete base conversion
reverse(shorturl.begin(), shorturl.end());
return shorturl;
}//Function to get integer ID back from a short url
long int shortURLtoID(string shortURL)
{
long int id = 0;
//initialize result//A simple base conversion logic
for ( int i=0;
i <
shortURL.length();
i++)
{
if ( 'a' <
= shortURL[i] &
&
shortURL[i] <
= 'z' )
id = id*62 + shortURL[i] - 'a' ;
if ( 'A' <
= shortURL[i] &
&
shortURL[i] <
= 'Z' )
id = id*62 + shortURL[i] - 'A' + 26;
if ( '0' <
= shortURL[i] &
&
shortURL[i] <
= '9' )
id = id*62 + shortURL[i] - '0' + 52;
}
return id;
}//Driver program to test above function
int main()
{
int n = 12345;
string shorturl = idToShortURL(n);
cout <
<
"Generated short url is " <
<
shorturl <
<
endl;
cout <
<
"Id from url is " <
<
shortURLtoID(shorturl);
return 0;
}
Java
//Java program to generate short url from integer id and
//integer id back from short url.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
//Function to generate a short url from integer ID
static String idToShortURL( int n)
{
//Map to store 62 possible characters
char map[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" .toCharArray();
StringBuffer shorturl = new StringBuffer();
//Convert given integer id to a base 62 number
while (n>
0 )
{
//use above map to store actual character
//in short url
shorturl.append(map[n % 62 ]);
n = n /62 ;
} //Reverse shortURL to complete base conversion
return shorturl.reverse().toString();
} //Function to get integer ID back from a short url
static int shortURLtoID(String shortURL)
{
int id = 0 ;
//initialize result //A simple base conversion logic
for ( int i = 0 ;
i <
shortURL.length();
i++)
{
if ( 'a' <
= shortURL.charAt(i) &
&
shortURL.charAt(i) <
= 'z' )
id = id * 62 + shortURL.charAt(i) - 'a' ;
if ( 'A' <
= shortURL.charAt(i) &
&
shortURL.charAt(i) <
= 'Z' )
id = id * 62 + shortURL.charAt(i) - 'A' + 26 ;
if ( '0' <
= shortURL.charAt(i) &
&
shortURL.charAt(i) <
= '9' )
id = id * 62 + shortURL.charAt(i) - '0' + 52 ;
}
return id;
} //Driver Code
public static void main (String[] args) throws IOException
{
int n = 12345 ;
String shorturl = idToShortURL(n);
System.out.println( "Generated short url is " + shorturl);
System.out.println( "Id from url is " +
shortURLtoID(shorturl));
}
}//This code is contributed by shubham96301
Python3
# Python3 code for above approach
def idToShortURL( id ):
map = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
shortURL = ""# for each digit find the base 62
while ( id>
0 ):
shortURL + = map [ id % 62 ]
id //= 62# reversing the shortURL
return shortURL[ len (shortURL): : - 1 ]def shortURLToId(shortURL):
id = 0
for i in shortURL:
val_i = ord (i)
if (val_i>
= ord ( 'a' ) and val_i <
= ord ( 'z' )):
id = id * 62 + val_i - ord ( 'a' )
elif (val_i>
= ord ( 'A' ) and val_i <
= ord ( 'Z' )):
id = id * 62 + val_i - ord ( 'Z' ) + 26
else :
id = id * 62 + val_i - ord ( '0' ) + 52
return idif (__name__ = = "__main__" ):
id = 12345
shortURL = idToShortURL( id )
print ( "Short URL from 12345 is : " , shortURL)
print ( "ID from" , shortURL, "is : " , shortURLToId(shortURL))
输出如下:
Generated short url is dnh
Id from url is 12345
优化:我们可以避免idToShortURL()中的反向步骤。为了确保返回相同的ID, 我们还需要更改shortURLtoID()以从头开始而不是从头开始处理字符。
【如何设计一个很小的URL或URL缩短器()】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 如何确定二叉树是否高度平衡()
- 如何声明一个指向函数的指针()
- 如何在C#中创建线程(解析和详细代码)
- 如何在C#中创建ArrayList(用法示例)
- 如何使用Kotlin在Android Studio中创建项目()
- 如何在Google AMP中创建Floating amp-addthis()
- 如何在Tableau中创建故事()
- 10个查找和删除重复文件的工具
- 简单判断是否存在丢包之ping+tracert+mtr