wy的leetcode刷题记录_Day81

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-3-4

前言

@TOC

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;
    }
};

收获

双指针的应用。