LeetCode 题解（1000-*, 持续更新，part3）

第一部分，编号500以内的部分
第二部分，编号501-1000部分
本博客不再更新，后面的部分见我写的另一个博客 myblog

这是编号1000以上的部分（加锁部分暂时买不起，后面有机会开个会员）

1001. Grid Illumination

题意：给定一个N，表示有N*N的网格（下标0到N-1），网格中有一些点放置有灯。每个灯能够照亮所在的行列以及两条对角线。
给定一些查询，每个查询是一个点，首先先确定位置是否被照亮，如果是，那么周围3*3方格内的灯都灭掉。接着查询下一个。
需要返回每个查询位置是否被照亮，保存为一个数组

题解：首先用一个set保存灯所在的点，接着我们可以保存被照亮的行，列和两个对角线，行和列直接用坐标就可以表示。而对角线我们取它和x轴的交点，分别是x - y 和x + y。接着就是在上面做查询和删除操作了。

class Solution {
    static const int MOD = 100007;
    struct pair_hash {
        inline size_t operator()(const pair<int,int> & p) const {
            return (p.first % MOD * 1000 + p.second) % MOD;
        }
    };
    
public:
    vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_set<pair<int, int>, pair_hash> lamps_pos;
        unordered_map<int, int> ill_pos[4];
        for(int i = 0;i < lamps.size(); ++i){
            int x = lamps[i][0], y = lamps[i][1];
            lamps_pos.insert(make_pair(x, y));
            ++ill_pos[0][x];
            ++ill_pos[1][y];
            ++ill_pos[2][x - y];
            ++ill_pos[3][x + y];
        }
        vector<int> ans;
        
        for(int i = 0;i < queries.size(); ++i){
            int x = queries[i][0], y = queries[i][1];
            
            if(ill_pos[0][x] || ill_pos[1][y] || ill_pos[2][x - y] || ill_pos[3][x + y])
                ans.push_back(1);
            else 
                ans.push_back(0);
            
            for(int j = -1; j <= 1; ++j){
                for(int k = -1; k <= 1; ++k){
                    int cur_x = x + j;
                    int cur_y = y + k;
                    if(cur_x < 0 || cur_y < 0 || cur_x >= N || cur_y >= N) continue;
                    if(lamps_pos.count(make_pair(cur_x, cur_y))){
                        lamps_pos.erase(make_pair(cur_x, cur_y));
                        --ill_pos[0][cur_x];
                        --ill_pos[1][cur_y];
                        --ill_pos[2][cur_x - cur_y];
                        --ill_pos[3][cur_x + cur_y];
                    }
                }
            }
        }
        return ans;
    }
};

1012. Numbers With Repeated Digits

题意：给定一个数字N，问不大于N的正整数有多少个里面具有重复数字的

题解：重复的难求，我们求不重复的，然后总数N + 1个减去不重复的
不重复的我们可以通过逐位计算。不过有另外的解法，稍慢一点，就是动态规划，见代码注释。

int dp[10][1024];

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        if (N < 10) return 0;
        string str = to_string(N);
        int numDigits = str.length();        
        memset(dp, -1, sizeof dp);
        
        return N - helper(0, 0, 1, str) + 1;
    }
    
    //dp[index][d]表示index位的数，位标记为d的不重复数字数目
    //helper计算的是不超过N的有多少
    //tight表示前缀固定，和N的前缀一样
    int helper(int index, int d, int tight, string& str)
    {
        if (index == str.length()) return 1;        
        if (tight != 1 && dp[index][d]  != -1) return dp[index][d];
        int res  = 0;
        int range = tight == 1 ? str[index] - '0' : 9;
        for (int i = 0 ; i <= range; i++)
        {
            if (d & (1 << i)) continue;
            int newTight = 0;
            
            if (tight == 1 && (str[index] - '0') == i) newTight = 1;
            //前导0不能做标记，因为可以重复出现
            if (d == 0 && i == 0) res += helper(index + 1, d, newTight, str);
            else res += helper(index + 1, d | (1 << i), newTight, str);
        } 
		if (!tight) dp[index][d] = res;
        return res;
    }
};

1023. Camelcase Matching

搞错了，这是个中等题，难怪这么简单。
题意：给定一些query串和一个pattern。一个query串能和pattern匹配如果pattern能够通过插入一些小写字母得到query串。
返回一个bool数组，表示每个query是否和pattern匹配

题解：贪心匹配。每个query如果能匹配完pattern，且其他字符都是小写字母就算匹配成功。

class Solution {
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> ans;
        
        for(int i = 0;i < queries.size(); ++i){
            
            string &cur_q = queries[i];
            int pos = 0;
            int match = true;
            
            for(int j = 0; j < cur_q.length(); ++j){
                if(pos < pattern.length() && cur_q[j] == pattern[pos]){
                    ++pos;
                    continue;
                }
                if('a' <= cur_q[j] && cur_q[j] <= 'z') continue;
                match = false;
                break;
            }
            ans.push_back(match && pos == pattern.size());
        }
        return ans;
    }
};

1024. Stream of Characters

题意：给定一些words（字符串），构造一个数据结构可以支持一下查询。每次查询一个字符。如果倒数k（k>=1）个查询的字符组成的字符串在words中出现，则返回true，否则返回false

题解：几乎是AC自动机的模板题。构建AC自动机。记录到当前字符为止，匹配的最长位置。然后如果当前位置是一个单词结尾返回true，否则如果last指针指向的位置不是0，则说明有后缀可以匹配到字符串，返回true。
当然，用逆序字符串构建Trie也可以过。

class AAM{
    static const int N = 300000;
    int ch[N][26];
    int fail[N],last[N],vis[N];
    bool val[N];
    int cnt,root;
    
    int p; //当前到达的节点（最长匹配）
public:

    void init(){
       cnt = 0, p = root = cnt++;
       memset(vis,0,sizeof(vis));
       memset(ch[0],0,sizeof(ch[0]));
       memset(val,0,sizeof(val));
        
    }
    
    void insert(string s){
            int len = s.length();
            int p = root;
            for(int i = 0; i < len; ++i){
                    int index = s[i] - 'a';
                    if(!ch[p][index]){
                            memset(ch[cnt],0,sizeof(ch[cnt]));
                            ch[p][index] = cnt++;
                    }
                    p = ch[p][index];
            }
            val[p] = true;
    }
    
    void getfail(){
            int p = root;
            queue<int>Q;
            fail[p] = last[p] = p;
            for(int i = 0;i < 26; ++i){
                int u = ch[p][i];
                if(u) {last[u] = fail[u] = p;Q.push(u);}
                else ch[p][i] = p;
            }
            while(!Q.empty()){
                int p = Q.front(); Q.pop();
                for(int i = 0; i < 26; ++i){
                        int &u = ch[p][i];
                        if(u) {
                                fail[u] = ch[fail[p]][i];
                                last[u] = val[fail[u]]?fail[u]:last[fail[u]];
                                Q.push(u);
                        }else u = ch[fail[p]][i];
                }
            }
    }
   
