一、线性结构
1.1 线性结构
- 可迭代 for ... in
- len() 可以获取长度
- 通过下标可以可以访问
- 可以切片
1.2 前面学习过的线性结构
- 列表(list)、元组(tuple)、字符串(string)、bytes、bytearray
二、切片
1.1 切片
- 通过索引区间访问线性结构的一段数据
- sequence[start:stop] 表示返回 [start, stop) 区间的子序列
- 支持负索引
- start 为 0，可省略
- stop 为末尾，可省略
- 超过上界（右边界），就取到末尾；超过下界（左边界），取到开头
- start 一定要在 stop 左边
- [:] 表示从头至尾，全部元素被取出，等效于 copy() 方法
- 示例
print('www.rookie.com'[4:10])
print('www.rookie.com'[:10])
print('www.rookie.com'[4:])
print('www.rookie.com'[:])
print('www.rookie.com'[:-1])
print('www.rookie.com'[4:-4])
print('www.rookie.com'[4:50])
print('www.rookie.com'[-40:10])
print(bytearray(b'www.rookie.com')[-4:10])
print(tuple('www.rookie.com')[-10:10])
print(list('www.rookie.com')[-10:-4])
切片示例 - 1.png
切片示例 - 2.png
1.2 步长切片
- [start: stop: step]
- step 为步长，可以正、负整数，默认是 1
- step 要和 start: stop 同向，否则返回空序列
- 示例
'www.rookie.com'[4:10:2]
list('www.rookie.com')[4:10:-2]
tuple('www.rookie.com')[-10:-4:2]
b'www.rookie.com'[-4:-10:2]
bytearray(b'www.rookie.com')[-4:-10:-2]
'www.rookie.com'[::2]
'www.rookie.com'[::-3]
步长示例.png
1.3 切片赋值
- 切片操作卸载等号左边
- 被插入值可迭代对象写在等号右边
- 示例
a = list(range(5))
a[1:2] = 10 # 右边必须是可迭代对象
a[1:2] = {10, 11} # [0, 10, 11, 2, 3, 4]
a[1:-1] = () # [0, 4]
b = list()
b[:] = a
c = a
print(id(a), id(b), id(c))
赋值示例.png
二、练习
2.1 求素数
- 方案 1
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)
print (count)
方案 1.png
- 方案 2
- 利用奇数来计算
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)
print (count)
方案 2.png
- 方案 3
- 奇数 + 质数列表
- 合数一定是质数的乘积，合数一定可以找到一个质数整除
n = 100000
count = 1
primenums = []
for x in range(3, n, 2): # 奇数
for i in primenums: # 从质数列表中提取质数
if x % i == 0: # 被质数整除了，说明是合数
break
else: # 质数
count += 1
primenums.append(x)
print (count)
方案 3.png
- 方案 4
- 奇数 + 质数列表
- 改进，添加判断 “ 中间点 ”，开方值
n = 100000
count = 1
primenums = []
for x in range(3, n, 2): # 奇数
flag = True # 假定为质数
edge = int(x**0.5) # 中间点，可提前判断
for i in primenums: # 从质数列表中提取质数
if x % i == 0: # 被质数整除了，说明是合数
flag = False
break
if i > edge: # 添加中间点判断，提升效率
flag = True # 质数
break
if flag: # 质数
count += 1
primenums.append(x)
print (count)
方案 4.png
- 方案 5
- 孪生素数
- 大于 3 的素数只有 6N-1 和 6N+1 两种形式，如果 6N-1 和 6N+1 都是素数，则称为孪生素数
n = 100000
count = 3
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 # 7
step = 4 if step == 2 else 2
print (count)
方案 5.png
2.2 杨辉三角
-
图示
杨辉三角.png
-
方案 1
triangle = [[1], [1,1]] # 所有行
for i in range(2, 6): # 行
row = [1] # 创建新行
pre = triangle[i-1]
for j in range(i-1):
row.append(pre[j] + pre[j+1])
row.append(1)
triangle.append(row)
print (triangle)
n = 1000
triangle = [] # 所有行
for i in range(n): # 行
row = [1] # 创建行
triangle.append(row)
if i == 0: continue
pre = triangle[i-1]
for j in range(i-1):
row.append(pre[j] + pre[j+1])
row.append(1)
print (triangle)
方案 1.png
方案 1.png
- 方案 2
- 补零
n = 1000
oldline = [1] # 第一行
print (oldline)
for i in range(1,n):
oldline.append(0) # [1,0]
newline = []
for j in range(i+1): # 2
newline.append(oldline[j-1] + oldline[j])
print (newline)
oldline = newline
方案 2.png
- 方案 3
- 对称性
n = 1000
triangle = [[1], [1, 1]] # 所有行
for i in range(2, n): # 121
row = [1] * (i + 1) # 一次性开辟内存空间，效率更高
triangle.append(row)
for j in range(i - 1):
val = triangle[i - 1][j] + triangle[i - 1][j + 1]
row[j + 1]=val
row[-(j + 2)] = val
print(triangle)
方案3.png
- 方案 4
- 单行覆盖
n = 1000
line = [1] * n # 一次性开辟优于次次追加
for i in range(n):
offset = n - i
swap = 1
for j in range(1, i//2+1): # i=3 range(1, 2)
line[j], swap = swap + line[j], line[j]
if i ~= 2*j:
line[-j-offset] = line[j]
print(line[:i+1])
方案4.png
网友评论