个人主页：星纭-CSDN博客
系列文章专栏：Python
踏上取经路，比抵达灵山更重要！一起努力一起进步！
目录
题目一：环形链表
题目二：删除有序数组中的重复项
题目三：有效的括号
题目四：用队列实现栈
题目五：用栈实现队列
题目一：环形链表
题目出处：. - 力扣（LeetCode）/
题目描述：这道题和上一期的环形链表很像只不过，一个是判断是否存在环，一个是求入环节点。
题解思路：采用双指针。定义两个指针fast，slow,fast一次走两步，slow一次走一步。
然后我们来分析一下这道题的数学关系。
相遇点指的是fast指针和slow指针第一次相遇的地方。
当fast和slow相遇的时候，fast行走的距离是slow的两倍，
slow:L + X
fast:2(L + X) = L + X + a * N。a指的是fast进入环后行走的圈数
L = (a - 1) * N + N - X;
N-X就是相遇点到环的距离。也就是说，如果fast从相遇出发，slow从起点出发，均每次走一步。两者第一次相遇的地方就是进入环的节点。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast = head,*slow = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
fast = head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
}
return NULL;
}题目二：删除有序数组中的重复项
题目出处：. - 力扣（LeetCode）
题目描述：给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
这道题的要求是，原地删除，所以空间复杂度是O(1)，因为这个数组是非严格递增的，重复的元素是挨在一起的，即相等的元素在数组中一定是连续的。
解题思路：使用双指针，定义两个指针src,dst.src表示下一个不同元素的下标，dst表示要填入的位置的下标。
dst开始指向0，src开始指向1.如果src和dst相同，src就加1。不相同，dst加1，然后移动元素，然后src也加1.
int removeDuplicates(int* nums, int numsSize) {
int src,dst;
src = 1;
dst = 0;
while(src < numsSize){
if(nums[src] != nums[dst]){
++dst;
nums[dst] = nums[src];
++src;
}
else{
src++;
}
}
int k = dst + 1;
return k;
}题目三：有效的括号
题目出处：. - 力扣（LeetCode）
题目描述 ：
这个题目的示例不够全面，
对于字符串s = "{[]}",这样的字符串也成立，s = "()[{}]"也是成立的，题目所给的示例会让人误以为匹配的括号必须连续，其实不是这样的，这是题目的一个问题。
题目思路：首先需要用C语言手动实现一个栈。
然后我们开始遍历整个字符串：当遇到左括号的时候，就入栈，遇到右括号的时候，就取出栈顶元素，进行匹配，如果不匹配说明这个字符串不有效，反之继续匹配 ，直到结束，该字符串就匹配。关于栈的代码参考前面的文章。
bool isValid(char* s) {
Stack st;
STInit(&st);
while (*s) {
if (*s == '(' || *s == '[' || *s == '{') {
STPush(&st, *s);
} else {
if (IsEmpty(&st)) {
STDestory(&st);
return false;
} else {
char ch = STTop(&st);
STPop(&st);
if ((ch == '(' && *s != ')') || (ch == '[' && *s != ']') ||
(ch == '{' && *s != '}')) {
STDestory(&st);
return false;
}
}
}
++s;
}
bool ret = IsEmpty(&st);
STDestory(&st);
return ret;
}在每次使用return语句之前都要销毁这个栈，避免内存泄漏。
最后为什么是返回ret？
如果遇到这样的字符，不难发现根本没有进入循环，直接返回了true，这明显是不正确的，所以需要进行判断，栈是否为空，如果为空，所以左括号并没匹配完成，这个字符串无效。
题目四：用队列实现栈
题目出处：. - 力扣（LeetCode）
题目描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
解题思路：
如果接下来我们要进行出栈，根据先进后出的规则，那么得到的第一个数据应该是5，可是仅仅在队列一中进行出队列入队列是达不到这样的效果的。
那么如何进行操作呢？
首先我们可以将1-4入队列到队列二中，这样队列一中就只剩下一个数据5了，此时出队列就是5.起到了先进后出的效果。如果还需要放入数据，很明显是放在队列二中，因为此时的队列一已经没有了数据了。
首先需要使用C语言实现一个队列。代码参考前面的文章。
初始化：
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&(pst->q1));
QueueInit(&(pst->q2));
return pst;
}push:
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&(obj->q1))) {
QueuePush(&(obj->q1), x);
} else {
QueuePush(&(obj->q2), x);
}
}新放入的数据，需要放在已经存放有数据的队列。如果两个队列都为空，那么此时随便放在那个队列中都可以。
删除数据：
int myStackPop(MyStack* obj) {
Queue* noempty = &(obj->q1);
Queue* empty = &(obj->q2);
if (!QueueEmpty(&(obj->q2))) {
noempty = &(obj->q2);
empty = &(obj->q1);
}
while (QueueSize(noempty) > 1) {
QueuePush(empty, QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}由于不确定，哪一个队列是空的，所以采用假设法进行判断，出数据的时候，需要将非空队列的数据的前n-1个全部转移到空队列中，留剩下一个出栈即可。
查看栈顶元素：
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&(obj->q2))) {
return QueueBack(&(obj->q2));
} else {
return QueueBack(&(obj->q1));
}
}实现的队列中是，含有查看队尾元素的，非空的队列的队尾元素就是栈顶元素。
判空与销毁：
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}
void myStackFree(MyStack* obj) {
QueueDestory(&(obj->q1));
QueueDestory(&(obj->q2));
free(obj);
}这里的判空，是判断两个队列都是否为空。
题目五：用栈实现队列
题目出处;. - 力扣（LeetCode）
题目描述：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
解题思路：
这道题与上一道题类似
只不过，需要判断空了，入栈的时候只需要把 数据固定存放在一个栈中，push栈，出栈的时候，先出pop栈中的数据，如果栈为空，把push栈的数据导过来。
初始化：
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}入数据：
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}查看数据：
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst)){
while(!STEmpty(&obj->pushst)){
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}首先需要判断popst中是否为空，如果不为空就直接返回即可，为空，就需要向pust中得到数据。
出数据：
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}出数据，直接使用peek函数先查看一下栈顶有没有元素，有才出，否则peek元素会先导数据。
判空与销毁：
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
STDestory(&obj->popst);
STDestory(&obj->pushst);
free(obj);
}
