Leetcode study - day 35

Day 35

I use C++, Sorry for the mistake , The original intention of this article is only to urge me to study , If it happens to help you , I will be very happy .

One 、1143. Longest common subsequence

Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount .

Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 .

You can think of the number of coins of each kind as infinite .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/coin-change
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

My first thought is to decrease from the maximum face value , It turns out that such an approach cannot find a combination that meets the conditions , Many elements will be missed , Just looking for the minimum number , But missed the combination that might make up enough . Greed alone is not enough

class Solution {
    
public:
    int coinChange(vector<int>& coins, int amount) {
    
        // First spell with the one with the a large face value 
        int n = coins.size(), cnt = 0;
        sort(coins.begin(), coins.end());
        for (int i = n - 1; i >= 0; --i){
    
            while(amount >= coins[i]){
    
                amount -= coins[i];
                ++cnt;
            }
        }
        if (amount == 0){
    
            return cnt;
        }
        else {
    
            return -1;
        }
    }
};

Two 、12. Integer to Roman number

Roman numerals contain the following seven characters ： I, V, X, L,C,D and M.

character The number
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
for example , Rome digital 2 Write to do II , Two parallel 1.12 Write to do XII , That is to say X + II . 27 Write to do XXVII, That is to say XX + V + II .

Usually , The small numbers in roman numbers are to the right of the big ones . But there are special cases , for example 4 Do not write IIII, It is IV. Numbers 1 In number 5 Left side , The number represented is equal to the large number 5 Decimal reduction 1 Value obtained 4 . similarly , Numbers 9 Expressed as IX. This special rule only applies to the following six cases ：

I Can be placed in V (5) and X (10) Left side , To express 4 and 9.
X Can be placed in L (50) and C (100) Left side , To express 40 and 90.
C Can be placed in D (500) and M (1000) Left side , To express 400 and 900.
Give you an integer , Turn it into Roman numerals .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/integer-to-roman
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

class Solution {
    
public:
    string intToRoman(int num) {
    
        // Check from high position , Special if yes 4、9, Need special treatment 
        const pair<int, string> Roman[] = {
    
           {
    1000, "M"},
           {
    900, "CM"}, 
           {
    500, "D"},
           {
    400, "CD"},
           {
    100, "C"},
           {
    90, "XC"},
           {
    50, "L"},
           {
    40, "XL"},
           {
    10, "X"},
           {
    9, "IX"},
           {
    5, "V"},
           {
    4, "IV"},
           {
    1, "I"},
        };
        string ans;
        for (auto &[value, str] : Roman){
    
            while (num >= value){
    
                num -= value;
                ans += str;
            }
            if (num == 0){
    
                break;
            }
        } 
        return ans;
    }
};

3、 ... and 、13. Roman numeral to integer

class Solution {
    
public:
    unordered_map<char, int>  Roman = {
    
        {
    'M', 1000},
        {
    'D', 500},
        {
    'C', 100},
        {
    'L', 50},
        {
    'X', 10},
        {
    'V', 5},
        {
    'I', 1},
    };
    int romanToInt(string s) {
    
        // The key is to 4、9 To deal with 
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; ++i){
    
            int value = Roman[s[i]];
            if (i < n - 1 && value < Roman[s[i + 1]]){
    // appear 4、9 The situation of 
                ans -= value;
            }
            else {
    
                ans += value;
            }
        }
        return ans;
    }
};