Leetcode game 297

summary

The last question of this week's competition is easy to make people dizzy , No hard algorithms , But a strong analytical ability is required .

List of topics

1. Calculate the total tax payable

Title Description

I'll give you a subscript from 0 Start with a two-dimensional integer array brackets , among brackets[i] = [upperi, percenti] , It means the first one i The upper limit of individual income tax is upperi , The tax rate charged is percenti . Tax level by upper limit Sort from low to high （ In the meet 0 < i < brackets.length Under the premise of ,upperi-1 < upperi）.

The tax is calculated as follows ：

No more than upper0 Income is taxed percent0 Pay
next upper1 - upper0 The part of the tax rate is percent1 Pay
then upper2 - upper1 The part of the tax rate is percent2 Pay
And so on
Give you an integer income Represents your total income . Return the total amount of tax you have to pay . The error with the standard answer does not exceed 10^-5 The result of will be regarded as the correct answer .
Example 1：

Input ：brackets = [[3,50],[7,10],[12,25]], income = 10
Output ：2.65000
explain ：
front $3 The tax rate is 50% . Taxes are payable $3 * 50% = $1.50 .
Next $7 - $3 = $4 The tax rate is 10% . Taxes are payable $4 * 10% = $0.40 .
Last $10 - $7 = $3 The tax rate is 25% . Taxes are payable $3 * 25% = $0.75 .
Total taxes to be paid $1.50 + $0.40 + $0.75 = $2.65 .
Example 2：
Input ：brackets = [[1,0],[4,25],[5,50]], income = 2
Output ：0.25000
explain ：
front $1 The tax rate is 0% . Taxes are payable $1 * 0% = $0 .
be left over $1 The tax rate is 25% . Taxes are payable $1 * 25% = $0.25 .
Total taxes to be paid $0 + $0.25 = $0.25 .
Example 3：
Input ：brackets = [[2,50]], income = 0
Output ：0.00000
explain ：
No income , No tax is required , Total taxes to be paid $0 .
Tips ：
1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi In ascending order
upperi All the values in Different from each other
The upper limit of the last tax level is greater than or equal to income

analysis

Simulation question , Traverse brackets , If income Greater than the previous tax level , Just add the tax of this tax level . For example, the tax levels are 3 7 12, The income is 10, The initial upper tax level last yes 0,10 > 0, Then calculate by 3 What is the amount of tax collection at the tax level , If 10 Greater than 3, Then the tax level 3 The amount of tax is 3, Multiplying by the corresponding tax rate is the tax to be paid at the current tax level . to update last = 3, Came to 7 This tax grade ,10 > 3 So you can follow the 7 This tax grade collects taxes , Tax amount is 7 - 3 = 4. to update last = 7, Came to 12 This tax grade ,10 > 7, however 10 < 12, So the current tax level is min(10,12) - 7 = 3.

As a sign in question , This topic friendly set the last tax level not less than income Conditions , Otherwise, it is necessary to judge the lower boundary .

Code

class Solution {
    
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
    
        double res = 0;
        int last = 0;
        for(auto x : brackets){
    
            int p = x[0],q = x[1];
            if(income > last){
    
                int s = min(income,p);
                res += q * (s - last) / 100.0;
                last = p;
            }
            else{
    
                break;
            }
        }
        return res;
    }
};

2. Minimum path cost in the grid

Title Description

I'll give you a subscript from 0 The starting integer matrix grid , The matrix size is m x n , From 0 To m * n - 1 Is composed of different integers . You can use this matrix , Move from a cell to The next line Any other cell of the . If you are in a cell (x, y) , And meet x < m - 1 , You can move to (x + 1, 0), (x + 1, 1), …, (x + 1, n - 1) Any cell in the . Be careful ： Cells in the last row cannot trigger a move .

Every possible move comes at a corresponding cost , The price is from with a subscript 0 Start with a two-dimensional array moveCost Express , The array size is (m * n) x n , among moveCost[i][j] Yes, the slave value is i The cell of moves to the next row j The cost of column cells . from grid The cost of cell movement in the last row can be ignored .

