算法之二分法
二分概念
二分算法,又称折半查找,即在一个单调有序的集合中查找一个解。
每次分为左右两部分,判断解在哪个部分中并调整上下界,直到找到目标元素,
每次二分后都将舍弃一半的查找空间。
定义and实现:
算法就是解决问题的高效办法
常见的算法:二分法
算法还可以锻炼我们的思维逻辑能力
# 二分查找法
l = [11, 2, 3, 44, 55, 66, 77, 88, 99, 100, 23, 34, 45, 56, 67]
# 在列表中找66是否有
1. for循环遍历
for i in l:
if i == 66:
print("找到了")
2. 二分法实现
'''算法不一定都是比其他方法高效的'''
l = [11, 2, 3, 44, 55, 66, 77, 88, 99, 100, 23, 34, 45, 56, 67]
# 1. 先排序
l.sort()
# 2. 定义一个目标数据
target = 200
def my_half(target, l):
'''判断列表的长度是否为0'''
if len(l) == 0:
print('要找的数据不在列表中')
return
# 3. 从列表的中间取一个值
# 得到的是中间数据的索引值
middle_index = len(l) // 2 # 整除
if target > l[middle_index]:
# 说明目标数据在列表的右侧
l_right = l[middle_index + 1:]
print(l_right)
my_half(target, l_right)
elif target < l[middle_index]:
# 说明目标数据在列表的左侧
l_left = l[:middle_index]
print(l_left)
my_half(target, l_left)
else:
print('存在')
my_half(target, l)
# 冒泡排序、快排、插入等
三元表达式
比价两个数的大小
普通方法一:
def my_max(a, b):
if a > b:
return a
else:
return b
my_max(1, 2)
三元表达式方法二:
def my_max(a, b):
return a if a > b else b
res=my_max(1, 2)
print(res)
语法结构:
条件成立返回if前面的值 if 条件 else 条件不成立返回else后面的值
使用场景:
"""只有当需求功能是二选一的情况下,才使用三元表达式"""
使用方法:
# res = '听音乐' if 2 > 1 else '看电影'
# print(res)
# res1 = '逛街' if True else '看展'
# print(res1)
# cmd = input('请问你是否喜欢榴莲:(y/n)')
# if cmd == 'y':
# print('YYDS')
# else:
# print('不喜欢,味道好臭')
# res = 'YYDS' if cmd == 'y' else '不喜欢,味道好臭'
# print(res)
# 它还可以支持嵌套
is_beautiful = True
res = '旅行' if 1 > 2 else '躺尸' if False else '喜欢' if is_beautiful == True else '不喜欢'
print(res)
注意:
"""
一般情况我们在写代码的时候,尽量不要使用嵌套的情况
但是,嵌套的是一般出现在面试题里面
"""
列表生成式
name_list = ['kevin', 'tank', 'tony', 'jerry']
# 1. 给列表中的所以名称加一个后缀_DSB
# 2. 定义一个空列表用来存储拼接之后的值
new_name_list = []
# 3. 循环列表
for name in name_list:
# res = '%s_DBS' % name
# res = name +'_DSB'
new_name_list.append('%s_DBS' % name)
print(new_name_list)
# 列表生成式
res = [name+'_DSB' for name in name_list]
print(res)
# 2. 定义一个空列表用来存储拼接之后的值
new_name_list = []
name_list = ['kevin', 'tank', 'tony', 'jerry']
# 2. 给列表中的所有名称都加一个后缀_DSB, 除了jerry不加
for name in name_list:
if name != 'jerry':
new_name_list.append('%s_DSB' % name)
print(new_name_list)
# 列表生成式
# res = ['%s_DSB' % name for name in name_list if name != 'jerry']
res = ['%s_DSB' % name if name != 'jerry' else name for name in name_list]
print(res)
字典生成式(了解)
"""
方法:enumerate
1. 循环enumerate方法可以得到两个值
索引、元素
"""
# for i, j in enumerate(l, start=2):
# print(i, j)
字典生成式
res = {i: j for i, j in enumerate(l) if j != 'name'}
print(res)
集合生成式
res = {i for i, j in enumerate(l)}
print(res)
元组
res1 = (i for i in enumerate(l)) # 生成器
print(res1)
匿名函数
"""没有名字的函数"""
之前使用def关键字定义的函数都是有名函数,有名字的函数
"""
语法格式:
lambda 形参:返回值
"""
res = lambda x: x+1
# res(1)
# print(res(1))
print((lambda x: x +1)(2))
# 有什么使用场景:他一般不会单独使用,会配合几个常见的内置函数使用
匿名函数的作用:
1、通过匿名函数可以实现闭包,若要创建一个闭包,往往都需要用到匿名函数。
2、模拟块级作用域,减少全局变量。执行完匿名函数,存储在内存中相对应的变量会被销毁,从而节省内存。
再者,在大型多人开发的项目中,使用块级作用域,会大大降低命名冲突的问题,从而避免产生灾难性的后果。自此开发者再也不必担心搞乱全局作用域了。
常见的内置函数
map() 会根据提供的函数对指定序列做映射。
zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。
max() 用于获取多个参数或者迭代对象元素中的最大值。
min() min()函数的用法和max()函数用法相反,获取的是最小值。
filter() 函数用于过滤序列,过滤掉不符合条件的元素,返回由符合条件元素组成的新列表。
方法:
1.zip:拉链
zip 语法:
zip([iterable, ...])
iterabl -- 一个或多个迭代器
# res=zip(l1, l2, l3, l4) # 拉链 # [(1, 'a', 'aa'), (2, 'b', 'bb'),
(3, 'c', 'cc'), (4, 'd', 'dd')]
# print(list(res))
2. max min : 最大值 最小值
# l1 = [1,2,3,4,5]
# print(max(l1))
# print(min(l1))
# s = ['kevin', 'tank', 'jerry']
# print(max(s))
d = {
'kevin': 2000,
'tank': 1000,
'oscar': 300000,
}
# def index(key):
# return d[key]
# print(max(d, key=index)) # tank
print(max(d, key=lambda key: d[key])) # tank
print(min(d, key=lambda key: d[key])) # tank
3. filter:过滤
ll = [11, 22, 33, 44, 55]
ls = []
# for i in ll:
# if i > 30:
# ls.append(i)
res=filter(lambda key: key > 30, ll)
print(list(res))