当前位置:网站首页>Leetcode frappe - 316 tous les jours.

Leetcode frappe - 316 tous les jours.

2021-10-14 04:09:46 Sun zhongming

Je te donne une chaîne. s ,Veuillez supprimer les lettres dupliquées de la chaîne,De sorte que chaque lettre n'apparaisse qu'une seule fois.Garantie requise L'ordre du dictionnaire qui renvoie les résultats est le plus petit(Exiger que la position relative des autres caractères ne soit pas perturbée).

Exemple 1:

Entrée:s = "bcabc"
Produits:"abc"

Exemple 2:

Entrée:s = "cbacdcbc"
Produits:"acdb"

Conseils:

1 <= s.length <= 104
s Composé de petites lettres anglaises

Idées
Pour supprimer les caractères dupliqués,Vous pouvez demander si la première traversée est répétée,Et lors de la génération des caractères traités,Besoin de trouver rapidement où le caractère apparaît pour la première fois,Il est donc possible de maintenir unHashMap<Character,Integer>.
La première fois que vous traversez une chaîne,Si le caractère actuellement traversé n'est pasmapMoyenne,Stocke ce caractère et sa position dans la chaînemapMoyenne;Existe déjàmapPas d'opération.
La deuxième fois que vous traversez une chaîne,Si le caractère courant estmapMoyenne,Laissez ce caractère,Et supprimer la paire de valeurs clés pour ce caractère;S'il n'existe pas,Aucune opération.De cette façon, vous pouvez conserver les caractères qui apparaissent pour la première fois.
Code


import java.util.*;

class Solution {
    
    public String removeDuplicateLetters(String s) {
    
        int len=s.length();
        if(s==null||len<1){
    
            return "";
        }

        StringBuffer res=new StringBuffer();

        HashMap<Character,Integer> map = new HashMap<Character,Integer>();



        for(int i=0;i<=len-1;i++){
    
            if(!map.containsKey(s.charAt(i))){
    
                map.put(s.charAt(i),i);
            }
        }

        for(int i =0;i<=len-1;i++){
    
            if(map.containsKey(s.charAt(i))){
    
                res.append(s.charAt(i));
                map.remove(s.charAt(i),i);
            }
        }

        return res.toString();

    }
}

Ce faisant, il n'est pas garanti que l'ordre du dictionnaire des résultats retournés soit minimal ; Donc nous devons utiliser la pile

Entrée "bcabc"
Produits "bca"
Résultats escomptés "abc"

Idées

  1. Comment peser ?

Avec unvisTableau, Si ce caractère est sur la pile , Alors on va le marquer comme 1, C'est le caractère , Quand il réapparaîtra , On n'en veut pas ,Sauter directement;

  1. Pour obtenir le plus petit ordre de Dictionnaire ,Que faire??

Quand uns[i]>s[i+1]( Plus précisément, lorsque le nombre précédent dans la pile est supérieur au nombre suivant , Comme une pile monotone )Heure,i Pour être éjecté ,Mais si ças[i] C'est un semis solitaire. ( Il n'y a plus ce caractère après ), On ne peut pas s'éjecter , Alors, on utilise un numArray Stores Cas des caractères restants dans , Chaque fois qu'on lance un caractère ou qu'on saute un nombre , Il faut réduire le nombre 1;


import java.util.Stack;

/** * Opération Stack o(n*log(n)) */
public class Solution {
    

    public String removeDuplicateLetters(String s) {
    
        Stack<Character> stack = new Stack<>();


        for (int i = 0; i < s.length(); i++) {
    
            Character c = s.charAt(i);
            if (stack.contains(c)) {
    
                continue;
            }

            //public int indexOf(int ch, int fromIndex): Retour de fromIndex  La position commence à rechercher l'index où le caractère spécifié apparaît pour la première fois dans la chaîne , S'il n'y a pas un tel caractère dans cette chaîne ,Renvoie -1.
            while (!stack.isEmpty() && stack.peek() > c && s.indexOf(stack.peek(), i) != -1) {
    
                stack.pop();
            }
            stack.push(c);
        }
        String rs = "";
        for (int i = 0; i < stack.size(); i++) {
    
            rs += stack.get(i);
        }
        return rs;
    }
}

版权声明
本文为[Sun zhongming]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211013211945140b.html

随机推荐