grid The cost of a path is ： Of all cells the path passes through Sum of values add All mobile Sum of costs . from first line Start from any cell , Return to The last line Minimum path cost of any cell .
Example 1：

Input ：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
Output ：17
explain ： The path with the least cost is 5 -> 0 -> 1 .

• The path passes through the sum of cell values 5 + 0 + 1 = 6 .
• from 5 Move to 0 The price is 3 .
• from 0 Move to 1 The price is 8 .
  The total cost of the path is 6 + 3 + 8 = 17 .
  Example 2：
  Input ：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
  Output ：6
  explain ：
  The path with the least cost is 2 -> 3 .
• The path passes through the sum of cell values 2 + 3 = 5 .
• from 2 Move to 3 The price is 1 .
  The total cost of the path is 5 + 1 = 6 .
  Tips ：
  m == grid.length
  n == grid[i].length
  2 <= m, n <= 50
  grid From 0 To m * n - 1 Is composed of different integers
  moveCost.length == m * n
  moveCost[i].length == n
  1 <= moveCost[i][j] <= 100

analysis

Simple linearity DP problem , It belongs to the digital triangle model . It takes more time to understand moveCost The representation of this two-dimensional array of stored costs , I also spent some time simulating use cases during the weekly competition to understand how this cost is expressed . such as moveCost[1][2] = 3, It means that the value is 1 The cell of moves to the next row 2 The cost of column cells is 3. The example of the title naturally only gives moveCost Value , Its subscript needs to be calculated by itself , This storage method is still quite rare .

State means ：f[i][j] It means to arrive at... From any cell in the first row (i,j) The minimum cost of . Obviously, the initial state is the cell in the first row ,f[0][i] = grid[0][i], This is because the cost of moving the path is equal to the sum of the cost of moving and the value passing through the cell , The first row of cells does not need to be moved , But the cost needs to add the value of its own cell .
The equation of state transfer is ：

f[i][j] = min(f[i][j],grid[i][j] + f[i-1][k] + moveCost[grid[i-1][k]][j]);

The first i The state of a row can be transferred from the state of different columns in the previous row , Find the minimum cost .

Code

class Solution {
    
public:
    /*f[i][j] Indicates arrival i,j The minimum cost of a cell */
    int f[55][55];
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
    
        int m = grid.size();
        int n = grid[0].size();
        memset(f,0x3f,sizeof f);
        for(int i = 0;i < n;i++)    f[0][i] = grid[0][i];
        for(int i = 1;i < m;i++){
    
            for(int j = 0;j < n;j++){
    
                for(int k = 0;k < n;k++){
    
                    f[i][j] = min(f[i][j],grid[i][j] + f[i-1][k] + moveCost[grid[i-1][k]][j]);
                }
            }
        }
        int res = 1e9;
        for(int i = 0;i < n;i++)    res = min(res,f[m-1][i]);
        return res;
    }
};

3. Fair distribution of biscuits

Title Description

Give you an array of integers cookies , among cookies[i] Said in the first i The number of cookies in a snack bag . I'll give you another integer k Indicates the number of children waiting to distribute snack packs , all Snack bags need to be distributed . All cookies in the same snack bag must be distributed to the same child , Can't be separated .

Distributed Degree of unfairness It is defined as the maximum total number of biscuits that a single child can obtain during the distribution process .

Returns the minimum unfairness of all distributions .
Example 1：

Input ：cookies = [8,15,10,20,8], k = 2
Output ：31
explain ： An optimal solution is [8,15,8] and [10,20] .

• The first 1 Children are assigned to [8,15,8] , A total of 8 + 15 + 8 = 31 A biscuit .
• The first 2 Children are assigned to [10,20] , A total of 10 + 20 = 30 A biscuit .
  The degree of unfairness in distribution is max(31,30) = 31 .
  It can be proved that there is no unfairness less than 31 The distribution plan of .
  Example 2：
  Input ：cookies = [6,1,3,2,2,4,1,2], k = 3
  Output ：7
  explain ： An optimal solution is [6,1]、[3,2,2] and [4,1,2] .
