Posted on  Updated on 

python算法实战

去年报名了蓝桥杯，却一直没有练习，也该开始了，为了300的报名费

时间复杂度

O(1),O(n),O($n^{2}$),O($log_{2}n$),O(n!)…

空间复杂度

递归

  • 调用条件
  • 结束自身

实例

1
2
3
4
5
6
7
8
9
10
def jiecheng(n):
    if n != 1:
        sum = n * jiecheng(n - 1)
        return sum
    else:
        return 1


print(jiecheng(5))

1
2
#结果
120

查找

  • 顺序查找
  • 二分查找

顺序查找

1
2
3
4
5
6
7
8
9
10
def shuxu(list_1, val):
    for i in range(len(list_1)):
        if val == list_1[i]:
            return i
    else:
        return


list_my = list(range(5))
print(shuxu(list_my, 3))
1
2
#结果
3

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(my_list, val):  # my_list 为list,val为待查找的值
    lift = 0
    right = len(my_list) - 1
    mid = (lift + right) // 2
    while lift <= right:
        if my_list[mid] == val:
            return mid
        elif my_list[mid] > val:
            right = mid - 1
        else:
            lift = mid + 1
    else:
        return None

排序

将一组无序序列变为有序序列
升序与降序
内置排序算法sort()

  • LOW
    • 冒泡排序
    • 选择排序
    • 插入排序
  • NB
    • 快速排序
    • 堆排序
    • 归并排序
  • 其他
    • 希儿排序
    • 计数排序
    • 基数排序

sort的使用

需要注意的是，sort()方法会直接修改原列表，而不是返回一个新的排序后的列表

冒泡排序

  • 列表每相邻的两个数，如果后面比前面大，交换两个数
  • 一次排序，无序区减少一个数，有序区增加一个数
1
2
3
4
5
6
7
8
9
10
11
12
13
import random

def bubble_sort(my_list):
    for i in range(len(my_list)-1): # -1防止内存溢出
        for j in range(len(my_list)-1-i):
            if my_list[j]>my_list[j+1]:
                my_list[j],my_list[j+1]=my_list[j+1],my_list[j]


my_list = [random.randint(0,10000) for i in range(5)]
print(my_list)
bubble_sort(my_list)
print(my_list)
1
2
3
# 结果
[3003, 7653, 1759, 5541, 3176]
[1759, 3003, 3176, 5541, 7653]

range详解

range() 函数是 Python 中常用的一个函数，用于生成一个整数序列。它常用于循环中，可以生成指定范围的整数序列。

range() 函数有三种常用的用法：

  • range(stop): 生成从 0 开始到 stop-1 的整数序列。
  • range(start, stop): 生成从 start 开始到 stop-1 的整数序列。
  • range(start, stop, step): 生成从 start 开始到 stop-1 的整数序列，步长为 step。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 生成从 0 到 4 的整数序列
    for i in range(5):
        print(i)  # 输出：0, 1, 2, 3, 4

    # 生成从 2 到 5 的整数序列
    for i in range(2, 6):
        print(i)  # 输出：2, 3, 4, 5

    # 生成从 1 到 10 的偶数序列
    for i in range(2, 11, 2):
        print(i)  # 输出：2, 4, 6, 8, 10

    需要注意的是，range() 函数生成的是一个可迭代对象，而不是一个列表。如果需要得到一个列表，可以使用 list() 函数将其转换为列表：
    1
    2
    my_list = list(range(5))  # 将 range 对象转换为列表
    print(my_list)  # 输出：[0, 1, 2, 3, 4]

random详解

使用前需要import random

  • random.random(): 返回一个 [0.0, 1.0) 之间的随机浮点数。
  • random.randint(a, b): 返回一个 [a, b] 之间的随机整数。
  • random.uniform(a, b): 返回一个 [a, b] 之间的随机浮点数。
  • random.choice(seq): 从序列 seq 中随机选择一个元素返回。
  • random.shuffle(seq): 将序列 seq 中的元素随机排序
  • random.sample(population, k): 从 population 中随机选择 k 个不重复的元素返回，返回一个列表。

选择排序

打擂台排序

1
2
3
4
5
6
7
8
9
10
11
import random
def select_sort(my_list):
    for i in range(len(my_list)):
        for j in range(i,len(my_list)):
            if my_list[j]<my_list[i]:
                my_list[j],my_list[i]=my_list[i],my_list[j]

my_list = [random.randint(0,10000) for i in range(5)]
print(my_list)
select_sort(my_list)
print(my_list)
1
2
3
# 结果
[3871, 3692, 8939, 1310, 1203]
[1203, 1310, 3692, 3871, 8939]

插入排序

  • 初始时手里（有序区）只有一张牌
  • 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    import random


    def insert_sort(arr):
        for i in range(1, len(arr)):
            key = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key


    my_list = [random.randint(0, 10000) for i in range(5)]
    print(my_list)
    insert_sort(my_list)
    print(my_list)

    1
    2
    3
    # 结果
    [904, 5335, 5843, 9487, 1597]
    [904, 1597, 5335, 5843, 9487]

数据结构

python中数据结构的类型

  • 元组
    • 无法修改，tuple,不可变数据结构
    • 利用in查找
  • 列表
    • 支持增删改查
    • 切片[x:y],左闭右开
    • 追加，列表末尾增加元素list.append(元素)
    • 插入，list.insert(下标,元素)
    • 删除, list.pop(下标)，默认为最后一个元素
  • 字典
    • 删除，dictionary.pop(“键”)

字符与字符串实战

统计出其中数字字符的个数

输入一行字符，统计出其中数字字符的个数。

1
2
3
4
5
6
7
8
user_input = input()
digit_count = 0

for char in user_input:
    if char <= '9' and char >= '0':
        digit_count += 1

print(digit_count)

isdigit() 是 Python 中字符串对象的一个方法，用于检查字符串中的所有字符是否都是数字字符（即 0-9）。
可以改为

1
2
3
4
5
6
7
8
user_input = input()
digit_count = 0

for char in user_input:
    if char.isdigit():
        digit_count += 1

print(digit_count)

给定一个只包含小写字母的字符串

请你找到第一个仅出现一次的字符。如果没有，输出 no

1
2
3
4
5
6
7
8
my_list = input()

for char in my_list:
    if my_list.count(char) == 1:
        print(char)
        break
else:
    print("no")

详解count

count() 方法是字符串对象的一个内置方法，用于统计指定子字符串在原字符串中出现的次数。
count() 方法只会统计不重叠的子字符串。例如，在字符串 “aaaaa” 中统计子字符串 “aa” 的出现次数，结果为 2，而不是 4，因为两个 “aa” 子字符串之间重叠

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。