• LeetCode题解
  • chap-7: 栈、队列
    • • 1、最小栈【设计】
      • 2、比较含退格的字符串
      • 3、设计一个支持增量操作的栈 【×】
      • 4、设计循环队列
      • 5、设计循环双端队列
      • 6、验证栈序列
      • 7、删除字符串中的所有相邻重复项
      • 8、删除字符串中的所有相邻重复项 II
    • section7-1: 栈、队列重构
      • 1、用队列实现栈
      • 2、用栈实现队列
    • section7-2: 单调栈
      • 1、接雨水
      • 2、柱状图中最大的矩形
      • 3、最大矩形
      • 4、下一个更大元素 I
      • 5、下一个更大元素 II【破环成链】
      • 6、每日温度
    • section7-3: 单调队列
      • 1、滑动窗口最大值
    • section7-4:逆波兰表达式/计算器
      • 1、逆波兰表达式求值
      • 2、基本计算器【×】
      • 3、基本计算器 II
    • section7-5:括号序列
      • 1、有效的括号
      • 2、最长有效括号
  • chap-8:双指针
    • section8.1 同向双指针
      • 1、外观数列【模拟】
      • 2、最后一个单词的长度
      • 3、删除有序数组中的重复项
      • 4、删除有序数组中的重复项 II
      • 5、移除元素
      • 6、颜色分类
      • 7、合并两个有序数组
      • 8、移动零
      • 9、判断子序列
      • 10、字符串中的单词数
      • 11、压缩字符串
      • 12、最大连续 1 的个数
      • 13、划分字母区间[×]
      • 14、按奇偶排序数组 II
      • 15、区间列表的交集
    • section8.2 滑动窗口
      • 1、无重复字符的最长子串
      • 2、最小覆盖子串
      • 3、长度最小的子数组
      • 4、替换后的最长重复字符
      • 5、找到字符串中所有字母异位词
      • 6、数组中的 k-diff 数对
      • 7、字符串的排列
      • 8、最大连续1的个数 III
      • 9、删掉一个元素以后全为 1 的最长子数组
      • 10、删除子数组的最大得分
    • section8.3 逆向双指针
      • 1、最长回文子串
      • 2、盛最多水的容器
      • 3、三数之和
      • 4、最接近的三数之和
      • 5、四数之和
      • 6、验证回文串
      • 7、两数之和 II - 输入有序数组
      • 8、反转字符串
      • 9、反转字符串中的元音字母
  • chap-9:哈希表
    • • 1、字母异位词分组
      • 2、最长连续序列
      • 3、存在重复元素
      • 4、存在重复元素 II
      • 5、存在重复元素 III
      • 6、猜数字游戏
      • 7、两个数组的交集
      • 8、两个数组的交集 II
      • 9、O(1) 时间插入、删除和获取随机元素
      • 10、O(1) 时间插入、删除和获取随机元素 - 允许重复
      • 11、赎金信
      • 12、字符串中的第一个唯一字符
      • 13、最长回文串
      • 14、路径总和 III
      • 15、四数相加 II
      • 16、和为 K 的子数组【×】
      • 17、LRU 缓存机制【×】
      • 18、LFU 缓存
      • 19、连续的子数组和【×】前缀和+哈希表
      • 20、连续数组【×】
      • 21、数组中的 k-diff 数对
      • 22、砖墙【×】
      • 23、分糖果
      • 24、设计哈希映射【×】
      • 25、设计哈希集合
      • 26、数的平方等于两数乘积的方法数
      • 27、警告一小时内使用相同员工卡大于等于三次的人
      • 28、字符频次唯一的最小删除次数
      • 29、K 和数对的最大数目
      • 30、同构字符串【双射】
      • 31、单词规律

LeetCode题解

chap-7: 栈、队列

1、最小栈【设计】

class MinStack {
public:
    stack a,b;
    /** initialize your data structure here. */
    MinStack() {
    }    
    void push(int val) {
        a.push(val);
        if(b.empty() || val <= b.top()) b.push(val);
    }    
    void pop() {
        auto t = a.top();
        if(b.size() && b.top() == t) b.pop();
        a.pop();
    }    
    int top() {
        return a.top();
    }    
    int getMin() {
        return b.top();
    }
};

2、比较含退格的字符串

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stacka,b;
        for(auto c:s){
            if(c == '#'){
                if(a.empty()) continue;
                else a.pop();
            }else a.push(c);
        }
        for(auto c:t){
            if(c == '#'){
                if(b.empty()) continue;
                else b.pop();
            }else b.push(c);
        }
        if(a.size() != b.size()) return false;
        while(a.size()){
            if(a.top() != b.top()) return false;
            a.pop(), b.pop();
        }
        return true;
    }
};

