Partage de technologie

150 questions d'entretien classiques

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Vérifier la chaîne palindrome

Une phrase est considérée comme un palindrome si elle se lit de la même manière à l'endroit et à l'envers après avoir converti tous les caractères majuscules en minuscules et supprimé tous les caractères non alphanumériques.

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.size()-1;
        while(left < right){
            while(left < right && !isalnum(s[left])){
                left++;
            }
            while(left < right && !isalnum(s[right])){
                right--;
            }
            if(left < right && tolower(s[left]) != tolower(s[right])){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

Déterminer la sous-séquence

Étant donné les chaînes s et t, déterminez si s est une sous-séquence de t.
Une sous-séquence fait référence à une nouvelle chaîne formée en supprimant certains caractères de la chaîne d'origine sans modifier les positions relatives des caractères restants.

double pointeur
Initialisez deux pointeurs i et j, pointant respectivement vers les positions initiales de s et t.
Pour chaque correspondance gourmande, si la correspondance est réussie, i et j seront décalés vers la droite en même temps, correspondant à la position suivante de s. Si la correspondance échoue, j sera décalé vers la droite et je ne changerai pas. .

Enfin, i se déplace vers la fin de s, indiquant que s est une sous-séquence de t.

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();
        int sIndex = 0, tIndex = 0;
        while(sIndex < n && tIndex < m){
            if(s[sIndex] == t[tIndex]){
                sIndex++;
                tIndex++;
            }else{
                tIndex++;
            }
        }
        return sIndex == n;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

somme de deux nombres

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size()-1;
        while(left < right){
            int num = numbers[left] + numbers[right];
            if(num == target){
                return {left+1, right+1};
            }else if(num < target){
                left++;
            }else{
                right--;
            }
        }
        return {0,0};
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

lettre de rançon

Il n'y a pas de relation d'ordre entre avant et après, utilisez simplement des pointeurs doubles.

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        sort(ransomNote.begin(), ransomNote.end());
        sort(magazine.begin(), magazine.end());
        int i = 0, j = 0, m = ransomNote.size(), n = magazine.size();
        while(i<m && j<n){
            if(ransomNote[i] == magazine[j]){
                i++;
                j++;
            }else{
                j++;
            }
        }
        return i == m;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

Table de hachage

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<int, int> count;
        for(char c : magazine){
            count[c]++;
        }
        for(char c : ransomNote){
            if(count[c] == 0){
                return false;
            }else{
                count[c]--;
            }
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

tableau

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int count[26] = {};
        for(char c : magazine){
            count[c-'a']++;
        }
        for(char c : ransomNote){
            if(count[c-'a'] == 0){
                return false;
            }else{
                count[c-'a']--;
            }
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

Chaînes isomorphes

Étant donné deux chaînes s et t, déterminez si elles sont isomorphes.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> s2t;
        unordered_map<char, char> t2s;
        
        for(int i=0; i<s.size(); i++){
            char x = s[i];
            char y = t[i];
            if((s2t.count(x) && s2t[x] != y) || (t2s.count(y) && t2s[y] != x)){
                return false;
            }
            s2t[x] = y;
            t2s[y] = x;
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

chaîne divisée

vector<string> splitString(string& str){
	istringstream iss(str);
	vector<string> res;
	string word;
	while(iss >> word){
		res.push_back(word);
	}
	return res;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
class Solution {
public:
    vector<string> splitString(string s){
        istringstream iss(s);
        vector<string> res;
        string word;
        while(iss >> word){
            res.push_back(word);
        }
        return res;
    }
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> char2s;
        unordered_map<string, char> s2char;
        
        vector<string> words = splitString(s);
        if(pattern.size() != words.size()){
            return false;
        }
        for(int i=0; i<pattern.size(); i++){
            char c = pattern[i];
            string word = words[i];
            if((char2s.count(c) && char2s[c] != word) || (s2char.count(word) && s2char[word] != c)){
                return false;
            }
            char2s[c] = word;
            s2char[word] = c;
        }
        return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

parenthèses valides

Insérer la description de l'image ici

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(int i = 0; i<s.size(); i++){
            char ch = s[i];
            if(ch == '(' || ch == '[' || ch == '{'){
                stk.push(ch);
            }else{
                if(stk.empty()){
                    return false;
                }
                char topCh = stk.top();
                if((topCh =='[' && ch == ']') || (topCh =='(' && ch == ')') || (topCh =='{' && ch == '}')){
                    stk.pop();
                }else{
                    return false;
                }
            }
        }
        return stk.empty();
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if(n % 2 == 1){
            return false;
        }

        unordered_map<char, char> pairs = {
            {']','['},
            {'}','{'},
            {')','('}
        };

        stack<char> stk;
        for(char ch:s){
            if(pairs.count(ch)){
                if(stk.empty() || stk.top() != pairs[ch]){
                    return false;
                }
                stk.pop();
            }else{
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

Simplifiez le chemin

Nous divisons d'abord le chemin de chaîne donné en une liste de plusieurs chaînes selon /, enregistrées sous forme de noms.
Les chaînes contenues dans les noms ne peuvent être que les suivantes :

  • Chaîne vide. Par exemple, lorsque plusieurs / consécutifs apparaissent, une chaîne vide sera divisée.
  • un point.
  • Deux points…
  • Nom du répertoire.

Pour les chaînes vides et un point, aucun traitement n'est requis.

Pour deux points ou noms de répertoire, une pile est nécessaire pour conserver chaque nom de répertoire dans le chemin. Lorsque vous rencontrez deux points, tant que la pile n'est pas vide, passez au niveau précédent (ouvrez le répertoire supérieur de la pile) et lorsque vous rencontrez un nom de répertoire, placez-le dans la pile.

class Solution {
public:
    vector<string> splitString(string &path){
        vector<string> res;
        string temp;
        for(char c : path){
            if(c == '/'){
                res.push_back(temp);
                temp.clear();
            }else{
                temp += c;
            }
        }
        res.push_back(temp);
        return res;
    }

    string simplifyPath(string path) {
        vector<string> names = splitString(path);
        vector<string> stk;
        for(int i=0; i<names.size(); i++){
            if(names[i] == ".."){
                if(!stk.empty()){
                    stk.pop_back();
                }
            }else if(!names[i].empty() && names[i] != "."){
                stk.push_back(names[i]);
            }
        }

        string res;
        if(stk.empty()){
            res = "/";
        }else{
            for(int i=0; i<stk.size(); i++){
                res += "/" + stk[i];
            }
        }
        return res;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

Pile minimale

Concevez une pile qui prend en charge les opérations push, pop et top et peut récupérer le plus petit élément en temps constant.

Pile auxiliaire

  • Lors de la poussée sur la pile, l'élément est d'abord placé dans la pile ordinaire, le haut de la pile auxiliaire actuelle est comparé à l'élément, puis la valeur minimale est insérée dans le haut de la pile.
  • Lorsque vous sortez de la pile, les deux apparaissent ensemble.
class MinStack {
    stack<int> stk;
    stack<int> min_stk;
public:
    MinStack() {
        min_stk.push(INT_MAX);    
    }
    
    void push(int val) {
        stk.push(val);
        min_stk.push(min(min_stk.top(), val));
    }
    
    void pop() {
        stk.pop();
        min_stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return min_stk.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

Évaluation inversée des expressions polonaises

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        for(int i=0; i<tokens.size(); i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                if(tokens[i] == "+"){
                    stk.push(num1 + num2);
                }else if(tokens[i] == "-"){
                    stk.push(num1 - num2);
                }else if(tokens[i] == "*"){
                    stk.push(num1 * num2);
                }else{
                    stk.push(num1 / num2);
                }
            }else{
                stk.push(stoi(tokens[i]));
            }
        }
        return stk.top();
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

calculatrice de base

Étant donné une expression de chaîne s, implémentez une calculatrice de base pour calculer et renvoyer sa valeur.

Extension de support + pile
En plus des nombres et des parenthèses, les chaînes n'ont que deux opérateurs : le signe plus et le signe moins.
Par conséquent, si vous développez toutes les parenthèses dans une expression, les nombres eux-mêmes ne changeront pas dans la nouvelle expression résultante, seul le signe devant chaque nombre le changera.

Une opération de pile doit être maintenue, dans laquelle l'élément supérieur de la pile enregistre le symbole de chaque support à la position actuelle.
1+2+(3-(4+5)):

  • Lors d'une numérisation vers 1+2, puisque la position actuelle n'est incluse entre parenthèses, l'élément supérieur de la pile est la valeur initiale + 1 ;
  • Lors de la numérisation vers 1+2+(3, la position actuelle est contenue par un crochet. Le symbole devant le crochet est +, donc l'élément supérieur de la pile est +1
class Solution {
public:
    int calculate(string s) {
        stack<int> ops;
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int i = 0;
        int n = s.size();
        while(i < n){
            if(s[i] == ' '){
                i++;
            }else if(s[i] == '+'){
                sign = ops.top();
                i++;
            }else if(s[i] == '-'){
                sign = -ops.top();
                i++;
            }else if(s[i] == '('){
                ops.push(sign);
                i++;
            }else if(s[i] == ')'){
                ops.pop();
                i++;
            }else{
                long num = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9'){
                    num = num * 10 + s[i]-'0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37