Leetcode 297 match de la semaine

Résumé

La dernière question de cette semaine est facile à tourner autour des gens,Sans examiner les algorithmes trop difficiles,Mais une forte capacité d'analyse est nécessaire.

Liste des sujets

1.Calcul du montant total de l'impôt à payer

Description du sujet

Pour vous donner un indice de 0 Tableau entier 2D à partir de brackets ,Parmi eux brackets[i] = [upperi, percenti] ,Indique le paragraphe i La limite supérieure de l'impôt sur le revenu des particuliers est: upperi ,Le taux d'imposition est le suivant: percenti .Niveau d'imposition par plafond Trier de bas en haut（Dans la satisfaction 0 < i < brackets.length Sur la base de,upperi-1 < upperi）.

L'impôt est calculé comme suit:：

Pas plus de upper0 Revenu imposable percent0 Paiement
Et voilà. upper1 - upper0 Taux d'imposition percent1 Paiement
Et puis upper2 - upper1 Taux d'imposition percent2 Paiement
Et ainsi de suite.
Pour vous donner un entier income Représente votre revenu total.Retour à impôt total à payer.L'erreur par rapport à la réponse standard n'est pas supérieure à 10^-5 Le résultat sera considéré comme la bonne réponse.
Exemple 1：

Entrée：brackets = [[3,50],[7,10],[12,25]], income = 10
Produits：2.65000
Explication：
Avant $3 Taux d'imposition 50% .Impôt à payer $3 * 50% = $1.50 .
Et puis... $7 - $3 = $4 Taux d'imposition 10% .Impôt à payer $4 * 10% = $0.40 .
Enfin $10 - $7 = $3 Taux d'imposition 25% .Impôt à payer $3 * 25% = $0.75 .
Total des impôts à payer $1.50 + $0.40 + $0.75 = $2.65 .
Exemple 2：
Entrée：brackets = [[1,0],[4,25],[5,50]], income = 2
Produits：0.25000
Explication：
Avant $1 Taux d'imposition 0% .Impôt à payer $1 * 0% = $0 .
Il reste $1 Taux d'imposition 25% .Impôt à payer $1 * 25% = $0.25 .
Total des impôts à payer $0 + $0.25 = $0.25 .
Exemple 3：
Entrée：brackets = [[2,50]], income = 0
Produits：0.00000
Explication：
Pas de revenus,Pas d'impôt à payer, Total des impôts à payer $0 .
Conseils：
1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi Ordre croissant
upperi Toutes les valeurs dans Ils sont différents les uns des autres
La limite supérieure de la dernière tranche d'imposition est supérieure ou égale à income

Analyse

Questions de simulation,Traverséebrackets ,Siincome Supérieur au dernier niveau d'imposition , Ajoutez l'impôt sur la partie de ce niveau d'impôt . Par exemple, les niveaux d'imposition sont les suivants: 3 7 12,Le revenu est10, Niveau d'imposition initial précédent last- Oui.0,10 > 0, Puis Calculez la pression 3 Quel est le montant de l'impôt perçu au niveau de l'impôt? ,Si10Plus grand que3, Niveau d'imposition 3 Le montant de l'impôt est 3, Multiplié par le taux d'imposition correspondant est l'impôt à payer pour le niveau d'imposition actuel .Mise à jourlast = 3,Viens.7 Ce niveau d'imposition ,10 > 3 Pour que vous puissiez suivre 7 Les impôts sont perçus à ce niveau , Le montant de l'impôt est 7 - 3 = 4.Mise à jourlast = 7,Viens.12 Ce niveau d'imposition ,10 > 7,Mais10 < 12, Donc le montant d'impôt actuel est min(10,12) - 7 = 3.

Comme question d'inscription , Ce sujet établit amicalement le dernier niveau d'imposition qui n'est pas inférieur à incomeConditions, Sinon, il faut aussi juger de la situation frontalière .

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.Coût minimal du chemin dans la grille

Description du sujet

Pour vous donner un indice de 0 Matrice entière de départ grid ,La taille de la matrice est m x n ,De 0 À m * n - 1 Composition des différents entiers de.Vous pouvez utiliser cette matrice,Passer d'une cellule à Ligne suivante Toute autre cellule de.Si vous êtes dans une cellule (x, y) ,Et satisfait x < m - 1 ,Vous pouvez vous déplacer vers (x + 1, 0), (x + 1, 1), …, (x + 1, n - 1) N'importe laquelle des cellules.Attention!： Les cellules de la dernière ligne ne peuvent pas déclencher le mouvement.

