class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;	// 不包括右端点
        while (left <= right) {					// [1,1]存在（循环条件的选择考虑初始只有一个元素来判断）
            int mid = (left + right) / 2;
            if (nums[mid] > target)
                right = mid - 1;				// 子区间右闭
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();		// 包括右端点
        while (left < right) {					// [1,1)不存在
            int mid = (left + right) / 2;
            if (nums[mid] > target)
                right = mid;					// 子区间右开
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};

class Solution {
public:
    int removeElement(vector<int> &nums, int val) {
        int k = 0; // k为不等于val的元素个数
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                k++;
                nums[k - 1] = nums[i];
            }
        }
        return k;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int> &nums) {
        int i, j;
        for (i = 0, j = 1; j < nums.size(); j++) {
            // 双指针，i用于标识非重复顺序表的表尾，j是遍历数组的工作指针
            if (nums[i] != nums[j])
                nums[++i] = nums[j];
        }
        return i + 1;
    }
};

class Solution {
public:
    vector<int> sortedSquares(vector<int> &nums) {
        vector<int> result(nums.size());
        int i = 0, j = nums.size() - 1, k = nums.size() - 1;
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                result[k--] = nums[i] * nums[i];
                i++;
            } else {
                result[k--] = nums[j] * nums[j];
                j--;
            }
        }
        return result;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int> &nums) {
        int result = INT_MAX;                          // 最小子数组的长度
        int sum = 0;                                   // 滑动窗口元素值的总和
        for (int i = 0, j = 0; j < nums.size(); j++) { // i,j为滑动窗口的起始位置和终止位置
            sum += nums[j];
            while (sum >= target) {
                result = min(result, j - i + 1);
                sum -= nums[i++];
            }
        }
        return result == INT_MAX ? 0 : result;
    }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int k = 1;
        vector<vector<int>> matrix(n, vector<int>(n));
        for (int loop = 0; loop <= n / 2; loop++) { // loop表示循环次数
            if (n % 2 != 0 && loop == n / 2) {
                matrix[n / 2][n / 2] = k;
                break;
            }
            for (int i = loop; i < n - 1 - loop; i++) // →
                matrix[loop][i] = k++;
            for (int i = loop; i < n - 1 - loop; i++) // ↓
                matrix[i][n - 1 - loop] = k++;
            for (int i = n - 1 - loop; i > loop; i--) // ←
                matrix[n - 1 - loop][i] = k++;
            for (int i = n - 1 - loop; i > loop; i--) // ↑
                matrix[i][loop] = k++;
        }
        return matrix;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        int m = matrix.size(), n = matrix[0].size();          // m行n列
        int top = 0, bottom = m - 1, left = 0, right = n - 1; // 上下左右边界
        vector<int> result;
        while (true) {
            for (int i = left; i <= right; i++) // →
                result.push_back(matrix[top][i]);
            if (++top > bottom) break;
            for (int i = top; i <= bottom; i++) // ↓
                result.push_back(matrix[i][right]);
            if (left > --right) break;
            for (int i = right; i >= left; i--) // ←
                result.push_back(matrix[bottom][i]);
            if (top > --bottom) break;
            for (int i = bottom; i >= top; i--) // ↑
                result.push_back(matrix[i][left]);
            if (++left > right) break;
        }
        return result;
    }
};

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int top = 0, bottom = n - 1, left = 0, right = n - 1; // 上下左右边界
        int k = 1;
        vector<vector<int>> matrix(n, vector<int>(n));
        while (true) {
            for (int i = left; i <= right; i++) // →
                matrix[top][i] = k++;
            if (++top > bottom) break;
            for (int i = top; i <= bottom; i++) // ↓
                matrix[i][right] = k++;
            if (left > --right) break;
            for (int i = right; i >= left; i--) // ←
                matrix[bottom][i] = k++;
            if (top > --bottom) break;
            for (int i = bottom; i >= top; i--) // ↑
                matrix[i][left] = k++;
            if (++left > right) break;
        }
        return matrix;
    }
};

class Solution {
public:
    void intervalSum() {
        int n, a, b, sum = 0;
        cin >> n;                        // 输入数组长度
        vector<int> Array(n), prefix(n); // prefix为前缀和列表
        for (int i = 0; i < n; i++) {
            cin >> Array[i]; 			 // 输入数组元素
            sum += Array[i];
            prefix[i] = sum;
        }
        while (cin >> a >> b)            // 输入指定区间[a,b]
            cout << (a == 0 ? prefix[b] : prefix[b] - prefix[a - 1]) << endl; // 输出对应的区间和
    }
};

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + A[i - 1][j - 1];	//注意下标

