Serendipity

山有木兮木有枝

0%

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

最长公共子序列问题

问题描述:

给定两个字符串s1s2s3…sn和t1t2t3…tm,求出这两个字符串最长的公共子序列(LCS,longest Common Subsequence 最长公共子序列问题),例如:

输入
n = 4
m = 4
s = ‘abcd’
t = ‘becd’

输出:
3(’bcd’)


解析:

定义:

dp[i][j] := a1...ai和b1...b[j]的最长公共子序列LCS数

由此,s1…si+1和t1…tm+1的子序列可能是:

  1. 当s1+1等于tj+1时,等于在si和tj公共列表后加si+1
  2. 或者等于Si+1和tj之间的LCS
  3. 或者等于si和tj+1之间的LCS

即可推出递推关系:

dp[i+1][j+1] = dp[i][j] + 1 (第1点)

dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]) (2和3点)


代码:

1
2
3
4
5
6
7
8
9
10
11
12
n,m,a,b = 5,6,'bcdef','bcdevf'
dp = [[0 for _ in range(m+1)] for j in range(n+1)]
def DP():
for i in range(n):
for j in range(m):
if a[i] == b[j]:
dp[i+1][j+1] = dp[i][j]+1
else:
dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]) #没有匹配上的两种情况
print(dp[n][m])
DP()

划分数问题

有n个无区别的物品,将他们划分成不超过m组,求出划分方法数模M的余数。
输入:n,m,M = 4,3,10000
输出:4

特别的,当m=n时,叫做n的划分数。通俗的讲就是一个正整数n可以划分成多少个正整数的和?

我们可以这样定义:

dp[i][j] := 把j划分成个数不超过i的方案总数

为了不重复计算,我们把n的划分数归纳于一系列非负整数的集合ai,
$$
\sum_{i=1}^ma_i = n
$$
ai 的定义如上,列入4的3划分为{0,0,4},{0,1,3},{0,2,2},{1,1,2},方案一{0,0,4}的a1,a2,a3分别是0,0,4,依次类推。

可以看出,每个集合里面有m个数,但是不都全为正整数。

所以我们可以将问题分成两类,一个是{ai}里面不包括0,一个是里面存在0。对于不存在0,将4的3划分数{1,1,2}作为例子,可以发现当里面的数个减去一,就变成了{0,0,1},即1的3划分数,它们两个的个数是相同的。所以{ai-1}就对应了n-m的m划分就不难理解了,就是集合里的每个数减去一,一共减了m个。

dp[i][j] = dp[i][j-i]

对于存在0,就好比上面的{0,0,4},{0,1,3},{0,2,2},可以发现集合里面各去掉一个数就变成了{0,4},{1,3},{2,2},即4的2划分。它们的个数是一样的。即

dp[i][j] = dp[i-1][j]

总结:

1
2
3
4
5
6
'''
由此可以发现 dp[3][4] = dp[3][1] + dp[2][4]
所以可以推出递推公式:
dp[i][j] = dp[i][j-i] + dp[i-1][j]
边界条件:dp[0][0] = 1
'''

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
有n个无区别的物品,将他们划分成不超过m组,求出划分方法数模M的余数
输入:
n,m,M = 4,3,10000
输出:
4
'''

n,m,M = 4,3,10000
dp = [[0 for i in range(n+1)] for j in range(m+1)] #用mxn列表记录j的i划分
def DP():
dp[0][0] = 1
for i in range(1,m+1):
for j in range(0,n+1):
if j-i >= 0:
dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % M
else:
dp[i][j] = dp[i-1][j]
print(dp[m][n])
DP()

同样的问题:n的划分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
'''
一个正整数可以划分为多个正整数的和,比如n=3时:
3;1+2;1+1+1;
共有三种划分方法。
给出一个正整数,问有多少种划分方法。
数据规模和约定
n< =100
样例输入
3
样例输出
3
'''

n = int(input())
dp = [[0 for i in range(n+1)] for j in range(n+1)]
def DP():
dp[0][0] = 1
for i in range(1,n+1):
for j in range(0,n+1):
if j - i >= 0:
dp[i][j] = dp[i-1][j] + dp[i][j-i]
else:
dp[i][j] = dp[i-1][j]
print(dp[n][n])
DP()

思维图:

0-1背包问题

有n个重量和价值分别为wi、vi的物品,从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。


穷竭搜索(DFS+递归)

其实这就像深度优先遍历搜索一样,每件物品有两种状态–拿或不拿,确定每个物品的状态转移函数如下:

f(i,j),表示从第i件物品挑选出总重量不超过j的物品的最大和价值

f(i,j) = f(i+1,j) (j<w[i] 第i件物品重量大于剩余重量,表示不能选取此物品)
max(f(i+1,j),f(i+1,j-w[i])+v[i]) (此物品可选,但是否选取由谁的价值大决定)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
def record(i,j):
res = 0
if i == n:
res = 0
elif j < w[i]:
res = record(i+1,j)
else:
res = max(record(i+1,j),record(i+1,j-w[i])+v[i])
return res
print(record(0,W))

不足:通过画深度优先遍历的图来看可以发现有重复计算的值,最坏需要O(2^n^)的时间


记忆化搜索

在进行DFS遍历每个数的时用一个二维列表记录,下次遇到同样的数字即可直接调用,只需O(n*w)的复杂度。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
d = [[-1 for i in range(W+1)] for j in range(n+1)] #-1表示标记
def record(i,j):
res = 0
if d[i][j] >= 0:
return d[i][j]
elif i == n:
res = 0
elif j < w[i]:
res = record(i+1,j)
else:
res = max(record(i+1,j),record(i+1,j-w[i])+v[i])
d[i][j] = res
return d[i][j]
print(record(0,W))


动态规划

二维列表dp根据状态转移函数的定义可以变化成如下递推公式:

dp[n][j]= 0

dp[i][j] = dp[i+1][j] (j<w[i])

max(dp[i+1][j]+ dp[i+1][j-w[i]]+v[i]) 其他

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
dp = [[-1 for i in range(W+1)] for j in range(n+1)]
#初始化dp[n][j] = 0
for index in range(W+1):
dp[n][index] = 0
def DP():
i = n-1
while i >= 0:
for j in range(W+1):
if j < w[i]:
dp[i][j] = dp[i+1][j]
else:
dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[i][j])
i -= 1
print(dp[0][W])
DP()


正向递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
正向递推,上面的方法是逆推的,dp[i+1][j] = 从前i个物品中挑选出总重量不超过j的物品的价值和的最大值
'''
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
dp = [[-1 for i in range(W+1)] for j in range(n+1)]
for index in range(W+1):
dp[0][index] = 0
def DP():
i = 0
while i < n:
for j in range(W+1):
if j < w[i]:
dp[i+1][j] = dp[i][j]
else:
dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
i += 1
print(dp[n][W])
DP()