Chaque mouvement possible coûte cher,Prix à partir d'un indice 0 Tableau bidimensionnel de départ moveCost Représentation,La taille du tableau est (m * n) x n ,Parmi eux moveCost[i][j] Est de la valeur de i Déplacer les cellules de la ligne suivante à la ligne j Coût des cellules de colonne.De grid Le coût du déplacement des cellules de la dernière ligne peut être ignoré.

grid Le prix d'un chemin est：Tous les chemins passant par les cellules La somme des valeurs Plus Tout ce qui bouge La somme des coûts .De Première ligne Départ de n'importe quelle cellule,Retour à l'arrivée La dernière ligne Coût minimal du chemin pour n'importe quelle cellule.
Exemple 1：

Entrée：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
Produits：17
Explication： Le chemin le moins cher est 5 -> 0 -> 1 .

• Somme des valeurs des cellules de chemin 5 + 0 + 1 = 6 .
• De 5 Déplacer vers 0 Au prix de 3 .
• De 0 Déplacer vers 1 Au prix de 8 .
  Le coût total du chemin est 6 + 3 + 8 = 17 .
  Exemple 2：
  Entrée：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]]
  Produits：6
  Explication：
  Le chemin le moins cher est 2 -> 3 .
• Somme des valeurs des cellules de chemin 2 + 3 = 5 .
• De 2 Déplacer vers 3 Au prix de 1 .
  Le coût total du chemin est 5 + 1 = 6 .
  Conseils：
  m == grid.length
  n == grid[i].length
  2 <= m, n <= 50
  grid De 0 À m * n - 1 Composition des différents entiers de
  moveCost.length == m * n
  moveCost[i].length == n
  1 <= moveCost[i][j] <= 100

Analyse

Linéarité simple DPQuestions, Appartient au modèle triangulaire numérique . Ce qui prend le plus de temps, c'est de lire moveCost Cette représentation d'un tableau bidimensionnel qui stocke le coût , Il m'a fallu un peu de temps pour simuler les cas d'utilisation pendant la semaine pour comprendre comment cela se traduit. .Par exemple,moveCost[1][2] = 3, Cela signifie que la valeur est 1Déplacer les cellules de la ligne suivante à la ligne2 Le coût des cellules de colonne est 3. Les exemples de sujets ne sont donnés que moveCostValeur de, Son indice doit être calculé par lui - même , Cette méthode de stockage est rare .

Représentation du Statut：f[i][j] Indique l'arrivée à partir de n'importe quelle cellule de la première ligne (i,j)Le coût minimum. Apparemment, l'état initial est la cellule de la première ligne ,f[0][i] = grid[0][i], C'est parce que le coût du chemin de déplacement du sujet est égal à la somme du coût du déplacement et de la valeur passant par la cellule. , La Cellule de la première ligne n'a pas besoin d'être déplacée , Mais le coût doit être ajouté à la valeur de sa propre cellule .
L'équation de transfert d'état est：

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

Noi L'état d'une ligne peut être transféré de l'état d'une colonne différente de la ligne précédente , Trouvez le coût minimum. .

Code

