Leetcode one week race 298, first three questions

2309. The best English letters with both upper and lower case

Give you a string of English letters s , Please find out and return to s Medium best English letter . The returned letters must be in upper case . If there is no letter that meets the condition , Then return an empty string .

best The upper and lower case forms of English letters must be all stay s It appears that .

English letter b Than another English letter a Better The premise is ： In the English alphabet ,b stay a And after appear .

Example 1：

Input ：s = “lEeTcOdE”
Output ：“E”
explain ：
Letter ‘E’ Is the only letter that appears in both uppercase and lowercase .

Example 2：

Input ：s = “arRAzFif”
Output ：“R”
explain ：
Letter ‘R’ It is the best English letter in both uppercase and lowercase .
Be careful ‘A’ and ‘F’ Both uppercase and lowercase forms of , however ‘R’ Than ‘F’ and ‘A’ Better .

Example 3：

Input ：s = “AbCdEfGhIjK”
Output ：“”
explain ：
There are no letters in both upper and lower case forms .

Tips ：

1 <= s.length <= 1000
s It consists of lowercase and uppercase English letters

Ideas

Traversal string , Mark as long as it is a letter , Then traverse the tag array , Judge from back to front , Both upper and lower case , The first one is also the largest

Code

class Solution {
    
public:
    int t[100];
    string greatestLetter(string s) {
    
        string res = "";
        for (int i = 0; i < s.size(); i++) {
    
            t[s[i] - 'A'] = 1;
        }
        for (int i = 0; i < 26; i++) {
    
            if (t[i] == 1 && t[i + 32] == 1) {
    
                res = i + 'A';
            }
        }
        
        return res;
    }
};

2310. The number of digits is K The sum of the integers of

Here are two integers num and k , Consider a positive integer multiset with the following properties ：

Every integer digit is k .
The sum of all integers is num .
Returns the minimum size of the multiset , If there are no such multiple sets , return -1 .

Be careful ：

A multiset is similar to a set , But a multiset can contain more than one integer , The sum of empty multisets is 0 .
One digit number Is the rightmost digit of the number .

Example 1：

Input ：num = 58, k = 9
Output ：2
explain ：
Multiple sets [9,49] Meet the conditions of the topic , And for 58 And the number of bits of each integer is 9 .
Another conditional multiple set is [19,39] .
Can prove that 2 Is the minimum length of a multiple set that satisfies the problem condition .

Example 2：

Input ：num = 37, k = 2
Output ：-1
explain ： The number of digits is 2 The integers of cannot be added together to get 37 .

Example 3：

Input ：num = 0, k = 7
Output ：0
explain ： The sum of empty multisets is 0 .

Tips ：

0 <= num <= 3000
0 <= k <= 9

greedy

Take apart ,nk + 10t == num

(num - nk) % 10 == 0

class Solution {
    
public:
    int minimumNumbers(int num, int k) {
    
        if (num == 0) return 0;
        //  Take apart ,nk + 10t == num
        // (num - nk) % 10 == 0

        for (int i = 1; i <= num && num - k * i >= 0; i++) {
     
            if ((num - k * i) % 10 == 0) {
    
                return i; //  Because it is simulated from small to large , The first suitable condition encountered is the minimum 
            }
        }

        return -1;
    }
};

Dynamic programming 1

When num == 0 when , return 0, If k It's even , however num Is odd , Go straight back to -1, impossible
The first bit to pick out is k Number of numbers , Make an array , As a backpack , Then one-dimensional scrolling array , Dynamic programming
Outer traversal items , Inner traversal Backpack Capacity
initialization ,dp[0] = 0, because num yes 0 When , from 0 Numbers make up , To take the composition num The minimum value of the number of , So the array is initialized to infinity
dp[j] = min(dp[j - i] + 1, dp[j]), Or take j-i The number of + 1, Or take 　dp[j]

class Solution {
    
public:
    int bg[3010];
    int dp[3010];
    int minimumNumbers(int num, int k) {
    
        if (num == 0) return 0;
        if (num % 2 == 1 && k % 2 == 0) return -1;
        int cnt = 0;
        for (int i = 1; i <= num; i++) {
    
            if (i % 10 == k) bg[cnt++] = i;
        }
        for (int i = 1; i <= num; i++) dp[i] = 99999;
        dp[0] = 0;
        for (int i = 0; i < cnt; i++) {
    
            for (int j = bg[i]; j <= num; j++) {
    
                dp[j] = min(dp[j - bg[i]] + 1, dp[j]);
            }
        }
        if (dp[num] == 99999) return -1;
        return dp[num];
        
    }
};

Dynamic programming 2

class Solution {
    
    int dp[3001];
public:
    int minimumNumbers(int num, int k) {
    
        memset(dp, 127, sizeof(dp)); //  Find the minimum , Initial infinity 

        dp[0] = 0;
        for (int i = 0; i <= num; i++) {
    
            for (int j = i; j <= num; j++) {
    
                if (i % 10 == k)
                    dp[j] = min(dp[j - i] + 1, dp[j]);
            }
        }
        if (dp[num] > 1 << 30) return -1;
        return dp[num];
    }
};

2311. Less than or equal to K The longest binary subsequence of

Give you a binary string s And a positive integer k .

Please return s Of The longest Subsequence , And the subsequence corresponds to Binary system The number is less than or equal to k .

Be careful ：

Subsequences can have Leading 0 .
An empty string is treated as 0 .
Subsequence It refers to deleting zero or more characters from a string , The sequence of remaining characters obtained without changing the order .

Example 1：

Input ：s = “1001010”, k = 5
Output ：5
explain ：s Less than equal to 5 The longest subsequence of is “00010” , The corresponding decimal number is 2 .
Be careful “00100” and “00101” It is also the longest possible subsequence , The decimal system corresponds to 4 and 5 .
The length of the longest subsequence is 5 , So back 5 .

Example 2：

Input ：s = “00101001”, k = 1
Output ：6
explain ：“000001” yes s Less than equal to 1 The longest subsequence of , The corresponding decimal number is 1 .
The length of the longest subsequence is 6 , So back 6 .

Tips ：

1 <= s.length <= 1000
s[i] Or ‘0’ , Or ‘1’ .
1 <= k <= 109

greedy ？

Set up a bool The array is initialized to false
Because there can be a lead 0, So first select all zeros ,ans Record the current number
then , because 1 Add less on the right , Too much on the left , So add from right to left , Look at this. 1 Will it exceed

class Solution {
    
    bool b[1001];
public:
    bool check(string &s, int k) {
    
        int n = s.size(), x = 0;
        for (int i = 1; i <= n; i++) {
    
            if (b[i])
                x = x * 2 + s[i - 1] - '0';
            if (x > k)
                return false;
        }
        return true;
    }
    int longestSubsequence(string s, int k) {
    
        memset(b, false, sizeof(b));
        int n = s.size();
        int ans = 0; //  Number of records 
        
        for (int i = 1; i <= n; i++) {
     //  First , Add all  0 
            if (s[i - 1] == '0')
                ++ans, b[i] = true; //  Record the number of current numbers , And change the selected number to  true 
        }
        
        for (int i = n; i > 0; i--)
            if (!b[i]) {
        //  Go back and forth , Add what was not added just now  1 
                b[i] = true;    //  First become true, It is convenient to calculate 
                if (!check(s, k)) //  If it exceeds , Just remove 
                    b[i] = false;
                else    //  No super ++
                    ++ans;
            }
        
        return ans;
    }
};