龙空技术网

Python最常见的170道面试题全解析答案(三)

编程玉子 296

前言:

而今姐妹们对“python123作业答案”可能比较看重,姐妹们都想要了解一些“python123作业答案”的相关资讯。那么小编在网摘上收集了一些关于“python123作业答案””的相关内容,希望姐妹们能喜欢,朋友们一起来学习一下吧!

123. 用 Python 实现一个二分查找的函数

答:

def binary_search(arr, target):

n = len(arr)

left = 0

right = n-1

while left <= right :

mid = (left + right)//2

if arr[mid] < target:

left = mid + 1

elif arr[mid] > target:

right = mid - 1

else:

print(f"index:{mid},value:{arr[mid]}")

return True

return False

if name == ‘main’:

l = [1,3,4,5,6,7,8]

binary_search(l,8)

小编是一名python开发工程师,这里有我自己整理了一套最新的python系统学习教程,包括从基础的python脚本到web开发、爬虫、数据分析、数据可视化、机器学习等。想要这些资料的可以关注小编,并在后台私信小编:“01”即可领取

124. Python 单例模式的实现方法

答:实现单例模式的方法有多种,之前再说元类的时候用 call 方法实现了一个单例模式,另外 Python 的模块就是一个天然的单例模式,这里我们使用 new 关键字来实现一个单例模式。

“”"

通过 new 函数实现简单的单例模式。

“”"

class Book:

def new(cls, title):

if not hasattr(cls, “_ins”):

cls._ins = super().new(cls)

print(‘in new’)

return cls._ins

def init(self, title):

print(‘in init’)

super().init()

self.title = title

if name == ‘main’:

b = Book(‘The Spider Book’)

b2 = Book(‘The Flask Book’)

print(id(b))

print(id(b2))

print(b.title)

print(b2.title)

125. 使用 Python 实现一个斐波那契数列

答: 斐波那契数列:数列从第 3 项开始,每一项都等于前两项之和。

def fibonacci(num):

“”"

获取指定位数的列表

:param num:

:return:

“”"

a, b = 0, 1

l = []

for i in range(num):

a, b = b, a + b

l.append(b)

return l

if name == ‘main’:

print(fibonacci(10))

126. 找出列表中的重复数字

答:

“”"

从头扫到尾,只要当前元素值与下标不同,就做一次判断,numbers[i]与 numbers[numbers[i]],

相等就认为找到了重复元素,返回 true,否则就交换两者,继续循环。直到最后还没找到认为没找到重复元素。

“”"

-- coding:utf-8 --

class Solution:

def duplicate(self, numbers):

“”"