class Solution {
    
public:
    /*f[i][j]Indique l'arrivéei,j Coût minimal des cellules */
    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.Distribution équitable des biscuits

Description du sujet

Pour vous donner un tableau entier cookies ,Parmi eux cookies[i] Indique que i Nombre de biscuits dans chaque paquet de snacks.Je vais te donner un autre entier k Indique le nombre d'enfants en attente de distribution de snacks,Tous les Tous les snacks doivent être distribués.Tous les biscuits dans le même sac de collation doivent être distribués au même enfant,On ne peut pas se séparer..

Distribution Degré d'injustice Défini comme le nombre maximum de biscuits qu'un enfant peut obtenir au cours de la distribution.

Renvoie le niveau minimal d'injustice pour toutes les distributions.
Exemple 1：

Entrée：cookies = [8,15,10,20,8], k = 2
Produits：31
Explication：Une solution optimale est [8,15,8] Et [10,20] .

• No 1 Pour les enfants. [8,15,8] ,Total général 8 + 15 + 8 = 31 Un biscuit.
• No 2 Pour les enfants. [10,20] ,Total général 10 + 20 = 30 Un biscuit.
  Le niveau d'injustice de la distribution est max(31,30) = 31 .
  Il peut être prouvé qu'il n'y a pas d'injustice inférieure à 31 Programme de distribution .
  Exemple 2：
  Entrée：cookies = [6,1,3,2,2,4,1,2], k = 3
  Produits：7
  Explication：Une solution optimale est [6,1]、[3,2,2] Et [4,1,2] .
• No 1 Pour les enfants. [6,1] ,Total général 6 + 1 = 7 Un biscuit.
• No 2 Pour les enfants. [3,2,2] ,Total général 3 + 2 + 2 = 7 Un biscuit.
• No 3 Pour les enfants. [4,1,2] ,Total général 4 + 1 + 2 = 7 Un biscuit.
  Le niveau d'injustice de la distribution est max(7,7,7) = 7 .
  Il peut être prouvé qu'il n'y a pas d'injustice inférieure à 7 Programme de distribution .
  Conseils：
  2 <= cookies.length <= 8
  1 <= cookies[i] <= 10⁵
  2 <= k <= cookies.length

Analyse

La gamme de données pour cette question est plus petite,Peut utiliser le plus basiqueDFSRésolution,Pas du tout.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 La condition limite est que l'énumération est terminée. , La valeur maximale pour obtenir des biscuits est maintenant trouvée dans tous les schémas d'allocation , Essayer d'obtenir une solution optimale mise à jour .En général, Pour la présente section u Des biscuits. ,Peut êtret Différentes méthodes d'allocation , énumérez - les un par un. , Le tableau global doit être restauré après chaque énumération num Pour la prochaine énumération . Le plus rapide de la semaine AC La solution est la violence pure et directe ,TotalkUn enfant, Chaque paquet de biscuits kMéthode d'ensemencement,C'est tout.8⁸ = 2²⁴Approximativement égal à1600wStatut des espèces, C'est abordable. .

Bien sûr, il n'y a pas assez de violence pour faire ce sujet en temps normal , Au moins, coupez - les. .

Tout d'abord, considérez le cisaillement optimal , Après avoir énuméré un scénario ,S'il vous plaîtansUne valeur pour, Il n'y a que ans Il sera mis à jour plus tôt. ,Etans La valeur de dépend du nombre de biscuits distribués par personne , Donc une fois qu'un plan d'allocation est attribué à une personne, le nombre de biscuits est égal ou supérieur à ans, Vous n'avez pas besoin de continuer à énumérer . Plus cette déclaration de coupure optimale ,dfs L'efficacité sera multipliée par dix. .

Pensez à optimiser l'ordre de recherche ,cookies La plus grande quantité de biscuits à l'intérieur, si elle est distribuée en premier , Le nombre de biscuits a augmenté plus rapidement parmi les personnes qui ont distribué des biscuits. , Et plus facile à couper , Donc la priorité est donnée aux biscuits avec de grandes valeurs ,dfsAvantcookies Trier de grand à petit . Plus optimisation de l'ordre de recherche ,dfs Peut être plus rapide 3X.

Il y a des recherches redondantes, bien sûr. , Comme le premier paquet de biscuits pour la première personne , Un deuxième paquet de biscuits pour la deuxième personne et un premier paquet pour la deuxième personne , L'effet du deuxième paquet à la première personne sur la solution du problème est cohérent , Nous ne nous préoccupons que des combinaisons assignées , Sans se soucier de l'ordre de tri , L'élimination de la redondance équivalente peut en effet accroître considérablement l'efficacité , .Par exemple, nous fixons le premier paquet de biscuits à la première personne seulement , Parce que c'est pareil pour tout le monde. . Parce que tout le monde peut obtenir plus d'un paquet de biscuits , Mauvaise représentation de la recherche de mémoire , Donc le Code ici n'exclut pas les recherches redondantes .

Pensez à la compression de l'état DPLa solution, Pas de compression hebdomadaire. DFS Rapide à terminer , Mais d'habitude, ça peut être étudié , Après tout, c'est plus efficace. .

NousDFS Est un cookie d'énumération , Pensez à qui. , Maintenant, une autre façon d'énumérer , énumérer tout le monde dans l'ordre , Essayez d'assigner des biscuits à tout le monde .Noi Le plan d'allocation individuel dépend uniquement de l'ancien i - 1 Plan de distribution individuel , Parce qu'il n'y a pas beaucoup de paquets de biscuits , Ainsi, l'état de Cookie déjà assigné peut être comprimé en utilisant l'état .

Représentation du Statut：f[i][j] Avant i Distribution personnelle de biscuits , L'état de distribution des biscuits est j Niveau minimal d'injustice ,Par exemple,f[2][3] Ça veut dire qu'il y a eu une distribution entre les deux premiers 1,2 Biscuits emballés ,Parce que3 Utiliser des tables binaires 
 Oui. 11, Ça veut dire que les deux premiers paquets de biscuits ont été distribués. .
Changement d'état：Maintenant quei L'état d'affectation d'une personne est j,Alorsj Tout sous - ensemble de i Plan de distribution individuel ,Donc nous pouvons énumérerjUn sous - ensemble dex,Avanti-1 L'état d'allocation d'une personne est j - x,Oui.
Exprimé enj ^ x,Par exemple,j = 1101,x = 0100,j ^ x = 1001,j ^ xC'estxPar rapport àj C'est un supplément. .
Équation de transfert d'état：f[i][j] = min(f[i][j],max(f[i-1][j^x],sum[x])),C'est avant.i Le degré d'injustice du plan de distribution individuel est égal à celui de l'ancien i-1 La solution optimale de l'individu et i Biscuits distribués individuellement 
 Le plus élevé des montants suivants: , Dans tous les systèmes d'allocation, la valeur minimale est f[i][j]La solution optimale pour.
Limite d'état：f[0][0] = 0,Autres statutsINF.

Deux autres problèmes doivent être résolus. , La première question est comment compresser l'état comment énumérer un sous - ensemble d'une collection .Par exemple,j = 1101Heure,jUn sous - ensemble de1100,1001.1000.0101.0100.0001Ces, Le Code couramment utilisé pour énumérer les sous - ensembles est for(int x = j;x;x=(x-1)&j),C'est - à - direjAvecj-1 Phase et obtient le premier sous - ensemble 1100,C'est l'équivalent de donnerjÀ droite.1Enlevée.,Et puis1100Moins1EtjPhase vs.,Je l'ai.1001, L'ordre d'énumération suivant est l'ordre d'énumération des sous - ensembles de grande à petite paires. . Pour une analyse détaillée, voir À propos de hypostasis DP Méthodes et compréhension de l'énumération des sous - ensembles .

Le deuxième problème est de savoir comment calculer rapidement le nombre de biscuits distribués dans un système de distribution. ,Parce quei Les programmes individuels sont: x, J'ai besoin de demander combien de biscuits cet homme a .Nous pouvons suivre1 2 4 8… Pour distribuer des biscuits ,Par exemple, plus que1 Un petit état n'a que 0,Alors0 | 1 = 1,sum[0 | 1] = sum[0] + cookies[0]; Et regarde. 2 Les petits états ont 0Et1,sum[0 | 2] = sum[0] + cookies[1];sum[1 | 2] = sum[1] + cookies[1], Ce changement d'état est simple , Il suffit d'ajouter i L'état donné au biscuit lors de l'emballage du nombre de biscuits est également 1 << i, Mais la séquence des transitions d'état est difficile à imaginer .

Code

DFS + Couper

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;
    }
};

