网站默认中文字体,南京建企业网站哪家好,建站公司不给源码,wordpress旅游类网站模板wy的leetcode刷题记录_Day81
声明
本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间#xff1a;2024-3-4
前言 目录 wy的leetcode刷题记录_Day81声明前言232. 用栈实现队列题目介绍思路代码收获 138. 随机链表的复制题目介绍思路代码收获 141. 环形链表题…wy的leetcode刷题记录_Day81
声明
本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间2024-3-4
前言 目录 wy的leetcode刷题记录_Day81声明前言232. 用栈实现队列题目介绍思路代码收获 138. 随机链表的复制题目介绍思路代码收获 141. 环形链表题目介绍思路代码收获 142. 环形链表 II题目介绍思路代码收获 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:stackint stk_in;stackint stk_out;MyQueue() {}void push(int x) {stk_in.push(x);}int pop() {if(stk_out.empty()){while(!stk_in.empty()){int xstk_in.top();stk_in.pop();stk_out.push(x);}}int xstk_out.top();stk_out.pop();return x;}int peek() {if(stk_out.empty()){while(!stk_in.empty()){int xstk_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_mapNode*,Node* cacheNode;Node* copyRandomList(Node* head) { if(headnullptr){return nullptr;}if(!cacheNode.count(head)){Node* newHeadnew Node(head-val);cacheNode[head]newHead;newHead-nextcopyRandomList(head-next);newHead-randomcopyRandomList(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(headnullptr||head-nextnullptr)return false; ListNode* lowhead;ListNode* highhead-next;while(low!high){if(highnullptr||high-nextnullptr)return false;lowlow-next;highhigh-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(headnullptr||head-nextnullptr)return nullptr; ListNode* lowhead;ListNode* highhead;while(low!high){if(highnullptr||high-nextnullptr)return nullptr;lowlow-next;highhigh-next-next;}highhead;while(low!high){lowlow-next;highhigh-next;}return high;}
};收获
双指针的应用。