    bool find(char c){
        p = ch[p][c - 'a'];
        return val[p] || last[p];
    }
   
};
class StreamChecker {
    AAM ac_m;
public:
    StreamChecker(vector<string>& words) {
        ac_m.init();
        for(int i = 0;i < words.size(); ++i)
            ac_m.insert(words[i]);
        
        ac_m.getfail();
    }
    
    bool query(char letter) {
        return ac_m.find(letter);
    }
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter)
*/
 
 

1028. Recover a Tree From Preorder Traversal

题意：给定一个字符串，表示一颗二叉树的前序遍历顺序，如下例，其中数字是节点值，横杠表示深度。而且如果一个节点只有一个儿子，那么必定是左儿子。

例子
Input: “1-2–3--4-5–6--7”
Output: [1,2,5,3,4,6,7]

题解：用一个栈恢复遍历过程即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */




class Solution {
    
    int get_val(const string &s, int &pos){
        int val = 0;
        while(pos < s.size() && isdigit(s[pos])) {
            val = val * 10 + s[pos] - '0';
            ++pos;
        }
        return val;
    }
    
    int get_depth(const string &s, int &pos){
        int depth = 0;
        while(pos < s.size() && s[pos] == '-') {
            ++depth;
            ++pos;
        }
        return depth;
    }
    
    
public:
    TreeNode* recoverFromPreorder(string s) {
        stack<pair<TreeNode*, int> >  st;
        TreeNode *root = nullptr;
        int pos = 0;
        root = new TreeNode(get_val(s, pos));
        st.push(make_pair(root, 0));
        
        while(pos < s.size()){
            int depth = get_depth(s, pos);
            int val = get_val(s, pos);
            TreeNode* cur = new TreeNode(val);
            
            
            TreeNode* top = st.top().first;
            int pre_depth = st.top().second;
            if(pre_depth + 1 == depth){
                top->left = cur;
            }else{
                while(pre_depth + 1 != depth){
                    st.pop();
                    top = st.top().first;
                    pre_depth = st.top().second;
                }   
                top->right = cur;
                st.pop();
            }
            st.push(make_pair(cur, depth));
        }
        
        return root;
    }
};

1036. Escape a Large Maze

题意：在一个$10^6\times 10^6$的棋盘上（索引从0到$10^6-1$），有一些障碍点（blocked最多200个），给定一个source和target两个点，问source能不能每次走上下左右四个方向到达target。

题解：如果不是棋盘这么大，直接BFS就能求解。稍微想一想就知道，这么少的障碍点，实际上大部分都是能通过的，我们可以将障碍点网里缩，而不改变source和target的连通性。具体做法就是将x坐标和y坐标重新布局索引。
直观的想象一下，如果不同的块之间有大于1的缝存在，我们只需要让这个缝等于1就可以了。
我们可以分别考虑x和y。考虑x的情况，先排序，如果有0，那么保持0，不然的话下标从1开始（把下方压缩为一行的空间）。
如果当前的x和前一个一样，那么保持相同的索引，如果比前面多一，那么保持多一。如果多二及以上，那么我们把它们的距离缩小到2，也就是索引加2。y同理。这样缩小得到的问题棋盘不会多于400 * 400。

题的数据有缺陷，标程也是：输入数据
[[99999,99998],[99998,99999]]
[0,0]
[99999,99999]
答案应该是false而标准程序给出的是true，并且数据中没有这样的例子。
这个和样例
[[0,1],[1,0]]
[0,0]
[1,1]
是一样的，只不过一个右上角，一个左下角。

class Solution {
public:
    
    int re_idx(vector<int> &xy_loc, map<int,int> &xy_map){
        int idx = 1;
        //边界触及0
        if(xy_loc[0] == 0) idx = 0;
        xy_map[xy_loc[0]] = idx;
        
        for(int i = 1;i < xy_loc.size(); ++i){
            if(xy_loc[i] == xy_loc[i - 1]) continue;
            if(xy_loc[i] == xy_loc[i - 1] + 1) xy_map[xy_loc[i]] = ++idx;
            else xy_map[xy_loc[i]] = (idx += 2);
        }
        //边界触及99999
        if(*xy_loc.rbegin() == 99999) return idx;
        return idx + 1;
    }
    
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        
        map<int,int> x_map, y_map;
        vector<int> x_loc, y_loc;
        x_loc.push_back(source[0]);
        x_loc.push_back(target[0]);
        y_loc.push_back(source[1]);
        y_loc.push_back(target[1]);
        
        
        for(int i = 0;i < blocked.size(); ++i){
            x_loc.push_back(blocked[i][0]);
            y_loc.push_back(blocked[i][1]);
        }
        
        int idx_x = 1, idx_y = 1;
        
        sort(x_loc.begin(), x_loc.end());
        sort(y_loc.begin(), y_loc.end());
        
        
        int x_max = re_idx(x_loc, x_map);
        int y_max = re_idx(y_loc, y_map);
        
        bool vis[x_max + 1][y_max + 1];
        memset(vis, 0, sizeof(vis));
        
        source[0] = x_map[source[0]];
        target[0] = x_map[target[0]];
        
        source[1] = y_map[source[1]];
        target[1] = y_map[target[1]];
        
        for(int i = 0;i < blocked.size(); ++i){
            int x = x_map[blocked[i][0]];
            int y = y_map[blocked[i][1]];
            vis[x][y] = true;
        }
        
        int x_dir[] = {1, 0, -1, 0};
        int y_dir[] = {0, 1, 0, -1};
        
        cout<<source[0]<<source[1]<<endl;
        cout<<target[0]<<target[1]<<endl;
        cout<<x_max<<y_max<<endl;
        
        queue<pair<int,int>> Q;
        Q.push(make_pair(source[0], source[1]));
        vis[source[0]][source[1]] = true;
        while(!Q.empty()){
            pair<int,int> u = Q.front(); Q.pop();
            int x = u.first, y = u.second;
            
            if(x == target[0] && y == target[1]) return true;
            
            for(int i = 0;i < 4; ++i){
                int next_x = x + x_dir[i];
                int next_y = y + y_dir[i];
                if(next_x < 0 || next_y < 0 || next_x > x_max || next_y > y_max || vis[next_x][next_y]) continue;
                vis[next_x][next_y] = true;
                Q.push(make_pair(next_x, next_y));
            }
        }
        return false;
        
    }
};

1044. Longest Duplicate Substring

题意；给定一个字符串，求里面最长的重复子串（出现2次或以上）。

题解：
解法1，二分答案+Rabin-Carp就是二分长度，然后滚动hash判断是否重复。
解法2，问题实际上就是求所有后缀的最长公共前缀，可以用后缀数组做法
下面是后缀数组代码

class Solution {
    static const int maxn = 1e5 + 2;

    int wa[maxn], wb[maxn], wv[maxn], ws[maxn], sa[maxn], height[maxn], *rank;
    int cmp(int *r, int a, int b, int l, int n){
        if(r[a] != r[b]) return false;
        if(a + l >= n && b + l >= n) return true;
        if(a + l >= n || b + l >= n) return false;
        return r[a + l] == r[b + l];
    }