class Solution {
public:
    int minGap() {
        int n, m, x, result = INT32_MAX;
        cin >> n >> m;                                    // n行m列
        vector<vector<int>> p(n + 1, vector<int>(m + 1)); // 二维前缀和列表
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                cin >> x;
                p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + x;
            }
        for (int i = 1; i < n; i++) // 横向划分
            result = min(result, abs(2 * p[i][m] - p[n][m]));
        for (int j = 1; j < m; j++) // 纵向划分
            result = min(result, abs(2 * p[n][j] - p[n][m]));
        return result;
    }
};

class Solution {
public:
    ListNode *removeElements(ListNode *head, int val) {
        ListNode *dummyHead = new ListNode(0, head); // 虚拟头结点
        ListNode *p = dummyHead;
        while (p->next != nullptr) {
            if (p->next->val == val) {
                ListNode *q = p->next;
                p->next = q->next;
                delete q;
            } else
                p = p->next;
        }
        return dummyHead->next;
    }
};

class MyLinkedList {
public:
    MyLinkedList() { // 初始化 MyLinkedList 对象
        this->head = new ListNode(0);
        this->size = 0;
    }

    int get(int index) { // 获取链表中下标为 index 的节点的值
        if (index < 0 || index >= this->size)
            return -1;
        ListNode *p = this->head;
        for (int i = 0; i <= index; i++)
            if (p->next != nullptr)
                p = p->next;
        return p->val;
    }

    void addAtHead(int val) { // 将一个值为 val 的节点插入到链表中第一个元素之前
        ListNode *p = new ListNode(val, this->head->next);
        this->head->next = p;
        this->size++;
    }

    void addAtTail(int val) { // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
        ListNode *p = this->head, *q = new ListNode(val);
        while (p->next != nullptr)
            p = p->next;
        p->next = q;
        this->size++;
    }

    void addAtIndex(int index, int val) { // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
        if (index < 0 || index > this->size)
            return;
        ListNode *p = this->head;
        for (int i = 0; i < index; i++)
            if (p->next != nullptr)
                p = p->next;
        ListNode *q = new ListNode(val, p->next);
        p->next = q;
        this->size++;
    }

    void deleteAtIndex(int index) { // 删除链表中下标为 index 的节点
        if (index < 0 || index >= this->size)
            return;
        ListNode *p = this->head;
        for (int i = 0; i < index; i++)
            if (p->next != nullptr)
                p = p->next;
        ListNode *q = p->next;
        p->next = q->next;
        delete q;
        this->size--;
    }

private:
    ListNode *head; // 头结点
    int size;       // 链表长度
};

class MyLinkedList {
public:
    MyLinkedList() { // 初始化 MyLinkedList 对象
        this->head = new DListNode(0);
        this->size = 0;
    }

    int get(int index) { // 获取链表中下标为 index 的节点的值
        if (index < 0 || index >= this->size)
            return -1;
        DListNode *p = this->head;
        for (int i = 0; i <= index; i++)
            if (p->next != nullptr)
                p = p->next;
        return p->val;
    }

    void addAtHead(int val) { // 将一个值为 val 的节点插入到链表中第一个元素之前
        DListNode *p = new DListNode(val, this->head, this->head->next);
        if (this->head->next != nullptr)
            this->head->next->prev = p;
        this->head->next = p;
        this->size++;
    }

    void addAtTail(int val) { // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
        DListNode *p = this->head, *q = new DListNode(val);
        while (p->next != nullptr)
            p = p->next;
        p->next = q;
        q->prev = p;
        this->size++;
    }

    void addAtIndex(int index, int val) { // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
        if (index < 0 || index > this->size)
            return;
        DListNode *p = this->head;
        for (int i = 0; i < index; i++)
            if (p->next != nullptr)
                p = p->next;
        DListNode *q = new DListNode(val, p, p->next);
        if (p->next != nullptr)
            p->next->prev = q;
        p->next = q;
        this->size++;
    }

