Κοινή χρήση τεχνολογίας

한어Русский язык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 δεν θα αλλάξει .

Τέλος, το 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, εφαρμόστε μια βασική αριθμομηχανή για να υπολογίσετε και να επιστρέψετε την τιμή της.

Επέκταση βραχίονα + στοίβα
Εκτός από τους αριθμούς και τις παρενθέσεις, οι συμβολοσειρές έχουν μόνο δύο τελεστές: το σύμβολο συν και το σύμβολο μείον.
Επομένως, εάν επεκτείνετε όλες τις παρενθέσεις σε μια παράσταση, οι ίδιοι οι αριθμοί δεν θα αλλάξουν στη νέα παράσταση που προκύπτει, αλλά θα αλλάξει μόνο το σύμβολο μπροστά από κάθε αριθμό.

Πρέπει να διατηρηθεί ένα stack ops, στο οποίο το επάνω στοιχείο της στοίβας καταγράφει το σύμβολο κάθε αγκύλης στην τρέχουσα θέση.
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