    //待排序的字符串放在r数组中，从r[0]到r[n-1]，长度为n，且最大值小于m
    //sa是我们要求的后缀数组
    //这里x数组保存的值相当于是rank值。下面的操作只是用x数组来比较字符的大小，所以没有必要求出当前真实的rank值。所以这里x保存位置i的字符就好
    //后面的x才是rank值，x[i]=后缀i的名次
    int* cal_suffix_arr(int *r, int *sa, int n, int m){
        int *x = wa,*y = wb;
        memset(ws, 0, m * sizeof(int));
        //对第一个字符排序
        for(int i = 0;i < n; ++i) ++ws[x[i] = r[i]];
        for(int i = 1;i < m; ++i) ws[i] += ws[i - 1];
        for(int i = n - 1; i >=0; --i) sa[--ws[x[i]]] = i;
    
        
        //对长度为2^j的后缀排序
        for(int j = 1, p = 0; p < n; j*=2, m = p){
            p = 0;
            //接下来进行若干次基数排序，在实现的时候，这里有一个小优化。基数排序要分两次，第一次是对第二关键字排序，
            //第二次是对第一关键字排序。对第二关键字排序的结果实际上可以利用上一次求得的sa直接算出，没有必要再算一次。
            //数组y保存的是对第二关键字排序的结果,y[p]= 排名为p的为哪个后缀的第二关键字
            //因为从n - j开始后面的第二部分都是空串，所以排在前面
            for(int i = n - j; i < n; ++i) y[p++] = i;
            for(int i = 0; i < n; ++i) if(sa[i] >= j) y[p++] = sa[i] - j;
            //wv[i] = x[y[i]]是第二关键字排名为i的后缀的第一关键字排名
            //基数排序。按第二关键字排序后，第一关键字的原排名。用第一关键字分桶就得到了一二关键字的排序
            //ws是m个桶
            for(int i = 0; i < n; ++i) wv[i] = x[y[i]];
            for(int i = 0; i < m; ++i) ws[i] = 0;
            //分桶，排序
            for(int i = 0; i < n; ++i) ++ws[wv[i]]; //++ws[x[i]]也一样
            for(int i = 1; i < m; ++i) ws[i] += ws[i - 1];
            for(int i = n - 1; i >= 0; --i) sa[--ws[wv[i]]] = y[i];
            //求解新的rank数组x
            //根据sa求rank。sa[i]是排名为i的后缀,rank[sa[i]]后缀sa[i]的排名
            //因为这里的sa数组对于后缀相同时，排名按位置前后排，所以这里rank还需要判重
            //对于两个后缀sa[i - 1]和sa[i]，他们第一关键字和第二关键字是否都一样，这个可以通过判断本来的rank在对应位置是否相同
            swap(x, y); x[sa[0]]=0; p = 1;
            for(int i = 1; i < n; ++i){
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], j, n) ? p - 1: p++;
                
            }
        }
        return x;
    }


    void cal_height(int n, int *sa, int *rank, int *r, int *height) {
        // vector<int> rank(n);
        // for(int i = 0; i < n; ++i)rank[sa[i]] = i;

        int k = 0;
        for(int i = 0; i < n; ++i){
            int cur = rank[i];
            if(cur == 0) {
                height[cur] = 0;
                k = 0;
            } else {
                if(k > 0) --k;
                int j = sa[cur-1];
                while(i + k < n && j + k < n && r[i + k] == r[j + k]) ++k;
                height[cur] = k;
            }
        }
    }
    
public:
    string longestDupSubstring(string S) {
        int n = S.size(), m = 26;
        int *s = new int[n];
        for(int i = 0;i < n; ++i){
            s[i] = S[i] - 'a';
        }
        
        rank = cal_suffix_arr(s, sa, n, m);
        cal_height(n, sa, rank, s, height);
        int max_len = 0, pos = 0;
        
        
        for(int i = 1;i < n; ++i){
            if(height[i] > max_len){
                max_len = height[i];
                pos = sa[i];
            }
        }
        delete []s;
        return S.substr(pos, max_len);
        
        return "";
    }
};

1045. Number of Submatrices That Sum to Target

题意：给定一个至多300*300的整数矩阵，和一个target，问有多少子矩阵的和为target

题解：做过最大矩阵和的应该很容易想到，这个用前缀和以及HashMap可以使得复杂度为O(N^3)。
具体的就是先求矩阵前缀和。然后枚举上下边，变成一维问题。
也就是给定一个数组，求和为target的子段有多少？
有了前缀和，枚举每个位置i，前缀和为pre_sum[i]，就是找前面有多少个j使得pre_sum[i] - pre_sum[j] = target
转化一下，就是求i前面的前缀和有多少个等于pre_sum[i] - target。这个可以用一个map来保存计数。

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        
        vector<vector<int>> pre_sum(n + 1, vector<int>(m + 1, 0));
        
        
        for(int i = 1;i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] + matrix[i - 1][j - 1] - pre_sum[i - 1][j - 1];
         unordered_map<int,int> pre_sum_catch;
        
        int ans = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = i; j <= n; ++j){
                pre_sum_catch.clear();
                pre_sum_catch[0] = 1;
                for(int k = 1; k <= m; ++k){
                    int p = pre_sum[j][k] - pre_sum[i - 1][k];
                    ans += pre_sum_catch[p - target];
                    ++pre_sum_catch[p];
                }
            }
        return ans;
    }
};

1092. Shortest Common Supersequence

题意：给定两个字符串，求一个最短的字符串能将这两个串作为子序列