• The first 1 Children are assigned to [6,1] , A total of 6 + 1 = 7 A biscuit .
• The first 2 Children are assigned to [3,2,2] , A total of 3 + 2 + 2 = 7 A biscuit .
• The first 3 Children are assigned to [4,1,2] , A total of 4 + 1 + 2 = 7 A biscuit .
  The degree of unfairness in distribution is max(7,7,7) = 7 .
  It can be proved that there is no unfairness less than 7 The distribution plan of .
  Tips ：
  2 <= cookies.length <= 8
  1 <= cookies[i] <= 10⁵
  2 <= k <= cookies.length

analysis

The data range of this question is small , You can use the most basic DFS solve , Not even TLE.

void dfs(vector<int>& cookies, int u){
    
        if(u == cookies.size()){
    
            int res = 0;
            for(int i = 0;i < t;i++)    res = max(res,num[i]);
            ans = min(ans,res);
            return;
        }
        for(int i = 0;i < t;i++){
    
            num[i] += cookies[u];
            dfs(cookies,u+1);
            num[i] -= cookies[u];
        }
    }

dfs The boundary condition is that the enumeration is complete , At this point, find the maximum value of obtained biscuits in all allocation schemes , Try to get the updated optimal solution . In general , For the current second u Baobiscuit , Can be t Different allocation methods in , Just enumerate one by one , After enumerating one by one, you need to restore the global array num Before the next enumeration . The fastest race of the week AC The method is to solve the problem directly with pure violence , altogether k A child , Every packet of biscuits has k Seed method , Altogether 8⁸ = 2²⁴ About equal to 1600w States , I can still bear it .

Of course, we can't be satisfied with violence when we do this topic at ordinary times , At least prune .

First, consider optimality pruning , After enumerating one scheme , Find out ans A value of , Only in the back ans It will be updated when it is younger , and ans The value of depends on the number of biscuits each person dispenses , So once a certain distribution scheme assigns a person more than or equal to the number of cookies ans, There is no need to continue enumerating . Add this optimality pruning statement ,dfs The efficiency will be increased by ten times .

Then consider optimizing the search order ,cookies If the value with a large number of cookies is allocated first , The number of biscuits distributed by the first few people increased faster , It's easier to prune , So give priority to those with large biscuits ,dfs Prior to cookies Sort from large to small . Plus optimization of search order ,dfs The speed can be even faster 3 times .

Of course, there are redundant searches , For example, the first packet of biscuits is given to the first person , The second package of biscuits for the second person and the first package for the second person , The second package gives the first person the same effect on the solution of the problem , We are only concerned with the allocation of portfolio schemes , And don't care about the order , Eliminating equivalent redundancy can indeed greatly improve efficiency , For example, we fixed the first packet of biscuits to the first person , Because it's the same no matter who you give it to . Because of this question, everyone can get more than one packet of biscuits , It is not good to search by memory , So the code here does not exclude redundant search .

Consider state compression DP Solution method , There must be no compression when writing state during the week DFS Fast completion , But you can still study it at ordinary times , After all, it is more efficient .

We DFS When it comes to enumerating cookies , Then think about who to assign it to , Now let's change the enumeration method , Enumerate everyone in order , Try to distribute cookies to everyone . The first i The individual's allocation scheme depends only on the previous i - 1 Individual distribution scheme , As the number of biscuits is small , So the allocated cookie state can be compressed by state .

 State means ：f[i][j] Show before i Individual distribution of biscuits , The distribution status of biscuits is j The minimum degree of unfairness , such as f[2][3] It means that the first two people have been assigned the 1,2 The biscuits in the bag , because 3 Use binary tables 
 The sign is 11, The first two packets of biscuits were allocated .
 State shift ： Since before i The individual's allocation status is j, that j Any subset of can be the i Individual distribution scheme , So we can enumerate j Subset x, front i-1 The individual allocation status is j - x, Can also be 
 Expressed as j ^ x, for instance j = 1101,x = 0100,j ^ x = 1001,j ^ x Namely x be relative to j The complement of .
 State transition equation ：f[i][j] = min(f[i][j],max(f[i-1][j^x],sum[x])), Is the former i The degree of unfairness of the individual distribution scheme is equal to that of the former i-1 Personal optimal solution and the i Biscuits distributed by individuals 
 The greater of the quantities , In all allocation schemes, the minimum value is f[i][j] The optimal solution of .
 State boundary ：f[0][0] = 0, Other states INF.