// 进一步地
class Solution {
public:
    string get(string& s) {
        string res;
        for (auto c: s)
            if (c == '#') {
                if (res.size()) res.pop_back();
            } else {
                res += c;
            }
        return res;
    }

    bool backspaceCompare(string s, string t) {
        return get(s) == get(t);
    }
};

3、设计一个支持增量操作的栈 【×】

// inc部分O(k)-O(1)
class CustomStack {
public:
    vecto1r inc_arr;
    stack st;
    int m_size,cnt = 0;
    CustomStack(int maxSize) {
        m_size = maxSize;
        inc_arr.resize(maxSize + 1,0);
    }

    void push(int x) {
        if(cnt < m_size){
            cnt ++;
            st.push(x);
        }
    }

    int pop() {
        if(cnt == 0)
            return -1;
        int p = st.top();
        st.pop();
        if(inc_arr[cnt] != 0){
            inc_arr[cnt - 1] += inc_arr[cnt];
            p += inc_arr[cnt];
            inc_arr[cnt] = 0;
        }
        cnt --;
        return p;
    }

    void increment(int k, int val) {
        inc_arr[min(k,cnt)] += val;
    }
};

4、设计循环队列

class MyCircularQueue {
public:
    int hh = 0, tt = 0;
    vector q;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        q.resize(k + 1);
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull()) return false;
        q[tt ++ ] = value;
        if (tt == q.size()) tt = 0;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) return false;
        hh ++ ;
        if (hh == q.size()) hh = 0;
        return true;
    }

    /** Get the front item from the queue. */
    int Front() {
        if (isEmpty()) return -1;
        return q[hh];
    }

    /** Get the last item from the queue. */
    int Rear() {
        if (isEmpty()) return -1;
        int t = tt - 1;
        if (t < 0) t += q.size();
        return q[t];
    }

    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return hh == tt;
    }

    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return (tt + 1) % q.size() == hh;
    }
};

5、设计循环双端队列

class MyCircularDeque {
public:
    int hh = 0, tt = 0;
    vector q;

    /** Initialize your data structure here. Set the size of the deque to be k. */
    MyCircularDeque(int k) {
        q.resize(k + 1);
    }

    int get(int x) {
        return (x + q.size()) % q.size();
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if (isFull()) return false;
        hh = get(hh - 1);
        q[hh] = value;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if (isFull()) return false;
        q[tt ++ ] = value;
        tt = get(tt);
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
        if (isEmpty()) return false;
        hh = get(hh + 1);
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
        if (isEmpty()) return false;
        tt = get(tt - 1);
        return true;
    }

    /** Get the front item from the deque. */
    int getFront() {
        if (isEmpty()) return -1;
        return q[hh];
    }

    /** Get the last item from the deque. */
    int getRear() {
        if (isEmpty()) return -1;
        return q[get(tt - 1)];
    }

    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        return hh == tt;
    }

    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        return get(hh - 1) == tt;
    }
};

6、验证栈序列

class Solution {
public:
    bool validateStackSequences(vector& pushed, vector& popped) {
        stack s; int j = 0;
        for(int i = 0;i

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;
        for(auto &c:s){
            if(stk.size() && stk.back() == c) stk.pop_back();
            else stk.push_back(c);
        }        
        return stk;
    }
};

class Solution {
public:
    string removeDuplicates(string s, int k) {
        string stk("#");
        stack cnt;
        cnt.push(1);
        for(int i = 0 ; i < s.size() ; i++) {
            if(s[i] == stk.back()) cnt.push(cnt.top()+1);
            else cnt.push(1);

            stk += s[i];

            if(cnt.top() >= k) {
                for(int j = 0 ; j < k ; j++) {
                    stk.pop_back();
                    cnt.pop();
                }
            }
        }
        return stk.substr(1);
    }
};

class MyStack {
public:
    /** Initialize your data structure here. */
    queue a,b;
    MyStack() {

    }
    
    /** Push element x onto stack. */
    void push(int x) {
        a.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        while(a.size() > 1) b.push(a.front()), a.pop();
        int t = a.front(); a.pop();
        while(b.size()) a.push(b.front()), b.pop();
        return t;
    }
    
    /** Get the top element. */
    int top() {
        while(a.size() > 1) b.push(a.front()), a.pop();
        int t = a.front(); b.push(a.front()), a.pop();
        while(b.size()) a.push(b.front()), b.pop();
        return t;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return a.empty();
    }
};

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack a,b;
    MyQueue() {

    }
    