题解：动态规划。dp[i][j]表示将str1的前缀i和str2的前缀j作为子序列的串的最短长度。
则当前串的最短长度的串，考虑最后一个字符，首先它必须等于str1[i]或者str2[j]
如果str1[i] == str2[j] 那么最后一个字符和他们都相等，则同时考虑它们两个不会产生更差的结果（就是贪心），转化为子问题，dp[i][j] = dp[i - 1][j - 1] + 1
如果不相等，那么考虑最后一个字符的两种情况取最优。

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int n = str1.length(), m = str2.length();
        int dp[n + 1][m + 1];
        
        //init
        for(int i = 0;i <= n; ++i) dp[i][0] = i;
        for(int j = 0;j <= m; ++j) dp[0][j] = j;
        
        
        for(int i = 1;i <= n; ++i){
            for(int j = 1;j <= m; ++j){
                if(str1[i - 1] == str2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        
        vector<char> s;
        int cur_i = n, cur_j = m;

        //回溯答案        
        for(int k = 0; k < dp[n][m]; ++k){
            if(cur_i > 0 && cur_j > 0 && str1[cur_i - 1] == str2[cur_j - 1]){
                s.push_back(str1[cur_i - 1]);
                --cur_i; --cur_j;
            }else{
                if(cur_i > 0 && dp[cur_i - 1][cur_j] + 1 == dp[cur_i][cur_j]){
                    s.push_back(str1[cur_i - 1]);
                    --cur_i;
                }else{
                    s.push_back(str2[cur_j - 1]);
                    --cur_j;
                }
            }
        }
         
        return string(s.rbegin(), s.rend());
        
    }
};

1095. Find in Mountain Array

题意：交互题。一个数组称为MountainArray，如果它的长度至少位3，且存在一个0<i<len - 1使得0到i递增，i到len - 1递减

题解：不能直接操作数组，要通过一个类获取第k个值。先找出最大值所在的下标。通过二分搜索得到，然后先搜索前半段，再搜索后半段即可。

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */
class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length();
        
        int left = 0, right = n - 1, peak_idx;
        
        while(left <= right){
            int mid = (left + right) / 2;
            int mid_num = mountainArr.get(mid);
            
            if(mountainArr.get(mid + 1) < mid_num){
                right = mid - 1;
            }else
                left = mid + 1;
        }
        
        peak_idx = right + 1;
        left = 0; right = peak_idx;

        while(left <= right){
            int mid = (left + right) / 2;

            int mid_num = mountainArr.get(mid);
            if(mid_num <= target){
                left = mid + 1;
            }else
                right = mid - 1;
        }
        
        if(left > 0 && mountainArr.get(--left) == target) return left;
        
        left = peak_idx + 1; right = n - 1;
        
        while(left <= right){
            int mid = (left + right) / 2;
            int mid_num = mountainArr.get(mid);
            if(mid_num >= target){
                left = mid + 1;
            }else
                right = mid - 1;
        }
        
        if(mountainArr.get(--left) == target) return left;
        return -1;
    }
};

1096. Brace Expansion II

题意：给定一个表达式，形式如 “{{a,z},a{b,c},{ab,z}}”，其中大括号表示可选内容。{a,z}表示a或者z，a{b,c}表示ab或者ac。所以前面的串能表示的有[“a”,“ab”,“ac”,“z”]

给定一个大括号表达式， 问这个串能表示哪些串，按字典序返回。

题解：采用递归,分解成子问题解决。比较难搞的一个模拟题。写的比较挫。
首先如果整个串被一个大括号包含，那么答案就是每个逗号分隔部分答案的并
如果不被括号包围，那么就是各部分答案的笛卡尔积

class Solution {
    //判断是否被一个大括号包围整个串
    bool check_split(string expression){
        int brace_num = 0;
        if(*expression.rbegin() != '}' or *expression.begin() != '{') return false;
        
        for(int i = 0;i < expression.length() - 1; ++i){
            if(expression[i] == '{') ++brace_num;
            else if(expression[i] == '}') --brace_num;

            if(brace_num == 0) return false;
        }
        return true;
    }
    
    //将串按照逗号分隔为子串
    vector<string> split(string expression){
        vector<string> vs;
        
        for(int i = 1; i < expression.size() - 1; ++i){
            int j = i + 1;
            int brace_num = (expression[i] == '{');
            
            while(j < expression.size() - 1 and (expression[j] != ',' or brace_num != 0)){
                switch(expression[j++]){
                    case '}': --brace_num; break;
                    case '{': ++brace_num; break;
                }
            }
            vs.push_back(expression.substr(i, j - i));
            
            i = j;
        }
        return vs;
    }
    //计算笛卡尔积
    vector<string> merge_strs(vector<vector<string>> &vs){
        vector<string> v(1,"");
        
        for(int i = 0;i < vs.size(); ++i){
            vector<string> t;
            for(int j = 0;j < v.size(); ++j){
                for(int k = 0;k < vs[i].size(); ++k){
                    t.push_back(v[j] + vs[i][k]);
                }
            }
            v.swap(t);
        }
        sort_and_remove_duplicate(v);
        return v;
    }
    //排序，去重
    void sort_and_remove_duplicate(vector<string> &v){
        sort(v.begin(), v.end());
        int pos = 0;
        for(int i = 0;i < v.size(); ++i){
            if(i < v.size() - 1 and v[i] == v[i + 1] ) continue;
            v[pos++] = v[i];
        }
        v.resize(pos);
    }
    
    
public:
    vector<string> braceExpansionII(string expression) {
        
        vector<string> vs;
        string substr = "";
        int brace_count = 0;
       //分两种情况
        if(check_split(expression)){
            vector<string> strs = split(expression);
            
            for(int i = 0;i < strs.size(); ++i){
                vector<string> t = braceExpansionII(strs[i]);
                vs.insert(vs.end(), t.begin(), t.end());
            }
            
            sort_and_remove_duplicate(vs);
            return vs;
        }
        
        vector<vector<string> >substrs;
        for(int i = 0;i < expression.size(); ++i){
            int j = i + 1;
            if(expression[i] == '{'){
                int brace_num = 0;
                
                while(expression[j] != '}' or brace_num != 0){
                    switch(expression[j++]){
                        case '}': --brace_num; break;
                        case '{': ++brace_num; break;
                    }
                }
                substrs.push_back(braceExpansionII(expression.substr(i, j - i + 1)));
                
            //字母
            }else{
                j = i;
                while(j + 1 < expression.size() and expression[j + 1] != '{') ++j;
                substrs.push_back(vector<string>(1, expression.substr(i, j - i + 1)));

            }
            i = j;
        }
        
        return merge_strs(substrs);
        
    }
};

1106. Parsing A Boolean Expression

题意：给定一个真值表达式，包函数字符{’(’, ‘)’, ‘&’, ‘|’, ‘!’, ‘t’, ‘f’, ‘,’}，求表达式的真值。
例如
Input: expression = “|(&(t,f,t),!(t))”
Output: false
题解：采用栈的方式进行计算，遇到有括号时，计算栈顶部分的表达式，所有表达式都计算完。因为没有空格，且都是合法的表达式，所以比较简单。

class Solution {
    
    
    bool is_opt(char e){
        return e == '&' || e == '|' || e == '!' || e == ' ';
    }
    
public:
    bool parseBoolExpr(string expression) {
        stack<char> s;
        stack<bool> val;
        char opt;
        bool cur_val;
        
        for(int i = 0;i < expression.size(); ++i){
            //碰到运算符，因为不存在空格，所以直接可以continue了
            //而且表达式都有括号，所以在遇到左括号时push，不然的话在遇到运算符就可push了
            if(is_opt(expression[i]) || expression[i] == ',') continue;
            //非运算符
            
            //左括号
            if(expression[i] == '('){
                if(i > 0 && is_opt(expression[i - 1])) s.push(expression[i - 1]);
                else s.push(' ');
            //右括号
            }else if(expression[i] == ')'){
                while(!is_opt(s.top())){
                    val.push(s.top() == 't');
                    s.pop();
                }
                opt = s.top(); s.pop();
                cur_val = (opt == '&');
                    
                while(!val.empty()){
                    switch(opt){
                        case ' ' : cur_val = val.top(); break;
                        case '|': cur_val |= val.top(); break;
                        case '&': cur_val &= val.top(); break;
                        case '!': cur_val = !val.top(); break;
                    }
                    val.pop();
                }
                if(cur_val) s.push('t');
                else s.push('f');
            // expression[i] == 't'或者'f'
            }else{
                s.push(expression[i]);
            }   
        }   
        return s.top() == 't';
        
    }
};