改进:dp数组再利用

改进,0-1背包问题只用一个数组完成,与上面的只是J控制时遍历的方向不同

1
2
3
4
5
6
7
8
9
10
11
12
n,W = 4,5
w,v = [2,1,3,2],[3,2,4,2]
dp = [0]*(n*W)
def DP():
for i in range(n):
j = W
while j >= w[i]:
dp[j] = max(dp[j],dp[j - w[i]] + v[i])
j -= 1
print(dp[W])
DP()

卑微小白blog https://yujian-code.github.io

卑微小白GitHub YuJian-code

[TOC]

python基础学习导图

python程序基础

程序 = 数据结构 + 算法,所以我用两部分概括了python程序设计基础的内容。

数据结构

数据

数据结构指数据的类型,计算机程序能处理各种数据,如数字、网页、音频、文本、视频等等,不同的数据则需要定义不同的数据类型。python中能直接处理的数据类型有:整型、浮点型、字符型以及布尔型、复数类型五种。

整型

整型,整数类型,例如1、100、-1221、1213243455…,整型有四种表现形式,分别是:

二进制:如 010、110…,只由1和0组成的数字,用0b或0B开头的数字就是二进制类型。

八进制:如0O171、0O732,由三位二进制组成,0o或0O开头的数据就是八进制。

十进制:平常的数字如 1、2、-121等。

十六进制:由四位二进制组成,如0x01af,af表示1015,由0x或0X表示。

由位数不同又分为int 、short、long等。

浮点型

浮点数(float)也就是小数,python的浮点数有两种表现形式:

一是十进制数表示,如:12.21等等

二是用科学计数法表示,如1.32e3,即1.32 * 10^3,虽然结果是整数,但类型是浮点型。

字符串型

字符串字符串是以单引号或双引号括起来的任意文本,比如'hello'"hello",字符串还有原始字符串表示法、字节字符串表示法、Unicode字符串表示法,而且可以书写成多行的形式(用三个单引号或三个双引号开头,三个单引号或三个双引号结尾)。

布尔类型

布尔值只有TrueFalse两种值,要么是True,要么是False,在Python中,可以直接用TrueFalse表示布尔值(请注意是大写),也可以通过布尔运算计算出来(例如3 < 5会产生布尔值True,而2 == 1会产生布尔值False)。

复数类型

import cmath

形如 3 + 2j,和数学上表示一样,只不过虚部是把i换成了j。

python相当于一个计算器,直接输入即可,

1
2
>>> (3+2j)*(3+2j)
(5+12j)

变量

变量(variable),在python中,名称只能由字母、数字、下划线组成,且只能由字母开头,变量不能和关键字相同。

python关键字列表:

img

其实开发者自己可以在python自带IDLE查看关键字列表

keyword.kwlist

字符串

所有的标准序列操作都适用与字符串,如索引、切片、乘法、成员资格检查、长度。最小值、最大值,但是别忘了字符串是不可变的,所以所有的赋值都是非法的。

字符串设置

字符串转义字符

‘/‘,在字符前加反斜线表示此字符不是特殊字符,是可以读出来的,如果不加程序会认为是特殊字符从而会有不同的效果。

format字符串格式转换

设置格式的值时,可以使用单个的值(如字符串或数字),可使用元组(如果要设置多个值的格式),还可以使用字典。‘%’ 字符串格式运算符,‘%’较format简单,format可以运用于更复杂的格式替换。

