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

举报
ceshiren001 发表于 2022/05/07 16:43:23 2022/05/07
【摘要】  关注 @霍格沃兹测试学院 公众号,回复「面试」,领取 BAT 大厂测试面试真题专辑。1. 排序实现有一组“+”和“-”符号,要求将“+”排到左边,“-”排到右边,写出具体的实现方法。答:如果让+等于 0,-等于 1 不就是排序了么from collections import dequefrom timeit import Timers = "++++++----+++----"# 方法一...

:arrow_up: 关注 @霍格沃兹测试学院 公众号,回复「面试」,领取 BAT 大厂测试面试真题专辑。

1. 排序实现

有一组“+”和“-”符号,要求将“+”排到左边,“-”排到右边,写出具体的实现方法。

答:

如果让+等于 0,-等于 1 不就是排序了么

from collections import deque
from 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

2. 单链表反转

答:

单链表反转

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()

3. 交叉链表求交点

答:

# 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

cur1、cur2,2 个指针的初始位置是链表 headA、headB 头结点,cur1、cur2 两个指针一直往后遍历。直到 cur1 指针走到链表的末尾,然后 cur1 指向 headB;直到 cur2 指针走到链表的末尾,然后 cur2 指向 headA;然后再继续遍历。

每次 cur1、cur2 指向 None,则将 cur1、cur2 分别指向 headB、headA。循环的次数越多,cur1、cur2 的距离越接近,直到 cur1 等于 cur2。则是两个链表的相交点。

4. 用队列实现栈 ww

**答: **

下面代码分别使用1个队列和2个队列实现了栈。

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())

5. 找出数据流的中位数

答:

对于一个升序排序的数组,中位数为左半部分的最大值,右半部分的最小值,而左右两部分可以是无需的,只要保证左半部分的数均小于右半部分即可。因此,左右两半部分分别可用最大堆、最小堆实现。

如果有奇数个数,则中位数放在左半部分;如果有偶数个数,则取左半部分的最大值、右边部分的最小值之平均值。分两种情况讨论:

当目前有偶数个数字时,数字先插入最小堆,然后选择最小堆的最小值插入最大堆(第一个数字插入左半部分的最小堆)。当目前有奇数个数字时,数字先插入最大堆,然后选择最大堆的最大值插入最小堆。

  • 最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。

  • 最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。

# -*- 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())

6. 二叉搜索树中第K小的元素

答:

二叉搜索树(BinarySearchTree),又名二叉排序树(BinarySortTree)。二叉搜索树是具有有以下性质的二叉树:

  • 若左子树不为空,则左子树上所有节点的值均小于或等于它的根节点的值。

  • 若右子树不为空,则右子树上所有节点的值均大于或等于它的根节点的值。

左、右子树也分别为二叉搜索树。二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。所以对其遍历一个节点就进行计数,计数达到k的时候就结束。

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

更多技术文章:  https://qrcode.ceba.ceshiren.com/link?name=article&project_id=qrcode&from=hwyun&timestamp=1651908099

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。