1107. Longest Chunked Palindrome Decomposition

题意：给定一个字符串text。问最多能把它分成多少个子串，text=（a_1, a_2,…,a_k）使得a_i = a_{k + 1 - i}

题解：贪心。贪心做分割。假设前缀a能和后缀a匹配，如果存在一个前缀包含a，假设为a b，能和后缀匹配。那么在a这里分割比在b处分割更好。
证明： 设前缀[a, c, b] 和后缀[a, a, c] 或者[a,c,a]匹配（分别对应的情况是[a c] 和末尾的[a c]或者[a]和末尾的[a]匹配，其中len(a) == len(b)），(中括号表示拼接，c可以为空串)。

• 情形1：$[a,c,b]$和$[a,a,c]$匹配。则有$[c,b]==[a,c]$ 。
  将c表示成$[c_1,c_2,...,c_0]$其中$len(c_i)==len(a),len(c_0)<len(a)$
  那么由$[c,b]=[a,c]$ 得到 $[c_1,...,c_n,c_0,b]=[a,c_1,...,c_n,c_0]$
  即有$c_1=c_2=...=c_n=a，且[c_0,b]=[a,c_0]$
  将$a$表示成$a=[d,e]，len(d)=len(c_0)$，则上面等式表示$[c_0,b]=[d,e,c_0]$
  我们得到$d=c_0,a=[c_0,e],b=[e,c_0]$
  代回原串$[a,c,b]$得到$[a,c,b]=[(c_0,e{)}^{n+1},c_0]$
  显然这个串可以进一步分割得到更优的分割方案
• 情形2:前缀$[a,c,b]$和后缀 $[a,c,a]$匹配。得到$a==b$。[a,c,a]可以分割成三段[a] [c] [a] 比一段好。

class Solution {
public:
    int longestDecomposition(string text) {
        deque<char> left;
        deque<char> right;

        int maxSplits = 0;
        const int textSize = text.size();
        int i = 0;
        int j = textSize - 1;

        while (i < j) { 
            left.push_back(text[i++]);
            right.push_front(text[j--]);
            //这里可以用hash比较是否相同,会更快一点
            if (left == right) {
                maxSplits += 2;
                left.clear();
                right.clear();
            }
        }
        //剩下多于一个字符不能成对或者剩下一个字符
        if (!left.empty() || i == j) {
            ++maxSplits;
        }
        return maxSplits;
    }
};

1125. Smallest Sufficient Team

题意：给定一个req_skills字符串数组表示团队的必备技能。people是一个数组，people[i]表示第i个人的技能，是个字符串数组。问最少是哪些人可以组成一个团队（每个技能都有人会）

题解：先把技能用位表示成状态对应位为1表示技能已具备。设dp[i][j]表示选第i个人，前i个人达到状态为j时的最少人数。就可以用递推解决。最小的人数就是所有k中dp[k][(1 <<n ) - 1]最小值。然后回溯得到答案。
递推方程为$$dp[i][j|s]=\underset{k<i}{\min }(dp[i][j|s],dp[k][j]+1)$$
s为第i个人的技能状态。
观察到我们计算dp[i][j|s]时，只需要最小的dp[k][j]即可，并不需要所有的k。
所以用一个state_catch[j]表示状态为j时的最少人数。递推方程变成
$$dp[i][j|s]=\min (dp[i][j|s],stat{e}_{c}atch[j]+1)$$
接着注意到，如果用一个数据people_idx表示达到状态时最少人数的最后一个人的id，那么我们就不需要保存dp值了。回溯的时候根据state_catch 和people_idx就能得到答案。
这样就对空间和时间都进行了一定的优化。

class Solution {
    
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        unordered_map<string, int> skill2bit;
        int state_catch[1<<17], people_idx[1<<17];
        
        int n = req_skills.size();
        
        vector<int> people_skill(people.size());
        
        for(int i = 0;i < n; ++i){
            skill2bit[req_skills[i]] = 1 << i;
        }
        
        memset(state_catch, -1, sizeof(state_catch));
        
        for(int i = 0;i < people.size(); ++i){
            int cur_skill = 0;
            for(int j = 0;j < people[i].size(); ++j)
                cur_skill |= skill2bit[people[i][j]];
            people_skill[i] = cur_skill;
        }
        
        state_catch[0] = 0;
        
        for(int i = 1;i <= people_skill.size(); ++i){
            int cur_skill = people_skill[i - 1];
            for(int j = (1 << n) - 1; j >= 0; --j){
                if(state_catch[j] == -1) continue;
                int next_skill = j | cur_skill;
                int &sk = state_catch[next_skill];
                
                int dp = sk == -1? state_catch[j] + 1 : min(sk, state_catch[j] + 1);
                
                if(sk == -1 || dp < sk){
                    sk = dp;
                    people_idx[next_skill] = i - 1;
                }
            }
        }
        
        int min_num = state_catch[(1<<n) - 1];
        int cur_skill = (1 << n) - 1;
        vector<int> ans;
        
        while(min_num){
        	//枚举所有包含cur_skill的状态，
            for(int j = cur_skill; j < (1 << n); ++j){
                if((j & cur_skill) != cur_skill) continue;
                if(min_num == state_catch[j]){
                    ans.push_back(people_idx[j]);
                    //计算剩下还需要的技能
                    cur_skill &= ((1 << n) - 1) ^ people_skill[people_idx[j]];
                    break;
                }
            }
            --min_num;
        }
        return ans;
    }
};

1126. Online Majority Element In Subarray

题意：对一个数组（1到20000）进行查询，每次查询一个子数组区间[left, right]，给定区间和一个threshold，返回区间中出现次数超过threshold的整数。其中threshold * 2 > right - left + 1。即超过半数。

题解：比较容易想到的是线段树的做法。每次查询是O(logn) 构建一颗线段树，节点保存的是区间超过半数的值。
某个值在某个区间出现的次数，我们可以用一个numbers来存每个数的下标，然后二分就得到了。
查询的时候，左右子树中各返回一个候选值。两个值取出现次数大于threshold的就可以了。

不过还有更多更好的方法：猫树1，猫树2 ，RMQ快速查询算法，

class MajorityChecker {
    static const int MAXN = 20001;
    vector<int> a;
    vector<int> numbers[MAXN];
    int n;
    int segment_tree[4 * MAXN];
    
    int get_num(int val, int left, int right){
        vector<int> &val_vec = numbers[val];
        return upper_bound(val_vec.begin(), val_vec.end(), right) - lower_bound(val_vec.begin(), val_vec.end(), left);
    }
    int build_tree(int node, int left, int right){
        if(left == right){
            segment_tree[node] = a[left];
        }else{
            int mid = (left + right) >> 1;
            
            int l_val = build_tree(node << 1, left, mid);
            int r_val = build_tree((node << 1) | 1, mid + 1, right);
            
            int interval_size = right - left + 1;
            if(l_val > 0 and 2 * get_num(l_val, left, right) > interval_size)
                segment_tree[node] = l_val;
            else if(r_val > 0 and 2 * get_num(r_val, left, right) > interval_size)
                segment_tree[node] = r_val;
        }
        return segment_tree[node];
    }
    