There are still two problems to be solved , The first problem is how to compress States, how to enumerate subsets of a set . such as j = 1101 when ,j The subset of is 1100,1001.1000.0101.0100.0001 these , The common code for enumerating subsets is for(int x = j;x;x=(x-1)&j), in other words j And j-1 Phase and get the first subset 1100, It is equivalent to giving j Far right 1 Removed , then 1100 subtract 1 And again j Meet each other , obtain 1001, In this way, the sequence of enumeration is the sequence of enumeration of subsets from large to small . For detailed analysis, please refer to About the pressure DP The method and understanding of enumerating subsets .

The second problem is how to quickly find the number of biscuits allocated by an allocation scheme , Because the first i The individual distribution scheme is x, You need to ask how many cookies this person has been given . We can follow 1 2 4 8… In order to distribute cookies , For example, more than 1 The small state is only 0, that 0 | 1 = 1,sum[0 | 1] = sum[0] + cookies[0]; Then look at it 2 Small states are 0 and 1,sum[0 | 2] = sum[0] + cookies[1];sum[1 | 2] = sum[1] + cookies[1], This state transition is simple , Just add the i Pack the number of biscuits when giving it the status or on 1 << i, But the order of state transition is still hard to think of .

Code

DFS + prune

class Solution {
    
public:
    int t,num[8];
    int ans = 1e9;
    void dfs(vector<int>& cookies, int u){
    
        if(u == cookies.size()){
    
            int res = 0;
            for(int i = 0;i < t;i++)    res = max(res,num[i]);
            ans = min(ans,res);
            return;
        }
        for(int i = 0;i < t;i++){
    
            num[i] += cookies[u];
            if(num[i] < ans)    dfs(cookies,u+1);
            num[i] -= cookies[u];
        }
    }
    int distributeCookies(vector<int>& cookies, int k) {
    
        t = k;
        sort(cookies.begin(),cookies.end(),[](int a,int b){
    return a > b;});
        dfs(cookies,0);
        return ans;
    }
};

State compression DP

class Solution {
    
public:
    int f[10][1<<8],sum[1<<8];
    int distributeCookies(vector<int>& cookies, int k) {
    
        int n = cookies.size();
        for(int i = 0;i < n;i++){
    
            int j = 1 << i;
            for(int k = 0;k < j;k++)    sum[k | j] = sum[k] + cookies[i];
        }
        memset(f,0x3f,sizeof f);
        f[0][0] = 0;
        for(int i = 1;i <= k;i++){
    
            for(int j = 1;j < (1 << n);j++){
    
                for(int x = j;x;x=(x-1)&j){
    
                    int t = max(f[i-1][j ^ x],sum[x]);
                    f[i][j] = min(f[i][j],t);
                }
            }
        }
        return f[k][(1<<n)-1];
    }
};

4. Company naming

Title Description

Here's an array of strings ideas Indicates the list of names used in the naming process of the company . The company naming process is as follows ：
from ideas Choose from 2 individual Different name , be called ideaA and ideaB .
In exchange for ideaA and ideaB The first letter of .
If you get two new names all be not in ideas in , that ideaA ideaB（ Series connection ideaA and ideaB , Separated by a space ） Is a valid company name .
otherwise , Not a valid name .
return Different Number of valid company names .
Example 1：
Input ：ideas = [“coffee”,“donuts”,“time”,“toffee”]
Output ：6
explain ： Here are some effective options ：

• (“coffee”, “donuts”)： The corresponding company name is “doffee conuts” .
• (“donuts”, “coffee”)： The corresponding company name is “conuts doffee” .
• (“donuts”, “time”)： The corresponding company name is “tonuts dime” .
• (“donuts”, “toffee”)： The corresponding company name is “tonuts doffee” .
• (“time”, “donuts”)： The corresponding company name is “dime tonuts” .
• (“toffee”, “donuts”)： The corresponding company name is “doffee tonuts” .
  therefore , All in all 6 Different company names .
  Here are some invalid options ：
