1. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
进阶：你能否实现每种操作的均摊时间复杂度为 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：
示例 2：
示例 3：
示例 4：
提示：
- 树中结点数在范围
[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]
