AcWing 算法基础课学习记录（Python，备战蓝桥杯）Day1 - Day30_acwing算法基础课怎么样

 备战蓝桥杯学习路线：AcWing算法基础课->AcWing蓝桥杯课

（由于基础课和蓝桥课一共有85小时，现在每天平均是30mins到45mins，可能不是很够。从明天开始，每天看视频讲解一小时并且要消化内容，估计一起得花3-4小时。这样子差不多一月底，二月初可以结束视频课程）

Day1.(2021.10.12)

#Python input是输入的字符串，当要输入一串数组需要用如下arrs的两种方法
#如果输入的字符串没有用空格分开，则可以不加split()
n = int(input())
arrs = list(map(int, input().split()))
arrs = [int(x) for x in input().split()]

学习思路：1 先理解算法主要思想，2 背模板，3多做几道题（在做题的时候，当你AC了，马上把代码删除，再重新写一边，重复两三次）

快速排序

其主要思想是分治

1. 确定分界点de，一般选择左端点q[l]，右端点q[r]或者中间q[(l+r)/2]

2. 调整范围，将左边调整为小于等于分界点，右边调整为大于等于分界点

3. 递归处理左右两段

其中重难点是2，简单方法（但耗空间）是：

1. 先设置两个数组a[], b[]

2. 数组q[l~r]中小于等于de的放入a[]，大于等于de的放入b[]

3. 然后将a和b合并放入数组q，a在左边，b在右边

主要方法是，在数组两端分别设置指针i,j，while q[i]<de: i++，while q[j]>de: j--，if i<j swap(q[i],q[j]) else 递归处理左边部分(l,j)和右边部分(j+1,r)。重复上述步骤。

Python模板：

# acwing.785 快速排序
 
n = int(input())
a = list(map(int, input().split()))
#a = [int(x) for x in input()]
 
def quick_sort(a,l,r):
    if l>=r: return
 
    # x = a[l]
    x= max(min(a[l], a[r]), a[(l + r) // 2])
    i,j = l-1,r+1
 
    while i<j:
        i+=1
        j-=1
        while a[i]<x: i+=1
        while a[j]>x: j-=1
        if i<j: a[i],a[j] = a[j],a[i]
 
    quick_sort(a,l,j)
    quick_sort(a,j+1,r)
 
quick_sort(a,0,n-1)
print(' '.join(map(str,a)))

Day2.(2021.10.14)

Python Append

• 当Append一个元素时，Python将创建一个足够大的列表，来容纳N个元素和将要被追加的元素。重新创建的列表长度大于N＋1（虽然我们只触发一次append操作），实际上，为了未来的Append操作，M个元素长度（M>N+1)的内存将会被额外分配，然后，旧列表中的数据被copy到新列表中，旧列表销毁。
• 额外内存的分配，只会发生在第一次Append操作时，当我们创建普通列表时，不会额外分配内存。

从这里还有网上其他地方整理知识点可以知道：

Append操作会申请新的一连串的空间，整体copy过去，那么就存在时间效率的下降，相对于一开始申请很大的空间。 

生成列表的五种方式（从0开始生成含有n个数的列表）

import timeit
 
def test1():
    l = []
    for i in range(1000):
        l += [i]
 
def test2():
    l = []
    for i in range(1000):
        l.append(i)
 
def test3():
    l = [i for i in range(1000)]
 
def test4():
    l = list(range(1000))
 
def test5():
    l = [0] * 1000
 
t1 = timeit.Timer("test1()", "from __main__ import test1")
print(t1.timeit(number=1000), "milliseconds")
 
t2 = timeit.Timer("test2()", "from __main__ import test2")
print(t2.timeit(number=1000), "milliseconds")
 
t3 = timeit.Timer("test3()", "from __main__ import test3")
print(t3.timeit(number=1000), "milliseconds")
 
t4 = timeit.Timer("test4()", "from __main__ import test4")
print(t4.timeit(number=1000), "milliseconds")
 
t5 = timeit.Timer("test5()", "from __main__ import test5")
print(t5.timeit(number=1000), "milliseconds")

这个结果和书上的结果有出入的地方在于1和2项，书上1的性能比2慢一个数量级（10倍）。

 Python数据结构性能分析

归并排序

归并排序的主要思想也是分治，它和快排的思想不同，快排是边分边治，它是先分后治。

1. 确定分界点 mid=(r+l)/2

2. 递归排序左右两部分 （根据选出的分界点，将分界点左边的递归处理，右边的递归处理）

3. 归并-合二为一 （递归的终止条件是l>=r，返回后就要考虑怎么把左右两部分正确的合在一起）

# acwing.787 归并排序
 
n = int(input())
a = list(map(int, input().split()))
 
def merge_sort(a,l,r):
    if l>=r:return
 
    mid = (l+r)//2
    merge_sort(a,l,mid)
    merge_sort(a,mid+1,r)
 
    tmp,i,j = [],l,mid+1
    while i<=mid and j<=r:
        if a[i]<a[j]:
            tmp.append(a[i])
            i+=1
        else:
            tmp.append(a[j])
            j+=1
    # or using tmp.extend(a[i:mid+1])
    if i<=mid:tmp+=a[i:mid+1]
    if j<=r:tmp+=a[j:r+1]
    a[l:r+1] = tmp[:]
 
merge_sort(a,0,n-1)
print(" ".join(map(str, a)))

Day3.(2021.10.14)

Day2的List五种生成方式和数据结构分析是今天做的。本来说把归并的788题做了，结果进去就跳转到算法基础课的活动，然后在leetcode上也没找到合适的题就把归并和快排复习了下，发现归并都是用<=或>=，而快排只有最开始判断的时候用了>=，其余都没有>=或<=，如果有的话还会报错。

Day4.(2021.10.15)

二分

这一节在刚开始听的时候还有点蒙蔽，一上来就在讲方法和思想，我连算法要解决的问题都还不清楚