Day 35

I use C + +, please forgive me for the mistakes. The original intention of this article is only to urge me to study. If I happen to be able to help you, I will be very happy.

1, 1143 Longest common subsequence

Give you an integer array of coins to represent coins of different denominations; And an integer amount, representing the total amount.

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

You can think that the number of coins of each kind is unlimited.

Source: LeetCode
Link: https://leetcode-cn.com/problems/coin-change
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

I first thought about decreasing from the maximum face value. As a result, I found that this approach could not find a combination that met the conditions, and many elements would be missed. I was just looking for the minimum number, but I missed the combination that might be enough. Greed alone is not enough

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //First spell the one with 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;
        }
    }
};

2, 12 Integer to Roman numeral

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

Character value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, the Roman numeral 2 is written as II, which is two parallel ones. 12 is written as XII, which is X + II. 27 is written as XXVII, which is XX + V + II.

Usually, the small Roman numerals are to the right of the large ones. But there are also special cases. For example, 4 is not written as IIII, but IV. The number 1 is on the left of the number 5, and the number represented is equal to the value 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is represented as IX. This special rule applies only to the following six cases:

I can be placed to the left of V (5) and X (10) to represent 4 and 9.
X can be placed to the left of L (50) and C (100) to represent 40 and 90.
C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
Give you an integer and convert it to Roman numerals.

Source: LeetCode
Link: https://leetcode-cn.com/problems/integer-to-roman
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

class Solution {
public:
    string intToRoman(int num) {
        //Check from the high position. Special treatment is required if it is 4 and 9
        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, 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 deal with 4 and 9
        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]]){//In case of 4 and 9
                ans -= value;
            }
            else {
                ans += value;
            }
        }
        return ans;
    }
};