下面简单用元组演示:

1
2
3
4
>>> format = "Hello,%s,my name is %s"
>>> values = ("python","yujian")
>>> format%values
'Hello,python,my name is yujian'

关于如何用format设置格式:

每个值被替换到字符串中都是替换用‘{}’括起来的元素,要在最终结果中包含‘{}’,则可以用两个花括号表示。

格式替换字段可以设置三部分:

替换字段名

可以向format提供未命名的参数,此参数表示一个字段名,然后在后面格式替换时表明参数值即可替换。如:

1
2
>>> "Hello,{name},welcome to {destination}  world".format(name="yujian",destination="python")
'Hello,yujian,welcome to python world'

name即字段名,后面赋值字符串‘yujian’替换此字段

若在{}里面是数字即表示索引,如:

1
2
>>> "{a}{0}{b}{1}".format(1,2,a=3,b=4)
'3142'

运用此方法要注意必须把索引的值放在前面,不然会引起位置冲突。

转换标志转换

‘!’转换标志符

转换标志:跟在‘ !’号后面的单个字符,当前支持的字符包括r(表示repr,简写‘r’,转义字符)、s(表示str)、a(表示ASCII)。

例如:

1
2
>>> "{a!r} {a!s} {a!a}".format(a = "Π")
"'Π' Π '\\u03a0'"

格式说明符

‘:’冒号表示格式说明符,冒号后面跟单个表达格式符或表达式,可以参照正则表达式。

1
2
>>> "This number is {0:b}".format(8)
'This number is 1000'

设置浮点数的格式

设置浮点数默认格式是到小数点后六位,若不是你想要的格式,则可以自行设定宽度和精度。

宽度和精度都是使用整数整定,例如:

整数整定:

1
2
3
4
5
6
>>> "This number is {0:b}".format(8)
'This number is 1000'
>>> "{num:10}".format(num = 3.14)
' 3.14'
>>> "{num:10}".format(num = "python")
'python '

可见,数字和字符串的对齐方式不一样。

精度整定:前面加一个小数点即可

1
2
3
>>> import math
>>> print("{num:.2f}".format(num = math.pi))
3.14

符号、对齐和0填充

在整度和精度的值前面添加一个标志,这个标志可以是0、加号、减号、或空格,其中0表示用0来填充数字。

填充0:

1
2
>>> "{num:05}".format(num = 3.14)
'03.14'

对齐:

1
2
3
4
>>> print("{0:<8.2f}\n{0:^8.2f}\n{0:>8.2f}".format(math.pi))
3.14
3.14
3.14

指定字符填充:

1
2
>>> "{0:a^15}".format("yujian")
'aaaayujianaaaaa'

说明符“=”

它指定将填充字符放在符号与数字之间,如:

1
2
3
>>> print("{0:8.2f}\n{1:=8.2f}".format(math.pi,-math.pi))
3.14
- 3.14

如图负号和数字分开了

若要加正负号,填充字符放在符号与数字之间加’+‘’-‘

‘#’

放在符号说明符和宽度之间,如:

1
2
3
4
>>> "{:b}".format(32)
'100000'
>>> "{:#b}".format(32)
'0b100000'

如图添加上了二进制信息

字符串常用方法

repr 和str

都表达转换成字符串的意思,函数str() 用于将值转化为适于人阅读的形式,而repr() 转化为供解释器读取的形式(如果没有等价的语法,则会发生SyntaxError 异常)

1
2
3
4
print('1:' + str(123))
print('2:' + repr(123))
print('3:' + str('123'))
print('4:' + repr('123'))

结果:

1
2
3
4
1:123
2:123
3:123
4:'123'

发现结果1、2是一样的,4却较3保留了引号,其实造成这种的原因是str和repr都分别调用的是对象的_str_,__repr__方法,repr保留了符号是其实就是机器识别的语言。

center

方法center()通过在字符串两边添加填充字符,如果不指定默认是空格,如:

1
2
>>> print("Hello,YuJian".center(20,' '))
Hello,YuJian
find、index

方法find()通过在字符串中寻找子串,如果找到返回子串第一个字符的索引,否则返回-1,如:

1
2
>>> "the sun,the moon and you".find("moon",1,20)
12

如上我寻找到“moon“在第12个字符位置处,查找范围是从从位置1到20,注意位置1是’the的’’t‘位置,但返回的都是在整个字符串中的位置。

方法index()查找指定字串在字符串中出现的位置,若没有则引发ValueError。

如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> "hello world".index("world")
6
>>> "hello world".index("wo")
6
>>> "hello world".index(" ")
5
>>> "hello world".index("w",0,15)
6
>>> "hello world".index("w",1,15)
6
>>> "hello world".index("you",1,15)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: substring not found

返回值与find方法一样。

split、join

作用于join相反,用于将字符串拆分为序列,返回的是列表。如:

1
2
3
4
5
6
7
8
>>> str = "maybe is she"
>>> print(str.split(' ' ,1))
['maybe', 'is she']
>>> print(str.split(' ' ,2))
['maybe', 'is', 'she']
>>> print(str.split('is' ,1))
['maybe ', ' she']