    void deleteAtIndex(int index) { // 删除链表中下标为 index 的节点
        if (index < 0 || index >= this->size)
            return;
        DListNode *p = this->head;
        for (int i = 0; i < index; i++)
            if (p->next != nullptr)
                p = p->next;
        DListNode *q = p->next;
        if (q->next != nullptr)
            q->next->prev = p;
        p->next = q->next;
        delete q;
        this->size--;
    }

private:
    DListNode *head; // 头结点
    int size;        // 链表长度
};

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode *dummyHead = new ListNode(0);
        ListNode *p = head, *r;
        while (p != nullptr) {
            r = p->next; // 暂存p的后继结点
            p->next = dummyHead->next;
            dummyHead->next = p; // 将p插入头结点之后
            p = r;
        }
        return dummyHead->next;
    }
};

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode *pre = nullptr, *cur = head;
        while (cur != nullptr) {
            ListNode *temp = cur->next; // 暂存cur的后继结点
            cur->next = pre;            // 改变指针朝向
            pre = cur;
            cur = temp; // pre和cur依次右移
        }
        return pre;
    }
};

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummyHead = new ListNode(0, head);
        ListNode *p = dummyHead;
        while (p->next != nullptr && p->next->next != nullptr) {
            ListNode *q = p->next->next;
            p->next->next = q->next;
            q->next = p->next;
            p->next = q;
            p = q->next;
        }
        return dummyHead->next;
    }
};

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummyHead = new ListNode(0, head);
        ListNode *p = dummyHead, *q = dummyHead; // 快慢双指针
        while (n--)
            p = p->next; // p先右移n次
        while (p->next != nullptr) {
            p = p->next;
            q = q->next; // p和q同步右移,结束后q指向待删除结点的前驱结点
        }
        ListNode *r = q->next;
        q->next = r->next;
        delete r;
        return dummyHead->next;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0; // headA和headB的长度
        ListNode *p, *q;
        for (p = headA; p != nullptr; p = p->next)
            lenA++;
        for (q = headB; q != nullptr; q = q->next)
            lenB++;
        p = headA;
        q = headB;
        if (lenA > lenB)
            for (int i = 0; i < lenA - lenB; i++)
                p = p->next;
        else if (lenA < lenB)
            for (int j = 0; j < lenB - lenA; j++)
                q = q->next;
        while (p != q) {
            p = p->next;
            q = q->next;
        }
        return p;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head; // 快慢双指针
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        if (fast == nullptr || fast->next == nullptr)
            return nullptr;
        ListNode *p = head, *q = fast; // 分别指向表头和相遇点
        while (p != q) {
            p = p->next;
            q = q->next;
        }
        return p; // 返回入口点
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0}; // 记录s中每个字符出现的次数
        for (int i = 0; i < s.size(); i++)
            record[s[i] - 'a']++;
        for (int i = 0; i < t.size(); i++)
            record[t[i] - 'a']--;
        for (int i = 0; i < 26; i++)
            if (record[i] != 0)
                return false;
        return true;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        unordered_set<int> result, s(nums1.begin(), nums1.end()); // vector转unordered_set
        for (int x : nums2)
            if (s.find(x) != s.end())
                result.insert(x);
        return vector<int>(result.begin(), result.end()); // unordered_set转vector
    }
};

class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        vector<bool> record(1001, false);
        unordered_set<int> result;
        for (int x : nums1)
            record[x] = true;
        for (int y : nums2)
            if (record[y] == true)
                result.insert(y);
        return vector<int>(result.begin(), result.end());
    }
};

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> s;
        while (n != 1) {
            int sum = 0;
            while (n > 0) { // 求和数
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            if (s.find(sum) != s.end()) // 和数重复出现,一定无限循环
                return false;
            s.insert(sum);
            n = sum;
        }
        return true;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> map; // key:数组元素 value:数组元素下标
        for (int i = 0; i < nums.size(); i++) {
            auto it = map.find(target - nums[i]);
            if (it != map.end())
                return {it->second, i};
            map.insert({nums[i], i});
        }
        return {};
    }
};

