目录
算法简介及二分法
1.什么是算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
2算法的特征
一个算法应该具有以下五个重要的特征：
有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
确切性：算法的每一步骤必须有确切的定义；
输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。
3算法应用场景
推荐算法(抖音视频推送 淘宝商品推送)
成像算法(AI相关)......
几乎涵盖了我们日常生活中的方方面面
4算法部门
不是所有的互联网公司都养得起算法部分 只有大型互联网公司才有
算法部门类似于药品研发部分.
5二分法
是算法中最简单的算法 甚至都称不上是算法
二分法使用要求:
待查找的数据集必须有序
二分法的缺陷:
针对开头结尾的数据 查找效率很低
常见算法的原理以及伪代码
二分法、冒泡、快拍、插入、堆排、桶排、数据结构(链表 约瑟夫问题 如 何链表是否成环)
l1 = [12, 21, 32, 43, 56, 76, 87, 98, 123, 321, 453, 565, 678, 754, 812, 987, 1001, 1232]
def get_middle(l1,target_num):
if len(l1)==0:
print('没找到')
return
minddle_index=len(l1)//2
if target_num>l1[minddle_index]:
right_l1=l1[minddle_index+1:]
print(right_l1)
return get_middle(right_l1,target_num)
elif target_num<l1[minddle_index]:
left_l1=l1[:minddle_index]
print(left_l1)
return get_middle(left_l1,target_num)
else:
print('恭喜你 找到了!!!')
get_middle(l1,22)
冒泡
快拍
插入
堆排
桶排
数据结构(链表 约瑟夫问题 如 何链表是否成环)
三元表达式
Python是示例可以看出，Python的三元表达式格式如下:
条件为真时的结果 if 判段的条件 else 条件为假时的结果
适用场景：变量赋值时，要做条件判断时，简化代码时使用。
a=1
b=2
方法1
c='qqq' if a<b else 'bbb'
print(c)#qqq
数据值1 if 条件 else 数据值2
条件成立则使用数据值1 条件不成立则使用数据值2
当结果是二选一的情况下 使用三元表达式较为简便
并且不推荐多个三元表达式嵌套
方法2
print({True: 'qqq', False: 'bbb'}[a > b])
模板：
{True:数据值1, False: 数据值2}[判断条件]
条件成立则使用数据值1 条件不成立则使用数据值2
方法3
print(('qqq','bbb')[a > b])
模板：
(数据值1,数据值2)[判断条件]
条件不成立则使用数据值1条件成立则使用数据值2
各种生成式/表达式/推导式
Python 推导式是一种独特的数据处理方式，可以从一个数据序列构建另一个新的数据序列的结构体。
Python 支持各种数据结构的推导式：
列表(list)推导式
字典(dict)推导式
集合(set)推导式
元组(tuple)推导式
列表推导式格式：
[表达式 for 变量 in 列表]
[out_exp_res for out_exp in input_list]
或者
[表达式 for 变量 in 列表 if 条件]
eg:
[out_exp_res for out_exp in input_list if condition]
name_list=['jason','xiaoming','xiaoghong','xiaolan']
# 给列表中所有人名的后面加上_NB的后缀
#for 循环
new_list=[]
for name in name_list:
name=f'{name}_NB'
new_list.append(name)
print(new_list)#['jason_NB', 'xiaoming_NB', 'xiaoghong_NB', 'xiaolan_NB']
#列表推导式
new_list1=[name +'_NB' for name in name_list]
print(new_list1)#['jason_NB', 'xiaoming_NB', 'xiaoghong_NB', 'xiaolan_NB']
#复杂情况
new_list11=[name +'_NB' for name in name_list if name=='jason']
print(new_list11)#['jason_NB']
new_list111=['嘻嘻'if name=='jason' else'哈哈' for name in name_list if name !='xiaoghong']
print(new_list111)#['嘻嘻', '哈哈', '哈哈']
字典推导式:
字典推导基本格式：
{ key_expr: value_expr for value in collection }
或
{ key_expr: value_expr for value in collection if condition }
# 将列表中各字符串值为键，各字符串的长度为值，组成键值对
eg:
s1='hello word'
for i,j in enumerate(s1):
print(i,j)
d1={i:j for i,j in enumerate('hello')}
print(d1)#{0: 'h', 1: 'e', 2: 'l', 3: 'l', 4: 'o'}
# enumerate
enumerate() 方法的语法:
enumerate(sequence, [start=0])
sequence -- 一个序列、迭代器或其他支持迭代对象。
start -- 下标起始位置。
enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
集合推导式:
集合推导式基本格式：
{ expression for item in Sequence }
或
{ expression for item in Sequence if conditional }
eg:
res = {i for i in 'hello'}
print(res)#{'e', 'h', 'l', 'o'}
元组推导式
元组推导式可以利用 range 区间、元组、列表、字典和集合等数据类型，快速生成一个满足指定需求的元组。
元组推导式基本格式：
(expression for item in Sequence )
或
(expression for item in Sequence if conditional )
元组推导式和列表推导式的用法也完全相同，只是元组推导式是用 () 圆括号将各部分括起来，而列表推导式用的是中括号 []，另外元组推导式返回的结果是一个生成器对象。
例如，我们可以使用下面的代码生成一个包含数字 1~9 的元组：
a=(b for b in range(1,10))
print(tuple(a))#(1, 2, 3, 4, 5, 6, 7, 8, 9)
匿名函数
Python 使用 lambda 来创建匿名函数。
所谓匿名，意即不再使用 def 语句这样标准的形式定义一个函数。
lambda 只是一个表达式，函数体比 def 简单很多。
lambda 的主体是一个表达式，而不是一个代码块。仅仅能在 lambda 表达式中封装有限的逻辑进去。
lambda 函数拥有自己的命名空间，且不能访问自己参数列表之外或全局命名空间里的参数。
虽然 lambda 函数看起来只能写一行，却不等同于 C 或 C++ 的内联函数，后者的目的是调用小函数时不占用栈内存从而增加运行效率。
语法
lambda 函数的语法只包含一个语句，如下：
lambda [arg1 [,arg2,.....argn]]:expression
设置参数 a 加上 10:
实例
x = lambda a : a + 10
print(x(5))
以上实例输出结果：
15
以下实例匿名函数设置两个参数：
实例(Python 3.0+)
#!/usr/bin/python3
# 可写函数说明
sum = lambda arg1, arg2: arg1 + arg2
# 调用sum函数
print ("相加后的值为 : ", sum( 10, 20 ))
print ("相加后的值为 : ", sum( 20, 20 ))
以上实例输出结果：
相加后的值为 : 30
相加后的值为 : 40
我们可以将匿名函数封装在一个函数内，这样可以使用同样的代码来创建多个匿名函数。
以下实例将匿名函数封装在 myfunc 函数中，通过传入不同的参数来创建不同的匿名函数：
实例
def myfunc(n):
return lambda a : a * n
mydoubler = myfunc(2)
mytripler = myfunc(3)
print(mydoubler(11))
print(mytripler(11))
以上实例输出结果：
22
33
内置函数
1map()映射
map(func,iterable)，其中func为函数名，可为lambda匿名函数，iterable为可迭代对象。此函数会将可迭代对象中的每一位元素作为参数传递到func中，并将func的计算结果加入到新列表内，map()返回的是一个包含所有结果的新列表。
eg:
l=[1,2,3,4,5]
res=map(lambda x:x+1,l)
print(list(res))#[2, 3, 4, 5, 6]
2.max()\min()
ll=[11, 22, 33, 44]
res=max(ll)
print(res)#44
res1=min(ll)
print(res1)#11
d1 = {
'zj': 100,
'jason': 8888,
'berk': 99999999,
'oscar': 1
}
def func(a):
return d1.get(a)
# res = max(d1, key=lambda k: d1.get(k))
res = max(d1, key=func)
print(res)
3.reduce
# reduce 传多个值 返回一个值
from functools import reduce
l1 = [11, 22, 33, 44, 55, 66, 77, 88]
res = reduce(lambda a, b: a * b, l1)
print(res)
作业
有下列用户数据
user_data = {
‘1’: {‘name’: ‘jason’, ‘pwd’: ‘123’, ‘access’: [‘1’, ‘2’, ‘3’]},
‘2’: {‘name’: ‘kevin’, ‘pwd’: ‘321’, ‘access’: [‘1’, ‘2’]},
‘3’: {‘name’: ‘oscar’, ‘pwd’: ‘222’, ‘access’: [‘1’]}
}
并有三个函数
def func1():
pass
def func2():
pass
def func3():
pass
要求:调用上述三个函数的时候需要从user_data中校验用户身份是否正确
并获取当前登录用户拥有的可执行函数功能编号即键access对应的功能编号列表
func1是1、func2是2、func3是3
并且一旦用户登录成功之后后续函数的调用不再校验用户身份
请思考如何获取函数功能编号 如何校验用户身份 如何校验权限
ps:装饰器知识 附赠:实现上述主体功能即可 其他扩展优化功能可暂且不写
user_data = {
'1': {'name': 'jason', 'pwd': '123', 'access': ['1', '2', '3']},
'2': {'name': 'kevin', 'pwd': '321', 'access': ['1', '2']},
'3': {'name': 'oscar', 'pwd': '222', 'access': ['1']}
}
login_data={
'islogin':False,
'user_access':[],
'user_name':None
}
def login(func_id):
def outer(fun_name):
def inner(*args,**kwargs):
if login_data['islogin']==True:
access=login_data['user_access']
user_name=login_data[ 'user_name']
if func_id in access:
res=fun_name(*args,**kwargs)
return res
else:
print(f'该用户{user_name}没有{func_id}的权限')
else:
user_id=input('请输入用户编号').strip()
if user_id not in user_data:
print('查无此人')
else:
user_name = input('输入名字').strip()
user_pwd = input('输入密码').strip()
if user_name==user_data[user_id]['name'] and user_pwd == user_data[user_id]['pwd']:
access=user_data[user_id]['access']
login_data['islogin']=True
login_data['user_access']=access
login_data['user_name']=user_name
if func_id in access:
res=fun_name(*args,**kwargs)
return res
else:
print(f'用户{user_name}没有{func_id}的权限')
return inner
return outer
@login('1')
def func1():
print('fun1')
@login('2')
def func2():
print('fun2')
@login('3')
def func3():
print('fun3')
func1()
func2()
func3()