spite()方法若没有指定分隔符,这默认从一个或多个连续的空白字符(空格、制表符、换行符等进行差分)。

join()方法连接多个字符串,返回通过指定“字符”连接生成的新字符串。如:

1
2
3
4
5
6
>>> str1 = "-"
>>> str2 = ["2019","11","11"]
>>> print(str1.join(str2))
2019-11-11
>>> print(str.join(str1,str2))
2019-11-11
lower 、upper、title

1
2
3
title()  #将每个单词开头改为大写
lower() #将整个字符串改为小写
upper() #将整个字符串改为大写

例如:

1
2
3
4
5
6
7
8
str = "hello,stranger"
print(str.lower())
print(str.upper())
print(str.title())
#结果
hello,stranger
HELLO,STRANGER
Hello,Stranger
strip、istrip、rstrip

strip() #删除字符串前后的空白并返回删除后的结果
lstrip() #删除字符串前面的空白并返回删除后的结果
rstrip() #删除字符串后面的空白并返回删除后的结果

如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> str = "    Hello,  world   "
>>> str.strip()
'Hello, world'
>>> str.lstrip()
'Hello, world '
>>> str.rstrip()
' Hello, world'
#指定删除哪些字符
>>> str.strip("*@")
'yujian'
>>> str.strip("* @")
'yujian'
>>> str.strip("*or@")
'yujian'
>>> str.strip("*and@")
'yuji'
replace、translate

replace()方法用指定子串替换字符串中的目标子串

如:

1
2
3
>>> "Hello world".replace("world","yujain",4)
'Hello yujain'
#将world替换成了yujian,4表示不超过4次

translate()方法使用指定的映射表对字符串进行替换,不过translate()方法需要手动输入各字符的编码进行替换,所以有了一种更方便的方法maketrans()来创建映射表,如:

1
2
3
>>> table = str.maketrans('abc','αβγ')
>>> table
{97: 945, 98: 946, 99: 947}

此时映射表已经创建完成,然后就可以较便捷的使用translate()替换了,如:

1
2
3
>>> str = "abscond"
>>> print(str.translate(table))
αβsγond

下面用一段程序来了解其他一些字符串的应用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def main():
str1 = 'hello, world!'
# 通过len函数计算字符串的长度
print(len(str1)) # 13
# 获得字符串首字母大写的拷贝
print(str1.capitalize()) # Hello, world!
# 获得字符串变大写后的拷贝
print(str1.upper()) # HELLO, WORLD!
# 从字符串中查找子串所在位置
print(str1.find('or')) # 8
print(str1.find('shit')) # -1
# 与find类似但找不到子串时会引发异常
# print(str1.index('or'))
# print(str1.index('shit'))
# 检查字符串是否以指定的字符串开头
print(str1.startswith('He')) # False
print(str1.startswith('hel')) # True
# 检查字符串是否以指定的字符串结尾
print(str1.endswith('!')) # True
# 将字符串以指定的宽度居中并在两侧填充指定的字符
print(str1.center(50, '*'))
# 将字符串以指定的宽度靠右放置左侧填充指定的字符
print(str1.rjust(50, ' '))
str2 = 'abc123456'
# 从字符串中取出指定位置的字符(下标运算)
print(str2[2]) # c
# 字符串切片(从指定的开始索引到指定的结束索引)
print(str2[2:5]) # c12
print(str2[2:]) # c123456
print(str2[2::2]) # c246
print(str2[::2]) # ac246
print(str2[::-1]) # 654321cba
print(str2[-3:-1]) # 45
# 检查字符串是否由数字构成
print(str2.isdigit()) # False
# 检查字符串是否以字母构成
print(str2.isalpha()) # False
# 检查字符串是否以数字和字母构成
print(str2.isalnum()) # True
str3 = ' jackfrued@126.com '
print(str3)
# 获得字符串修剪左右两侧空格的拷贝
print(str3.strip())


if __name__ == '__main__':
main()

列表、元组、字典、集合

列表

创建列表,两种方法,

a: a = []

b: a = list()

list() #list() 方法用于将元组或字符串转换为列表。

列表是可以修改的序列,可以像一般的序列进行增、删、修改、检查成员操作。

append() #追加元组,元组会被当成一个元素添加到列表中,追加列表也是一样,会被当成一个元素
如果不想把追加的列表或元组当成一个整体,可以用extend()方法。

PS:也就是说append追加的是一个整体,会把”[]”也加进去,而extend是把里面的元素逐一加进去,元组不能追加,里面的元素是固定了的不能改的

1
2
3
4
5
6
7
8
>>> list_a = [1,23,4]
>>> list_b = [2,5]
>>> list_a.extend(list_b)
>>> print(list_a)
[1, 23, 4, 2, 5]
>>> list_a.append(list_b)
>>> list_a
[1, 23, 4, 2, 5, [2, 5]]

del() #删除列表里单个元素或者一列元素,还可以删除变量
insert(number,element) #插入一个或者一段元素,可指定位置
remove() #移除列表匹配到元素的第一项 list.remove(obj)
clear() #清空列表