class Solution {
public:
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4) {
        unordered_map<int, int> map; // key:a+b的值 value:a+b的值出现的次数
        for (int a : nums1)
            for (int b : nums2)
                map[a + b]++;
        int result = 0;
        for (int c : nums3)
            for (int d : nums4)
                if (map.find(-c - d) != map.end())
                    result += map[-c - d];
        return result;
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> record(26, 0); // 记录magazine中各字符出现的次数
        for (char ch : magazine)
            record[ch - 'a']++;
        for (char ch : ransomNote)
            if (--record[ch - 'a'] < 0)
                return false;
        return true;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) // 排序后最小元素大于0, 一定不存在和为0的三元组（剪枝）
                return result;
            if (i > 0 && nums[i] == nums[i - 1]) // 对nums[i]去重
                continue;
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0)
                    left++;
                else if (sum > 0)
                    right--;
                else {
                    result.push_back({nums[i], nums[left], nums[right]});
                    // 找到一个三元组后, 对nums[left]和nums[right]去重
                    while (left < right && nums[left] == nums[left + 1])
                        left++;
                    while (left < right && nums[right - 1] == nums[right])
                        right--;
                    // 找到答案时, 双指针同时收缩
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int a = 0; a < nums.size(); a++) {
            if (nums[a] > target && nums[a] >= 0) // 剪枝
                break;
            if (a > 0 && nums[a] == nums[a - 1]) // 对nums[a]去重
                continue;
            for (int b = a + 1; b < nums.size(); b++) {
                if (nums[a] + nums[b] > target && nums[a] + nums[b] >= 0) // 二级剪枝
                    break;
                if (b > a + 1 && nums[b] == nums[b - 1]) // 对nums[b]去重
                    continue;
                int c = b + 1, d = nums.size() - 1;
                while (c < d) {
                    // 使用long类型(8位)防止溢出
                    long sum = (long)nums[a] + nums[b] + nums[c] + nums[d]; 
                    if (sum < target)
                        c++;
                    else if (sum > target)
                        d--;
                    else {
                        result.push_back({nums[a], nums[b], nums[c], nums[d]});
                        while (c < d && nums[c] == nums[c + 1]) // 对nums[c]去重
                            c++;
                        while (c < d && nums[d - 1] == nums[d]) // 对nums[d]去重
                            d--;
                        c++;
                        d--;
                    }
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    void reverseString(vector<char> &s) {
        for (int i = 0; i < s.size() / 2; i++)
            swap(s[i], s[s.size() - 1 - i]);
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k)
            if (s.size() - i < k) // 剩余字符少于k个
                reverse(s.begin() + i, s.end());
            else
                reverse(s.begin() + i, s.begin() + i + k); // 反转s[i..i+k-1]
        return s;
    }
};

class Solution {
public:
    string replaceDigits(string s) {
        int i = s.size() - 1, count = 0; // 统计数字字符个数
        for (char ch : s)
            if (ch >= '0' && ch <= '9')
                count++;
        s.resize(s.size() + count * 5); // 数组扩容
        int j = s.size() - 1;
        for (; i >= 0; i--)
            if (s[i] >= 'a' && s[i] <= 'z')
                s[j--] = s[i];
            else {
                s[j--] = 'r';
                s[j--] = 'e';
                s[j--] = 'b';
                s[j--] = 'm';
                s[j--] = 'u';
                s[j--] = 'n';
            }
        return s;
    }
};

class Solution {
public:
    string replaceDigits(string s) {
        for (int i = 0; i < s.size(); i++)
            if (s[i] >= '0' && s[i] <= '9')
                s.replace(i, 1, "number"); // 从位置i开始，替换1个字符为"number"
        return s;
    }
};

class Solution {
public:
    string reverseWords(string s) {
        int k = 0;                         // 用k记录s中应保留字符的个数
        for (int i = 0; i < s.size(); i++) // 去除冗余空格
            if (s[i] != ' ') {
                if (k != 0)
                    s[k++] = ' '; // 对于非首词前面留一空格
                while (i < s.size() && s[i] != ' ')
                    s[k++] = s[i++]; // 将应保留的字符移动至下标k的位置
            }
        s.resize(k);                 // 调整字符串长度
        reverse(s.begin(), s.end()); // 反转字符串
        for (int i = 0, start = 0; i <= s.size(); i++)
            if (i == s.size() || s[i] == ' ') {
                reverse(s.begin() + start, s.begin() + i); // 反转每个单词
                start = i + 1;
            }
        return s;
    }
};

class Solution {
public:
    string rightRotate(string s, int k) {
        reverse(s.begin(), s.end());       // 反转 s[0..n-1]
        reverse(s.begin(), s.begin() + k); // 反转 s[0..k-1]
        reverse(s.begin() + k, s.end());   // 反转 s[k..n-1]
        return s;
    }
};

class Solution {
public:
    int strStr(string s, string t) {
        // 1.计算next数组
        vector<int> next(t.size(), -1);
        for (int i = 0, j = -1; i < t.size() - 1;) {
            if (j == -1 || t[i] == t[j])
                next[++i] = ++j; // 若t[i]==t[j],则next[j+1]=next[j]+1
            else
                j = next[j]; // 否则令j=next[j],循环继续
        }
        // 2.使用KMP算法匹配
        for (int i = 0, j = 0; i < s.size();) {
            if (j == -1 || s[i] == t[j]) {
                i++;
                j++;
                if (j == t.size())
                    return i - t.size(); // 匹配成功
            } else
                j = next[j]; // 模式串向右滑动
        }
        return -1;
    }
};

class Solution {
public:
    int strStr(string s, string t) {
        // 1.计算nextval数组
        vector<int> nextval(t.size(), -1);
        for (int i = 0, j = -1; i < t.size() - 1;) {
            if (j == -1 || t[i] == t[j]) {
                if (t[++i] == t[++j])
                    nextval[i] = nextval[j];
                else
                    nextval[i] = j;
            } else
                j = nextval[j];
        }
        // 2.使用KMP算法匹配
        for (int i = 0, j = 0; i < s.size();) {
            if (j == -1 || s[i] == t[j]) {
                i++;
                j++;
                if (j == t.size())
                    return i - t.size(); // 匹配成功
            } else
                j = nextval[j]; // 模式串向右滑动
        }
        return -1;
    }
};

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin());
        t.erase(t.end() - 1);             // 去除首尾字符
        return t.find(s) != string::npos; // 找到则返回true
    }
};

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        // 1.计算next数组
        string t = s + '*'; // 添加一个任意字符
        vector<int> next(t.size(), -1);
        for (int i = 0, j = -1; i < t.size() - 1;) {
            if (j == -1 || t[i] == t[j])
                next[++i] = ++j;
            else
                j = next[j];
        }
        // 2. 求最小重复子串
        int len = next[s.size()]; // 最长公共前后缀的长度
        return len != 0 && s.size() % (s.size() - len) == 0;
    }
};