:param numbers:  :return:  """  if numbers is None or len(numbers) <= 1:      return False  use_set = set()  duplication = {}  for index, value in enumerate(numbers):      if value not in use_set:          use_set.add(value)      else:          duplication[index] = value  return duplication  12345678910111213

if name == ‘main’:

s = Solution()

d = s.duplicate([1, 2, -3, 4, 4, 95, 95, 5, 2, 2, -3, 7, 7, 5])

print(d)

127. 找出列表中的单个数字

答:

def find_single(l :list):

result = 0

for v in l:

result ^= v

if result == 0:

print(“没有落单元素”)

else:

print(“落单元素” ,result)

if name == ‘main’:

l = [1,2,3,4,5,6,2,3,4,5,6]

find_single(l)

128. 写一个冒泡排序

答:

“”"

冒泡排序

“”"

def bubble_sort(arr):

n = len(arr)

for i in range(n - 1):

for j in range(n - i - 1):

if arr[j] > arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

if name == ‘main’:

l = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]

bubble_sort(l)

print(l)

129. 写一个快速排序

答:

“”"

快速排序

“”"

def quick_sort(arr, first, last):

if first >= last:

return

mid_value = arr[first]

low = first

high = last

while low < high:

while low < high and arr[high] >= mid_value:

high -= 1 # 游标左移

arr[low] = arr[high]

while low < high and arr[low] < mid_value:      low += 1  arr[high] = arr[low]  arr[low] = mid_value  1234

quick_sort(arr, first, low - 1)

quick_sort(arr, low + 1, last)

if name == ‘main’:

l = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]

quick_sort(l, 0, len(l) - 1)

print(l)

130. 写一个拓扑排序

答:

“”"

拓扑排序

对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。

“”"

import pysnooper

from typing import Mapping

@pysnooper.snoop()

def topological_sort(graph: Mapping):

in_degrees = {‘a’: 0, ‘b’: 0, ‘c’: 0, ‘d’: 0, ‘e’: 0, ‘f’: 0}

in_degrees = dict((u, 0) for u in graph)

for u in graph:

for v in graph[u]: # 根据键找出值也就是下级节点

in_degrees[v] += 1 # 对获取到的下级节点的入度加 1

循环结束之后的结果: {‘a’: 0, ‘b’: 1, ‘c’: 1, ‘d’: 2, ‘e’: 1, ‘f’: 4}

Q = [u for u in graph if in_degrees[u] == 0] # 入度为 0 的节点

in_degrees_zero = []

while Q:

u = Q.pop() # 默认从最后一个移除

in_degrees_zero.append(u) # 存储入度为 0 的节点

for v in graph[u]:

in_degrees[v] -= 1 # 删除入度为 0 的节点,以及移除其指向

if in_degrees[v] == 0:

Q.append(v)

return in_degrees_zero

if name == ‘main’:

用字典的键值表示图的节点之间的关系,键当前节点。值是后续节点。

graph_dict = {

‘a’: ‘bf’, # 表示 a 指向 b 和 f

‘b’: ‘cdf’,

‘c’: ‘d’,

‘d’: ‘ef’,

‘e’: ‘f’,

‘f’: ‘’

}

t = topological_sort(graph_dict)

print(t)

131. Python 实现一个二进制计算

答:

“”"

二进制加法

“”"

def binary_add(a: str, b: str):

return bin(int(a, 2) + int(b, 2))[2:]

if name == ‘main’:

num1 = input(“输入第一个数,二进制格式:\n”)

num2 = input(“输入第二个数,二进制格式:\n”)

print(binary_add(num1, num2))

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

答:

“”"

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

如果让+等于 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.39003764func2 1.593012875func3 3.3487415590000005func1 的方式最优,其次是 func2133. 单链表反转

答:

“”"

单链表反转

“”"

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

134. 交叉链表求交点

答:

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  12345

cur1、cur2,2 个指针的初始位置是链表 headA、headB 头结点,cur1、cur2 两个指针一直往后遍历。 直到 cur1 指针走到链表的末尾,然后 cur1 指向 headB; 直到 cur2 指针走到链表的末尾,然后 cur2 指向 headA; 然后再继续遍历; 每次 cur1、cur2 指向 None,则将 cur1、cur2 分别指向 headB、headA。 循环的次数越多,cur1、cur2 的距离越接近,直到 cur1 等于 cur2。则是两个链表的相交点。

135. 用队列实现栈

答: 下面代码分别使用 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  123456

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

136. 找出数据流的中位数

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

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

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

当目前有奇数个数字时,数字先插入最大堆,然后选择最大堆的最大值插入最小堆。 最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。 最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。

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

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

答: ??二叉搜索树(Binary Search Tree),又名二叉排序树(Binary Sort Tree)。 ? 二叉搜索树是具有有以下性质的二叉树:?

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

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

左、右子树也分别为二叉搜索树。

二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。所以对其遍历一个节点就进行计数,计数达到 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

if self.count == k:

self.nodeVal = node.val

# 将该节点的左右子树置为 None,来结束递归,减少时间复杂度

node.left = None

node.right = None

self.dfs(node.right, k)

爬虫相关

138. 在 requests 模块中,requests.content 和 requests.text 什么区别

答: requests.content 获取的是字节,requests.text 获取的是文本内容。

139. 简要写一下 lxml 模块的使用方法框架

答:

from lxml import html

source=’’’

中国

root=html.fromstring(source) _content=root.xpath("string(//div[@class='nam'])")

if _content and isinstance(_content,list):

content=_content[0]

elif isinstance(_content,str):

content=_content

print(content)

标签: #python123作业答案