    int mode_query(int node, int int_left, int int_right, int q_left, int q_right, const int &threshold){
        if(int_right < q_left or int_left > q_right) return 0;
        if(q_left <= int_left and int_right <= q_right) return segment_tree[node];
        
        int mid = (int_left + int_right) >> 1;
        int l_val = mode_query(node << 1, int_left, mid, q_left, q_right, threshold);
        int r_val = mode_query((node << 1) | 1, mid + 1, int_right, q_left, q_right, threshold);
        
        if(l_val > 0 and get_num(l_val, q_left, q_right) >= threshold)
            return l_val;
        else if(r_val > 0 and get_num(r_val, q_left, q_right) >= threshold)
            return r_val;
        return 0;
    }
    
public:
    MajorityChecker(vector<int>& arr) {
        this->a.swap(arr);
        
        n = a.size();
        for(int i = 0;i < n; ++i){
            numbers[a[i]].push_back(i);
        }
        
        build_tree(1, 0, n - 1);
        
    }
    
    int query(int left, int right, int threshold) {
        int mode = mode_query(1, 0, n - 1, left, right, threshold);
        if(mode > 0 and get_num(mode, left, right) >= threshold)
            return mode;
        else
            return -1;
    }
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */

1163. Last Substring in Lexicographical Order

题意：给定一个字符串，输出最大字典序的子串

题解：首先字典序最大的一定是某个后缀。可以用后缀数组，但是显得有点杀鸡用牛刀。有更好的办法。我们可以从前往后扫一遍，避免一些冗余计算，可以让时间复杂度为O(n)。

我们设i位置之前的最大字典序后缀的下标是maxidx。
如果s[i] > s[maxidx]，则到i这里，最大字典序是后缀i
如果s[i] < s[maxidx]，则到i这里，最大字典序依然是后缀maxidx
如果s[i] == s[maxidx]，则i后缀有可能比后缀maxidx大。这时候往后继续比较
也就是先比较子串s[maxidx,i] 和s[i, 2i - maxidx] （不包含后面那个字符）。

• 如果不相等，那么后缀就可以确定哪个大。并且i + 1 到2i - maxidx 的后缀都不可能比它大（子串已经比较过了，如果有更大的，那么maxidx应该往后移，不可能是当前位置）
  假设从max_idx开始到i的串为[s c] ，i到 2i-maxidx的串同样为[s c] 而2i-maxidx后面的为d，即max_idx开始的后缀表示为 [s c][s c][d]
  如果i到2i - maxidx中有某个位置的后缀更大，也就是上面从c开始的后缀。那么有 [c d] > [c s c d]，即有[c d] > [c s] 推出[c > s]
  这和maxidx的定义矛盾。i前面比s开始后缀大的还有以c开始的后缀
• 如果相等，和上面一样。将串表示成[s][s][d]，则要么[s s d]是最大的，要么[d]更大，不可能是[s d]最大。因为如果[s d] > [s s d]，则有[d] > [s]

class Solution {
public:
    string lastSubstring(string s) {
        int maxidx = 0 , i = 1 , n = s.size();
        while(i < s.size())
        {
            if(s[i] > s[maxidx])
            {
                maxidx = i;
            }
            else if(s[i] == s[maxidx]){
                int curr = i , j = maxidx;
                while(i < n && j < curr && s[i] == s[j]){
                    ++i; ++j
                }
                if(i >= n || j >= curr ||  s[j] > s[i])
                    continue;
                else
                    maxidx = curr;
                continue;
            }
            i++;
        }
        return s.substr(maxidx);
    }
};

1164. Dinner Plate Stacks

题意：设计一个结构它由无穷个栈组成，每个的容量为capacity。 支持三种操作。

• push:找到最前面未满的栈，往栈顶添加元素
• pop:找到最末非空的栈，pop出栈顶
• popAtStack，指定下标的栈进行pop操作

题解：可以使用双指针找对应位置。下面是用两个堆维护插入和删除栈下标。一个大顶堆，一个小顶堆。虽然渐进时间复杂度比较低，但是常数比较大，所以还是比较耗时的，比不上双指针。

class DinnerPlates {
    int cap;
    int tot_num;
    //可以初始化为一个较大的容量，但是这里采用动态增长。存所有栈
    vector<stack<int>> stacks;
    //小顶堆，存那些没有满的stack下标。堆顶是下标最小的
    priority_queue <int, vector<int>, greater<int>> unfull_Q;
    //大顶堆，存那些非空的stack下标。堆顶是最大非空栈下标
    set<int, greater<int>> nonempty_Q;
    
    
public:
    DinnerPlates(int capacity) {
        cap = capacity;
        tot_num = 0;
    }
    
    void push(int val) {
        if(stacks.size() * cap <= tot_num){
            stacks.push_back(stack<int>());
            unfull_Q.push(stacks.size() - 1);
        }
        int stack_idx = unfull_Q.top(); 
        stacks[stack_idx].push(val);
        if(stacks[stack_idx].size() == 1) nonempty_Q.insert(stack_idx);
        if(stacks[unfull_Q.top()].size() == this -> cap) unfull_Q.pop();
        
        ++tot_num;
    }
    
    int pop() {
        if(tot_num == 0) return -1;
        int stack_idx = *nonempty_Q.begin();
        //while(stacks[stack_idx].empty()){
        //     nonempty_Q.erase(nonempty_Q.begin());
        //     stack_idx = *nonempty_Q.begin();
        // }
        int r = stacks[stack_idx].top();
        if(stacks[stack_idx].size() == this->cap) unfull_Q.push(stack_idx);
        stacks[stack_idx].pop();
        if(stacks[stack_idx].size() == 0) nonempty_Q.erase(nonempty_Q.begin()); 
        
        --tot_num;
        
        return r;
    }
    