Compression de l'étatDP

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. Nom de l'entreprise

Description du sujet

Pour vous donner un tableau de chaînes ideas Représente la liste des noms utilisés dans le processus de désignation de l'entreprise.Le processus de désignation de l'entreprise est le suivant:：
De ideas Sélectionner parmi 2 - Oui. C'est différent. Nom,Appelé ideaA Et ideaB .
Echange ideaA Et ideaB Les initiales de.
Si vous obtenez deux nouveaux noms Tous Non. ideas Moyenne,Alors ideaA ideaB（Tandem ideaA Et ideaB ,Le Centre est séparé par un espace）Est un nom d'entreprise valide.
Sinon,Pas un nom valide.
Retour C'est différent. Nombre de noms d'entreprise valides.
Exemple 1：
Entrée：ideas = [“coffee”,“donuts”,“time”,“toffee”]
Produits：6
Explication： Voici quelques options disponibles ：

• (“coffee”, “donuts”)： Le nom de l'entreprise correspondante est “doffee conuts” .
• (“donuts”, “coffee”)： Le nom de l'entreprise correspondante est “conuts doffee” .
• (“donuts”, “time”)： Le nom de l'entreprise correspondante est “tonuts dime” .
• (“donuts”, “toffee”)： Le nom de l'entreprise correspondante est “tonuts doffee” .
• (“time”, “donuts”)： Le nom de l'entreprise correspondante est “dime tonuts” .
• (“toffee”, “donuts”)： Le nom de l'entreprise correspondante est “doffee tonuts” .
  Donc,,En tout. 6 Différents noms d'entreprise .
  Voici quelques options invalides ：
• (“coffee”, “time”)： Le nom formé après l'échange existe dans le tableau original “toffee” .
• (“time”, “toffee”)： Il y a deux noms formés après l'échange dans le tableau original .
• (“coffee”, “toffee”)： Il y a deux noms formés après l'échange dans le tableau original .
  Exemple 2：
  Entrée：ideas = [“lack”,“back”]
  Produits：0
  Explication： Aucune option valide n'existe .Donc,,Retour 0 .
  Conseils：
  2 <= ideas.length <= 5 * 10⁴
  1 <= ideas[i].length <= 10
  ideas[i] Composé de petites lettres anglaises
  ideas Toutes les chaînes dans Ils sont différents les uns des autres