• (“coffee”, “time”)： The name formed after exchange exists in the original array “toffee” .
• (“time”, “toffee”)： There are two names formed after exchange in the original array .
• (“coffee”, “toffee”)： There are two names formed after exchange in the original array .
  Example 2：
  Input ：ideas = [“lack”,“back”]
  Output ：0
  explain ： There is no valid alternative . therefore , return 0 .
  Tips ：
  2 <= ideas.length <= 5 * 10⁴
  1 <= ideas[i].length <= 10
  ideas[i] It's made up of lowercase letters
  ideas All the strings in Different from each other

analysis

This question does not examine any complex algorithm , But the problem-solving logic is still very convoluted , It's easy to make people dizzy , Try to analyze the problem as succinctly as possible .

Given a string sequence , For string sequences a and b, If you exchange a and b The two strings formed after the first letter do not appear in the string sequence , Then these two strings can appear as a legal company name , How many legal company names are there . The complexity of the double loop enumeration of violent practices is square , The amount of calculation is 2.5 * 10⁹, Still will TLE Of , So we can only enumerate one of the two string pairs at most .

The violence is done on every string , Enumerate the remaining strings , Swap the initials of two strings , If the two strings after the exchange do not appear in the string sequence , You can increase the number of schemes , What method can be used to quickly find the number of legal strings after exchanging initial letters with a string in a string sequence ？ for instance A = “abcd”,B=“bcda”, We exchange AB After the initial letter of bbcd and acda, And then determine bbcd Have you ever seen ,acda Have you ever seen . You can find , about A Come on , We only care about what the initials are exchanged with it , No matter B What is the following character , as long as B Replace the initials of A The string after the first letter of has not appeared , Then the replaced A It's legal . The strings in this question are all composed of lowercase letters , most 26 Kind of , Therefore, the string sequence can be divided into 26 Group string sequence ：
A Group ： With a Starting string ,B Group ： With b Starting string ,…,Z Group ： With z Starting string .

In the original string sequence , We need to take any two strings , Judge whether it can constitute a legal company name . Now we have grouped the string sequences , In the same string sequence , Because the first character is the same , The string does not change after the first character is exchanged , It must not constitute a legal company name , Then the two strings can only be selected from two different groups . For example A Select a string from the group ,B Select a string from the group , If you want two strings to form a legal company name , that A Replace the first character of the selected string with b It is required that there is no occurrence in the string sequence ,B Replace the first character of the selected string in the group with a You also need to be sure that it does not appear in the string sequence . If A There's... In the group x The first characters are replaced by b String that does not appear after ,B There's... In the group y The first characters are replaced by a String that does not appear after , So in A Group and B A total of... Can be selected from the group x * y A legal company name , That is to say C(x,1) * C(y,1) = x * y. So we need to know that there are characters in the string sequence c1 Replace the beginning with c2 The number of strings that do not appear in the original string sequence , You can use a 26 * 26 Two dimensional array of f To store .

Based on the above analysis , We need to count the string sequence with c1 Replace the initial letter with... In the beginning string c2, The number of strings that make the new string never appear , You can traverse the next string sequence , Replace each string initial with a~z A character in , Count the number of legal schemes . After that, I was right f[i][j] * f[j][i] In sum , This is the solution to the problem .

Code

class Solution {
    
public:
    unordered_map<string,bool> m;
    long long distinctNames(vector<string>& ideas) {
    
        for(auto s : ideas) m[s] = true;
        int n = ideas.size();
        int f[26][26] = {
    0};
        for(auto s : ideas){
    
            int c = s[0] - 'a';
            for(int i = 0;i < 26;i++){
    
                s[0] = 'a' + i;
                if(!m.count(s)) f[c][i]++;//c Replace with i Number of legal schemes after ++
            }
        }
        long long res = 0;
        for(int i = 0;i < 26;i++)
            for(int j = 0;j < 26;j++)
                res += f[i][j] * f[j][i];
        return res;
    }
};