class MyQueue {
public:
    MyQueue() {}

    void push(int x) { // 队尾插入
        sIn.push(x);
    }

    int pop() { // 队头删除
        if (sOut.empty())
            while (!sIn.empty()) { // 先将输入栈中的所有元素移入输出栈中
                sOut.push(sIn.top());
                sIn.pop();
            }
        int x = sOut.top();
        sOut.pop();
        return x;
    }

    int peek() { // 返回队头元素
        if (sOut.empty())
            while (!sIn.empty()) {
                sOut.push(sIn.top());
                sIn.pop();
            }
        return sOut.top();
    }

    bool empty() { // 判空
        return sIn.empty() && sOut.empty();
    }

private:
    stack<int> sIn, sOut; // 输入栈和输出栈
};

class MyStack {
public:
    MyStack() {}

    void push(int x) { // 入栈
        q1.push(x);
    }

    int pop() { // 出栈
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        int x = q1.front();
        q1.pop();
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        return x;
    }

    int top() { // 获取栈顶元素(实际上就是q1.back())
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        int x = q1.front();
        q2.push(q1.front());
        q1.pop();
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        return x;
    }

    bool empty() { // 判空
        return q1.empty();
    }

private:
    queue<int> q1, q2;
};

class MyStack {
public:
    MyStack() {}

    void push(int x) { // 入栈
        q.push(x);
    }

    int pop() { // 出栈
        int size = q.size();
        while (--size) {
            q.push(q.front());
            q.pop();
        }
        int x = q.front();
        q.pop();
        return x;
    }

    int top() { // 获取栈顶元素
        int size = q.size();
        while (--size) {
            q.push(q.front());
            q.pop();
        }
        int x = q.front();
        q.push(q.front());
        q.pop();
        return x;
    }

    bool empty() { // 判空
        return q.empty();
    }

private:
    queue<int> q;
};

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        unordered_map<char, char> map = {{')', '('}, {']', '['}, {'}', '{'}};
        for (char ch : s) {
            if (map.find(ch) == map.end()) // ch为左括号,入栈
                stk.push(ch);
            else if (!stk.empty() && map[ch] == stk.top()) // ch为右括号且与栈顶匹配,栈顶出栈
                stk.pop();
            else
                return false;
        }
        return stk.empty();
    }
};

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stk;
        for (char ch : s) {
            if (!stk.empty() && stk.top() == ch)
                stk.pop();
            else
                stk.push(ch);
        }
        string result;
        while (!stk.empty()) {
            result = stk.top() + result;
            stk.pop();
        }
        return result;
    }
};

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> s; // 存放操作数
        for (string op : tokens) {
            if (op == "+" || op == "-" || op == "*" || op == "/") {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                if (op == "+")
                    s.push(x + y);
                if (op == "-")
                    s.push(x - y);
                if (op == "*")
                    s.push(x * y);
                if (op == "/")
                    s.push(x / y);
            } else
                s.push(stoi(op)); // string转int
        }
        return s.top();
    }
};