wy的leetcode刷題記錄_Day81

聲明

本文章的所有題目信息都來源于leetcode
如有侵權請聯系我刪掉!
時間：2024-3-4

前言

232. 用棧實現隊列

今天的每日一題是：232. 用棧實現隊列

題目介紹

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

• void push(int x) 將元素 x 推到隊列的末尾
• int pop() 從隊列的開頭移除并返回元素
• int peek() 返回隊列開頭的元素
• .boolean empty() 如果隊列為空，返回 true ；否則，返回 false
  說明：

你只能使用標準的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

示例 1：

輸入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2],[], [], []]
輸出：
[null, null, null, 1, 1, false]
解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路

本題是一道簡單的題，我們只需要使用倆個棧一個輸入棧一個輸出棧，輸入棧用來存貯push到隊列中的元素，輸出棧用來保存隊列。push時將隊列元素輸入到輸入棧，pop時將輸入棧中所有元素pop到輸出棧中保存，此時輸出棧的pop順序就是隊列順序。

代碼

class MyQueue {
public:stack<int> stk_in;stack<int> stk_out;MyQueue() {}void push(int x) {stk_in.push(x);}int pop() {if(stk_out.empty()){while(!stk_in.empty()){int x=stk_in.top();stk_in.pop();stk_out.push(x);}}int x=stk_out.top();stk_out.pop();return x;}int peek() {if(stk_out.empty()){while(!stk_in.empty()){int x=stk_in.top();stk_in.pop();stk_out.push(x);}}return stk_out.top();}bool empty() {return stk_in.empty()&&stk_out.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

收獲

一道非常簡單且基礎的題。

138. 隨機鏈表的復制

138. 隨機鏈表的復制

題目介紹

給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節點或空節點。

構造這個鏈表的 深拷貝。 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的 next 指針和 random 指針也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點 。

例如，如果原鏈表中有 X 和 Y 兩個節點，其中 X.random --> Y 。那么在復制鏈表中對應的兩個節點 x 和 y ，同樣有 x.random --> y 。

返回復制鏈表的頭節點。

用一個由 n 個節點組成的鏈表來表示輸入/輸出中的鏈表。每個節點用一個 [val, random_index] 表示：

• val：一個表示 Node.val 的整數。
• random_index：隨機指針指向的節點索引（范圍從 0 到 n-1）；如果不指向任何節點，則為 null 。

你的代碼 只 接受原鏈表的頭節點 head 作為傳入參數。

示例 1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

示例 3：

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

思路

正常的鏈表深拷貝就僅僅只需要將節點的值以及節點的后續指針拷貝即可，本題的難點就在節點還包含一個隨機指針指向隨機的一個節點。假設在我們一個一個深拷貝檢點時深拷貝一個節點的隨機指針時，這個隨即指針指向的新節點并未創建那么就會造成指向不明的后果。所以對于每一個節點，我們將遞歸的深拷貝其后續指針和隨即指針，并使用哈希表將原節點與新節點相映射。

代碼

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:unordered_map<Node*,Node*> cacheNode;Node* copyRandomList(Node* head) {  if(head==nullptr){return nullptr;}if(!cacheNode.count(head)){Node* newHead=new Node(head->val);cacheNode[head]=newHead;newHead->next=copyRandomList(head->next);newHead->random=copyRandomList(head->random);}return cacheNode[head];}
};

另一種解法請參考題解：

class Solution {
public:Node* copyRandomList(Node* head) {if (head == nullptr) {return nullptr;}for (Node* node = head; node != nullptr; node = node->next->next) {Node* nodeNew = new Node(node->val);nodeNew->next = node->next;node->next = nodeNew;}for (Node* node = head; node != nullptr; node = node->next->next) {Node* nodeNew = node->next;nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;}Node* headNew = head->next;for (Node* node = head; node != nullptr; node = node->next) {Node* nodeNew = node->next;node->next = node->next->next;nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;}return headNew;}
};

收獲

遞歸的使用大大簡化了代碼。

141. 環形鏈表

141. 環形鏈表

題目介紹

給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞 。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環 ，則返回 true 。 否則，返回 false 。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

思路

快慢指針，使用步長不等的指針進行遍歷，如果倆個指針重新相遇說明存在換否則不存在。

代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(head==nullptr||head->next==nullptr)return false;      ListNode* low=head;ListNode* high=head->next;while(low!=high){if(high==nullptr||high->next==nullptr)return false;low=low->next;high=high->next->next;}return true;}
};

收獲

雙指針的應用。

142. 環形鏈表 II

142. 環形鏈表 II

題目介紹

給定一個鏈表的頭節點 head ，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改 鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

思路

本題很巧去看題解！題解

代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head==nullptr||head->next==nullptr)return nullptr;      ListNode* low=head;ListNode* high=head;while(low!=high){if(high==nullptr||high->next==nullptr)return nullptr;low=low->next;high=high->next->next;}high=head;while(low!=high){low=low->next;high=high->next;}return high;}
};

收獲

雙指針的應用。