前言:
而今姐妹们对“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作业答案