[Algorithme]. Bijoux et pierres

Description du problème

Donnez deux chaînes:

représenter le type de gemme,

représente les pierres que vous possédez. jewels Chaque personnage représente une sorte de pierre que vous possédez. Vous devez calculer le nombre de gemmes dans les pierres que vous avez. stones stones lettres de lettres, donc "A" et "A" représentent différents types de pierres.

La clé du problème

Trouvez le caractère dans la chaîne dans la chaîne

et renvoyez le nombre total de ces caractères.

jewels Exemple 1 stones

Exemple 2

<code>输入：jewels = "aA", stones = "aAAbbbb"
输出：3</code>

Les conditions de contrainte

<code>输入：jewels = "z", stones = "ZZ"
输出：0</code>

1 ≤ ,

≤ 50 et

ne comprennent que des lettres anglaises.

• Tous les personnages sont uniques. jewels.length stones.length
Plan 1: Utilisez la méthode incluse ()
• jewels stones
étape:
• jewels Initialiser le compteur
utilisé pour stocker le nombre total de gemmes.

Traversed String et utilisez la méthode pour vérifier si chaque caractère est dans la chaîne .

<code class="language-javascript">/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewels.includes(stones[i])) {
            count++;
        }
    }
    return count;
};</code>

s'il contient, il augmentera

.

Dernier retour .
1. count
La complexité temporelle de cette méthode est O (m * n), où m est la longueur de la chaîne
2. , et n est la longueur de la chaîne stones. Parce que les méthodes ont traversé chaque caractère sur la chaîne includes(). Lorsque l'échelle d'entrée augmente, cette méthode est inefficace. Nous devons optimiser le plan pour réduire la complexité du temps. jewels
Plan 2: Utilisez la méthode set () (table de hachage)
3. count
4. étape: count
Initialiser le compteur

utilisé pour stocker le nombre total de gemmes.

stones Utiliser chaînes pour créer un jewels. includes() Utilisez des tables de hachage pour trouver une recherche plus rapide. jewels

TRAVERSED String et utilisez la méthode

pour vérifier si chaque caractère est dans .

s'il existe, il augmentera

<code class="language-javascript">/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jewelsSet = new Set(jewels);
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewelsSet.has(stones[i])) {
            count++;
        }
    }
    return count;
};</code>

.

Dernier retour .

1. count Pourquoi est réglé plus vite que l'inclusion ()?
2. Méthodes pour vérifier la valeur en traversant jewels la chaîne à travers des caractères un par un. Set Set et HACH Tables à l'intérieur de la structure des données, permettant l'utilisation de la méthode
pour une recherche de temps constant O (1). Bien qu'il soit nécessaire de créer un temps O (n) initial, la recherche de suivi est beaucoup plus rapide que la méthode
3. . stones

   Si j'ai des erreurs ou si vous avez des vues différentes, veuillez laisser un message à tout moment. Je suis toujours heureux d'apprendre de différents angles! ? Si vous aimez cet article, veuillez me contacter sur LinkedIn à tout moment.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!