每周刷題第三期

個人主頁：星紜-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);
}