今天先来三道力扣题
第一题：
原题链接如下
https://leetcode-cn.com/problems/palindrome-linked-list/
一道链表题，方法有多种。我最开始做的方法是用数组记录链表的每个结点，将链表转换成数组，然后就用数组的方法去写。
bool isPalindrome(struct ListNode* head){
int a[100000],k=0;
while(head)
{
a[k++] = head->val;
head = head->next;
}
int i=0,j=k-1;
while(i<j)
{
if(a[i]!=a[j])
return false;
i++;
j--;
}
return true;
}
但还有空间复杂度更低的方法，直接对链表进行操作，将链表后半部分反转过来，然后进行匹配。
那么如何对链表后半部分进行反转呢，首先得找到链表中间的位置，这里我们考虑用快慢指针法，定义一个慢指针slow和一个快指针fast，慢指针移动一个结点时快指针移动两个结点，这样当快指针遍历到链表末尾时，慢指针就在链表的中间位置。（注意奇偶问题）
while(fast)
{
slow = slow->next;
fast = fast->next ? fast->next->next : fast->next;
}
如图是slow指针和fast指针的指向，接着我们要更改后半段链表指针的指向，这里我们需要借助另外两个指针（可以定义为pre和temp）,为什么要两个指针呢？首先我们需要更改slow的指向吧，令它指向NULL，然后slow需要移动到下一个结点，然后再指向上一个结点。可这时slow的指向已经改变了，因此我们需要定义一个指针变量temp率先移动到slow的下一个结点，再更改slow的指向，我们可以用pre表示slow的上一个结点，pre初始为NULL。
更改指向后使pre移动到slow，再使slow移动到temp就行了，重复这个过程到链表尾部。
最后就是这样。
代码如下：
while(slow)
{
struct ListNode* temp = slow->next; //移动到slow的下一个结点
slow->next = pre; //改变slow的指向
pre = slow; //上一个结点移动到当前位置
slow = temp; //slow移动到temp
}
最后只需要同时遍历头结点和pre就行了判断是否相等。
完整代码如下：
bool isPalindrome(struct ListNode* head){
struct ListNode* slow=head,*fast=head,*pre = NULL;
while(fast)
{
slow = slow->next;
fast = fast->next ? fast->next->next : fast->next;
}
while(slow)
{
struct ListNode* temp = slow->next; //移动到slow的下一个结点
slow->next = pre; //改变slow的指向
pre = slow; //上一个结点移动到当前位置
slow = temp; //slow移动到temp
}
while(head && pre)
{
if(head->val != pre->val)
return false;
head = head->next;
pre = pre->next;
}
return true;
}
第二题属于栈的题目。
https://leetcode-cn.com/problems/valid-parentheses/
括号匹配以前做过类似的题。
具体思路是将括号的左半部分压入栈中，栈顶元素碰到匹配的右括号时，将栈顶元素弹出栈，若遇到的右括号 与栈顶元素不匹配或栈内没有元素则返回false。最后判断站内是否含有元素，若含有则返回false,没有则返回true。
代码如下：
bool isValid(char * s){
char a[10001];
int i,len = strlen(s);
int top = 0;
for(i=0;i<len;i++)
{
if(s[i]=='('||s[i]=='['||s[i]=='{')
a[++top] = s[i];
else if(a[top]=='('&&s[i]==')'||a[top]=='['&&s[i]==']'||a[top]=='{'&&s[i]=='}')
top--;
else
return false;
}
if(top==0)
return true;
return false;
}
第三题了！
https://leetcode-cn.com/problems/valid-parenthesis-string/
咋一看又是一道括号匹配的题，先入为主就想用栈来写了。
我先提供一种用栈的方法，由于*可以变成’（‘或者’）‘或者空字符，这里我们考虑用两个栈，一个栈用来存’（‘一个用来存’*‘,当碰到’）‘时优先将存储’（‘的栈顶元素弹出，若存储'（'的栈内没有元素，则弹出存储‘*’的栈顶元素（ 视作‘*“变成了’（' )，若两个栈内都没有元素，则说明右括号无法匹配完全，返回false,若整个过程都能匹配，还需判断‘（’能否全部匹配，从后往前按照相同的方法再遍历一遍就行了。
参考代码入下：
bool checkValidString(char * s){
int a[101],b[101];
int len = strlen(s),i,top1=0,top2=0;
for(i=0;i<len;i++)
{
if(s[i]=='(')
a[++top1] = i;
else if(s[i]=='*')
b[++top2] = i;
else if(s[i]==')'&&top1>0)
top1--;
else if(s[i]==')'&&top2>0)
top2--;
else
return false;
}
top1=0,top2=0;
for(i=len-1;i>=0;i--)
{
if(s[i]==')')
a[++top1] = i;
else if(s[i]=='*')
b[++top2] = i;
else if(s[i]=='('&&top1>0)
top1--;
else if(s[i]=='('&&top2>0)
top2--;
else
return false;
}
return true;
}
其实这题还有更简单的方法，用贪心解决，
设想一下，我们可以用一个变量来表示未匹配的左括号数，当遇到‘（’时使该变量加1，遇到‘）’时使该变量减1，那么遇到‘*'时该怎么办呢？由于’*‘可能变成’（‘可能变成’）‘还可能变成空字符，对该变量的影响分别就是加1，减1，不变。因此我们可以定义两个变量来确定这个范围的最大值和最小值，在这过程中出现范围最大值小于0的情况，则直接返回false(表示最左端为’）‘无法完成匹配），若出现范围最小值小于0的情况则最小值变成0（未匹配的括号数不能为负数），最后进行判断，如果整个范围包括0（即最小值为0），说明整个过程能完成匹配。
bool checkValidString(char * s){
int len=strlen(s);
int min=0,max=0,i;
for(i=0;i<len;i++)
{
if(s[i]=='(')
{
min++;
max++;
}
else if(s[i]==')')
{
min--;
max--;
if(min<0)
min=0;
if(max<0)
return false;
}
else
{
min--;
max++;
if(min<0)
min=0;
}
}
if(min==0)
return true;
return false;
}
终于写完啦！！！
文中代码可能写的冗长，我尽量用简单的方式呈现给大家！希望大家不要建议。
与君共勉！
看到这里你也累了吧，不妨三连一波！！！