真正想要的东西，
不只是踮踮脚尖那么简单，
所有的收获，一定要全力以赴，奋不顾身!
现在的怕和愁，都是能力小和经历少;十年后，所有的事，都只是下酒菜。
算法里面最经典的题目：（必须掌握*****）质数、杨辉三角、矩阵
列表在Python中是最重要的数据结构，数组在Java中也是最重要的数据结构；
面试题其实就是问你在这些基础解法上有优化策略没有（进行改进，变换）
算法中玩的就是这些东西；所以我们必须学到极致；
1.杨辉三角
最朴素的想法:下一行依赖于上一行所有元素，是上一行所有元素相加的和，再在两头各加1；
# 杨辉三角的打印；
#如何思考，哪个地方卡住了；
#列表用的好，编成搞定了一小块了（高手的门槛）
方法1 二位数组 列表循坏迭代，大的框架到小框架下解决问题（二维列表的操作）；
tri=[[1],[1,1]]
n=9
for i in range(2,n):
lst=[1] # 头部；
pre=tri[i-1] #先命名内部列表，由大到小的简化过程；
for j in range(i-1): #迭代（i-1次） 计数器
#算121
val=pre[j]+pre[j+1] #这就是加法；
lst.append(val)
#这两种追加本质上不同；
lst.append(1) #尾巴
tri.append(lst) # 内部内标 放到大列表中；
print(tri)
#问题：1.列表的层级命名不会，总想一部到位；思路断掉
可优化方案：
1.大框架迭代会消耗大量的内存，去掉大列表 tri，循环打印；
2.两个列表不停的追加，用完就丢掉了，对GC垃圾回收机制是一种负担；
方法1.1 只把第一行当作特例处理
tri=[[1]]
n=9
for i in range(1,n):
lst=[1] # 头部；
pre=tri[i-1] #先命名内部列表，由大到小的简化过程；
for j in range(i-1): #迭代（i-1次） for循环相当于 计数器
#算121
val=pre[j]+pre[j+1] #这就是加法；
lst.append(val)
lst.append(1) #尾巴
tri.append(lst) # 内部内标 放到大列表中；
print(tri)
方法1.2 第一行特例处理，进一步优化——容器处理问题（方法1变体）
tri=[]
n=6
for i in range(n):
newline=[1]
tri.append(newline)
if i==0:
continue
for j in range(i-1):
val=tri[i-1][j]+tri[i-1][j+1]
newline.append(val)
newline.append(1) #尾巴
print(tri)
方法2 杨辉三角 两头补0法；
# 锻炼思维，算法；
n=6
pre=[1]
print(pre)
pre.append(0)
for i in range(1,n):
lst=[]
for j in range(i+1):
s=pre[j-1]+pre[j]
lst.append(s)
print(lst)
pre=lst
pre.append(0)
-----------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
#问题：
1.索引怎么算？一步一步算；
2.效率不太高，两头的1都是加出来的，但思维方法值得学习；
3.变量名也要规范，从现在养成习惯；
4.清楚自己循环多少次的，建议用for循环；不知道多少次，用while;
方法3 问题所在：
1.能不能一次新开辟每一行空间：列表解析式、循环迭代、乘法效率最高，减少每一次追加元素拓展带来的性能损耗；
2.能不能少算一半的数字（对称性）；
优化方案：
1.每一次append是一种效率较低的方法，每次都开辟空间；内存中给你默认开辟的列表空间往往比你想象的大；你感觉不出来；一次性开辟空间效率最高；
2.迭代+算太多次，中点和负索引可以减少计算的次数；
方法3 一次性开辟所有需要的列表空间
tri=[]
n=6
for i in range(n):
row=[1]*(i+1) #一次性开辟所有空间
tri.append(row)
for j in range(1,i//2+1): # i=2 第三行才能进来，计算一半的值；
val=tri[i-1][j-1]+tri[i-1][j]
row[j]=val
if i !=2*j: #奇数个数重点断开；（对称负索引赋值）
row[-j-1]=val
print(tri)
--------------------------------
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]
总结优化方案;
1.对称折半思想可以大大减少计算机计算的量;
2.两边的1也可不用计算，如何开辟更有效？
方法4 杨辉三角
n=6
row=[1]*n #一次性开辟足够的空间；
for i in range(n):
offset=n-i
z=1 #因为会有覆盖影响计算，索引引入一个临时变量；
for j in range(1,i//2+1):
val=z+row[j]
row[j],z=val,row[j]
if i !=2*j:
row[-j-offset]=val
print(row[:i+1])
----------------------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
2.素数问题
求100以内的素数
基本做法：
1.一个数能被从2开始到自己的平方根的正整数整除，就是合数；
2.一个合数一定可以分解成几个素数的乘积，也就是说，一个数如果被一个素数整除就是合数；
#素数问题
import math
n=100
for x in range(2,n):
for i in range(2,math.ceil(math.sqrt(x))):
if x%i == 0:
break
else:
print(x)
方法2 去掉math函数部分；
#储存质数合数一定可以分解为几个质数的乘积；
n=100
lst=[2]
for i in range(3,n,2): #
for j in lst: # (3,i**0.5+1,2)=lst
if i%j==0:
break
else:
print(i) #找到了一个质数；
lst.append(i)
方法2.1——改进方案；
n=100
lst=[2]
for i in range(3,n,2): #
flag=False
for j in lst: # (3,i**0.5+1,2)=lst
if j>i**0.5:
flag=True
break
if i%j==0:
flag=False
break #合数
if flag:
print(i) #找到了一个质数；
lst.append(i)
几种优化策略
网友评论