原題
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
解析
TinyURL編碼/解碼
我的解法
LEETCODE、Medium難度的題。。也是只有思路沒有實現。。
我一開始的思路是有問題的，還嘗試找出一種算法可以讓長鏈和短鏈一一對應，但這種算法不存在，除非短鏈不限長度，但這樣就失去了意義
一般的短鏈都是域名+6位長度的隨機碼組成，試想所有大小寫+數字一共62個，那最多也只有62^6個短鏈，所以根本不能滿足無限多的長鏈
查了一些資料，網上的解法大致分三種：
算法一（超復雜。。覺得沒必要）
將長鏈進行md5加鹽編碼，所得32位；
8個一組（共4組），按16進制與0x3fffffff（30個1）與，即取后30位，忽略其他位；
30位分成6段，每段5位的數字作為字符表62個字符（大小寫+0-9）的索引取得共6個字符；
md5一共4個8位共取4個6位字符，隨便取一個即可作為短鏈。
算法二（有缺陷，長度不受控制，且會出現一個長鏈對多個短鏈）
直接用遞增返回id作為短鏈，短鏈可以有無限多個
算法三（leetcode上面的最優解，覺得不復雜也比較可行）
最優解
public class TinyURL {//用于存儲長鏈接-短鏈接映射private static Map<String, String> longShort = new HashMap();//用于存儲短鏈接-長鏈接映射private static Map<String, String> shortLong = new HashMap();private static String HOST = "www.tinyUrl.com/";// Encodes a URL to a shortened URL.public static String encode(String longUrl) {//如果映射中存在key則直接返回if (longShort.containsKey(longUrl)) {return HOST + longShort.get(longUrl);}//構造短鏈String shortUrl;String chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";//碰撞直到沒有重復do {StringBuilder sb = new StringBuilder();for (int i = 0; i < 6; i++) {int n = (int) (Math.random() * chars.length());sb.append(chars.charAt(n));}shortUrl = sb.toString();} while (shortLong.containsKey(shortUrl));//存儲并返回shortLong.put(shortUrl, longUrl);longShort.put(longUrl, shortUrl);return HOST + shortUrl;}// Decodes a shortened URL to its original URL.public static String decode(String shortUrl) {return shortLong.get(shortUrl.replace(HOST, ""));}
}