sort() #list.sort( key=None, reverse=False) 默认升序,返回一个列表,sort()返回原列表,sorted()返回新列表。

1
2
3
4
5
6
7
8
9
>>> a = [1,2,3,4,5]
>>> b = [2,3,1,4,0]
>>> b.sort()
>>> b
[0, 1, 2, 3, 4]
>>> c = sorted(a)
>>> c
[1, 2, 3, 4, 5]
>>>

pop() #将列表当成栈使用

PS:pop是唯一既修改列表又返回一个非None值的列表方法

reverse() #将列表中的元素反向存放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def main():
list1 = [1, 3, 5, 7, 100]
print(list1)
list2 = ['hello'] * 5
print(list2)
# 计算列表长度(元素个数)
print(len(list1))
# 下标(索引)运算
print(list1[0])
print(list1[4])
# print(list1[5]) # IndexError: list index out of range
print(list1[-1])
print(list1[-3])
list1[2] = 300
print(list1)
# 添加元素
list1.append(200)
list1.insert(1, 400)
list1 += [1000, 2000]
print(list1)
print(len(list1))
# 删除元素
list1.remove(3)
if 1234 in list1:
list1.remove(1234)
del list1[0]
print(list1)
# 清空列表元素
list1.clear()
print(list1)


if __name__ == '__main__':
main()

元组

元组,是不可更改的序列,用()包括的序列就是元组,元组和列表的创建和内存占比明显前者更优。元组的列表有许多相似的,唯一不同之处就在于元组不可更改,里面的元素是固定了的。

创建方式:

a = (element1,element2…)

a = turple()

tuple() #Python 元组 tuple() 函数将列表转换为元组

元组和列表的共用方法

只有一个元素的元组:(1,) 必须带逗号

列表和元组都可以用加法和乘法,但只能同类型的

max() 求元组或列表的最大值
min() 求元组或列表的最小值
len() 求元组或列表的长度

index() #用于某个元素出现在列表或元组中的位置
count() #用于统计某个元素在列表中或元组出现的次数

in运算运用于列表、元组是否包含元素

列表封包和序列解包

程序把多个值赋给一个变量时,python会自动把多个值封装成元组,这叫做封包;

程序允许直接将序列(列表或元组)赋给多个变量,此时序列的各元素会依次赋给各个变量,这叫做解包,但序列的元素和变量的元素应该相同。

1
2
3
4
5
6
7
8
>>> list_a = [1,2,3]
>>> a,b,c = list_a
>>> print(a,b,c)
1 2 3
#变量前加*号表示该变量表示一个列表
>>> c,*d = list_a
>>> print(c,d)
1 [2, 3]

集合

set和dict类似,也是一组key的集合,但不存储value。由于key不能重复,所以,在set中,没有重复的key。

要创建一个set,需要提供一个list作为输入集合:

1
2
3
4
5
6
7
8
9
10
>>> set1 = set([1,2,2,3,3,4,4,5,6,])
>>> set1
{1, 2, 3, 4, 5, 6}
>>> set2 = set([2,3,4,7,8])
>>> set1&set2
{2, 3, 4}
>>> set1|set2
{1, 2, 3, 4, 5, 6, 7, 8}
>>> set1-set2
{1, 5, 6}

Python中的集合跟数学上的集合是一致的,不允许有重复元素,而且可以进行交集、并集、差集等运算,也和数学上的运算一致。

字典

元组可以作为dictionary的key,但列表不能,这是因为字典要求key是不可变的

1
2
3
dict = dict()
dict = {}.fromkeys()
dict = {}

字典的基本用法: 通过key访问value值,修改、删除、添加key-value对,以及判断key-value对是否存在

字典的常用方法:

clear() #清空所有的key-value对
get() #获取key的value值
update() #用新字典更新原有字典,若有则覆盖无则添加
items()、keys()、values() #分别用于获取所有的key-value值,所有的key值,所有的value值,分别返回 dict_items、dict_keys、dict_values对象。

pop() #获取指定key的value同时这个键-值会从子典中删除。

popitem() #方法用于弹出字典最后一个key-value对,并且封装成元组

setdefalt() #也是根据key来获取value值,但有一点不同,如若没有它将返回为之设置的默认值。

1
2
3
4
5
6
7
8
9
10
>>> dict1 = {'sun':20,'liu':21}
#没有 key='deng',则先设置key = 'deng',value=20,然后返回该key的键值
>>> print(dict1.setdefault('deng',20))
20
>>> dict1['xia'] = 21
>>> dict1
{'sun': 20, 'liu': 21, 'deng': 20, 'xia': 21}
#存在key='xia',则不会修改该value值
>>> dict1.setdefault('xia',23)
21

{}.fromkeys() #设置新字典

运算符

Python支持多种运算符,下表大致按照优先级从高到低的顺序列出了所有的运算符,我们会陆续使用到它们。
| 运算符 | 描述 |
| ———————————————————— | —————————— |
| [] [:] | 下标,切片 |
| ** | 指数 |
| ~ + - | 按位取反, 正负号 |
| * / % // | 乘,除,模,整除 |
| + - | 加,减 |
| >> << | 右移,左移 |
| & | 按位与 |
| ^ \| | 按位异或,按位或 |
| <= < > >= | 小于等于,小于,大于,大于等于 |
| == != | 等于,不等于 |
| is is not | 身份运算符 |
| in not in | 成员运算符 |
| not or and | 逻辑运算符 |
| = += -= *= /= %= //= **= &= \|= ^= >>= <<= | (复合)赋值运算符 |