    int popAtStack(int index) {
        if(index >= stacks.size() ||  stacks[index].empty()) return -1;
        int r = stacks[index].top(); stacks[index].pop();
        if(stacks[index].size() == this->cap - 1) unfull_Q.push(index);
        if(stacks[index].size() == 0) nonempty_Q.erase(index);
        
        --tot_num;
        return r;
    }
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAtStack(index);
 */

1173. Number of Valid Words for Each Puzzle

题意：给定两个字符串数组words，和puzzles。puzzles是一些谜面，words是一些谜底。一个谜面的谜底必须满足

• 包含谜面的第一个字符
• 所有字符都在谜面中出现

对每个谜面puzzles[i],我们要计算words中有多少个谜底可以和它对应。

题解：用位表示表示每个字符串，然后words用一个map存起来就可以进行计数了。对于每个puzzels[i]，枚举可能的字符子集然后在map获取对应word的数目。

class Solution {
public:
	//字符串转换为位表示
    int bit_rep(string s){
        int r = 0;
        for(int i = 0;i < s.size(); ++i){
            r |= 1 << (s[i] - 'a');
        }
        return r;
    }
    //计算每个puzzles[i]对应的word数目
    int num_count(int r, int first_char, map<int,int> &word_num){
        if(!r) return 0;
        vector<int> bit_pos;
        int pos = 0;
        while((1 << pos) <= r){
            if(r & (1 << pos)) bit_pos.push_back(pos);
            ++pos;
        }
        
        int num = 0;
        for(int i = 0;i < (1 << bit_pos.size()); ++i){
            
            r = 0;
            for(int j = 0;j < bit_pos.size(); ++j){
                if(((1 << j) & i) == 0) continue;
                r |= 1 << bit_pos[j];
            }
            
            if((r & (1 << first_char)) == 0) continue;
            num += word_num[r];
        }
        
        return num;
    }

    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
    	//用一个map保存二进制表示的word的数目
        map<int,int> word_num;
        vector<int> ans;
        for(int i = 0;i < words.size(); ++i){
            int r = bit_rep(words[i]);
            ++word_num[r];
        }
        
        for(int i = 0;i < puzzles.size(); ++i){
            int puzzle_r = bit_rep(puzzles[i]);
            int first_char = puzzles[i][0] - 'a';
            ans.push_back(num_count(puzzle_r, first_char, word_num));
            
        }
        return ans;
    }
};

1187. Make Array Strictly Increasing

题意：给定两个数组arr1和arr2。每次可以进行一个操作，任选arr1的下标i和arr2的下标j，令arr1[i] = arr2[j]。问最少多少次操作后，arr1为递增序列。如果不能使得arr1为递增序列，返回-1

题解：容易想到的两种动态规划
dp[i][j]表示前i个数，进行j次赋值，第i个数的最小值是多少。转移方程由当前i赋值或者不赋值两种情况取最小。
如果当前不赋值，则最小值是arr1[i]
如果当前赋值，则最小值是比dp[i - 1][j - 1]大的最小值（这可以通过预处理或者保存下标解决）。
下面采用另一种动态规划,dp[i][j]表示，数组1的位置i赋值为数组2的j位置时，arr1[i] = arr2[j]，前i个(0到i)数保持递增的最小赋值次数。dp[i][m]表示不赋值

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        int m = arr2.size();
        //dp[i][j]表示arr1第i个数赋值为arr2第j个数时，前i个数为递增列的最少赋值次数
        int dp[n + 1][m + 1];
        //保存arr2中比arr1[i]小的最大数的下标。arr2先去重
        int idx[n];
        memset(dp, 0x3f, sizeof(dp));
        dp[0][m] = 0;
        for(int i = 0;i < m; ++i) dp[0][i] = 1;
        
        sort(arr2.begin(), arr2.end());
        
        //去重
        m = 0;
        for(int i = 0;i < arr2.size(); ++i){
            if(i > 0 && arr2[i] == arr2[i - 1]) continue;
            arr2[m++] = arr2[i];
        }
        arr2.resize(m);

       	//计算比每个arr1[i]小的最大的arr2[j]的下标j
        for(int i = 0;i < n; ++i){
            idx[i] = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin() - 1;
        }
        
        for(int i = 1;i < n; ++i){
            //当前值不变
            if(arr1[i] > arr1[i - 1])
                dp[i][m] = dp[i - 1][m];
            
            if(idx[i] != -1){
                dp[i][m] = min(dp[i][m], dp[i - 1][idx[i]]);
            }
            //当前值变为arr2[j]
            for(int j = 0; j < m; ++j){
                if(arr2[j] > arr1[i - 1]) dp[i][j] = dp[i - 1][m] + 1;
                if(j > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        
        int ans = m + 1;
        for(int i = 0;i <= m; ++i) ans = min(ans, dp[n - 1][i]);
        
        return ans > m ? -1 : ans;
    }
};

1192. Critical Connections in a Network
      题意：给定一个图，connects保存的是边。问哪些边是重要的。即删除该边后，图不连通。
      题解：双联通分量模板题。边u->v是critical的，当且仅当，u到v只有一条简单路径。双联通分量就是，一个连通分量中的任意两点都存在大于等于2条简单路径。求双联通分量的办法和求连通分量基本一致。将无向边当做有向边处理（按dfs遍历顺序确定方向即可），且一条边只能走一次（加一个father防止多走一次）。然后用求强联通分量的方法Tarjan算法即可。

class Solution {
    static const int MAXN = 1e5+5;
    int n,m;
    int dfn[MAXN],low[MAXN],vis[MAXN],color[MAXN];
    int color_num, tot;
    stack<int> s;
    vector<int> graph[MAXN];
    
    void init(int n){
        tot = 0;
        color_num = 0;
        memset(vis, 0, sizeof(vis));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(color, 0, sizeof(color));
        stack<int>().swap(s);
        for(int i = 0;i <= n; ++i) graph[i].clear();
    }
    
    void Tarjan(int now,int fa) {
        dfn[now]=low[now] = ++tot;
        vis[now] = true;
        s.push(now);
        
        for (int i = 0;i < graph[now].size(); ++i) {
            int u = graph[now][i];
            //点还没有遍历过
            if(dfn[u] == 0)  
                Tarjan(u, now),low[now] = min(low[now], low[u]);
            //点遍历过的，并且还在栈中
            else if(vis[u] && u != fa) 
                low[now] = min(low[now], dfn[u]);
        }
        //找到一个双联通分量
        if(dfn[now] == low[now]) {
            int top;
            ++color_num;
            do{
                top=s.top();    
                color[top] = color_num;
                vis[top]=0; 
                s.pop();
            }while(top != now);
        }
    }
    
    
public:
    //有重边的下，要处理一下重边
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        init(n);
        //建图
        for(size_t i = 0;i < connections.size(); ++i){
            graph[connections[i][0]].push_back(connections[i][1]);
            graph[connections[i][1]].push_back(connections[i][0]);
        }
        
        for(int i = 0; i< n; ++i){
            if(dfn[i]) continue;
            Tarjan(i, -1);
        }
        vector<vector<int> > ans;
        for(size_t i = 0;i < connections.size(); ++i){
            if(color[connections[i][0]] != color[connections[i][1]]) ans.push_back(connections[i]);
        }
        
        return ans;       
        
    }
};

1193. Design Skiplist

题意：设一一个跳表

题解：见代码，易懂。每个节点保存右方和下方的地址。增加一个虚拟表头，使得实现更方便。它还有可以再优化的地方，就是我们可以提前计算出当前插入的节点网上插入多少层，这样查找的时候就可以顺便插入，不用用一个vector保存所有可能插入点。

代码来自讨论区，有个bug，没有删除节点，会有内存泄漏

struct Node {
    Node *right, *down;
    int val;
    Node(Node *right, Node *down, int val): right(right), down(down), val(val) {}
};

class Skiplist {
    Node* head;
    
public:
    Skiplist() { head = new Node(NULL, NULL, 0); }
    
