1.知识点总结

突然想到AK不是很难（？），但是要是时间空间都达到80%+的胜率……昂，好难吖👀

题目	难度	知识点
括号生成	🐸	DFS
合并K个升序链表	🐸	list+STL
下一个排列	🐸🐸	STL（我感觉我在作弊🤣，这题不用STL的话要回炉的）
最长有效括号	🐸🐸	还是有点难度？STL中的stack用法了解一下需要回炉用DP试一下

2. 分题题解

2.1 括号生成

个人感觉是比较基础的题目，而且n的范围1-8，emm，基础的dfs就可以，感觉用bool也没有很省内存

执行用时：4 ms, 在所有 C++ 提交中击败了66.29%的用户

内存消耗：13.5 MB, 在所有 C++ 提交中击败了38.21%的用户

class Solution {
public:
    vector<bool>temp;// "("->true ; ")"->false
    vector<string>ans;
    int len;
    void v2str(){
        string str="";
        for(int i=0;i<len*2;i++){
            if(temp[i]){
                str+="(";
            }else{
                str+=")";
            }
        }
        ans.push_back(str);
    }
    void dfs(int left,int right,bool isleft){
        temp.push_back(isleft);
        //记录左右括号的个数
        if(left>len||right>len||right>left){//不合法的情况
           
        }else if(left==right&&left==len){
            //当前的答案合法，需要保存 
            v2str();
        }else{
            //需要继续
            dfs(left,right+1,false);
            dfs(left+1,right,true);
        }
        temp.pop_back();//回溯
    }
    vector<string> generateParenthesis(int n) {
        //dfs叭，主要是保存答案比较麻烦
        len=n;
        dfs(1,0,true);
        return ans;
    }
};

2.2 合并K个升序链表

基础思路：倾向于遍历完所有的数据存到vector中然后新建list,值得一提的是这种解法的时间复杂度居然似乎比单纯链表操作低？空间是肯定有问题啦，vector和list毕竟都新开了

执行用时：20 ms, 在所有 C++ 提交中击败了78.28%的用户

内存消耗：13.6 MB, 在所有 C++ 提交中击败了22.22%的用户

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int>nums;
    ListNode* Create(){
        //创建链表
        ListNode*head,*pre,*p;
        head=NULL;
        for(int i=0;i<nums.size();i++){
            p=new ListNode(nums[i]);
            if(head==NULL){
                head=p;
                pre=p;
            }else{
                pre->next=p;
                pre=p;
            }
        }
        return head;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode*p,*pre;
        for(int i=0;i<lists.size();i++){
            p=pre=lists[i];
            while(p){
                nums.push_back(p->val);
                pre=p;
                p=p->next;
            }
        }
        sort(nums.begin(),nums.end());
        return Create();
    }
};

2.3 下一个排列

这题如果会STL中的next_permutation的话，基本上毫无难度……就一行代码就非常优雅地AK了，可能也没有很卡空间叭

执行用时：4 ms, 在所有 C++ 提交中击败了73.82%的用户

内存消耗：11.8 MB, 在所有 C++ 提交中击败了46.67%的用户

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
       next_permutation(nums.begin(),nums.end());
    }
};

参考的非STL题解，可以说很nice容易理解了,但是我还没有复现……emm,留个坑到周末（要不要开一个周末”查漏补缺“专题捏😁）

2.4 最长有效括号

两遍遍历，第一遍找出不合法的(，存在的主要问题是，如果第一次不标记，无法成功识别并切割()(()这种样例，两遍遍历以及标记的代价是空间复杂度会比较糟糕:

执行用时：4 ms, 在所有 C++ 提交中击败了68.91%的用户

内存消耗：7.3 MB, 在所有 C++ 提交中击败了11.74%的用户

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s==""){
            return 0;
        }
        //找出最长的括号字串的长度
        int len=s.length();
        vector<bool>good(len);
        fill(good.begin(),good.end(),true);
        stack<char>st;
        stack<int>pos;
        int cnt=0;
        int ans=0;
        //先将（没有办法配对的标记出来
        for(int i=0;i<len;i++){
            if(s[i]=='('){
                st.push(s[i]);
                pos.push(i);
            }else{
                if(st.empty()){
                    //不合法
                }else{
                    st.pop();
                    pos.pop();
                }
            }
        }
        while(!st.empty()){
            good[pos.top()]=false;
            st.pop();
            pos.pop();
        }
        //重新遍历
        for(int i=0;i<len;i++){
            if(s[i]=='('){
                if(good[i]){
                    st.push(s[i]);
                }else{
                    ans=max(ans,cnt);
                    cnt=0;
                }
            }else{
                if(st.empty()){
                    //不合法
                    ans=max(ans,cnt);
                    cnt=0;
                }else{
                    cnt+=2;
                    st.pop();
                }
            }
        }
        ans=max(ans,cnt);
        return ans;
    }
};