注:在实际开发中,如果搞不清楚优先级可以使用括号来确保运算的执行顺序。

算法

过程控制

程序控制结构有顺序结构、分支结构以及循环结构,类似于C语言及、java。

顺序

顺序结构很好理解,一行一行运行下去,直达最后为止。

分支

1
2
3
4
5
6
7
8
9
10
grades = int(input("请输入你的成绩:"))

if grades >= 90:
print("excellent")
elif grades >= 70:
print("good")
elif grades >= 60:
print("qualified")
else:
print("disqualified")

上面用简单的if分支结构来输出你的成绩等级,共有三条关键语句,if 、elif(else if),和else语句。

if 语句还有一个亲戚断言即 assert,语句逻辑为

1
2
3
4
5
6
7
8
9
10
11
grades = int(input("请输入你的成绩:"))

assert grades >= 80
print("great")

#结果
请输入你的成绩:60
Traceback (most recent call last):
File "d:\Vscode\My code\blog.py", line 3, in <module>
assert grades >= 80
AssertionError

如上,未为满足成绩大于等于80将引发错误

注意:python语句缩进必须全部相同,一般python习惯缩进四个字符, 另外if条件可以是任意类型,当下面的值作为bool类型表达式时,会被认为false类型 ,各类空值如:False、None、0、””、[]、{}

循环

Python中构造循环结构有两种做法,一种是for-in循环,一种是while循环。

for循环

如果明确的知道循环执行的次数或者是要对一个容器进行迭代(后面会讲到),那么我们推荐使用for-in循环, for循环专门用于遍历范围、列表、元素和字典等可迭代对象包含的元素。语法格式如下:

1
2
for 变量 in 字符串|范围|集合等:
statements

例如我们要计算1~100的和
$$
\sum_{n=1}^{100}n
$$

1
2
3
4
sum = 0
for i in range (1,101):
sum += i
print(sum)

.range()可以用来产生一个不变的数值序列,而且这个序列通常都是用在循环中的,例如:
·range(101),可以用来产生1-100的数
·range(1,10),可以产生1-9的数
·range(0,101,2)可以产生1-100的偶数序列,2是步长

while循环

如果要构造不知道具体循环次数的循环结构,我们推荐使用while循环,while循环通过一个能够产生或转换出bool值的表达式来控制循环,循环条件表达式的值为True循环继续,表达式的值为False循环结束。

while 循环条件:

​ 循环体

举一个简单例子,

1
2
3
4
5
6
name = str(input("input your name:"))
while name == "yujian":
print("welcome,yujian")
break
else:
print("hey,who are you?")

注意:上面的代码中使用了break关键字来提前终止循环,需要注意的是break只能终止它所在的那个循环,这一点在使用嵌套的循环结构(下面会讲到)需要引起注意。除了break之外,还有另一个关键字是continue,它可以用来放弃本次循环后续的代码直接让循环进入下一轮。

只有输入正确的名字才可以通过,这就类似于登录账户时的情景了。

练习:

1、判断一个数是不是素数( 素数又叫质数(prime number),有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数 )

1
2
3
4
5
6
7
8
9
num = int(input('please enter a number:'))
for i in range(2, num):
if num % i == 0:
print('%d不是素数' % num)
break
else:
print('%d是素数' % num)
break

或者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from math import sqrt

num = int(input('请输入一个正整数: '))
end = int(sqrt(num))
is_prime = True
for x in range(2, end + 1):
if num % x == 0:
is_prime = False
break
if is_prime and num != 1:
print('%d是素数' % num)
else:
print('%d不是素数' % num)
#参照一个大佬的计算量减了一个深度,zan

2、统计素数

1
2
3
4
5
6
7
8
9
10
11
a, b = int(input("请输入起点数:")), int(input("请输入终点数:"))
sum = 0
for i in range(a, b+1):
for j in range(2, i):
if i % j == 0:
break
else:
print(i, end=",")
sum += 1
print("质素一共有%d个" % sum)

3、打印等腰三角形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#正等腰
lines = int(input("请输入行数 : "))
for i in range(lines):
for j in range(lines - i):
print(end=" ")
print("*" * (2*i+1))
print()
'''请输入行数 : 5
*

***

*****

*******

*********'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#倒等腰
lines = int(input("请输入行数 : "))
for i in range(lines):
for j in range(i):
print(end=" ")
print("*" * ((lines - i) * 2 - 1))
print()
'''
请输入行数 : 5
*********

*******

*****

***

