首页 > 编程开发 > Python基础教程 >
-
python基础教程之Python知识点(4)
试听地址 https://www.xin3721.com/eschool/pythonxin3721/
''' 二分查找(升序) arr:传入的序列 data:需要查找的数据 ''' def binarySearch(arr,data): len_arr = len(arr) mid = len_arr // 2 if len_arr >= 1: if arr[mid] > data: return binarySearch(arr[0:mid],data) elif arr[mid] < data: return binarySearch(arr[mid+1:],data) else: return True # 列表长度小于1,代表查询结束,没有找到需要的数据 else: return False l = [1,2,3,4,5] print(binarySearch(l,2)) # True print(binarySearch(l,9)) # False
120.找出列表中的重复数字
l = [2,1,3,3,6,2,4,7,2] # 方法一 from collections import Counter print(Counter(l)) # 打印Counter({2: 3, 3: 2, 1: 1, 6: 1, 4: 1, 7: 1}) # 方法二 d = {} for i in l: d[i] = l.count(i) print(d) # 方法三 s = set(l) for i in s: print('%s有%s个' %(i,l.count(i)))
121.写一个冒泡排序、快速排序、拓扑排序
-
冒泡排序
- 原理:一组无序的列表,遍历整个列表,依次比较相邻的两个数,如果后面的数比前面的小,则两数交换位置,第一轮排序过后最大的数字就被排到了末尾,下一轮只用遍历到倒数第二个数即可,以此类推,直到整个列表变为有序(升序)列表即可退出循环。
-
快速排序
- 原理:在一组序列中选取一个基准值(可以随便选,最好选取中间位置的值),循环查找出比基准值小的放在左边,比基准值大的放在右边,然后在左右两边递归重复上面的步骤,知道列表的长度为1或0表示排序结束,返回列表。
-
缺点:
- 基准值的选取对排序的性能有决定性的影响
- 不稳定,比如基准值前后都有和基准值相同的数据,那么相同值就会被放在一边,打乱了之前的相对顺序
- 对于小规模的数据集性能不是很好
l = [33,218,7,96,45,11,4,99,63,28] # 冒泡排序 def bubbling_sort(l): len_l = len(l) # 外层循环控制循环的次数 for i in range(len_l - 1): # 内层循环控制遍历到哪一位 for j in range(len_l - 1 - i): # 如果后一位比前一位小,则交换位置 if l[j+1] < l[j]: l[j],l[j+1] = l[j+1],l[j] return l # 快速排序 def fast_sort(l): # 如果列表的长度等于0或1表示排序结束,返回列表 if len(l) < 2: return l else: # 选取基准值 mid = l[len(l) // 2] # 先把基准值从列表中排序,不然会有重复 l.remove(mid) left = [i for i in l if i < mid] right = [j for j in l if j > mid] return fast_sort(left) + [mid] + fast_sort(right) print('冒泡排序的结果:%s' %bubbling_sort(l)) print('快速排序的结果:%s' %fast_sort(l))
122.python 实现一个二进制计算
a = '10010' # 18 b = '11000' # 24 a,b = int(a,2),int(b,2) # int()第二个参数表示传入的字符串进制数,默认十进制,返回结果十进制 print(bin(a+b)[2:]) # bin(a+b) 返回0b101010,所以要从第三位开始取
123.有一组“+”和“-”符号,要求将“+”排到左边,“-”排到右边,写出具体的实现方法
def symbol_sort(symbols): l1 = list() l2 = list() for s in symbols: if s == '+': l1.append(s) else: l2.append(s) l1.extend(l2) return l1 sym = '+--+++-' print(symbol_sort(sym))
124.单链表反转
反转链表的图例,便于理解:https://blog.csdn.net/songyunli1111/article/details/79416684
class ListNone(): def __init__(self,val): self.val = val self.next = None ''' 主要逻辑步骤: 1.先把第一个节点后的数据保存赋值给一个变量 2.把第一个变量的next赋值为空,即从链表分裂掉第一个节点 3.把声明的指针指向分裂出来的节点 4.最后把链表的头部指针赋值给下一个节点,即指针往后移动一位 如此循环...... ''' def reverseList(head): last = None while head: tmp = head.next head.next = last last = head head = tmp return last l = ListNone(1) l.next = ListNone(3) l.next.next = ListNone(9) l1 = reverseList(l) print(l1.val,l1.next.val,l1.next.next.val) # 打印 9 3 1
125.交叉链表的交叉点(若两个链表有一个公共结点,则该公共节点之后的所有结点都是重合的,及它们的最后一个结点必然重合)
''' 交叉链表逻辑: 若两个链表有一个公共结点,则该公共节点之后的所有结点都是重合的,及它们的最后一个结点必然重合(结构是Y字形) 利用这个特性,可以先获取两个列表的长度,然后长的列表比短的链表先走(len(长)-len(短))个长度,然后两个链表的指针同时往后走 直到找到公共节点,没有找到相交节点返回None ''' class ListNode(): def __init__(self,val,next=None): self.val = val self.next = next # 获取链表长度 def get_length(head): length = 0 while head: length += 1 head = head.next return length # 获取公共节点 def get_cross_node(list_a,list_b): len_a = get_length(list_a) len_b = get_length(list_b) # 给两个链表各声明一个指针 cur_a = list_a cur_b = list_b if len_a > len_b: for i in range(len_a - len_b): cur_a = list_a.next else: for i in range(len_b - len_a): cur_b = list_b.next flag = False while cur_a and cur_b: if cur_a.val == cur_b.val: print(cur_a.val) flag = True break else: cur_a,cur_b = cur_a.next,cur_b.next if not flag: print("链表没有交叉节点") list_a = ListNode('a1',ListNode('a2',ListNode('c1',ListNode('c2',ListNode('c3'))))) list_b = ListNode('b1',ListNode('b2',ListNode('b3',ListNode('c1',ListNode('c2',ListNode('c3')))))) get_cross_node(list_a,list_b)
126.用队列实现栈
''' 栈:先进后出 队列:先进先出 方法一: 逻辑: 进栈push:在一个空的队列中添加元素,然后把另一个非空队列中的元素弹出并追加到该队列后面,所以,总会有一个队列是空的,以此循环追加即可 删除栈顶元素pop: 进栈时已把元素重新排序,所以直接弹出栈顶元素即可 方法二: 使用列表的insert()方法,指定每次插入的元素都放在最前面 ''' # 方法一 class Stack1(): def __init__(self): self.queue_a = [] self.queue_b = [] # 进栈 def push(self,n): if len(self.queue_a) == 0: self.queue_a.append(n) elif len(self.queue_b) == 0: self.queue_b.append(n) # 把队列b中的元素追加到a的后面 if len(self.queue_a) == 1 and len(self.queue_b) > 1: for i in range(len(self.queue_b)): self.queue_a.append(self.queue_b.pop(0)) elif len(self.queue_b) == 1 and len(self.queue_a) >= 1: for i in range(len(self.queue_a)): self.queue_b.append(self.queue_a.pop(0)) # 删除栈顶元素 def pop(self): if self.queue_a: return self.queue_a.pop(0) elif self.queue_b: return self.queue_b.pop(0) else: return None # 查询当前栈内元素 def get_stack(self): if self.queue_a: return self.queue_a elif self.queue_b: return self.queue_b else: return None # 查询栈顶元素: def peek(self): if self.queue_a: return self.queue_a[0] elif self.queue_b: return self.queue_b[0] else: return None # 查询当前栈长度 def len_stack(self): if self.queue_a: return len(self.queue_a) elif self.queue_b: return len(self.queue_b) else: return None # 方法二 class Stack2(): def __init__(self): self.list_a = list() def push(self,num): self.list_a.insert(0,num) def get_stack(self): return self.list_a s = Stack1() s2 = Stack2() for i in range(5): s.push(i) s2.push(i) print(s.get_stack()) # [4,3,2,1,0] print(s.pop()) print(s.get_stack()) print(s.pop()) print(s.get_stack()) print(s.pop()) print(s.get_stack()) print('*'*50) print(s2.get_stack()) # [4,3,2,1,0]
127.找出数据流的中位数
- 中位数:有序列表中间的数。如果列表元素个数是偶数,中位数是中间两个数的平均数;如果是奇数,则就是中间的数
def get_mid(l): l.sort() if len(l) == 0: return elif len(l) == 1: return l[0] else: if len(l) % 2 == 0: mid = (l[len(l) // 2] + l[len(l) // 2 - 1]) / 2 else: mid = l[len(l) // 2] return mid l = [2,15,7,3,100,10] print(get_mid(l)) # 8.5
128.二叉搜索树中第 K 小的元素
- 关于二叉树:https://www.jianshu.com/p/9503238394df
- 关于二叉搜索树:https://www.cnblogs.com/lliuye/p/9118591.html
- 算法:利用二叉搜索树特点(左树都比根节点小,右树都比根节点大),使用中序遍历后结果保存在列表中,其结果一定是有序排序,找出第K-1位元素即可
class Node(): def __init__(self,n): self.val = n self.left = None self.right = None ''' 数据域:节点中存储数据元素的部分 指针域:节点中存储数据元素之间的链接信息,即链接到下一节点地址的部分 内嵌函数: 内部函数需要递归调用并不能实现全部功能,外层函数完成剩余功能,也可以分开写 ''' def kthSmallest(root,k): # l = list() def search_min(root): if not root: return [] # 在内层函数申明列表是因为只需返回最后一次递归的结果,即[10, 12, 15, 16, 20, 21, 22, 23] # 若是申明在外部,则会把每一层递归的结果都追加的列表里 [10,10,12,10,10,12,15,10,10,12,15,16........] l = list() # 递归查询左树数据域 l.extend(search_min(root.left)) l.append(root.val) # 递归查询右树数据域 l.extend(search_min(root.right)) return l return search_min(root)[k-1] n1 = Node(20) n1.left = Node(15) n1.right = Node(22) n1.left.left = Node(12) n1.left.right = Node(16) n1.left.left.left = Node(10) n1.right.left = Node(21) n1.right.right = Node(23) kthSmallest(n1,6) # 21
129.TCP 和 UDP 的区别
- TCP协议在传送数据段的时候要给段标号;UDP不用
- TCP协议可靠;UDP不可靠
- TCP协议是面向连接;UDP采用无连接
- TCP协议负载较高,采用虚电路;UDP采用无连接
- TCP协议发送方要确认接收方是否收到数据段(三次握手协议)
- TCP协议采用窗口技术和流控制
130.简要介绍三次握手和四次挥手
-
三次握手
-
第一次握手
- Client端首先发送一个SYN包告诉Server端我的初始序列号是X,Client进入SYN-SENT(同步已发送)状态
-
第二次握手
- Server端收到SYN包后回复给Client端一个ACK确认包,告诉Client端我收到了,Server端进入SYN-RCVD(同步收到)状态
- Server端也需要告诉Client端一个初始序列号,于是,Server端也发送一个SYN包告诉Client端我的初始序列号是Y
-
第三次握手
- Client收到后,回复给Server端一个ACK确认包说我知道了,之后Client和Server进入ESTABLISHED(已建立连接)状态,完成三次挥手
-
第一次握手
-
四次挥手
-
第一次挥手
- Client端发送一个FIN包告诉Server端我的初始序列号是X,用来关闭Client到Server的数据传送,Client端进入FIN_WAIT_1(主动关闭,已经发送关闭请求,等待确认)状态
-
第二次挥手
- Server端收到FIN包后,发给Client端一个ACK确认包,Server端进入CLOSE_WAIT(被动关闭,收到对方关闭请求,已经确认)状态
-
第三次挥手
- Server端发送一个FIN包告诉Client端我的序列号是Y,用来关闭Server端到Client端的数据传送,同时发送给Client一个ACK确认包,Server端进入LAST_ACK(被动关闭,等待最后一个关闭确认,并等待所有分组死掉)状态
-
第四次挥手
- Client端收到FIN包后进入TIME_WAIT(完成双向关闭,并等待所有分组死掉)状态,接着发给给Server端一个ACK确认包,Server端进入CLOSED(关闭状态,没有连接活动或正在进行)状态,完成四次挥手
-
第一次挥手
扩展:三次握手改成两次握手可以吗?不可以,主要防止已经失效的请求连接突然又传送到了服务器,从而产生错误
132.TIME_WAIT状态的作用
主动关闭的那端最后经历的状态,一般为2MSL秒(1~4分钟)
- 保证当最后一个ACK包丢失后,能收到对端重新传的FIN包
- 保证ACK包消失,不会影响下一个连接
132.什么是粘包? socket 中造成粘包的原因是什么? 哪些情况会发生粘包现象?
定义:在接收数据时,一次性多接收了其他请求发送来的数据(即多包接收)。比如,对方第一次发送hello,第二次发送world,在接收时应该接收两次,一次是hello,一次是world,但事实上一次收到
helloworld,一次收到空,这种现象叫粘包。
原因:主要是因为接收方不知道消息之间的界限,不知道一次性提取多少字节的数据造成的
会发生的情况:
- 发送端需要等缓存区满才发送出去,造成粘包(发送数据时间间隔很短,数据很小,会合到一起,产生粘包)
- 接收方不及时接收缓存区的包,造成多个包接收(客户端发送了一段数据,服务端只接收了一小部分,服务端下次再收的时候还是从缓存区拿上次遗留的数据,产生粘包)
133.举例说明 concurrent.futures 中的线程池的用法
concurrent.futures模块的基础是Exectuor,Exectuor是一个抽象类,不能直接被调用,它的子类ThreadPoolExectuor和ProcessPoolExectuor,分别用来创建线程池和进程池,可以将相应的tasks放入相应
的线程池/进程池,不需要维护Queue来操心死锁的问题,线程池/进程池会自动调度
from concurrent.futures import ThreadPoolExecutor import time def ret_msg(msg): time.sleep(2) return msg pool = ThreadPoolExecutor(max_workers=2) # 最多加入两个task future1 = pool.submit(ret_msg,("hello")) # 加入task1 future2 = pool.submit(ret_msg,("world")) # 加入task2 print(future1.done()) # 查看task1任务是否完成 打印False time.sleep(3) print(future2.done()) # 打印True print(future1.result()) # 查看task1结果 print(future2.result())
134.说一说多线程,多进程和协程的区别
-
线程与进程比较
- 地址空间:线程是进程内的一个执行单元,进程内至少有一个线程,它们共享进程的地址空间,而进程有自己独立的地址空间
- 资源拥有:进程是资源分配和拥有的单位,同一个进程内的线程共享进程的资源
- 线程是处理器调度的基本单位,但进程不是
- 二者均可并发执行
- 每个独立的线程有一个程序运行的入口,顺序执行序列和程序的出口,但是线程不能独立执行,必须依存在应用程序中,由应用程序提供多个线程执行控制
-
线程与协程比较
- 一个线程可以多个协程,一个进程也可以单独拥有多个协程,这样python中则能使用多核CPU
- 线程进程都是同步机制,而协程是异步
- 协程能保留上一次调用时的状态,每次过程重入时,就相当于进入上一次调用的状态
135.进程之间如何通信
共享内存、信号量、互斥锁、消息队列等
136.IO 多路复用的作用
I/O多路复用就通过一种机制,可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作。但select,poll,epoll本质上都是同步I/O,因为他们都需要
在读写事件就绪后自己负责进行读写,也就是说这个读写过程是阻塞的,而异步I/O则无需自己负责进行读写,异步I/O的实现会负责把数据从内核拷贝到用户空间
137.select、poll、和epoll模型的区别
- select, poll是为了解決同时大量IO的情況(尤其网络服务器),但是随着连接数越多,性能越差
- epoll是select和poll的改进方案,在 linux 上可以取代 select 和 poll,可以处理大量连接的性能问题
138.什么是并发和并行
- 并行是指两个或者多个事件在同一时刻发生;而并发是指两个或多个事件在同一时间间隔发生
- 并行是在不同实体上的多个事件,并发是在同一实体上的多个事件
139.一个线程 1 让线程 2 去调用一个函数怎么实现
import threading def func1(t2): print("我是func1") t2.start() t2 = threading.Thread() t1 = threading.Thread(target=func1,args=(t2,)) t1.start()
140.解释什么是异步非阻塞
当一个异步过程调用发出后,调用者不会立刻得到结果。实际处理这个调用的部件是在调用发出后,通过状态、通知来通知调用者,或通过回调函数处理这个调用;非阻塞的意思是,不能立刻得到结果
之前,该函数不会阻塞当前线程,而会立刻返回
141.threading.local 的作用
Python提供了 threading.local 类,将这个类实例化得到一个全局对象,但是不同的线程使用这个对象存储的数据其它线程不可见(本质上就是不同的线程使用这个对象时为其创建一个独立的字典)
142.说说你知道的 git 命令
- git clone:从远端库克隆代码到本机
- git push:将本地仓库的代码推送到远端库
- git init:创建一个git仓库,创建之后会在当前目录生成一个.git文件
- git status:查看git库的状态,未提交的文件分为两种:add过已经在缓存区的,未add过的
- git add:把文件添加到缓存区
- git commit:提交缓存区的所有修改到仓库
- git rm:删除文件
143.git 如何查看某次提交修改的内容
知道commit id的情况下:
1. 获取commit id
git log
2. 查看commit内容
git show commit_id
查看最近n次提交的修改
git log -p -n
指定n为1则可以查看最近一次修改的内容
并行”指两个或两个以上事件或活动在同一时刻发生。在多道程序环境下,并行性使多个程序同一时刻可在不同CPU上同时执行