Berbagi teknologi

150 pertanyaan wawancara klasik

2024-07-12

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

Verifikasi string palindrom

Sebuah frasa dianggap palindrom jika bacaannya sama tegak dan mundur setelah mengubah semua karakter huruf besar menjadi huruf kecil dan menghapus semua karakter non-alfanumerik.

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

Tentukan selanjutnya

Diketahui string s dan t, tentukan apakah s merupakan barisan berikutnya dari t.
Urutan mengacu pada string baru yang dibentuk dengan menghapus beberapa karakter dari string asli tanpa mengubah posisi relatif dari karakter yang tersisa.

penunjuk ganda
Inisialisasi dua pointer i dan j, masing-masing menunjuk ke posisi awal s dan t.
Untuk setiap pencocokan serakah, jika pencocokan berhasil, i dan j akan digeser ke kanan secara bersamaan, mencocokkan posisi s berikutnya. Jika pencocokan gagal, j akan digeser ke kanan, dan i tidak akan berubah .

Akhirnya i berpindah ke akhir s, menunjukkan bahwa s adalah kelanjutan dari 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

jumlah dua angka

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

surat tebusan

Tidak ada hubungan urutan antara sebelum dan sesudah, cukup gunakan petunjuk ganda.

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

Tabel hash

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

Himpunan

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

String isomorfik

Diberikan dua string s dan t, tentukan apakah string tersebut isomorfik.

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

tali terbelah

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

tanda kurung yang sah

Masukkan deskripsi gambar di sini

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

Sederhanakan jalannya

Kami pertama-tama membagi jalur string yang diberikan menjadi daftar beberapa string menurut /, dicatat sebagai nama.
String yang terdapat dalam nama hanya dapat berupa berikut ini:

  • Tali kosong. Misalnya, ketika beberapa /s berturut-turut muncul, string kosong akan dipisahkan.
  • satu poin.
  • Dua poin…
  • Nama direktori.

Untuk string kosong dan titik, tidak diperlukan pemrosesan.

Untuk dua titik atau nama direktori, tumpukan diperlukan untuk mempertahankan setiap nama direktori di jalurnya. Ketika menemukan dua titik, selama tumpukan tidak kosong, beralih ke tingkat sebelumnya (munculkan direktori teratas tumpukan), dan ketika menemukan nama direktori, masukkan ke dalam tumpukan.

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

Tumpukan minimal

Rancang tumpukan yang mendukung operasi push, pop, dan top serta dapat mengambil elemen terkecil dalam waktu yang konstan.

Tumpukan tambahan

  • Saat mendorong ke tumpukan, elemen pertama-tama dimasukkan ke dalam tumpukan biasa, bagian atas tumpukan tambahan saat ini dibandingkan dengan elemen, dan kemudian nilai minimum dimasukkan ke bagian atas tumpukan.
  • Saat keluar dari tumpukan, keduanya muncul bersamaan.
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

Evaluasi ekspresi Polandia terbalik

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

kalkulator dasar

Diberikan ekspresi string s, terapkan kalkulator dasar untuk menghitung dan mengembalikan nilainya.

Ekspansi braket + tumpukan
Selain angka dan tanda kurung, string hanya mempunyai dua operator: tanda plus dan tanda minus.
Oleh karena itu, jika Anda memperluas semua tanda kurung dalam sebuah ekspresi, angka-angka itu sendiri tidak akan berubah dalam ekspresi baru yang dihasilkan, hanya tanda di depan setiap angka yang akan berubah.

Operasi tumpukan perlu dipertahankan, di mana elemen teratas tumpukan mencatat simbol setiap tanda kurung pada posisi saat ini.
1+2+(3-(4+5))：

  • Saat memindai ke 1+2, karena posisi saat ini tidak disertakan dalam tanda kurung apa pun, elemen teratas tumpukan adalah nilai awal + 1;
  • Saat memindai ke 1+2+(3, posisi saat ini terdapat dalam tanda kurung. Simbol di depan tanda kurung adalah +, sehingga elemen teratas tumpukan adalah +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

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. Ia telah memberikan banyak kontribusi di bidang open source stasiun dokumentasi pengembang untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang. Semua orang memeriksanya

informasi kontak saya

Surat