Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点

简介: Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点

1. 用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

示例:

输入:

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

输出:

[null, null, null, 2, 2, false]


解释: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False

提示:

  • 1 <= x <= 9
  • 最多调用100pushpoptopempty
  • 每次调用 poptop 都保证栈不为空

进阶:你能否实现每种操作的均摊时间复杂度为 O(1) 的栈?换句话说,执行 n 个操作的总时间复杂度 O(n) ,尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

出处:

https://edu.csdn.net/practice/25389378

代码:

class MyStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
        self.help = []
    def push(self, x):
        """
        Push element x onto stack.
        """
        while len(self.queue) != 0:
            self.help.append(self.queue.pop(0))
        self.queue.append(x)
        while len(self.help) > 0:
            self.queue.append(self.help.pop(0))
    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        """
        de = self.queue.pop(0)
        return de
    def top(self):
        """
        Get the top element.
        """
        de = self.queue[0]
        return de
    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        if len(self.queue) == 0:
            return True
        return False
# %%
myStack = MyStack();
myStack.push(1)
myStack.push(2)
print(myStack.top())
print(myStack.pop())
print(myStack.empty())

输出:

2

2

False


2. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式(/faq/#binary-tree)。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

示例 1:

输入:root = [1,2,3,null,null,4,5]

输出:[1,2,3,null,null,4,5]


示例 2:

输入:root = []

输出:[]


示例 3:

输入:root = [1]

输出:[1]


示例 4:

输入:root = [1,2]

输出:[1,2]


提示:

  • 树中结点数在范围 [0, 104]
  • -1000 <= Node.val <= 1000

出处:

https://edu.csdn.net/practice/25389379

代码:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        if root == None:
            return "null,"
        left_serialize = self.serialize(root.left)
        right_serialize = self.serialize(root.right)
        return str(root.val) + "," + left_serialize + right_serialize
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def dfs(queue):
            val = queue.popleft()
            if val == "null":
                return None
            node = TreeNode(val)
            node.left = dfs(queue)
            node.right = dfs(queue)
            return node
        from collections import deque
        queue = deque(data.split(","))
        return dfs(queue)
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

3. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]

输出:[2,1,4,3]


示例 2:

输入:head = []

输出:[]

示例 3:

输入:head = [1]

输出:[1]


提示:

  • 链表中节点的数目在范围 [0, 100]
  • 0 <= Node.val <= 100

进阶:你能在不修改链表节点值的情况下解决这个问题吗?(也就是说,仅修改节点本身。)

出处:

https://edu.csdn.net/practice/25389380

代码:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class LinkList:
    def __init__(self):
        self.head=None
    def initList(self, data):
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
    def    convert_list(self,head):
        ret = []
        if head == None:
            return
        node = head
        while node != None:
            ret.append(node.val)
            node = node.next
        return ret
class Solution(object):
    def swapPairs(self, head):
        dummyHead = ListNode(-1)
        dummyHead.next = head
        prev, p = dummyHead, head
        while p != None and p.next != None:
            q, r = p.next, p.next.next
            prev.next = q
            q.next = p
            p.next = r
            prev = p
            p = r
        return dummyHead.next
# %%
l = LinkList()
head = [1,2,3,4]
l1 = l.initList(head)
s = Solution()
print(l.convert_list(s.swapPairs(l1)))

输出:

[2, 1, 4, 3]


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
7天前
|
Python
Python实现数据结构(如:链表、栈、队列等)。
Python实现数据结构(如:链表、栈、队列等)。
260 0
|
7天前
|
存储
线性表、链表、栈和队列的初始化
线性表、链表、栈和队列的初始化
17 1
|
7天前
数据结构 模拟实现Queue队列(双链表模拟)
数据结构 模拟实现Queue队列(双链表模拟)
26 1
|
7天前
|
存储 Python
如何在Python中实现单向链表和双向链表?
如何在Python中实现单向链表和双向链表?
|
7天前
|
Python 人工智能
讯飞星火、文心一言和通义千问同时编“贪吃蛇”游戏,谁会胜出?
讯飞星火、文心一言和通义千问同时编“贪吃蛇”游戏,谁会胜出?
54 1
讯飞星火、文心一言和通义千问同时编“贪吃蛇”游戏,谁会胜出?
|
7天前
|
Shell Unix Linux
Linux 终端命令之文件浏览(3) less
Linux 终端命令之文件浏览(3) less
35 0
Linux 终端命令之文件浏览(3) less
|
算法 Python
<LeetCode天梯>Day024 删除链表中的节点 | 初级算法 | Python
<LeetCode天梯>Day024 删除链表中的节点 | 初级算法 | Python
<LeetCode天梯>Day024 删除链表中的节点 | 初级算法 | Python
|
1天前
|
存储 算法 安全
Python编程实验六:面向对象应用
Python编程实验六:面向对象应用
15 1
|
1天前
|
Python
Python编程作业五:面向对象编程
Python编程作业五:面向对象编程
13 1
|
1天前
|
存储 人工智能 自然语言处理
Python编程实验五:文件的读写操作
Python编程实验五:文件的读写操作
8 0