    void in2out(){
        while(a.size()) b.push(a.top()), a.pop();
    }

    /** Push element x to the back of queue. */
    void push(int x) {
        a.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(b.empty()) in2out();
        int t = b.top(); b.pop();
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        if(b.empty()) in2out();
        return b.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return a.empty() &&　b.empty();
    }
};

class Solution {
public:
    int trap(vector& h) {
        stack help;
        int ans = 0;
        for(int i=0;i top()
                    auto t = help.top(); help.pop();
                    while(help.size() && h[t] <= h[i]){
                        auto q = help.top(); 
                        if(h[q] <= h[i]) help.pop();
                        ans += (min(h[q],h[i]) - h[t])*(i-q-1);
                        t = q;
                    }
                    help.push(i);
                }
            }
        }
        return ans;
    }
};

// 逻辑优化
class Solution {
public:
    int trap(vector& h) {
        stack help;
        int ans = 0;
        for(int i=0;i

class Solution {
public:
    int largestRectangleArea(vector& h) {
        int ans = 0; h.push_back(-1);
        stack s;
        for(int i=0;i

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if(matrix.size() <= 0) return 0;
        int ans = 0, m = matrix.size(), n = matrix[0].size();
        vectorhelp = vector(n+1,0);
        for(int i=0;i s;
            for(int j=0;j<=n;j++){
                while(s.size() && help[j] < help[s.top()]){
                    auto t = s.top(); s.pop();
                    if(s.empty()) ans = max(ans,help[t]*j);
                    else ans = max(ans,help[t]*(j-s.top()-1));
                }
                s.push(j);
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector nextGreaterElement(vector& nums1, vector& nums2) {
        unordered_maphash;
        stack s;
        for(int i=nums2.size()-1;~i;i--){
            if(s.empty()) hash[nums2[i]] = -1, s.push(nums2[i]);
            else{
                while(s.size() && nums2[i] > s.top()){
                    s.pop();
                    if(s.empty()) {
                        hash[nums2[i]] = -1, s.push(nums2[i]);
                        break;
                    }
                }
                if(nums2[i] < s.top()) hash[nums2[i]] = s.top(), s.push(nums2[i]);
            }                
        }
        vector ans;
        for(auto &num:nums1) ans.push_back(hash[num]);
        return ans;
    }
};

class Solution {
public:
    vector nextGreaterElements(vector& nums) {
        int n = nums.size();
        vector ans(n,0);
        nums.insert(nums.end(),nums.begin(),nums.end());
        stack s;
        for(int i = 2*n-1;~i;i--){
            int x = nums[i];
            while(s.size() && x >= s.top()) s.pop();
            if(i

class Solution {
public:
    vector dailyTemperatures(vector& t) {
        stack s; int n = t.size();
        vector ans(n);
        for(int i=n-1;~i;i--){
            while(s.size() && t[i] >= t[s.top()]) s.pop();
            if(s.empty()){
                ans[i] = 0;
            }else ans[i] = s.top()-i;
            s.push(i);
        }
        return ans;
    }
};

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        deque q;
        vector ans;
        for(int i = 0;i q.front()) q.pop_front();            
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if(i>=k-1) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

class Solution {
public:
    int evalRPN(vector& tokens) {
        stack s;
        for(auto &t:tokens){
            if(t == "+" || t == "-" || t == "*" || t == "/"){
                int a = s.top(); s.pop();
                int b = s.top(); s.pop();
                if(t == "+") s.push(b+a);
                if(t == "-") s.push(b-a);
                if(t == "*") s.push(b*a);
                if(t == "/") s.push(b/a);
            }else{
                s.push(stoi(t));
            }
        }
        return s.top();
    }
};

class Solution {
public:
    void eval(stack& num,stack& op)
    {
        auto b=num.top();num.pop();
        auto a=num.top();num.pop();
        auto c=op.top();op.pop();
        if(c=='+') num.push(a+b);
        else num.push(a-b);
    }

    int calculate(string rs) {
        string s;
        for(auto c:rs)
            if(c!=' ')
                s+=c;

        stack num;
        stack op;
        for(int i=0;i

class Solution {
public:
    int calculate(string s) {
        char pre = '+';
        vector help;
        for(int i = 0;i

class Solution {
public:
    bool isValid(string s) {
        stack stk;
        for(auto c:s){
            if(c == '(' || c == '[' || c == '{') stk.push(c);
            else{
                if(stk.size()){
                    auto t = stk.top();
                    if(c-t==')'-'(' || c-t==']'-'[' || c-t=='}'-'{')
                        stk.pop();
                    else return false;                   
                } else return false;                    
            }
        }
        return stk.empty();
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        stack stk; // 记录左括号位置
        int start = 0, ans = 0;
        for(int i = 0;i

class Solution {
public:
    string countAndSay(int n) {
        string ans = "1";
        while(--n){
            string temp;
            for(int i = 0;i

class Solution {
public:
    int lengthOfLastWord(string s) {
        int n = s.length() - 1;
        while(n >=0 && s[n] == ' ') n--;
        int i = n;
        while(~i && s[i] != ' ') i--;
        return i>=0 ? n-i:n+1;
    }
};

class Solution {
public:
    int removeDuplicates(vector& nums) {
        if(nums.empty()) return 0;
        int j=0;
        for(int i=j+1;i

class Solution {
public:
    int removeDuplicates(vector& nums) {
        if(nums.empty()) return 0;
        int j=0;
        for(int i = j+1;i

class Solution {
public:
    int removeElement(vector& nums, int val) {
        if(nums.empty()) return 0;
        int len = 0;
        for(int i=len;i

class Solution {
public:
    void sortColors(vector& nums) {
        int l=-1,r=nums.size();
        for(int i=0;i

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        int i = m-1, j = n-1, k = m+n-1;
        while(~i && ~j){
            if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
        while(~i) nums1[k--] = nums1[i--];
        while(~j) nums1[k--] = nums2[j--];
    }
};

class Solution {
public:
    void moveZeroes(vector& nums) {
        int i = 0;
        while(i

class Solution { // 双指针
public:
    bool isSubsequence(string t, string s) {
        int i = 0, j = 0;
        while(i> f(m+1, vector(26,0));
        for(int i = 0;i<26;i++) f[m][i] = m;
        for(int i = m-1;i>=0;i--){
            for(int j = 0;j<26;j++){
                if(j == t[i]-'a') f[i][j] = i;
                else f[i][j] = f[i+1][j];
            }
        }
        int idx = 0; // f起始处开始搜
        for (int i = 0; i < n; i++) {
            if (f[idx][s[i] - 'a'] == m) {
                return false;
            }
            idx = f[idx][s[i] - 'a'] + 1; // 下一个位置
        }
        return true;
    }
};

// 库函数
class Solution {
public:
    int countSegments(string s) {
        stringstream sin(s);
        int ans = 0; string c;
        while(sin>>c) ans++;
        return ans;
    }
};

// 双指针
class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        for(int i = 0;i

class Solution {
public:
    int compress(vector& chars) {
        int ans = 0;
        for(int i = 0;i 1) {
                i = j-1;
                string s = to_string(t);                
                for(j=0;j

class Solution {
public:
    int findMaxConsecutiveOnes(vector& nums) {
        int ans = 0;
        for(int i=0;i

class Solution {
public:
    vector partitionLabels(string s) {
        unordered_map hash;
        int i = 0,start = 0,end = 0;
        vector ans;
        for(;i

class Solution {
public:
    vector sortArrayByParityII(vector& nums) {
        int slow = 0, fast = slow+1;
        while(true){
            while(slow < nums.size() && nums[slow]%2 == 0) slow+=2;
            while(fast < nums.size() && nums[fast]%2) fast+=2;
            if(fast >= nums.size()) break;
            else{
                swap(nums[slow],nums[fast]);
            }
        }
        return nums;
    }
};

class Solution {
public:
    vector> intervalIntersection(vector>& f, vector>& s) {
        vector> ans;
        for(int i = 0,j = 0;i= s[j][0])
                ans.push_back({max(f[i][0],s[j][0]),min(f[i][1],s[j][1])});
            if(f[i][1] <= s[j][1]) i++;
            else j++;
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        unordered_map hash;
        for(int last = 0, cur = 0;cur < s.size();cur++){
            hash[s[cur]]++;
            while(hash[s[cur]] == 2){
                hash[s[last++]]--;
            }
            ans = max(ans,cur-last+1);
        }
        return ans;
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        string ans = "";
        unordered_map hash;
        int cnt = 0;
        for(auto c:t) {
            if(!hash[c]) cnt++;
            hash[c]++;
        }
        for(int i=0,j=0,c=0;i i-j+1) ans = s.substr(j,i-j+1);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int ans = 0;
        for(int i=0,j=0,t=0;i= target) {
                ans = ans == 0?i-j+1: min(ans,i-j+1);
                t-=nums[j++];
                if(t >= target) ans = ans == 0?i-j+1: min(ans,i-j+1);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int characterReplacement(string s, int k) {
        int ans = 0;
        for (char c='A'; c<='Z'; c++){
            for(int i=0,j=0,cnt=0;i k){
                    if(s[j] == c) cnt--;
                    j++;
                }
                ans = max(ans, i-j+1);
            }
        }        
        return ans;
    }
};

class Solution {
public:
    vector findAnagrams(string s, string p) {
        int m=s.size(),n=p.size();
        vector res;
        if(n>m) return res;
        unordered_map hash;
        for(auto&c:p)hash[c]++;
        int tot = hash.size();
        for(int i=0,j=0,k=0;i p.size()){
                if(hash[s[j]] == 0) k--;
                hash[s[j++]]++;
            }
            if(k == tot) res.push_back(j);
        }
        return res;
    }
};

// O(n)
class Solution {
public:
    int findPairs(vector& nums, int k) {
        if(k<0) return 0;
        unordered_set first_ele, hash;
        for(int i=0;i& nums, int k) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        for(int i=0,j=0;i k) j++;
            if(j < i && nums[i] - nums[j] == k) ans++;
        }
        return ans;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s) {
        unordered_map hash;
        for(auto c:s1) hash[c]++;
        int tot = hash.size();
        for(int i=0, j=0, cnt = 0; i s1.size()){
                if(hash[s[j]] == 0) cnt--;
                hash[s[j++]]++;
            }
            if(cnt == tot) return true;
        }
        return false;
    }
};

class Solution {
public:
    int longestOnes(vector& nums, int k) {
        int ans=0;
        for(int i=0,j=0,cnt=0;i k){
                if(nums[j++] == 1) cnt--;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int longestSubarray(vector& nums) {
        int res = 0;
        for(int l = 0 ,r = 0, cnt = 0;r1){
                if(nums[l]==0){
                    cnt--;
                }
                l++;
            }
            res = max(res,r-l+1);
        }
        return res-1;
    }
};

class Solution {
public:
    int maximumUniqueSubarray(vector& nums) {
        int ans = 0;
        unordered_map hash;
        for(int i=0,j=0,tot=0;i

class Solution {
public:
    string longestPalindrome(string s) {
        vector t = {0,0};
        for(int i = 0;i= 0 && r < s.size() && s[l] == s[r]){
                if(t[1] - t[0] < (r-l+1)){
                    t[0] = l; t[1] = r;                    
                }
                l--; r++;
            }
            l = i-1;r = i;
            while(l >= 0 && r < s.size() && s[l] == s[r]){
                if(t[1] - t[0] < (r-l+1)){
                    t[0] = l; t[1] = r;                    
                }
                l--; r++;
            }
        }
        return s.substr(t[0],t[1] - t[0] + 1);
    }
};

class Solution {
public:
    int maxArea(vector& height) {
        int l = 0, r = height.size()-1, res = 0;
        while(l

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> res;
        if(nums.size() < 3) return res;
        sort(nums.begin(),nums.end());
        for(int i = 0;i 0 - nums[i]) k--;
                    else {
                        res.push_back({nums[i],nums[j],nums[k]});
                        j++;
                    }
                }                
            }
        }
        return res;
    }
};

class Solution {
public:
    int threeSumClosest(vector& nums, int target) {
        pair pii(INT_MAX,INT_MAX);
        sort(nums.begin(),nums.end());
        for(int i = 0;i target){
                    k--;
                    pii = min(pii,make_pair(abs(target - t),t));
                }else return target;
            }
        }
        return pii.second;
    }
};

class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        vector> res;
        if(nums.size() < 4) return res;
        sort(nums.begin(),nums.end());
        for(int  i = 0;i

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = s.size()-1;
        while(l

class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        for(int i = 0,j = numbers.size()-1;i target) j--;
            if(numbers[i] + numbers[j] < target) i++;
            if(numbers[i] + numbers[j] == target) return{i+1,j+1};
        }
        return {-1,-1};
    }
};

class Solution {
public:
    void reverseString(vector& s) {
        for(int l = 0, r = s.size()-1;l

class Solution {
public:
    bool is(char c) {
        if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u' ||
        c=='A' || c=='E' || c=='I' || c=='O' || c=='U' )
        return true;
        else return false;
    }
    string reverseVowels(string s) {
        string ans = s;
        for(int l=0,r=s.size()-1;ll && !is(ans[r])) r--;
            swap(ans[l], ans[r]);
            l++; r--;
        }
        return ans;
    }
};

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        unordered_map> hash;
        for(auto &str:strs){
            string s = str;
            sort(s.begin(),s.end());
            if(hash.find(s) != hash.end()){
                hash[s].emplace_back(str);
            }else{
                hash[s] = vector({str});
            }
        }
        vector> ans;
        for(auto &iter:hash){
            ans.emplace_back(iter.second);
        }
        return ans;
    }
};

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_set s(nums.begin(),nums.end());
        int ans = 0;
        for(auto& num:s){
            if(s.find(num - 1) == s.end()){
                int st = num;
                while(s.find(++st) != s.end());
                ans = max(st - num,ans);
            }
        }
        return ans;
    }
};

// 法2
class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_map right,left;
        int ans = 0;
        for(auto &num:nums){
            int l = right[num-1]; // right:表示以x为右终点
            int r = left[num+1]; // left:表示以x为左起点
            right[num+r] = max(right[num+r], l+r+1);
            left[num-l] = max(left[num-l], l+r+1);
            ans = max(ans, l+r+1);
        }
        return ans;
    }
};

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        unordered_set v;
        for (int i = 0; i < nums.size(); i++) {
            if (v.find(nums[i]) != v.end())
                return true;
            v.insert(nums[i]);
        }
        return false;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector& nums, int k) {
        unordered_map hash;
        for(int i=0;i

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
        typedef long long ll;
        multiset hash;
        hash.insert(1e18); hash.insert(-1e18);
        for(int i=0,j=0;i k){
                hash.erase(hash.find(nums[j++]));
            }
            int x = nums[i];
            auto it = hash.lower_bound(x);
            if(*it - x <= t) return true;
            it--;
            if(x - *it <= t) return true;
            hash.insert(x);
        }
        return false;
    }
};

class Solution {
public:
    string getHint(string secret, string guess) {
        unordered_map hash;
        for(auto c:secret) hash[c]++;
        int tot=0, bulls=0;
        for(int i=0;i

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        unordered_set n1(nums1.begin(), nums1.end());
        vector ans;
        for(auto x:nums2){
            if(n1.count(x)) {
                ans.push_back(x);
                n1.erase(x);
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        unordered_multiset S;
        vector res;
        for (int x : nums1) S.insert(x);
        for (int x : nums2)
            if (S.count(x))
            {
                res.push_back(x);
                S.erase(S.find(x));
            }
        return res;
    }
};

class RandomizedSet {
public:
    vector temp;
    unordered_map hash;
    int cnt = 0;
    RandomizedSet() {
    }
    
    bool insert(int val) {
        if(hash.find(val) == hash.end()){
            hash[val] = cnt++;
            temp.push_back(val);
            return true;
        }
        else return false;
    }
    
    bool remove(int val) {
        auto it = hash.find(val);
        if(it != hash.end()){
            int idx = it->second;
            temp[idx] = temp.back();
            hash[temp[idx]] = idx;
            temp.pop_back();
            cnt--;
            hash.erase(it);
            return true;
        }else return false;

    }
    
    int getRandom() {
        return temp[rand()%cnt];
    }
};

class RandomizedCollection {
public:
    vector num;
    unordered_map> hash;
    RandomizedCollection() {

    }
    
    bool insert(int val) {
        bool f = hash.find(val) == hash.end();
        num.push_back(val);
        hash[val].insert(num.size()-1);
        return f;
    }
    
    bool remove(int val) {
        if(hash.find(val) != hash.end()){
            if(num.back() == val){
                hash[val].erase(hash[val].find(num.size()-1));
                num.pop_back();
                if (hash[val].empty())
                    hash.erase(val);
                return true;
            }

            int t = *hash[val].begin();

            hash[num.back()].erase(num.size() - 1);
            hash[num.back()].insert(t);

            swap(num[t], num.back());

            num.pop_back();
            hash[val].erase(t);
            if (hash[val].empty())
                hash.erase(val);
            return true;
        }
        return false;
    }
    
    int getRandom() {
        return num[rand() % num.size()];
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(magazine.size() < ransomNote.size()) return false;
        unordered_map hash;
        for(auto c:magazine) hash[c]++;
        for(auto c:ransomNote){
            if(hash[c] == 0) return false;
            else hash[c]--;
        }
        return true;
    }
};

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map hash;
        for(auto c:s) hash[c]++;
        for(int i=0;i

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map hash;
        for(auto c:s) hash[c]++;
        int ans = 0;
        bool f = false;
        for(auto &it:hash){
            if(it.second % 2){
                if(!f) f = true;
                ans+=it.second-1;
            }else ans+=it.second;
        }
        if(f) return ans+1;
        else return ans;
    }
};

class Solution {
public:
    int res = 0;
    unordered_map cnt;
    int pathSum(TreeNode* root, int t) {
        cnt[0] = 1;
        dfs(root,t,0);
        return res;
    }
    void dfs(TreeNode*root,int t,int cur_sum){
        if(root == nullptr) return;
        cur_sum += root->val;
        res += cnt[cur_sum - t];
        cnt[cur_sum]++;
        dfs(root->left,t,cur_sum);
        dfs(root->right,t,cur_sum);
        cnt[cur_sum]--;
    }
};

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
        unordered_map hash;
        for(int i=0;i

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int ans=0,tot=0;
        unordered_map hash;
        hash[0]=1;
        for(auto &x:nums){
            tot+=x;
            ans+=hash[tot-k];
            hash[tot]++;
        }
        return ans;
    }
};

//通俗做法-超时O(n2)
class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int ans = 0;
        for(int i=0;i=0;j--){
                sum+=nums[j];
                if(sum == k) ans++;
            }
        }
        return ans;
    }
};

class LRUCache {
public:
    struct Node{
        int key, val;
        Node* left;
        Node* right;
        Node(int _key, int _val): key(_key), val(_val), left(nullptr), right(nullptr){}
    }*L, *R;
    unordered_map hash;
    int n;

    void remove(Node *p){
        p->left->right = p->right;
        p->right->left = p->left;
    }

    void insert(Node *p){        
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1,-1);
        R = new Node(-1,-1);
        L->right = R;
        R->left = L;
    }
    
    int get(int key) {
        if(hash.find(key) == hash.end()) return -1;
        auto p = hash[key];
        remove(p); // 先后顺序搞清
        insert(p);
        return p->val;
    }
    
    void put(int key, int value) {
        if(hash.find(key)!=hash.end()){
            auto p = hash[key];
            p->val = value;
            remove(p);
            insert(p);

        }else{
            if(hash.size() == n){
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            auto q = new Node(key, value);
            insert(q);
            hash[key] = q;
        }
    }
};

class LFUCache {
public:
    struct Node{
        Node *left, *right;
        int key, val;
        Node(int _key,int _val):key(_key), val(_val), left(NULL), right(NULL){}
    };

    struct Block{
        Block *left,*right;
        Node *head,*tail;
        int cnt;
        ~Block(){
            delete head;
            delete tail;
        }
        Block(int _cnt){
            cnt = _cnt;
            left = right = NULL;
            head = new Node(-1,-1);
            tail = new Node(-1,-1);
            head->right = tail, tail->left = head;
        }
        void insert(Node *p){
            p->right = head->right;
            head->right->left = p;
            p->left = head;
            head->right = p;
        }
        void remove(Node *p){
            p->left->right = p->right;
            p->right->left = p->left;
        }
        bool empty(){
            return head->right == tail;
        }
    }*head,*tail;
    int n;
    unordered_map hash_block;
    unordered_map hash_node;

    void insert(Block *p){   // 在p的右侧插入新块，cnt是p->cnt + 1
        auto cur = new Block(p->cnt + 1);
        cur->right = p->right;
        p->right->left = cur;
        p->right = cur;
        cur->left = p;
    }

    void remove(Block* p) {
        p->left->right = p->right;
        p->right->left = p->left;
        delete p;
    }

    LFUCache(int capacity) {
        n = capacity;
        head = new Block(0), tail = new Block(INT_MAX);
        head->right = tail, tail->left = head;
    }
    
    int get(int key) {
        if(hash_block.find(key) == hash_block.end()) return -1;
        auto block = hash_block[key];
        auto node = hash_node[key];
        block->remove(node);
        if (block->right->cnt != block->cnt + 1) insert(block);
        block->right->insert(node);
        hash_block[key] = block->right;
        if (block->empty()) remove(block);
        return node->val;
    }
    
    void put(int key, int value) {
        if(!n) return; // 特例
        if(hash_block.find(key) != hash_block.end()){
            hash_node[key]->val = value;
            get(key);
        }
        else{
            if (hash_block.size() == n) {
                auto p = head->right->tail->left;
                head->right->remove(p);
                if (head->right->empty()) remove(head->right);
                hash_block.erase(p->key);
                hash_node.erase(p->key);
                delete p;
            }
            auto p = new Node(key, value);
            if (head->right->cnt > 1) insert(head);
            head->right->insert(p);
            hash_block[key] = head->right;
            hash_node[key] = p;
        }
    }
};

class Solution {
public:
    bool checkSubarraySum(vector& nums, int k) {
        int n = nums.size();
        vector s(n+1);
        for(int i=1;i<=n;i++) s[i] = s[i-1]+nums[i-1];
        unordered_set hash;
        for(int i =2;i<=n;i++){
            hash.insert(s[i-2]%k);
            if(hash.count(s[i]%k)) return true;
        }
        return false;
    }
};

class Solution {
public:
    int findMaxLength(vector& nums) {
        int ans = 0;
        unordered_maphash;
        hash[0] = 0;
        for(int i=1,x=0;i<=nums.size();i++){
            x+=(nums[i-1] == 1?1:-1);
            if(hash.count(x)) ans = max(ans,i-hash[x]);
            else hash[x]=i;
        }
        return ans;
    }
};

class Solution {
public:
    int findPairs(vector& nums, int k) {
        unordered_set hash, ele;
        for(int i=0;i

class Solution {
public:
    int leastBricks(vector>& wall) {
        int width = accumulate(wall[0].begin(), wall[0].end(), 0);
        unordered_map hash;
        int sum;
        for(auto &a:wall){
            sum = 0;
            for(auto& b:a)
                sum+=b, hash[sum]++;
        }
        sum=0;
        for(auto &it:hash){
            if(it.first != width)
                sum = max(sum,it.second);
        }
        return wall.size() - sum;
    }
};

class Solution {
public:
    int distributeCandies(vector& candyType) {
        unordered_set hash(candyType.begin(), candyType.end());
        return min(candyType.size()/2, hash.size());
    }
};

// 开放寻址法
class MyHashMap {
public:
    const static int N=20011;
    int hash_key[N], hash_val[N];

    MyHashMap() {
        memset(hash_key,-1,sizeof(hash_key));
    }
    
    int find(int key){
        int t = key%N;
        while(hash_key[t] != key && hash_key[t] != -1) 
            if(++t == N) 
                t = 0;
        return t;
    }

    void put(int key, int value) {
        int t = find(key);
        hash_key[t] = key;
        hash_val[t] = value;        
    }
    
    int get(int key) {
        int t = find(key);
        if(hash_key[t] == -1) return -1;
        return hash_val[t];
    }
    
    void remove(int key) {
        int t = find(key);
        if (hash_key[t] != -1)
            hash_key[t] = -2;
    }
};

// 拉链法
class MyHashSet {
public:
    const static int N = 20011;
    vector help[N];

    MyHashSet() {

    }
    
    int find(vector&h, int key){
        for(int i=0;i

class Solution {
public:
    int numTriplets(vector& nums1, vector& nums2) {
        typedef long long ll;
        unordered_map hash;
        for(auto num:nums1) hash[(ll)num*num]++;
        int ans = 0;
        for(int i=0;i=0;j--){
                if(hash.count((ll)nums2[i]*nums2[j]))
                    ans+=hash[(ll)nums2[i]*nums2[j]];
            }
        }
        unordered_map hash1;
        for(auto num:nums2) hash1[(ll)num*num]++;
        for(int i=0;i=0;j--){
                if(hash1.count((ll)nums1[i]*nums1[j]))
                    ans+=hash1[(ll)nums1[i]*nums1[j]];
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector alertNames(vector& keyName, vector& keyTime) {
        unordered_map> hash;
        for(int i=0;i ans;
        for(auto &it:hash){
            sort(it.second.begin(),it.second.end());
            for(int i=2;i

class Solution {
public:
    int minDeletions(string s) {
        vector help(26);
        for(auto c:s) help[c-'a']++;
        sort(help.rbegin(), help.rend());
        int ans = 0;
        for(int i=0;i help[i+1]) continue;
            if(help[i] == 0){
                ans += help[i+1];
                help[i+1] = 0;
            }else{
                int a = help[i]-1;
                ans += help[i+1] - a;
                help[i+1] = a;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxOperations(vector& nums, int k) {
        unordered_map hash;
        for(auto t:nums) hash[t]++;
        int ans = 0;
        for(auto &t:hash){
            if(hash.find(k - t.first) != hash.end()){
                if(k - t.first == t.first) ans += t.second-1;
                else ans += min(t.second, hash[k - t.first]);
            }
        }
        return (ans+1)/2; // 
    }
};

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map hashs;
        unordered_map hasht;
        for(auto i=0;i

class Solution {
public:
    bool wordPattern(string t, string s) {
        stringstream sstream(s);
        unordered_map ts;
        unordered_map st;
        int i = 0;
        while(sstream){
            string tt;
            sstream>>tt;
            if(ts.count(t[i])){
                if(ts[t[i]] != tt) return false;
            }else ts[t[i]] = tt;

            if(st.count(tt)){
                if(st[tt] != t[i]) return false;
            }else st[tt] = t[i];
            i++;
        }
        return i == (t.size()+1);
    }
};