class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(int i=0;i<nums2.size();i++)nums1.push_back(nums2[i]);
        sort(nums1.begin(),nums1.end());
        if(nums1.size()&1){
            return nums1[nums1.size()/2];
        }else{
            double res=nums1[nums1.size()/2]+nums1[nums1.size()/2-1];
            return res*0.5;
        }
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        string r;
        for(int i=0;i<p.size();i++){
            if('a'<=p[i] && p[i]<='z')r+=p[i];
            if(p[i]=='.')r+="[a-z]";
            if(p[i]=='*')r+="*";
        }
        regex reg(r);
        return regex_match(s,reg);
    }
};

class Skiplist {
public:
    vector<int> cnt;
    Skiplist() {
        cnt.resize(20005);
    }
    
    bool search(int target) {
        return cnt[target];
    }
    
    void add(int num) {
        cnt[num]++;
    }
    
    bool erase(int num) {
        if(!search(num))return false;
        cnt[num]--;
        return true;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

class Solution {
public:
    int cal(vector<int>& a,int n){
        priority_queue<int> pq;
        for(int i=0;i<n;i++)pq.push(-a[i]);
        int val=-1;
        int ans=0;
        while(pq.size()){
            ans+=pq.top()*val;
            pq.pop();
            val--;
        }
        return ans;
    }
    int maxSatisfaction(vector<int>& dis) {
        sort(dis.rbegin(),dis.rend());
        int mx=0xc0c0c0c0;
        for(int i=0;i<=dis.size();i++){
            mx=max(mx,cal(dis,i));
        }
        return mx;
    }
};

给你一个非负整数数组 nums 。在一步操作中，你必须：

选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
nums 中的每个正整数都减去 x。
返回使 nums 中所有元素都等于 0 需要的 最少 操作数。
就是除了0外数组的不同数字个数。

class Solution {
public:
    set<int> st;
    int minimumOperations(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            if(nums[i])st.insert(nums[i]);
        }
        return st.size();
    }
};

给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：

第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。
返回可以形成的 最大 组数。

class Solution {
public:
    int maximumGroups(vector<int>& gs) {
        //sort(gs.begin(),gs.end());
        int ans=0;
        int dif=1;
        while(true){
            ans+=dif;
            dif++;
            if(ans+dif>gs.size())return dif-1;
        }
        return dif;
    }
};

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

class Solution {
public:
    vector<int> vis1,vis2,dis1,dis2;
    int closestMeetingNode(vector<int>& e, int node1, int node2) {
        int n=e.size();
        vis1.resize(n+10);
        vis2.resize(n+10);
        dis1.resize(n+10);
        dis2.resize(n+10);
        fill(dis1.begin(),dis1.end(),0x3f3f3f3f);
        fill(dis2.begin(),dis2.end(),0x3f3f3f3f);
        queue<int> q;
        q.push(node1);
        vis1[node1]=1;
        dis1[node1]=0;
        while(q.size()){
            int frt=q.front();
            q.pop();
            int dis=dis1[frt];
            if(e[frt]!=-1 && !vis1[e[frt]]){
                vis1[e[frt]]=1;
                dis1[e[frt]]=dis1[frt]+1;
                q.push(e[frt]);
            }
        }
        q.push(node2);
        vis2[node2]=1;
        dis2[node2]=0;
        while(q.size()){
            int frt=q.front();
            q.pop();
            int dis=dis2[frt];
            if(e[frt]!=-1 && !vis2[e[frt]]){
                vis2[e[frt]]=1;
                dis2[e[frt]]=dis2[frt]+1;
                q.push(e[frt]);
            }
        }
        int mn=0x3f3f3f3f;
        int mnp=0;
        for(int i=0;i<vis1.size();i++){
            if(max(dis1[i],dis2[i])<mn)mnp=i;
            mn=min(max(dis1[i],dis2[i]),mn);
            //cout<<dis1[i]<<' '<<dis2[i]<<endl;
        }
        if(mn==0x3f3f3f3f)return -1;
        return mnp;
    }
};

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。

图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。

请你返回图中的 最长 环，如果没有任何环，请返回 -1 。

一个环指的是起点和终点是 同一个 节点的路径。

class Solution {
public:
    vector<int> dfn;
    set<int> lft;
    set<int> ddf;
    vector<int> edg;
    int mx;
    int n;
    int num;
    void dfs(int u){
        lft.erase(u);
        ddf.insert(u);
        dfn[u]=num++;
        if(edg[u]!=-1){
            if(dfn[edg[u]]){if(ddf.count(edg[u])){mx=max(mx,num-dfn[edg[u]]);}return;}
            dfs(edg[u]);
        }
    }
    int longestCycle(vector<int>& e) {
        mx=-1;
        num=0;
        n=e.size();
        dfn.resize(n);
        edg=e;
        for(int i=0;i<n;i++){
            lft.insert(i);
        }
        while(lft.size()){
            dfs(*lft.begin());
            ddf.clear();
        }
        //for(int i=0;i<n;i++)cout<<i<<' '<<dfn[i]<<endl;
        return mx;
    }
};