【每日刷题】Day38
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 2696. 删除子串后的字符串最小长度 - 力扣（LeetCode）
2. LCR 123. 图书整理 I - 力扣（LeetCode）
3. 面试题 02.06. 回文链表 - 力扣（LeetCode）
1. 2696. 删除子串后的字符串最小长度 - 力扣（LeetCode）
//思路：栈。遍历字符串，如果遇到'B'且栈顶元素为'A'，出栈；如果遇到'D'且栈顶元素为'C'，出栈；其余情况入栈。
int minLength(char * s)
{
int count = 1;
char* Stack = (char*)malloc(sizeof(char)*strlen(s)+1);
Stack[0] = s[0];
int i = 1;
while(i<strlen(s))
{
if((count&&s[i]=='B'&&Stack[count-1]=='A')||(count&&s[i]=='D'&&Stack[count-1]=='C'))//出栈情况
{
count--;
}
else//入栈
{
Stack[count++] = s[i];
}
i++;
}
Stack[count] = '\0';
return strlen(Stack);
}
2. LCR 123. 图书整理 I - 力扣（LeetCode）
//思路：栈。利用栈将数组逆置。
int* reverseBookList(struct ListNode* head, int* returnSize)
{
int* Stack = (int*)malloc(sizeof(int)*10000);
int count = 0;
int* ans = (int*)malloc(sizeof(int)*10000);
struct ListNode* pmove = head;
while(pmove)
{
Stack[count++] = pmove->val;
pmove = pmove->next;
}
int size = 0;
while(--count>=0)
{
ans[size++] = Stack[count];
}
*returnSize = size;
return ans;
}
3. 面试题 02.06. 回文链表 - 力扣（LeetCode）
//思路：将链表节点入栈，对栈进行入栈出栈操作，最后判断栈是否为空，为空则说明链表为回文结构，否则不是。注意：这里需要考虑链表长度为奇数和偶数的情况
bool isPalindrome(struct ListNode* head)
{
if(!head)
{
return true;
}
if(!head->next)
{
return true;
}
int count = 0;
int flag = 0;
struct ListNode* pmove = head;
while(pmove)//计算链表长度
{
count++;
pmove = pmove->next;
}
pmove = head->next;
int* arr = (int*)malloc(sizeof(int)*count);
arr[0] = head->val;
int num = 1;
if(count%2)//如果链表长度为奇数，则当遍历到链表中间节点时不能够进行入栈出栈操作，直接跳过
{
while(pmove)
{
flag++;
if(flag==count/2)//遍历到链表中间节点，不进行操作，直接跳过
{
pmove = pmove->next;
continue;
}
if(num&&pmove->val==arr[num-1])//如果当前节点值与栈顶元素相同，则出栈
{
num--;
}
else//否则，入栈
{
arr[num++] = pmove->val;
}
pmove = pmove->next;
}
}
else//偶数情况
{
while(pmove)//与奇数类似，省去了遍历到链表中间节点的情况
{
if(num&&pmove->val==arr[num-1])
{
num--;
}
else
{
arr[num++] = pmove->val;
}
pmove = pmove->next;
}
}
return num==0;
}