    bool search(int num) {
        Node *p = head;
        while(p) {
            //先往右
            while(p -> right and p -> right -> val < num) p = p -> right;
            //不能往右走就往下
            if(!p -> right or p -> right -> val > num) p = p -> down;
            else return true;
        }
        return false;
    }
    
    void add(int num) {
        insertPoints.clear();
        Node *p = head;
        while(p) {
            while(p -> right and p -> right -> val < num) p = p -> right;
            insertPoints.push_back(p);
            p = p -> down;
        }
        
        Node* downNode = NULL;
        bool insertUp = true;
        while(insertUp and insertPoints.size()) {
            Node *ins = insertPoints.back();
            insertPoints.pop_back();
            
            ins -> right = new Node(ins -> right, downNode, num);
            downNode = ins -> right;
            
            insertUp = (rand() & 1) == 0;
        }
        //增加一层
        if(insertUp) {
            return NULL;
            head = new Node(new Node(NULL, downNode, num), head, 0);
        }
    }
    vector<Node*> insertPoints;hb
    
    bool erase(int num) {
        Node *p = head;
        bool seen = false;
        
        while(p) {
            while(p -> right and p -> right -> val < num) p = p -> right;
            if(!p -> right or p -> right -> val > num) p = p -> down;
            else {
                //找到一个p->right->val == num，则
                seen = true;
                Node *tmp = p -> right;
                p -> right = p -> right -> right;
                p = p -> down;
                delete tmp;
            }
        }
        return seen;
    }
};

/**
 * 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);
 */

1207. Minimum Moves to Reach Target with Rotations

题意：有一个n*n的网格。有一条蛇，占用两个格，从位置(0,0)和(0,1)位置，往右下方走，问走到右下角(n - 1,n - 2), (n - 1, n - 1)至少多少步，不能通过则返回-1？
每一步，蛇能按如下规则移动：

• 不能移动到格子为1的地方，不能超出方格范围
• 向右移动，整体向右平移一格（蛇可以是横向的，或者纵向的）
• 向下移动，整体向下平移一格
• 顺时针旋转，如果当前蛇在位置(i,j)和(i,j + 1)，且以(i,j)为左上角的2*2方格中的数为0。则蛇可以旋转为(i,j)和(i + 1,j)位置
• 逆时针旋转，蛇是纵向的，4个格子为0，旋转为横向的。
  如下图所示
  

题解：动态规划。设dp[i][j][k]表示到达蛇尾在位置i,j,面向为k的（k为0表示水平，1是竖直）。代码中，为了

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int n = grid.size();
        if(grid[0][0] != 0 || grid[0][1] != 0 || grid[n - 1][n - 2] != 0 || grid[n - 1][n - 1] != 0) return -1;
        
        int dp[n + 1][n + 1][2];
        //初始化成一个大的值
        memset(dp, 0x3f ,sizeof(dp));

        dp[0][0][0] = 0;
        
        for(int i = 0;i < n ; ++i){
            for(int j = 0;j < n - 1; ++j){
                if(grid[i][j] != 0) continue;
                
                //两种平移
                if(grid[i][j + 1] == 0)
                    dp[i][j][0] = min(dp[i][max(j - 1, 0)][0], dp[max(i - 1, 0)][j][0]) + 1;
                
                if(i < n - 1 && grid[i + 1][j] == 0)
                    dp[i][j][1] = min(dp[max(i - 1, 0)][j][1], dp[i][max(j - 1, 0)][1]) + 1;
                
                //左下角不为0，则不能旋转
                if(i >= n - 1 || grid[i + 1][j + 1] != 0) continue;
                
                //两种旋转
                if(i < n - 1 && grid[i + 1][j] == 0)
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j][0] + 1);
                
                if(grid[i][j + 1] == 0)
                    dp[i][j][0] = min(dp[i][j][0], dp[i][j][1] + 1);
            } 
        }
        
        return dp[n - 1][n - 2][0] >= 0x3f3f3f3f? -1 : dp[n - 1][n - 2][0] - 1;
    }
};

1203. Sort Items by Groups Respecting Dependencies

题意：有n个项目和m个小组（都是从0开始）。每个项目要么没有归属group[i] = -1，要么归属为group[i]。
你需要安排这些项目的次序，返回排序后的项目，满足以下条件

• 同一个组的项目，彼此相邻
• 项目之间有一个依赖关系。要执行第i个项目必须先完成的项目为beforeItems[i]（一个列表）
  返回任意一个符合的结果，如果没有，返回空列表

题解：拓扑排序。使用两层的拓扑排序。建立一个group间的依赖关系图（-1的组每个元素单独成一个组即可），以及一个组内项目的依赖关系图。然后进行拓扑排序。先按group排，对每个group，对组内的项目进行排序。没有可行方案当且仅当两个图中有环，拓扑排序不能排完所有元素。

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int> >& beforeItems) {
        vector<vector<int> > group_graph(n + 1, vector<int>()), item_graph(n + 1, vector<int>());
        vector<int> item_degree(n + 1, 0);

        int group_idx = m;

        for(int i = 0;i < group.size(); ++i)
            if(group[i] == -1) group[i] = group_idx++;
		//保存每个group的元素，后面遍历使用
        vector<vector<int> > group2items(group_idx, vector<int>());
        vector<int> group_degree(group_idx, 0);

        //建图
        for(int i = 0;i < beforeItems.size(); ++i){
            int i_group = group[i];

            for(int j = 0;j < beforeItems[i].size(); ++j){
                int u = beforeItems[i][j];
                int j_group = group[u];

                if(i_group == j_group){//item graph
                        item_graph[u].push_back(i);
                        ++item_degree[i];
                }else{// group graph
                    group_graph[j_group].push_back(i_group);
                    ++group_degree[i_group];
                }
            }
            group2items[i_group].push_back(i);
        }

        vector<int> ans;
        queue<int> group_Q, item_Q;
        
        //group的拓扑排序
        for(int i = 0;i < group_idx; ++i){
            if(group_degree[i] == 0) group_Q.push(i);
        }
        while(!group_Q.empty()){
            int g = group_Q.front(); group_Q.pop();
           

            //一个group的item的拓扑排序
            for(int i = 0;i < group2items[g].size(); ++i){
                int u = group2items[g][i];
                if(item_degree[u] == 0) item_Q.push(u);
            }
            while(!item_Q.empty()){
                int u =  item_Q.front(); item_Q.pop();
                ans.push_back(u);
                for(int i = 0;i < item_graph[u].size(); ++i){
                    int v = item_graph[u][i];
                    if(--item_degree[v] == 0) item_Q.push(v);
                }
            }
            for(int i = 0;i < group_graph[g].size(); ++i){
                int g2 = group_graph[g][i];
                if(--group_degree[g2] == 0) group_Q.push(g2);
            }
            
        }
        if(ans.size() != n) return {};
        else  return ans;
    }
};