*
'''

4、打印菱形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#实心菱形
lines = int(input("请输入奇数行: "))
half_lines = lines // 2 + 1

#上半部分
for i in range(half_lines):
print(" "*(half_lines-i), end="")
print("*" * (2*i+1))

#下半部分
for i in range(half_lines-1):
print((" ")*(i+2), end="")
print("*" * (lines-2-2*i))
'''请输入奇数行: 5
*
***
*****
***
*'''

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#空心菱形
side = int(input("请输入菱形每条边星星的个数: "))
a = side
b = side

print(" "*(a-1), "*")

#上半部分菱形
for i in range(2, a+1):
print(" "*(a-i), "*", " "*(2*i-4), "*")

#下半部分
for i in range(b-1, 1, -1):
print(" "*(b-i), "*", " "*(2*i-4), "*")

print(" "*(side-1), "*")
'''请输入菱形每条边星星的个数: 5
*
* *
* *
* *
* *
* *
* *
* *
*'''

5、N宫格横竖斜和相等算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#小时候玩的九宫格游戏
lines = int(input("请输入奇数行数: "))

array = [[0] * lines]

for i in range(lines):
array = array + [[0] * lines]

row, col = 0, lines // 2

for i in range(1, lines * lines + 1):
array[row][col] = i
if i % lines == 0:
row += 1
elif row == 0:
row = lines - 1
col += 1
elif col == lines - 1:
row -= 1
col = 0
else:
row -= 1
col += 1

for i in range(lines):
for j in range(lines):
print("%02d" % array[i][j], end=" ")
print()
'''
请输入奇数行数: 5
17 24 01 08 15
23 05 07 14 16
04 06 13 20 22
10 12 19 21 03
11 18 25 02 09
'''


现在才懂的多位数的解法 :man_facepalming:

n奇数幻方口诀:

  1. 数字1放在第一行中间
  2. 依次放在上一个数的右上角

2.1如果右边出去了就回到左边(3,4)
2.2 如果上面出去了就放下面(1,2)
2.3 如果右上角有了就放在这个数的下面

6、水仙花数

水仙花数指一个三个位,其个位数字的立方和等于该数本身,如153 = 1^3+5^3+3^3

1
2
3
4
5
6
7
8
#查找100~1000之间的水仙花数
for i in range(100, 1000):
a = i % 10
b = i // 10 % 10
c = i//100
if a**3 + b**3 + c**3 == i:
print(i,end="、")

7、统计字符串里面的字母、数字、空格以及其他字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
input_str = input("请输入一个字符串:")

char_num, digit_num, char_kon, other_num = 0, 0, 0, 0

for c in input_str:
if c.isdigit():
digit_num += 1
elif c.isalpha():
char_num += 1
elif c is " ":
char_kon += 1
else:
other_num += 1

print("字母个数为:", char_num)
print("数字个数为:", digit_num)
print("空格个数为: ", char_kon)
print("其他字符个数:", other_num)
'''请输入一个字符串:qaz123_- - =—— +——23sasd^%&
字母个数为: 7
数字个数为: 5
空格个数为: 4
其他字符个数: 12'''

说明: str.isalpha() 判断是否由字符组成,str.isdigit() 判断是否由数字组成

函数

定义函数

1、语法格式:

def 函数名(形参列表):
//由零条到多条可执行语句组成的函数
return 返回值

2、从程序的可读性来看,函数名应该由一个或多个有意义的单词连缀而成,每个单词全部小写,单词与单词之间使用下划线分隔。

3、函数的说明文档, 在函数声明之后,注释说明即可。

1
2
3
4
5
6
7
8
9
def max(x,y):
'''
获取两个值较大的那个数
'''
max = x if x > y else y
return max

help(max)
print(max.__doc__)

可以调用__doc__函数来看说明文档,也可以 用help()函数来看说明文档

4、递归函数

在一个函数内调用它自身,被称为递归函数,定义递归函数时,递归一定要向已知方向进行,否则造成死循环。

函数参数

1、python要求将带默认值的参数定义在形参的最后,关键字参数必须位于位置参数的后面,意思是若传入两个参数,有一个是关键字参数,那另一个就是位置参数,必须将位置参数放在传入参数的第一位,若此时关键字参数对应的事函数的第一位参数,则将与传入的参数起冲突。

例如:

1
2
3
4
5
6
7
8
9
10
11
def student(grade,number):
print("I am in %d grade %d number" % (grade,number))

student(15,1)
student(grade=15,number=1)
student(number=1,grade=15)
student(15,number=1)
#不可将关键字参数放在前面,错误方式
#student(number=1,15)
#或者两个都指向同一个位置参数,错误
#student(grade=15,15)

2、参数收集(参数可变的参数)

说明:在形参前面添加一个星号,这就意味着该参数可以接受多个参数,多个参数会被当成元组传入,加两个星号该参数可以收集字典

1
2
3
4
5
6
7
8
9
10
11
def foo(x,*y):
print("x参数:",x)
print("y参数:",y)
foo(1,2,3,4,"伍")
#逆向参数收集
my_tuple = (1,2,3,4)
foo(*my_tuple)

'''
x参数: 1
y参数: (2, 3, 4, '伍')'''

观察结果,y传入的参数是一个元组

3、逆向参数收集

说明: 指的是在传入的列表、元组参数之前添加一个星号,字典添加两个,可以使他们的元素拆开来传递。

可见,它传入的参数是一个已经定义的数组,逆向参数收集方式可以把这个数组拆开传递。

lambda表达式

格式:lambda [parameter_list]: 表达式

说明: lambda关键字之后,冒号左边的是参数列表,可以没有参数,也可以用逗号隔开的多个参数,右边是该lambda表达式的返回值。

1
2
3
4
5
#例子
lambda x,y:x + y
#等同于
def sum(x,y):
return x + y

调用函数

说明:__name__是Python中一个隐含的变量它代表了模块的名字

只有被Python解释器直接执行的模块的名字才是_main_

类和对象

定义类

class [name]():可调用参数

类可继承,父类写在括号里,默认是object参数,所有的类都是object的继承
类的实例化叫对象,对象是存在的具体

def _init_(self,):

#也叫做构造方法,self参数是默认的,也就是自动绑定到构造方法初始化的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Student(object):
def __init__(self,name,age,height):
self.name = name
self.age = age
self.height = height
def student_name(self):
print("The boy who watching book is name %s" % self.name,end=",")
def student_age(self):
print("ia a %d boy"%self.age,end=",")
def student_height(self):
print("and am is %5.2f tall."%self.height)

def main():
student_A = Student('sun',20,175)
student_A.student_name()
student_A.student_age()
student_A.student_height()

if __name__ == "__main__":
main()

类可以调用实例方法,类方法与静态方法区别是:类方法会自动绑定第一个参数class到类本身,而静态方法则不会。

注意:在英语交谈中,使用复数来表示一个类如birds-鸟类,但是python中约定使用单数并将首字母大写。

@函数装饰器

在函数前加@表示将被装饰的函数被作为一个从参数传给了装饰函数,并且将返回值给被装饰函数,因此被装饰的函数此时可能不再是一个函数而可能是一个值或字符串。

1
2
3
4
5
6
7
8
9
10
11

def funB(fn):
print('B')
fn()#执行传入的fn参数
return 'result'

@funB
def funA():
print("A")
print(funA)

step1:将funA作品为参数传给funB,即funB(funA)。

step2: 将funA替换成step1的返回值即’result‘,此时funB不在是一个函数而是一个字符。

变量

变量分为类变量和实例变量,分属不同的命名空间,从而调用的时候方式就不一样。

类命名空间对象都可以访问。

property()定义属性
property(getting,setting,doing,doc)
property函数有四个参数,分别是不读不写、只读、读写、读写删 。其实程序尝试对对象进行读写操作都被委托给了property里参数代表的方法来实现。

封装

封装指将对象的信息隐藏在对象内部,用户只能通过对象访问。python使用双下划线来表示变量隐藏起来,但实际并没有隐藏,通过类依旧可以访问。

类中将双下划线开头(__)的认定为隐藏属性,Import*不会导入隐藏属性的变量、方法。

直接访问下划线开头的方法会被python报错,可以通过类访问,但通常不会这么做,因为隐藏属性就是不希望外部人员能直接访问。

继承

一个子类可以继承多个父类,只需要在类命名是在后面括号类声明即可。子类继承父类的方法。户可以直接从写父类方法,也可以使用未绑定方法调用被重写的方法,需要注意的是:在通过类名调用实例方法时,python不会为实例方法的第一个参数self自动绑定值,而是需要自己显式绑定self,这种机制被称为未绑定方法。

使用super()调用父类的构造方法, python在继承多个父类时,排在前面的构造方法会被优先使用
super()会自动绑定第一个参数self

1
2
3
4
5
def __init__(self,method1,method2...):
#使用super方法重构造属性
super().__init__(methods1)
#直接通过继承的父类重构造
class2.__init__(self,method2)

多态

当同一变量在调用同一个方法时,完全可能呈现不同的多种行为,这就是多态。
issubclass(cls,class or tuple):检查cls是否是后一个类或元组的子类
isinstance(obj,class or tuple)检测obj是否是后一个类或元组的对象

__slots__限定属性

1
2
3
4
class Person(object):

# 限定Person对象只能绑定_name, _age和_gender属性
__slots__ = ('_name', '_age', '_gender')

python语言的动态性

动态性指对象、方法都是可以增删修改的,类都是type()方法创建的,type(’类名’,(object),dict(,))
__slots__动态添加方法属性

异常处理

1
2
3
4
5
6
7

try:
x = int(input("please input a number: "))
y = int(input("please input a number: "))
print(x/y)
except:
print("something wrong...")
1
2
3
4
5
6
7
8
9
try:
print('try...')
r = 10 / 0
print('result:', r)
except ZeroDivisionError as e:
print('except:', e)
finally:
print('finally...')
print('END')

当我们认为某些代码可能会出错时,就可以用try来运行这段代码,如果执行出错,则后续代码不会继续执行,而是直接跳转至错误处理代码,即except语句块,执行完except后,如果有finally语句块,则执行finally语句块,至此,执行完毕。

2、断言assert、logging也是调试异常处理的重要方式

参考资料

骆昊大神GitHub Python-100-Days-master

python3基础 芒努斯·利·海特兰德

疯狂的python讲义 李刚

python教程 廖雪峰

学无止境,未完待续…