技術共有

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 の部分列であるかどうかを判断します。
サブシーケンスとは、残りの文字の相対位置を変更せずに、元の文字列から一部の文字を削除することによって形成された新しい文字列を指します。

ダブルポインタ
2 つのポインター i と j を初期化し、それぞれ s と t の初期位置を指します。
各貪欲マッチングでは、マッチングが成功した場合、i と j は同時に右にシフトされ、s の次の位置と一致します。マッチングが失敗した場合、j は右にシフトされ、i は変更されません。 。

最後に 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

2 つの数値の合計

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

同型文字列

2 つの文字列 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

パスを簡略化する

まず、指定された文字列パスを / に従って複数の文字列のリストに分割し、名前として記録します。
名前に含まれる文字列は次のもののみです。

  • 空の文字列。たとえば、複数の連続した / が出現すると、空の文字列が分割されます。
  • ワンポイント。
  • 2点…
  • ディレクトリ名。

空の文字列とドットの場合、処理は必要ありません。

2 つのドットまたはディレクトリ名の場合、パス内の各ディレクトリ名を維持するためにスタックが必要です。 2 つの点に遭遇した場合、スタックが空でない限り、前のレベルに切り替え (スタックの最上位ディレクトリをポップ)、ディレクトリ名に遭遇した場合は、それをスタックに置きます。

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

最小スタック

プッシュ、ポップ、トップの操作をサポートし、最小の要素を一定時間で取得できるスタックを設計します。

補助スタック

  • スタックにプッシュする場合、要素はまず通常のスタックに置かれ、現在の補助スタックの先頭が要素と比較され、次に最小値がスタックの先頭に挿入されます。
  • スタックからポップするときは、両方が一緒にポップアップします。
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 を指定して、その値を計算して返す基本的な計算機を実装します。

ブラケット拡張 + スタック
数値と括弧のほかに、文字列にはプラス記号とマイナス記号の 2 つの演算子のみがあります。
したがって、式内のすべての括弧を展開した場合、結果として得られる新しい式では数値自体は変更されず、各数値の前の符号のみが変更されます。

スタック操作を維持する必要があります。スタックの最上位要素は、現在の位置にある各括弧のシンボルを記録します。
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 などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便