535. encryption and decryption of tinyurl / Jianzhi offer II 103 Minimum number of coins

535. TinyURL Encryption and decryption 【 Medium question 】【 A daily topic 】

Ideas ：

Generate random short string for encryption , Will be encrypted after shortUrl As key,longUrl As value Store in database , When decrypting, the shortUrl As key Get the corresponding value from the database .

For the first time, we did not consider the problem of encrypting short string repetition , Perfect it for the second time , Judge before saving into the database , If it is repeated, the random short string is regenerated .

Code 1：

public class Codec {
    

    // Storage  long - short URL
    private Map<String,String> map;
    // Used to generate random numbers 
    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) {
    
        // Yes long Encryption to short
        StringBuilder pwd = new StringBuilder("htttp://");
        // Keep the domain name still while encrypting 
        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);
        // Generate the next level directory of the domain name  6  position   Random short string and stored in the database 
        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) {
    
        // Decrypt , from map2 Lieutenant general  shortUrl  Corresponding  longUrl  Take out 
        return map.getOrDefault(shortUrl,null);
    }
}

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

Code 2：

public class Codec {
    

    // Storage  long - short URL
    private Map<String,String> map;
    // Used to generate random numbers 
    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) {
    
        // Yes long Encryption to short
        StringBuilder pwd = new StringBuilder("http://");
        // Keep the domain name still while encrypting 
        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);
        // Generate the next level directory of the domain name  6  position   Random short string and stored in the database 
        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) {
    
        // Decrypt , from map Lieutenant general  shortUrl  Corresponding  longUrl  Take out 
        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));

---

The finger of the sword Offer II 103. The minimum number of coins 【 Medium question 】

Ideas ：【 Dynamic programming 】

『 Understand the complete knapsack problem 』 from 0-1 Backpack to full backpack , Go deep layer by layer + Mathematical derivation

Learn the idea of problem solving in the comment area

Highlight the conclusion ：

The optimal solution that does not exceed the backpack capacity （ Maximum Backpack Capacity ）

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

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

The optimal solution that just fills the backpack （ Minimum item scheme ）

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

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

Code ：

class Solution {
    
    public int coinChange(int[] coins, int amount) {
    
        int n = coins.length;
        // Definition dp Array ,dp[i][j] Before presentation i The total value of the coin combination is j The minimum number of coins required for 
        int[][] dp = new int[n+1][amount+1];
        // The boundary conditions  j = 0 when , The meaning of the title can be satisfied without taking any coins , namely  dp[i][0] = 0, Because the array is assigned by default 0, So there is no need to repeat the operation here 
        // The boundary conditions  i = 0 when , Only  j = 0  when , That is, do not take any coins , Only the required number of combined coins is 0 Meet the requirements when , For greater than 0 The goal of , It is obviously impossible to get it , Here we assign the initial value to a number that can never be obtained  amount+1  that will do 
        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];
    }
}