测试面试 | Python 算法与数据结构面试题系列二（附答案）

from collections import dequefrom timeit import Timer
s = "++++++----+++----"
# 方法一def func1():    new_s = s.replace("+", "0").replace("-", "1")    result = "".join(sorted(new_s)).replace("0", "+").replace("1", "-")    return result
# 方法二def func2():    q = deque()    left = q.appendleft    right = q.append    for i in s:        if i == "+":            left("+")        elif i == "-":            right("-")
# 方法三def func3():    data = list(s)    start_index = 0    end_index = 0    count = len(s)    while start_index + end_index < count:        if data[start_index] == '-':            data[start_index], data[count - end_index - 1] = data[count - end_index - 1], data[start_index]            end_index += 1        else :            start_index += 1    return "".join(data)
if __name__ == '__main__':    timer1 = Timer("func1()", "from __main__ import func1")    print("func1", timer1.timeit(1000000))    timer2 = Timer("func2()", "from __main__ import func2")    print("func2", timer2.timeit(1000000))    timer3 = Timer("func3()", "from __main__ import func3")    print("func3", timer3.timeit(1000000))
# 1000000 测试结果# func1 1.39003764# func2 1.593012875# func3 3.3487415590000005# func1 的方式最优，其次是 func2

class Node:    def __init__(self, val=None):        self.val = val        self.next = None
class SingleLinkList:    def __init__(self, head=None):        """链表的头部"""        self._head = head
    def add(self, val:int):    """    给链表添加元素    :param val: 传过来的数字    :return:    """        # 创建一个节点        node = Node(val)        if self._head is None:            self._head = node        else :            cur = self._head        while cur.next is not None:            cur = cur.next  # 移动游标            cur.next = node  # 如果 next 后面没了证明以及到最后一个节点了
def traversal(self):    if self._head is None:        return    else :        cur = self._head        while cur is not None:        print(cur.val)        cur = cur.next
def size(self):    """    获取链表的大小    :return:    """    count = 0    if self._head is None:        return count    else :        cur = self._head        while cur is not None:        count += 1        cur = cur.next        return count
def reverse(self):    """    单链表反转    思路:    让 cur.next 先断开即指向 none，指向设定 pre 游标指向断开的元素，然后    cur.next 指向断开的元素，再把开始 self._head 再最后一个元素的时候.    :return:    """    if self._head is None or self.size() == 1:        return    else :        pre = None        cur = self._head        while cur is not None:            post = cur.next            cur.next = pre            pre = cur            cur = post            self._head = pre  # 逆向后的头节点
if __name__ == '__main__':    single_link = SingleLinkList()    single_link.add(3)    single_link.add(5)    single_link.add(6)    single_link.add(7)    single_link.add(8)    print("对链表进行遍历")    single_link.traversal()    print(f"size:{single_link.size()}")    print("对链表进行逆向操作之后")    single_link.reverse()    single_link.traversal()

# Definition for singly-linked list.class ListNode:    def __init__(self, x):        self.val = x        self.next = None
class Solution:    def getIntersectionNode(self, headA, headB):    """    :tye head1, head1: ListNode    :rtye: ListNode    """    if headA is not None and headB is not None:        cur1, cur2 = headA, headB
    while cur1 != cur2:        cur1 = cur1.next if cur1 is not None else headA        cur2 = cur2.next if cur2 is not None else headB
    return cur1

