leetcode刷题笔记

STL set用法

特点：集合，元素唯一，对元素自动进行升序排序;
set s;

s.begin();
s.end();
s.insert(x); //插入x元素
s.erase(x);  s.erase(it) //删除x元素 ,it迭代器指向元素
s.find(x); //查找x元素,不存在则返回s.end()
s.lower_bound(x); //大于或等于x，得到定位器

22. 括号生成

1. 暴力递归解法:得到n对”()”的全排列情况，验证平衡；
   时间复杂度O(2^2n);

   class Solution {
   public:
       vector<string> result;
       
       // '('==1  ; ')'==-1
       bool vaild(int array[],int len){
           int res=0;
           for(int i=0;i<len;i++){
               res+=array[i];
               if(res<0)return false;
           }
           return (res==0);
       }
       
       void generate(int arr[],int pos,int len){
           if(pos == len){
               //判断是否有效
               if(vaild(arr,len)){
                   //将数组转换为string
                   string temp="";
                   for(int i=0;i<len;i++){
                       if(arr[i]==1)temp+="(";
                       else temp+=")";
                   }
                   result.push_back(temp);
                   // ncout<<result.size();
               }
           }
           else {
               arr[pos]=1;
               generate(arr,pos+1,len);
               arr[pos]=-1;
               generate(arr,pos+1,len);
           }
       }
       
       vector<string> generateParenthesis(int n) {
           int *arr=new int[2*n];
           generate(arr,0,2*n);
           return result;
       }
   };

2. 动态规划：初始状态为0的””,1的”()”，接下来的值根据前面得到的：(p组括号的所有可能情况)+q组括号的所有可能情况,其中p+q=n-1;

   class Solution {
   public:
       vector<string> generateParenthesis(int n) {
           vector<vector<string> >dp(n+1);
           dp[0]={""};
           dp[1]={"()"};
           if(n==1||n==0)return dp[n];
           for(int i=2;i<=n;i++){
               for(int j=0;j<i;j++){
                   for(int x=0;x<dp[j].size();x++){
                       for(int y=0;y<dp[i-j-1].size();y++){
                           string res="("+dp[j][x]+")"+dp[i-j-1][y];
                           dp[i].push_back(res);
                       }
                   }
               }
           }
           return dp[n];
       }
   };

23.合并K个排序链表

1. 最简单粗暴的链表操作：

• 原始k个链表已排好序；
• 在每个列表的表头筛选最小值，即结果链表的下一个值
• 更新获得最小值的当前链表的下一个值
• 重复第2步，循环直到所有k个链表到达结尾；

时间复杂度O(m*k),m为所有k个链表结点总数；额外的空间复杂度O(m);

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int findMin(vector<ListNode*>& lists){
        int len=lists.size();
        int min=99999999;
        int minindex=-1;
        for(int i=0;i<len;i++){
            if(lists[i]!=NULL && lists[i]->val<min){
                min=lists[i]->val;
                minindex=i;
            }
        }
        
        return minindex;//-1结束：所有链表都已遍历完成
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head=new ListNode(0);
        ListNode *pre=head;
        int pos=0;
        while((pos=findMin(lists))>=0){
            ListNode *newnode=new ListNode(lists[pos]->val);

            //找到最小下标，进行一定操作
            if(lists[pos]->next!=NULL)lists[pos]=lists[pos]->next;
            else lists[pos]=NULL;
        
            pre->next=newnode;
            pre=newnode;
        }
        return head->next;
    }
};

2. 分治法:将链表两两合并（递归）;
   时间复杂度:O(mlogk),空间复杂度O(1);

   /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
    * };
    */
   class Solution {
   public:
       ListNode* MergeTwoSortedList(ListNode* l1,ListNode* l2){
           if(l1==NULL){
               return l2;
           }
           if(l2==NULL){
               return l1;
           }
           if(l1->val <= l2->val){
               l1->next=MergeTwoSortedList(l1->next,l2);
               return l1;
           }
           l2->next=MergeTwoSortedList(l1,l2->next);
           return l2;
       }
       
       ListNode* mergeKLists(vector<ListNode*>& lists,int left,int right){
           //最小分治，左右边界相等
           if( left == right ){
               return lists[left];
           }
           int mid=(left+right)/2;
           ListNode* l1=mergeKLists(lists,left,mid);
           ListNode* l2=mergeKLists(lists,mid+1,right);
           return MergeTwoSortedList(l1,l2);
       }
       
       ListNode* mergeKLists(vector<ListNode*>& lists) {
           int len=lists.size();
           if(len==0)return NULL;
           ListNode* res=mergeKLists(lists,0,len-1);
           return  res;
       }
   };