------------恢复内容开始------------

Python内置数据结构

分类

? 数值型 ? int、float、complex、bool ? 序列对象 ? 字符串 str ? 列 表 list ? tuple ? 键值对 ? 集合set ? 字典dict

数值型

数值型

? 数值型 ? int、float、complex、bool都是class，1、5.0、2+3j都是对象即实例 ? int：python3的int就是长整型，且没有大小限制，受限于内存区域的大小 ? float：由整数部分和小数部分组成。支持十进制和科学计数法表示。C的双精度型实现 ? complex：有实数和虚数部分组成，实数和虚数部分都是浮点数，3+4.2J ? bool：int的子类，仅有2个实例True、False对应1和0，可以和整数直接运算 ? 类型转换（built-in） ? int(x) 返回一个整数 ? float(x) 返回一个浮点数 ? complex(x)、complex(x,y) 返回一个复数 ? bool(x) 返回布尔值，前面讲过False等价的对象

数字的处理函数

? round()，四舍五入？ ? math模块、floor()地板、天花板ceil() ? int() 、// ? 举例：

import math
print(math.floor(2.5), math.floor(-2.5))
print(math.ceil(2.5), math.ceil(-2.5))
----------------------------------------------
2 -3
3 -2

以下打印什么结果？说明什么

?
print(int(-3.6), int(-2.5), int(-1.4))
print(int(3.6), int(2.5), int(1.4))
print(7//2, 7//-2, -7//2, -(7//2))
print(2//3, -2//3, -1//3)
print(round(2.5), round(2.5001), round(2.6))
print(round(3.5), round(3.5001), round(3.6), round(3.3))
print(round(-2.5), round(-2.5001), round(-2.6))
print(round(-3.5), round(-3.5001), round(-3.6), round(-3.3))
---------------------------------------------------
-3 -2 -1
3 2 1
3 -4 -4 -3
0 -1 -1
2 3 3
4 4 4 3
-2 -3 -3
-4 -4 -4 -3
?

数字的处理函数

?round()，四舍六入五取偶 ?floor()向下取整、ceil()向上取整 ?int() 取整数部分 ?// 整除且向下取整

数字的处理函数

?min() ?max() ?pow(x,y) 等于x**y ?math.sqrt()

?进制函数，返回值是字符串 ?bin() ?oct() ?hex()

?math.piπ ?math.e自如常数

类型判断

?type(obj) ，返回类型，而不是字符串 ?isinstance(obj, class_or_tuple)，返回布尔值 ?举例：

type(a)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
NameError: name ‘a‘ is not defined
>>> type(‘abc‘)
<class ‘str‘>
>>> type(123)
<class ‘int‘>
>>> isinstance(6,str)
False
>>> isinstance(6,(str,bool,int))
True
>>> type(1+True)
<class ‘int‘>
>>> type(1+True+2.0)# 是什么？隐式转换
<class ‘float‘> 

列表list

?一个队列，一个排列整齐的队伍 ?列表内的个体称作元素，由若干元素组成列表 ?元素可以是任意对象（数字、字符串、对象、列表等） ?列表内元素有顺序，可以使用索引 ?线性的数据结构 ?使用[ ] 表示 ?列表是可变的

?列表list、链表 ?queue、stack

列表list定义初始化

?list() -> new empty list ?list(iterable) -> new list initialized from iterable‘s items ?列表不能一开始就定义大小 lst = list() lst = [] lst = [2, 6, 9, ‘ab‘] lst = list(range(5))

列表索引访问

?索引，也叫下标 ?正索引：从左至右，从0开始，为列表中每一个元素编号 ?负索引：从右至左，从-1开始 ?正负索引不可以超界，否则引发异常IndexError ?为了理解方便，可以认为列表是从左至右排列的，左边是头部，右边是尾部，左边是下界，右边是上界 ?列表通过索引访问 ?list[index] ，index就是索引，使用中括号访问

列表查询

?index(value,[start,[stop]]) ?通过值value，从指定区间查找列表内的元素是否匹配 ?匹配第一个就立即返回索引 ?匹配不到，抛出异常ValueError ?count(value) ?返回列表中匹配value的次数 ?时间复杂度 ?index和count方法都是O(n) ?随着列表数据规模的增大，而效率下降 ?如何返回列表元素的个数？如何遍历？如何设计高效？ ?len()

如何查帮助

?官方帮助文档 ?搜索关键字

?IPython中 ?help(keyword) ?keyword可以是变量、对象、类名、函数名、方法名

列表元素修改

?索引访问修改 ?list[index] = value ?索引不要超界

列表增加、插入元素

?append(object) -> None ?列表尾部追加元素，返回None ?返回None就意味着没有新的列表产生，就地修改 ?时间复杂度是O(1) ?insert(index, object) -> None ?在指定的索引index处插入元素object ?返回None就意味着没有新的列表产生，就地修改 ?时间复杂度是O(n) ?索引能超上下界吗？ ?超越上界，尾部追加 ?超越下界，头部追加

列表增加、插入元素

?extend(iteratable) -> None ?将可迭代对象的元素追加进来，返回None ?就地修改 ?+-> list ?连接操作，将两个列表连接起来 ?产生新的列表，原列表不变 ?本质上调用的是魔术方法add()方法 ?*-> list ?重复操作，将本列表元素重复n次，返回新的列表

列表*重复的坑

?*-> list ?重复操作，将本列表元素重复n次，返回新的列表

x = [[1, 2, 3]]*3
print(x)
x[0][1] = 20
print(x)
y = [1]*5
y[0] = 6
y[1] = 7
print(y)
?
------------------------------
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[1, 20, 3], [1, 20, 3], [1, 20, 3]]
[6, 7, 1, 1, 1]

上面代码运行结果是什么？为什么？

列表删除元素

? remove(value) -> None ? 从左至右查找第一个匹配value的值，移除该元素，返回None ? 就地修改 ? 效率？ ? pop([index]) -> item ? 不指定索引index，就从列表尾部弹出一个元素 ? 指定索引index，就从索引处弹出一个元素，索引超界抛出IndexError错误 ? 效率？指定索引的的时间复杂度？不指定索引呢？ ? clear() -> None ? 清除列表所有元素，剩下一个空列表

列表其它操作

? reverse() -> None ? 将列表元素反转，返回None ? 就地修改 ? sort(key=None, reverse=False) -> None ? 对列表元素进行排序，就地修改，默认升序 ? reverse为True，反转，降序 ? key一个函数，指定key如何排序 ? lst.sort(key=function)

? in ? [3,4] in [1, 2, [3,4]] ? for x in [1,2,3,4]

列表复制 ? copy() -> List ? shadow copy返回一个新的列表

lst0 = list(range(4))
lst5 = lst0.copy()
print(lst5 == lst0)#True
lst5[2] = 10
print(lst5 == lst0)#Fulse
?
--------------------------------------
True
False

lst0和lst5一样吗？ ? 对比左右程序的差别

lst0 = [1, [2, 3, 4], 5]
lst5 = lst0.copy()
lst5 == lst0
lst5[2] = 10
lst5 == lst0
lst5[2] = 5
lst5[1][1] = 20
lst5 == lst0
print(lst0,lst5)
--------------------------------------
[1, [2, 20, 4], 5] [1, [2, 20, 4], 5]

列表复制

? shadow copy ? 影子拷贝，也叫浅拷贝，遇到引用类型，只是复制了一个引用而已 ? 深拷贝 ? copy模块提供了deepcopy

import copy
    lst0 = [1, [2, 3, 4], 5]
    lst5 = copy.deepcopy(lst0)
    lst5[1][1] = 20
    lst5 == lst0

随机数

? random模块 ? randint(a, b) 返回[a, b]之间的整数 ? choice(seq) 从非空序列的元素中随机挑选一个元素，比如random.choice(range(10))，从0到9中 随机挑选一个整数。random.choice([1,3,5,7]) ? randrange ([start,] stop [,step]) 从指定范围内，按指定基数递增的集合中获取一个随机数，基数 缺省值为1。 random.randrange(1,7,2) ? random.shuffle(list) ->None 就地打乱列表元素 ? sample(population, k) 从样本空间或总体（序列或者集合类型）中随机取出k个不同的元素，返回 一个新的列表 ? random.sample([‘a‘, ‘b‘, ‘c‘, ‘d‘], 2) ? random.sample([‘a‘, ‘a‘], 2) 会返回什么结果

列表作业

? 求100内的素数 ? 从2开始到自身的-1的数中找到一个能整除的=》从2开始到自身开平方的数中找到一个能整除的 ? 一个合数一定可以分解成几个素数的乘积，也就是说，一个数如果能被一个素数整除就是合数 ? 计算杨辉三角前6行 ? 第n行有n项，n是正整数 ? 第n行数字之和为2n-1 只要求打印出杨辉三角的数字即可

左右部分：

求100内的素数 为了比较算法效率我们扩大到求100000内素数

import datetime
# 1 简单算法
# 一个数能被从2开始到自己的平发根的正整数整数整除，就是合数
start = datetime.datetime.now()
n = 100000
count = 0
for x in range(2, n):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            break
        else:
            count += 1
#print(x)
delta = (datetime.datetime.now() - start).total_seconds()
print(count) # 9592
print(delta) # 0.267015
print(‘-‘ * 30)
----------------------------------------------
2655287
0.680335
------------------------------

使用奇数：

start = datetime.datetime.now()
?
n = 100000
count = 1
for x in range(3, n, 2):
    for i in range(3, int(x ** 0.5)+1, 2):
        if x % i == 0:
            break
        else:
        count += 1
#print(x)
delta = (datetime.datetime.now() - start).total_seconds()
print(count) # 9592
print(delta) # 0.132007
print(‘-‘ * 30)
--------------------------------------
1305035
0.35907
------------------------------

3 存储质数

合数一定可以分解为几个质数的乘积，2是质数

质数一定不能整除1和本身之内的整数

start = datetime.datetime.now()
n = 100000
count = 1
primenumbers = [2]
for x in range(3, n, 2):
    for i in primenumbers:
        if x % i == 0:
            break
        else:
            primenumbers.append(x)
            count += 1
delta = (datetime.datetime.now() - start).total_seconds()
print(count) # 9592
print(delta) # 4.02523
print(‘-‘ * 30)
----------------------------------------
9592
4.569395
------------------------------

4 缩小范围

?
start = datetime.datetime.now()
n = 100000
count = 1
primenumbers = [2] # 质数列表
?
for x in range(3, n, 2):
    flag = False # 不是素数
    for i in primenumbers:
        if i > int(x ** 0.5): # 素数
            flag = True
            break
        if x % i == 0: # 合数
            flag = False
            break
    if flag:
        primenumbers.append(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()
print(count) # 9592
print(delta) # 0.315018
----------------------------------------
9592
0.330924
------------------------------

算法2和算法4对比，算法2的奇数应该是多于算法4的，也就是算法4应该要快一点，但是测试的记过却不是，为什 么？ 结果是增加了质数列表反而慢了，为什么？ 修改算法如下

# 4 缩小范围
# x ** 0.5 在循环中只需计算一次
# 使用列表存储已有的质数，同时缩小范围
start = datetime.datetime.now()
n = 100000
count = 1
primenumbers = [2]
?
for x in range(3, n, 2): # 大于2质数只可能是奇数
    flag = False # 不是素数
    edge = int(x**0.5) # 计算一次
    for i in primenumbers:
        if i > edge: # 素数
            flag = True
            break
        if x % i == 0: # 合数
            flag = False
            break
    if flag:
        primenumbers.append(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()
print(count) # 9592
print(delta) # 0.106006
---------------------------------------------
9592
0.108905
-------------------------------------

这回测试，速度第一了。也就是增加了列表，记录了质数，控制了边界后，使用质数来取模比使用奇数计算更少。 空间换时间，使用列表空间存储质数列表，来换取计算时间。

孪生素数性质 大于3的素数只有6N-1和6N+1两种形式，如果6N-1和6N+1都是素数称为孪生素数

# 大于3的素数只有6N-1和6N+1两种形式，如果6N-1和6N+1都是素数称为孪生素数
# 注意，其实测试的都是6的倍数的前后的数字，这些数字一定是奇数
n = 100
count = 5 # 2, 3, 5
x = 7
step = 4
?
while x < n:
    if x % 5 != 0:
        print(x) # 打印出待测试的数
    x += step
    step = 4 if step == 2 else 2

由此，得到下面算法5

# 5 使用素数性质
# 大于3的素数只有6N-1和6N+1两种形式，如果6N-1和6N+1都是素数称为孪生素数
start = datetime.datetime.now()
n = 100000
count = 3 # 2, 3, 5
x = 7
step = 4
?
while x < n:
    if x % 5 != 0:
        for i in range(3, int(x**0.5)+1, 2):
            if x % i == 0: # 合数
                break
        else:
            count += 1
    x += step
    step = 4 if step == 2 else 2
delta = (datetime.datetime.now() - start).total_seconds()
print(count) # 9592
print(delta) # 0.122006
----------------------------------------------
9592
0.146466
----------------------------------------------

用了这个性质并没有超过算法4，原因还是在于使用列表来存储已经计算得到的素数来减少计算。请自行使用列表完成素数的存储。

计算杨辉三角前6行

第n行有n项，n是正整数

第n行数字之和为2**(n-1)

解法1 杨辉三角的基本实现

下一行依赖上一行所有元素，是上一行所有元素的两两相加的和，再在两头各加1

预先构建前两行，从而推导出后面的所有行

triangle = [[1], [1, 1]]
?
for i in range(2, 6):
    cur = [1]
    pre = triangle[i-1]
    for j in range(i - 1):
        cur.append(pre[j] + pre[j+1]) # 前一行2项之和
    cur.append(1)
    triangle.append(cur)
print(triangle)

变体 从第一行开始

triangle = []
n = 6
?
for i in range(n):
    cur = [1]
    triangle.append(cur)
?
    
    if i == 0: continue
    pre = triangle[i-1]
    for j in range(i - 1):
        cur.append(pre[j] + pre[j+1]) # 前一行2项之和
    cur.append(1)
print(triangle)

解法2 补零

除了第一行以外，每一行每一个元素（包括两头的1）都是由上一行的元素相加得到。如何得到两头的1呢？目标是打印指定的行，所以算出一行就打印一行，不需要用一个大空间存储所有已经算出的行。

for循环实现

n = 6
newline = [1] # 第一行是特例，因为0+0不等于1
print(newline)
?
for i in range(1, n):
    oldline = newline.copy() # 浅拷贝并补0
    oldline.append(0) # 尾部补0相当于两端补0
    newline.clear() # 使用append，所以要清除
?
    for j in range(i+1):
        newline.append(oldline[j - 1] + oldline[j])
    print(newline)

解法3 对称性

思路： 能不能一次性开辟空间，可以使用列表解析式或者循环迭代的方式。 能不能减少一半的数字计算。左右对称。

1、 构建行

triangle = []
n = 6
?
for i in range(n):
    row = [1]
    for k in range(i):
        row.append(1) if k==i-1 else row.append(0)
    triangle.append(row)
print(triangle)

上面创建每一行的代码过于啰嗦了，一次性创建出一行，以后覆盖其中数据就行了

triangle = []
n = 6
?
for i in range(n):
    row = [1] * (i + 1) # 开辟速度快
    triangle.append(row)
print(triangle)

2、 中点的确定

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
把整个杨辉三角看成左对齐的二维矩阵。
i==2时，在第3行，中点的列索引j==1
i==3时，在第4行，无中点
i==4时，在第5行，中点的列索引j==2
得到以下规律，如果有i==2j，则有中点
?
triangle = []
n = 6
?
for i in range(n):
    row = [1] * (i + 1) # 一次开辟空间
    triangle.append(row)
?
    # i为0、1不进来，前两行进不来
    # i为2，range(1,2)，j取1
    # i为3，range(1,2)，j取1
    # i为4，range(1,3)，j取1 2
    for j in range(1, i//2+1):
        val = triangle[i-1][j-1] + triangle[i-1][j]
        row[j] = val
        row[-j-1] = val
?
print(triangle)

上面的代码row[-j-1] = val 多做了一次

triangle = []
n = 6
?
for i in range(n):
    row = [1] * (i + 1) # 一次开辟空间
    triangle.append(row)
    
    # i为0、1不进来
    # i为2，range(1,2)，j取1
    # i为3，range(1,2)，j取1
    # i为4，range(1,3)，j取1 2
    for j in range(1, i//2+1):
        val = triangle[i-1][j-1] + triangle[i-1][j]
        row[j] = val
        if i != 2 * j:
            row[-j-1] = val
?
print(triangle)

另一种中点的处理

                            i 中点索引 j
[1]
[1, 1]
[1, 2, 1]                   2 1 or -2 0
[1, 3, 3, 1]
[1, 4, 6, 4, 1]             4 2 or -3 1
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]    6 3 or -4 2
由此，得到中点的索引处i和j关系为i=2*(j+1)

其实，相当于上例中代码的j循环向左平移1，将所有的j变成 j+1

# 对称
triangle = [[1], [1, 1]] # 所有行
n = 10
for i in range(2, n): # 121
    row = [1] * (i + 1) # 一次性开辟内存空间，效率更高
    triangle.append(row)
?
    for j in range(i//2): # i=4, range(2) => 0, 1
        val = triangle[i-1][j] + triangle[i-1][j+1] # 1 3 3 1
        row[j+1] = val
        if i != 2*(j+1):
            row[-(j+2)] = val # 有可能被重置
        else: # i == 2*(j+1) 中点，n=7出现过3次中点
            print(‘,,,,,‘, val)
print(triangle)

解法4 单行覆盖

方法2每次都要清除列表，有点浪费时间。 能够用上方法3的对称性的同时，只开辟1个列表实现吗？

首先我们明确的知道所求最大行的元素个数，例如前6行的最大行元素个数为6个。 下一行等于首元素不变，覆盖中间元素。

n = 6
row = [1] * n # 一次性开辟足够的空间
print(row)
print(‘-‘ * 30)
for i in range(n):
    print(row[:i+1])
运行结果如下
[1, 1, 1, 1, 1, 1]
------------------------------
[1]
[1, 1]
[1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]

由于，这一次直接开辟了所有大小的列表空间，导致负索引比较难计算。 是否可以考虑直接使用正索引计算呢？

以第七行为例，索引1对称索引为5，而1 + 5 = 6当前索引值。

n = 6
row = [1] * n # 一次性开辟足够的空间
print(row)
print(‘-‘ * 30)
?
for i in range(n):
    for j in range(i//2): # i为0,1不进入
        val = row[j] + row[j+1]
        row[j+1] = val
        if i != 2 * (j+1):
            row[i-(j+1)] = val
    print(row[:i+1])
运行结果如下
[1, 1, 1, 1, 1, 1]
------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 7, 4, 1]
[1, 5, 12, 12, 5, 1]

问题出在哪里了呢？ 原因在于，4覆盖了3，导致3+3变成了3+4才有了7。使用一个临时变量解决

n = 6
row = [1] * n # 一次性开辟足够的空间
print(row)
print(‘-‘ * 30)
?
for i in range(n):
    old = 1 # 相当于每行行首1，因为i从4开始就有覆盖了，引入这个变量
    for j in range(i//2): # i为0,1不进入
        val = old + row[j+1]
        old = row[j+1]
        row[j+1] = val
        if i != 2 * (j+1):
            row[i-(j+1)] = val
?
    print(row[:i+1])

也可以写成下面这样

?
n = 6
row = [1] * n # 一次性开辟足够的空间
print(row) 
print(‘-‘ * 30)
?
for i in range(n):
    old = 1 # 相当于每行行首1，因为i从4开始就有覆盖了，引入这个变量
    for j in range(i//2): # i为0,1不进入
        # val = old + row[j+1]
        # old = row[j+1]
        # row[j+1] = val
        row[j+1], old = old + row[j+1], row[j+1] 
        if i != 2 * (j+1):
            row[i-(j+1)] = row[j+1]
    print(row[:i+1])
--------------------------------------------
[1, 1, 1, 1, 1, 1]
------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

------------恢复内容结束------------

Python内置数据结构

原文：https://www.cnblogs.com/adaxi/p/12450122.html