from queue import Queue# 使用 2 个队列实现class MyStack:    def __init__(self):        """        Initialize your data structure here.        """        # q1 作为进栈出栈，q2 作为中转站        self.q1 = Queue()        self.q2 = Queue()
    def push(self, x):        """        Push element x onto stack.        :type x: int        :rtype: void        """        self.q1.put(x)
    def pop(self):
        """        Removes the element on top of the stack and returns that element.        :rtype: int        """
        while self.q1.qsize() > 1:            self.q2.put(self.q1.get())  # 将 q1 中除尾元素外的所有元素转到 q2 中            if self.q1.qsize() == 1:                res = self.q1.get()  # 弹出 q1 的最后一个元素                self.q1, self.q2 = self.q2, self.q1  # 交换 q1,q2        return res
    def top(self):
        """        Get the top element.        :rtype: int        """        while self.q1.qsize() > 1:            self.q2.put(self.q1.get())  # 将 q1 中除尾元素外的所有元素转到 q2 中            if self.q1.qsize() == 1:                res = self.q1.get()  # 弹出 q1 的最后一个元素                self.q2.put(res)  # 与 pop 唯一不同的是需要将 q1 最后一个元素保存到 q2 中                self.q1, self.q2 = self.q2, self.q1  # 交换 q1,q2        return res
    def empty(self):        """        Returns whether the stack is empty.        :rtype: bool        """        return not bool(self.q1.qsize() + self.q2.qsize())  # 为空返回 True，不为空返回 False    # 使用 1 个队列实现    class MyStack2(object):        def __init__(self):            """            Initialize your data structure here.            """            self.sq1 = Queue()
        def push(self, x):        """        Push element x onto stack.        :type x: int        :rtype: void        """            self.sq1.put(x)
        def pop(self):            """            Removes the element on top of the stack and returns that element.            :rtype: int            """            count = self.sq1.qsize()            if count == 0:                return False            while count > 1:                x = self.sq1.get()                self.sq1.put(x)                count -= 1            return self.sq1.get()
    def top(self):        """        Get the top element.        :rtype: int        """        count = self.sq1.qsize()        if count == 0:            return False        while count:            x = self.sq1.get()            self.sq1.put(x)            count -= 1        return x
    def empty(self):        """        Returns whether the stack is empty.        :rtype: bool        """        return self.sq1.empty()
    if __name__ == '__main__':        obj = MyStack2()        obj.push(1)        obj.push(3)        obj.push(4)        print(obj.pop())        print(obj.pop())        print(obj.pop())        print(obj.empty())

# -*- coding:utf-8 -*-from heapq import *
class Solution:    def __init__(self):        self.maxheap = []        self.minheap = []
    def Insert(self, num):        if (len(self.maxheap) + len(self.minheap)) & 0x1:  # 总数为奇数插入最大堆            if len(self.minheap) > 0:                if num > self.minheap[0]:  # 大于最小堆里的元素                    heappush(self.minheap, num)  # 新数据插入最小堆                    heappush(self.maxheap, -self.minheap[0])  # 最小堆中的最小插入最大堆                    heappop(self.minheap)                else :                    heappush(self.maxheap, -num)            else :                heappush(self.maxheap, -num)        else :  # 总数为偶数 插入最小堆            if len(self.maxheap) > 0:  # 小于最大堆里的元素                if num < -self.maxheap[0]:                    heappush(self.maxheap, -num)  # 新数据插入最大堆                    heappush(self.minheap, -self.maxheap[0])  # 最大堆中的最大元素插入最小堆                    heappop(self.maxheap)                else :                    heappush(self.minheap, num)            else :                heappush(self.minheap, num)
    def GetMedian(self, n=None):        if (len(self.maxheap) + len(self.minheap)) & 0x1:            mid = self.minheap[0]        else :            mid = (self.minheap[0] - self.maxheap[0]) / 2.0        return mid
if __name__ == '__main__':    s = Solution()    s.Insert(1)    s.Insert(2)    s.Insert(3)    s.Insert(4)    print(s.GetMedian())

class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = None
class Solution:    count = 0    nodeVal = 0
    def kthSmallest(self, root, k):        """        :type root: TreeNode        :type k: int        :rtype: int        """        self.dfs(root, k)        return self.nodeVal
    def dfs(self, node, k):
        if node != None:            self.dfs(node.left, k)            self.count = self.count + 1        if self.count == k:            self.nodeVal = node.val            # 将该节点的左右子树置为 None,来结束递归，减少时间复杂度            node.left = None            node.right = None            self.dfs(node.right, k)