2024-10-18

复习

1. 链表

141. 环形链表 - 力扣（LeetCode）
快慢指针法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            head = head->next;
            if (fast == head) return true;
        }
        return false;
    }
};

142. 环形链表 II - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                while (slow != head) {
                    slow = slow->next;
                    head = head->next;
                }
                return head;
            }
        }
        return nullptr;
    }
};

2. 栈

20. 有效的括号 - 力扣（LeetCode）

class Solution {
public:
    bool isValid(string str) {
        for (char ch : str) {
            if (ch == '(' || ch == '[' || ch == '{') s.push(ch);
            else {
                if (s.empty()) return false;
                if (ch == ')' && s.top() != '(') return false;
                if (ch == ']' && s.top() != '[') return false;
                if (ch == '}' && s.top() != '{') return false;
                s.pop();
            }
        }
        return s.empty();
    }

private:
    stack<char> s;
};

155. 最小栈 - 力扣（LeetCode）

class MinStack {
public:
    MinStack() {}
    void push(int val) {
        s.push(val);
        if (!preMin.empty()) val = min(val, preMin.top());
        preMin.push(val);
    }
    void pop() {
        s.pop();
        preMin.pop();
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return preMin.top();
    }
private:
    stack<int> s, preMin;
};

150. 逆波兰表达式求值 - 力扣（LeetCode）

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        for (string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int y = s.top(); s.pop();
                int x = s.top(); s.pop();
                int z = calc(x, y, token);
                s.push(z);
            }
            else s.push(stoi(token));
        }
        return s.top();
    }
private:
    stack<int> s;
    int calc(int x, int y, string token) {
        if (token == "+") return x + y;
        if (token == "-") return x - y;
        if (token == "*") return x * y;
        if (token == "/") return x / y;
        return 0;
    }
};

224. 基本计算器 - 力扣（LeetCode）

class Solution {
public:
    int calculate(string s) {
        s += " ";
        vector<string> tokens;
        string number = "";
        bool needsZero = true;
        for (char ch : s) {
            if (ch >= '0' && ch <= '9') {
                number += ch;
                needsZero = false;
                continue;
            }
            else if (!number.empty()) {
                tokens.push_back(number);
                number = "";
            }
            if (ch == ' ') continue;
            if (ch == '(') {
                ops.push(ch);
                needsZero = true;
                continue;
            }
            if (ch == ')') {
                while (ops.top() != '(') {
                    tokens.push_back(string(1, ops.top()));
                    ops.pop();
                }
                ops.pop();
                needsZero = false;
                continue;
            }
            if ((ch == '+' || ch == '-') && needsZero)
                tokens.push_back("0"); // 在(或者操作符后加个0，用于区分后一个是加减还是正负
            int currRank = getRank(ch);
            while (!ops.empty() && getRank(ops.top()) >= currRank) {
                tokens.push_back(string(1, ops.top()));
                ops.pop();
            }
            ops.push(ch);
            needsZero = true;
        }
        while (!ops.empty()) {
            tokens.push_back(string(1, ops.top()));
            ops.pop();
        }
        return evalRPN(tokens);
    }

private:
    stack<char> ops;
    
    int getRank(char ch) {
        if (ch == '*' || ch == '/') return 2;
        if (ch == '+' || ch == '-') return 1;
        return 0;
    }

    stack<int> s;

    int evalRPN(vector<string>& tokens) {
        for (string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || 
            token == "/") {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                int z = calc(x, y, token);
                s.push(z);
            }
            else 
                s.push(stoi(token));
        }
        return s.top();
    }

    int calc(int x, int y, string& op) {
        if (op == "+") return x + y;
        if (op == "-") return x - y;
        if (op == "*") return x * y;
        if (op == "/") return x / y;
        return 0;
    }
};