题目链接：最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

方法一：栈

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> t;
        stack<int> ss;
        for (int i = 0;i < s.size();i++) {
            if (s[i] == '(') {
                ss.push(i);
            }else {
                if (ss.size() && s[ss.top()] == '(') {
                    t.push_back(ss.top());
                    t.push_back(i);
                    ss.pop();
                }
            }
        }
        int ans = 0;
        int tt = 1;
        sort(t.begin(),t.end());
        for (int i = 1;i < t.size();i++) {
            if (t[i] == t[i-1] + 1) {
                tt++;
                ans = max(ans,tt);
            }else {
                
                tt = 1;
            }
        }
        return ans;
    }
};

题目链接：N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

方法一：回溯

class Solution {
public:
    vector<vector<string>> ans;
    int m[15][15];
    bool check(int x,int y,int n) {
        for (int i = 0;i < x;i++) {
            if (m[i][y]) return false;
        }
        for (int i = 0;i < y;i++) {
            if (m[x][i]) return false;
        }
        int num = min(x,y);
        // 左上
        for (int i = 1;i <= num;i++) {
            if (m[x-i][y-i]) return false;
        }
        num = min(x,n-y);
        //右上
        for (int i = 1;i <= num;i++) {
            if (m[x-i][y+i]) return false;
        }
        num = min(n-x,n-y);
        
        return true;
    }
    void f(int n,int x) {
        if (x >= n) {
            vector<string> t;
            for (int i = 0;i < n;i++) {
                string s = "";
                for (int j = 0;j < n;j++) {
                    if (m[i][j] == 1) {
                        s += "Q";
                    }else {
                        s += ".";
                    }
                }
                t.push_back(s);
            }
            ans.push_back(t);
            return ;
        }
        for (int i = 0;i < n;i++) {
            if (check(x,i,n)) {
                m[x][i] = 1;
                f(n,x+1);
                m[x][i] = 0;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        f(n,0);
        return ans;
    }
}; 

题目链接：缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

方法：哈希表

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int,int> m;
        for (int num:nums) {
            m[num]++;
        }
        for (int i = 1;i <= nums.size();i++) {
            if (m.find(i) == m.end()) return i;
        }
        return 0;
    }
};

题目链接：最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

方法：滑动窗口

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty() || t.size() > s.size()) {
            return "";
        }

        int need[128] = {0};
        for (char c : t) {
            need[(unsigned char)c]++;
        }

        int needCount = t.size();     // 还需要匹配多少字符
        int left = 0, right = 0;
        int minLen = INT_MAX;         // 当前找到的最短长度
        int start = 0;                // 最优区间的起始位置

        while (right < (int)s.size()) {
            char rc = s[right];
            if (need[(unsigned char)rc] > 0) {
                needCount--;          // 用掉一个需要的字符
            }
            need[(unsigned char)rc]--; // 窗口中多了一个 rc
            right++;

            // 当前窗口已经包含了所有需要的字符，开始尽量缩小左边界
            while (needCount == 0) {
                // 更新最小区间
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                char lc = s[left];
                need[(unsigned char)lc]++; // 移出左边字符
                if (need[(unsigned char)lc] > 0) {
                    // 移出了一个“必须”的字符，窗口不再满足条件
                    needCount++;
                }
                left++;
            }
        }

        // 注意 substr 的第二个参数是长度，不是右边界
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

题目链接：滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

方法：单调队列

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

        }
        return res;
    }
};