第20题：有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
思路
首先判断输入字符串的长度是否为偶数，若不是，直接返回false。
（类似栈的想法）建立一个字符串，当前输入的字符为左括号的时候，将当前字符赋值给字符串，当前输入字符为右括号时，判断字符串最后一个字符是否与这个括号匹配，若匹配，字符串最后一个字符置空，若不匹配，返回false，直至所有字符匹配完成。
bool isValid(char * s){
int len = strlen(s);
if(len % 2== 1) return false;
char m[len+1];
int i, j;
j = 0;
for(i = 0; i < len; i++)
{
if(j == 0)
{
if(s[i] == ')' || s[i] == '}' || s[i] == ']') return false;
m[j] = s[i];
j++;
continue;
}
if(s[i] == '}')
{
if(m[j-1] == '{')
{
m[j-1] = 'h';
j--;
continue;
}
else return false;
}
if(s[i] == ']')
{
if(m[j-1] == '[')
{
m[j-1] = 'h';
j--;
continue;
}
else return false;
}
if(s[i] == ')')
{
if(m[j-1] == '(')
{
m[j-1] = 'h';
j--;
continue;
}
else return false;
}
m[j]= s[i];
j++;
}
if(j == 0) return true;
else return false;
}
第21题：合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
来源：LeetCode
链接：21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *s, *t, *m;
if(!list1 && !list2) return NULL;
if(!list1 && list2) return list2;
if(!list2 && list1 ) return list1;
s = list1;
t = list2;
while(t && t->val < s->val)
{
m = t;
t = t->next;
m->next = s;
s = m;
}
list1 = s; //注意若是上步骤执行，头结点位置偏移
while(t && s)
{
if(t->val >= s->val && s->next &&t->val < s->next->val)
{
m = t;
t = t->next;
m->next = s->next;
s->next = m;
s = s->next;
}
else if(t->val >= s->val && !s->next)
{
s->next = t;
return list1;
}
else s = s->next;
}
return list1;
}
第22题：括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
来源：LeetCode
链接：22. 括号生成 - 力扣（LeetCode） (leetcode-cn.com)
思路*
将所有可能的数组进行排列，同时用balance代表已经排列的字符中左括号比右括号多的数目，当balance<0时当前排列不符合条件；当balance=0且已经排列出2*n个括号，则当前排列符合条件。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define sum 2048
void match(char **ans, int n, int balance, int *returnSize, char *tmp, int dos)
{
if( balance < 0) return;
int i;
if(dos == 2*n && balance==0)
{
tmp[2*n] = '\0';
ans[*returnSize] = (char *)malloc(sizeof(char) * (2*n+1));
strcpy(ans[*returnSize], tmp);
*returnSize += 1;
return;
}
if(dos == 2*n && balance > 0) return;
tmp[dos] = '(';
match(ans, n, balance+1, returnSize, tmp, dos+1);
tmp[dos]= ')';
match(ans, n, balance-1, returnSize, tmp, dos+1);
}
char ** generateParenthesis(int n, int* returnSize){
*returnSize = 0;
int i, j, k;
char **ans = (char **)malloc(sizeof(char*) * sum);
char *tmp = (char*)malloc(sizeof(char) * (2*n + 1));
match(ans, n, 0, returnSize, tmp,0 );
return ans;
}
第23题：合并k个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
来源：LeetCode
链接：23. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)
思路
将链表两两合并。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *s, *t, *m;
if(!list1 && !list2) return NULL;
if(!list1 && list2) return list2;
if(!list2 && list1 ) return list1;
s = list1;
t = list2;
while(t && t->val < s->val)
{
m = t;
t = t->next;
m->next = s;
s = m;
}
list1 = s; //注意若是上步骤执行，头结点位置偏移
while(t && s)
{
if(t->val >= s->val && s->next &&t->val < s->next->val)
{
m = t;
t = t->next;
m->next = s->next;
s->next = m;
s = s->next;
}
else if(t->val >= s->val && !s->next)
{
s->next = t;
return list1;
}
else s = s->next;
}
return list1;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
int i;
if(listsSize == 0) return NULL;
struct ListNode *sum;
sum = lists[0];
for(i = 1; i < listsSize; i++)
{
sum = mergeTwoLists(sum, lists[i]);
}
return sum;
}
第24题：两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
来源：LeetCode
链接：24. 两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
if(!head) return NULL;
struct ListNode *s, *t, *m, *k;
s = head;
if(s && s->next)
{
t = s->next;
m = s;
s = t->next;
t->next = m;
m->next = s;
k = m;
head = t;
}
while(s && s->next)
{
t = s->next;
m = s;
s = t->next;
t->next = m;
m->next = s;
k->next = t; //注意，交换后前一个结点的前驱也要链接
k = m;
}
return head;
}
