五、最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
这道题目平常的思路真的不好想。我们还是先看一下几个测试用例：
emm，比较恶心，刚开始没想到的情况是第二种，然后被第三种和第四种恶心到了。
但是我们注意到一个特点：就是碰到右括号代表如果栈中没有和它匹配的左括号，就代表计算一段有效长度括号的结束，我们需要重新开始！！
这道题目主流的解法有三种：1、动态规划(没学，不会)；2、栈；3、正向逆向结合法。
①栈（非常规）
虽说是用栈的方法，不如说是借用了栈的思想，通过下标的方式计算长度。
这里初始化栈的第一个元素为-1有妙用，我们这是在模拟第一个元素为’）‘，但它不是真的’）‘。
它的用处是：
如果碰到元素就是‘）’，而此时栈里面只有-1，那么我们就把元素-1弹出去，把栈顶更新为‘）’的下标，因为每当计算最长有效括号终止的原因就是碰到右括号，但同时他也是新的计算长度的开始，但是刚开始没有‘）’，所以我们要模拟一个出来！！
如果碰到左括号，就入栈它的下标，如果遇到右括号就拿出来匹对。计算下标差异得出最长长度。
int longestValidParentheses(char * s) { int length=strlen(s); int stk[length+1]; int top=-1; stk[++top]=-1; int maxlength=0; for(int i=0;i<length;++i) { if(s[i]=='(') { stk[++top]=i; } else { //不是左括号 top--; if(top==-1) { stk[++top]=i;//标记右括号 } else { maxlength=fmax(maxlength,i-stk[top]); } } } return maxlength; }
②正逆结合的方式
这种方式十分巧妙，通过一次正向遍历和一次逆向遍历就可以得出最长长度！
1、如果左括号和右括号的个数相等，就更新最长有效括号为它们的和或任意一个个数的两倍。
2、正向遍历：如果右括号的个数多于左括号，那么就不可能再有左括号和它匹配，就结束这一次计数。
3、逆向遍历：如果左括号的个数多于右括号，那么就不可能再有右括号和它匹配，就结束这一次计数。
说明：
为什么不进行一次遍历？因为只有正向会有左括号个数多于右括号而没有更新最长有效括号的情况：
没有更新最长，而当正向左括号多于右括号的情况时，反向肯定可以求出最长有括号，互补，所以两次遍历就可以求出！！
int longestValidParentheses(char * s) { int left=0; int right=0; int maxans=0; int n=strlen(s); //正是找右括号 for(int i=0;i<n;++i) { if(s[i]=='(') { left++; } else { right++; } if(left==right) { maxans=fmax(maxans,2*right); } else if(right>left) { left=right=0; } } left=right=0; for(int i=n-1;i>=0;--i) { if(s[i]=='(') { left++; } else { right++; } if(left==right) { maxans=fmax(maxans,2*left); } else if(left>right) { left=right=0; } } return maxans; }
六、合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
①排序求解
①取下来排序求解
这种方式比较暴力，就是全部取下来，然后排序，组建新链表。时间复杂度：0(N*logN)，空间复杂度：0(N)
int cmp(const void* x,const void* y) { return *(int*)x-*(int*)y; } struct ListNode* CreateNode(int n) { struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode)); if(newnode==NULL) { perror("malloc fail"); exit(-1); } newnode->next=NULL; newnode->val=n; return newnode; } struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) { //如果你把链表的所有数据都摘下来存到数组，然后排序 if(listsSize==0||lists==NULL) return NULL; int capacity=100; int* arr=(int*)malloc(sizeof(int)*capacity); int j=0; for(int i=0;i<listsSize;++i) { struct ListNode* cur=lists[i]; while(cur) { arr[j++]=cur->val; if(j==capacity) { capacity*=2; int* tmp=(int*)realloc(arr,sizeof(int)*capacity); if(tmp==NULL) { perror("realloc fail"); exit(-1); } arr=tmp; } cur=cur->next; } } if(j==0) return NULL; qsort(arr,j,sizeof(int),cmp); struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur=guard; for(int i=0;i<j;++i) { struct ListNode* newnode=CreateNode(arr[i]); cur->next=newnode; cur=cur->next; } struct ListNode* head=guard->next; free(guard); free(arr); return head; }
②归并递归
②归并递归
对于任意多个链表，我们都可以对无限二分，直到只剩一个链表，这样选出其中两个进行合并，合并为一个有序链表。比如4个链表，先选出两个合并，变成3 个链表，再任意两个合并 变成 2 个再两个合并变成1个即为所求。
对于任意两个链表合并可以使用递归实现。
struct ListNode* dfs(struct ListNode* l1,struct ListNode* l2) { if(l1==NULL) return l2; if(l2==NULL) return l1; if(l1->val<l2->val) { l1->next=dfs(l1->next,l2); return l1; } l2->next=dfs(l1,l2->next); return l2; } struct ListNode* TwoLists(struct ListNode**lists,int l,int r) { if(l==r) return lists[l]; if(l>r) return NULL; int mid=l+(r-l)/2; struct ListNode* l1=TwoLists(lists,l,mid); struct ListNode* l2=TwoLists(lists,mid+1,r); return dfs(l1,l2); } struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) { if(!listsSize) return NULL; return TwoLists(lists,0,listsSize-1); }