Analyse

Cette question n'examine pas les algorithmes complexes , Mais la logique de résolution des problèmes est encore très tordue. , C'est facile d'assommer les gens. , Essayez d'analyser le problème aussi simplement que possible. .

Séquence de chaînes donnée , Pour les séquences de chaînes aEtb,Si l'échangeaEtb Les deux chaînes formées après les initiales n'apparaissent pas dans la séquence de chaînes , Ces deux chaînes peuvent apparaître comme un nom d'entreprise légal , Combien de noms d'entreprise légitimes . La complexité de l'énumération en double boucle des pratiques violentes est au niveau du carré ,La quantité calculée est2.5 * 10⁹,Oui.TLEDe, Nous ne pouvons donc énumérer qu'une seule des deux paires de chaînes .

La violence est contre chaque chaîne , énumérer les chaînes restantes , Échange des initiales de deux chaînes , Si les deux chaînes n'apparaissent pas dans la séquence de chaînes après l'échange , Vous pouvez augmenter le nombre de programmes , Qu'est - ce qui vous permet de trouver rapidement le nombre de chaînes légitimes dans une séquence de chaînes après avoir échangé des initiales avec une chaîne? ？Par exemple,A = “abcd”,B=“bcda”,On échange.AB Après les initiales bbcdEtacda,Et jugerbbcd Est - ce que ça s'est déjà produit? ,acda Est - ce que ça s'est déjà produit? .On peut le découvrir.,PourADis, Nous ne nous préoccupons que des initiales échangées ,Peu importeB Quels sont les caractères suivants ,Tant queB Remplacer les initiales par A La chaîne après les initiales n'apparaît pas , Remplacer AC'est légal.. Et les chaînes dans ce titre sont faites de minuscules lettres ,La plupart26Espèce, Donc vous pouvez diviser la séquence de chaînes en différentes initiales 26 Séquence de chaînes de groupe ：
AGroupe：ParaLa chaîne au début,BGroupe：ParbLa chaîne au début,…,ZGroupe：ParzLa chaîne au début.

Dans la séquence originale , Il nous faut deux chaînes. , Pour déterminer s'il constitue un nom légal . Maintenant nous groupons la séquence de chaînes , Dans la même séquence de chaînes , Parce que le premier caractère est le même , Chaîne inchangée après l'échange du premier caractère , Ça ne doit pas constituer un nom légal , Deux chaînes ne peuvent être sélectionnées que dans deux groupes différents .Comme dansA Sélectionnez une chaîne dans le Groupe ,B Sélectionnez une chaîne dans le Groupe , Pour que deux chaînes puissent former un nom d'entreprise légal ,AlorsA Le premier caractère de chaîne sélectionné par le Groupe est remplacé par b Plus tard, vous n'avez pas besoin d'apparaître dans la séquence de chaînes ,B Le premier caractère de la chaîne sélectionnée dans le Groupe est remplacé par a Il n'est pas non plus nécessaire qu'il n'apparaisse pas dans la séquence de chaînes .SiA Il y en a dans le Groupe. x Remplacer les premiers caractères par b Chaîne qui n'est pas apparue après ,B Il y en a dans le Groupe. y Remplacer les premiers caractères par a Chaîne qui n'est pas apparue après ,Alors, dansAGroupes etB Tous les membres du Groupe peuvent choisir x * y Nom légal de l'entreprise ,C'est - à - direC(x,1) * C(y,1) = x * y. Donc nous avons besoin de savoir qu'il y a des caractères dans la séquence de chaîne c1Remplacer le début par le texte suivant:c2 Nombre de chaînes qui n'apparaissent pas dans la séquence originale ,On peut en avoir un.26 * 26Un tableau bidimensionnel defPour stocker.

Selon l'analyse ci - dessus, Nous avons besoin de statistiques dans la séquence de chaînes pour c1 Remplacer les initiales par c2, Nombre de chaînes qui font que la nouvelle chaîne n'apparaît pas , Peut traverser la séquence de chaînes suivante , Remplacer les initiales de chaque chaîne par a~zUn caractère dans, Nombre de programmes licites au titre des statistiques .Après ça, à droite.f[i][j] * f[j][i]Faire la somme, C'est la solution. .

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]++;//cRemplacer par:i Nombre de régimes légaux postérieurs ++
            }
        }
        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;
    }
};