Обмен технологиями

150 классических вопросов для собеседования

2024-07-12

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

Проверка строки-палиндрома

Фраза считается палиндромом, если она читается одинаково в прямом и обратном порядке после преобразования всех символов верхнего регистра в нижний регистр и удаления всех небуквенно-цифровых символов.

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

Определить подпоследовательность

Учитывая строки s и t, определите, является ли s подпоследовательностью t.
Подпоследовательность относится к новой строке, образованной путем удаления некоторых символов из исходной строки без изменения относительных положений остальных символов.

двойной указатель
Инициализируйте два указателя i и j, указывающие на начальные позиции s и t соответственно.
Для каждого жадного сопоставления, если сопоставление прошло успешно, i и j будут одновременно сдвинуты вправо, что соответствует следующей позиции s. Если совпадение не удалось, j будет сдвинуто вправо, а i не изменится. .

Наконец, я перемещаюсь в конец s, указывая, что s является подпоследовательностью 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

сумма двух чисел

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

письмо с требованием выкупа

Между «до» и «после» нет отношения порядка, просто используйте двойные указатели.

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

Хеш-таблица

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

множество

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

Изоморфные строки

Даны две строки s и t. Определите, изоморфны ли они.

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

разделить строку

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

допустимые скобки

Вставьте сюда описание изображения

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

Упростите путь

Сначала мы разбиваем заданный путь к строке на список из нескольких строк в соответствии с /, записанных как имена.
Строки, содержащиеся в именах, могут быть только следующими:

  • Пустая строка. Например, при появлении нескольких последовательных /s пустая строка будет разделена.
  • один пункт.
  • Два момента…
  • Имя каталога.

Для пустых строк и точки обработка не требуется.

Для двух точек или имен каталогов необходим стек для хранения каждого имени каталога в пути. При встрече двух точек, пока стек не пуст, переключитесь на предыдущий уровень (вытолкните верхний каталог стека), а при обнаружении имени каталога поместите его в стек.

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

Минимальный стек

Спроектируйте стек, который поддерживает операции push, pop и top и может извлекать наименьший элемент за постоянное время.

Вспомогательный стек

  • При занесении в стек элемент сначала помещается в обычный стек, вершина текущего вспомогательного стека сравнивается с элементом, а затем минимальное значение вставляется в вершину стека.
  • При извлечении из стека оба появляются вместе.
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

Обратная оценка польского выражения

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

базовый калькулятор

Учитывая строковое выражение s, реализуйте базовый калькулятор для вычисления и возврата его значения.

Расширение скобок + стек
Помимо чисел и круглых скобок, строки имеют только два оператора: знак плюс и знак минус.
Следовательно, если раскрыть все круглые скобки в выражении, сами числа в полученном новом выражении не изменятся, изменится только знак перед каждым числом.

Необходимо поддерживать операции стека, в которых верхний элемент стека записывает символ каждой скобки в текущей позиции.
1+2+(3-(4+5))：

  • При сканировании до 1+2, поскольку текущая позиция не заключена ни в какие скобки, верхний элемент стека имеет начальное значение +1;
  • При сканировании до 1+2+(3 текущая позиция содержится в скобках. Символ перед скобкой — +, поэтому верхний элемент стека — +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

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта