535. TinyURL 的加密与解密 / 剑指 Offer II 103. 最少的硬币数目

535. TinyURL 的加密与解密【中等题】【每日一题】

思路：

生成随机短串进行加密，将加密后的 shortUrl 作为 key，longUrl 作为value存入数据库，解密的时候将shortUrl作为key在数据库中取出其对应的值即可。

第一次做没有考虑加密短串重复问题，第二次将其完善，存入数据库前先进行判断，如果重复就重新生成随机短串。

代码1：

public class Codec {
    

    //存储 long - short URL
    private Map<String,String> map;
    //用于生成随机数
    private Random random;

    public Codec() {
    
        this.map = new HashMap<>();
        this.random = new Random();
    }
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
    
        //对long加密转为short
        StringBuilder pwd = new StringBuilder("htttp://");
        //加密时保持域名不动
        int start = 0,end = 0,n = longUrl.length();
        int flag = 0;
        for (int i = 0; i < n; i++) {
    
            if (longUrl.charAt(i) == '/'){
    
                if (flag == 0){
    
                    flag++;
                }else if (flag == 1){
    
                    flag++;
                    start = i+1;
                }else if (flag == 2){
    
                    flag++;
                    end = i+1;
                }else {
    
                    break;
                }
            }
        }
        pwd.append(longUrl, start, end);
        //对域名的下一级目录生成 6 位 随机短串并存入数据库
        pwd.append(random.nextInt(10));
        pwd.append((char) ('a' + random.nextInt(26)));
        pwd.append(random.nextInt(10));
        pwd.append((char) ('a' + random.nextInt(26)));
        pwd.append((char) ('A' + random.nextInt(26)));
        pwd.append((char) ('a' + random.nextInt(26)));
        map.put(pwd.toString(),longUrl);
        return pwd.toString();
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
    
        //解密，从map2中将 shortUrl 对应的 longUrl 取出
        return map.getOrDefault(shortUrl,null);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

代码2：

public class Codec {
    

    //存储 long - short URL
    private Map<String,String> map;
    //用于生成随机数
    private Random random;

    public Codec() {
    
        this.map = new HashMap<>();
        this.random = new Random();
    }
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
    
        //对long加密转为short
        StringBuilder pwd = new StringBuilder("http://");
        //加密时保持域名不动
        int start = 0,end = 0,n = longUrl.length();
        int flag = 0;
        for (int i = 0; i < n; i++) {
    
            if (longUrl.charAt(i) == '/'){
    
                if (flag == 0){
    
                    flag++;
                }else if (flag == 1){
    
                    flag++;
                    start = i+1;
                }else if (flag == 2){
    
                    flag++;
                    end = i+1;
                }else {
    
                    break;
                }
            }
        }
        pwd.append(longUrl, start, end);
        //对域名的下一级目录生成 6 位 随机短串并存入数据库
        String shortStr = generate6();
        while (map.containsKey(shortStr)){
    
            shortStr = generate6();
        }
        map.put(pwd + shortStr,longUrl);
        return pwd + shortStr;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
    
        //解密，从map中将 shortUrl 对应的 longUrl 取出
        return map.getOrDefault(shortUrl,null);
    }

    public String generate6(){
    
        return String.valueOf(random.nextInt(10)) +
                (char) ('a' + random.nextInt(26)) +
                random.nextInt(10) +
                (char) ('a' + random.nextInt(26)) +
                (char) ('A' + random.nextInt(26)) +
                (char) ('a' + random.nextInt(26));
    }

}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

---

剑指 Offer II 103. 最少的硬币数目【中等题】

思路：【动态规划】

『 一文搞懂完全背包问题 』从0-1背包到完全背包，逐层深入+数学推导

学习评论区的题解思路

划重点记结论：

不超过背包容量的最优解（最大背包容量）

0-1背包：
dp[i][j] = max{dp[i-1][j] , dp[i-1][j-vi] + vi}, 0 <= vi <= j

完全背包：
dp[i][j] = max{dp[i-1][j] , dp[i][j-vi] + vi},0 <= vi <= j

恰好装满背包的最优解（最小物品方案）

0-1背包：
dp[i][j] = max{dp[i-1][j] , dp[i-1][j-vi] + 1}, 0 <= vi <= j

完全背包：
dp[i][j] = max{dp[i-1][j] , dp[i][j-vi] + 1},0 <= vi <= j

代码：

class Solution {
    
    public int coinChange(int[] coins, int amount) {
    
        int n = coins.length;
        //定义dp数组，dp[i][j]表示前i个硬币组合总价值为j时所需的最小硬币个数
        int[][] dp = new int[n+1][amount+1];
        //边界条件 j = 0时，不取任何硬币即可满足题意，即 dp[i][0] = 0,由于数组默认赋0，因此这里不用重复操作
        //边界条件 i = 0时，只有 j = 0 时，即不取任何硬币，只对要求的组合硬币数为0时符合要求，对于大于0的目标，显然是不可能取到的，这里赋初值为一个永远取不到的数 amount+1 即可
        for (int j = 1; j <= amount ; j++) {
    
            dp[0][j] = amount+1;
        }
        for (int i = 1; i <= n; i++) {
    
            for (int j = 0; j <= amount; j++) {
    
                if (j >= coins[i-1]){
    
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                }else {
    
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][amount] == amount + 1 ? -1 : dp[n][amount];
    }
}