设python中有模块m、如果希望同时导入m中的所有成员_python-interview-questions
十六进数由数字 0-15 组成，用前缀 0x 或者 0X 表示 16 进制数
`print(hex(16))#0x10
print(hex(15))#0xf
`
121. 怎样声明多个变量并赋值？
**答：**Python 是支持多个变量赋值的，代码示例如下
`#对变量 a,b,c 声明并赋值
a,b,c = 1,2,3
`
算法和数据结构
122. 已知：
`AList = [1,2,3]
BSet = {1,2,3}
`
(1) 从 AList 和 BSet 中 查找 4，最坏时间复杂度哪个大？
(2) 从 AList 和 BSet 中 插入 4，最坏时间复杂度哪个大？
答：
(1) 对于查找，列表和集合的最坏时间复杂度都是 O(n)，所以一样的。
(2) 列表操作插入的最坏时间复杂度为 o(n),集合为 o(1)，所以 Alist 大。
set 是哈希表所以操作的复杂度基本上都是 o(1)。
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)
`
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
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
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.39003764
# func2 1.593012875
# func3 3.3487415590000005
# func1 的方式最优，其次是 func2
`
133. 单链表反转
答：
`"""
单链表反转
"""
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
`
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
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)。
二叉搜索树是具有有以下性质的二叉树：