py_notes

Posted on Edited on In Views: Word count in article: 11k Reading time ≈ 20 mins.

自用

字符串处理

1
2
3
4
5
6
7
8
s = 'xiex'
s1 = s.center(2)
print(s1)#数字小于字符串长度则不做处理
s2 = s.center(7)
print(s2.index('x'))#若填充数为奇数则左侧多一个
print(s.center(20))#居中并填充使总长度为20
print(s.ljust(20))#左对齐并填充
print(s.rjust(20))#右对齐并填充

集合运算和处理

1
2
3
4
5
6
7
setA = {2,1,3};setB = {3,4,5}
print(setA|setB)#并集，运算。而A.union(B)作为方法有同样的功能
print(setA&setB)#交集，A.intersectiom(B)
print(setA-setB)#仅出现于setA的元素
print(setA<=setB)#setA是否包含于setB
print({1,2,3,4,5}.pop())#“随机”移除，但实际删除集合中的“第一个”元素，由于集合的无序性而称为随机，例如纯数字是会输出最小的
print({'a','b','c','d','e','f','g'}.pop())#此处即为随机

字典处理

1
2
3
4
dict = {1:4,'a':'c'}
print('c' in dict ,1 in dict)#直接用in所查找的是是否在索引中
itemdict = {"item":"banana","cost":24}
print("The %(item)s costs %(cost)7.1f cents" % itemdict)# %(name)d可以获取字典中name所代表的值

人为抛出一条异常信息

1
2
3
4
5
6
7
8
9
10
11
anumber = int(input())
if anumber < 0:
    raise RuntimeError("You can't use a negative number")

from math import sqrt
def squareroot(n):#牛顿法求平方根
    root = n/2 #initial guess will be 1/2 of n
    for k in range(20):
        root = (1/2)*(root + (n / root))
    return root
print((squareroot(5)-sqrt(5))*(10**10))

面向对象

python为所有的类提供了一套标准的工作方法，但可能在一些情况下没有正常工作，如下： 

1
2
3
4
5
class fraction:
    def __init__(self, top,bottom):
        self.top = top
        self.bottom = bottom
print(fraction(2,5))#返回指向的地址字符串
此处__str__方法即为内置的方法，指示了如何将对象转化为字符串 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class fraction1:
    def __init__(self, top,bottom):
        self.top = top
        self.bottom = bottom
    def __str__(self):
        return str(self.top)+"/"+str(self.bottom)
    def __add__(self,other):#加法运算
        top1 = self.top*other.bottom + \
               other.top*self.bottom#\可以作为续行符
        bottom1 = self.bottom*other.bottom
        return fraction1(top1,bottom1)#可以加入用找最小公倍数的方法化简来优化,但这部分的重点不在此处
print(fraction1(2,5))
print(fraction1(2,5).__str__())
print(str(fraction1(2,5)))
print(fraction1(1,2)+fraction1(1,5))
## 浅相等与深相等 对于两个对象来说，直接==比较是比较两者是否引用了同一个对象，而非对值的比较 
1
2
3
4
5
6
7
8
9
10
11
12
13
a = fraction1(3,5)
b = fraction1(3,5)
print(a==b)
#建立__eq__方法，进行值的比较
class frac:
    def __init__(self, top,bottom):
        self.top = top
        self.bottom = bottom
    def __eq__(self, other):
        return self.top == other.top and self.bottom == other.bottom#仍不完善，可能输入的并非最简分数
a = frac(3,5)
b = frac(3,5)
print(a==b)
fraction的完整实现 
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
def gcd(m,n):
    while m%n != 0:
        oldm = m
        oldn = n

        m = oldn
        n = oldm%oldn
    return n
class Fraction:
    def __init__(self, top, bottom):
        self.num = top
        self.den = bottom

    def __str__(self):
        return str(self.num) + "/" + str(self.den)

    def show(self):
        print(self.num, "/", self.den)

    def __add__(self, otherfraction):
        newnum = self.num * otherfraction.den + \
        self.den * otherfraction.num
        newden = self.den * otherfraction.den
        common = gcd(newnum, newden)
        return Fraction(newnum//common, newden//common)

    def __eq__(self, other):
        firstnum = self.num * other.den
        secondnum = other.num * self.den
        return firstnum == secondnum
## 继承：以逻辑门为例 
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class LogicGate:#超类LogicGate
    def __init__(self,n):
        self.label = n
        self.output = None
    def getLabel(self):
        return self.label
    def getOutput(self):
        self.output = self.performGateLogic()
        return self.output

class BinaryGate(LogicGate):#有两个输入的门（与&或门），继承LogicGate
    def __init__(self,n):
        super().__init__(n)#先调用父类的构造方法

        self.pinA = None
        self.pinB = None

    def getPinA(self):
        if self.pinA is None:
            return int(input('Enter Pin A: input for gate' + \
                            self.getLabel() + '-->'))
        else:
            return self.pinA.getFrom().getOutput()
    def getPinB(self):
        if self.pinB is None:
            return int(input('Enter Pin B: input for gate' + \
                         self.getLabel() + '-->'))
        else:
            return self.pinB.getFrom().getOutput()

class UnaryGate(LogicGate):#非门
    def __init__(self,n):
        super().__init__(n)
        self.pin = None
    def getPin(self):
        if self.pin is None:
            return int(input('Enter Pin: input for gate ' + self.getLabel() + '-->'))
        else:
            return self.pin.getFrom().getOutput()#即返回连接器所连接的上一个类的输出


class AndGate(BinaryGate):#与门，继承BinaryGate
    def __init__(self,n):
        super().__init__(n)
    def performGateLogic(self):
        a = self.getPinA()
        b = self.getPinB()
        if a==1 and b==1:
            return 1
        else:
            return 0

    def setNextPin(self, source):
    # 在BinaryGate 类中，逻辑门有两个输入，但连接器必须只连接其中一个。如果两个都能连接，那么默认选择pinA。如果pinA 已经有了连接，就选择pinB。如果两个输入都已有连接，则无法连接逻辑门。
        if self.pinA == None:
            self.pinA = source
        else:
            if self.pinB == None:
                self.pinB = source
            else:
                raise RuntimeError("Error: NO EMPTY PINS")

# g1 = AndGate('G1')
# print(g1.getOutput())

class OrGate(BinaryGate):#与门，继承BinaryGate
    def __init__(self,n):
        super().__init__(n)
    def performGateLogic(self):
        a = self.getPinA()
        b = self.getPinB()
        if a==0 and b==0:
            return 0
        else:
            return 1
    def setNextPin(self, source):
        if self.pinA == None:
            self.pinA = source
        else:
            if self.pinB == None:
                self.pinB = source
            else:
                raise RuntimeError("Error: NO EMPTY PINS")


class NotGate(UnaryGate):
    def __init__(self,n):
        super().__init__(n)
    def performGateLogic(self):
        pin = self.getPin()
        if pin == 1:
            return 0
        else:
            return 1
    def setNextPin(self, source):
        if self.pin == None:
            self.pin = source
        else:
            raise RuntimeError("Error: NO EMPTY PINS")

class Connector:#连接两个逻辑门，内部包含LogicGate的实例但不在继承关系中
    def __init__(self,fgate,tgate):
        self.fromgate = fgate
        self.togate = tgate
        tgate.setNextPin(self)#此处传递参数self,即让tgate的值设定为连接器这个类的实例

    def getFrom(self):
        return self.fromgate

    def getTO(self):
        return self.togate

g1 = AndGate("G1")
g2 = AndGate("G2")
g3 = OrGate("G3")
g4 = NotGate("G4")
c1 = Connector(g1,g3)
c2 = Connector(g2,g3)
c3 = Connector(g3,g4)
print(g4.getOutput())

算法

递归

递归的三个原则为：

①基本情况，即无需处理就可以直接return的情况

②算法会改变待处理数据的状态，使其更接近于基本状态

③调用自己

1
2
3
4
5
6
def toStr(n,base):#递归示例，转换进制。
    convertstring = '0123456789ABCDEF'
    if n<base:
        return convertstring[n]
    else:
        return toStr(n//base,base)+convertstring[n%base]

基本状态为一位数，于是不断将原整数整除10

用栈来储存结果，那么python会将函数的返回值储存在栈的顶端

1
2
3
4
5
6
7
8
rStack = Stack()#将储存的结果压入栈中
def toStr(n, base):
    convertString = "0123456789ABCDEF"
    if n < base:
        rStack.push(convertString[n])
    else:
        rStack.push(convertString[n % base])
        toStr(n // base, base)

示例：汉诺塔

其基本思路是，若有n层，从a挪到c，那问题可以分解为：

n-1层从a到b \(->\) 1层从a到c \(->\) n-1层从b到c

代码如下（五层为例）

1
2
3
4
5
6
7
8
9
#汉诺塔
def moveTower(height, fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)
def moveDisk(fromPole, toPole):
    print(fromPole+'->'+toPole)
moveTower(5,'a','b','c')

动态规划

以找零钱为例，采用递归算法结果如下： 

1
2
3
4
5
6
7
8
9
10
11
12
def recMC(coinValueList, change):
	minCoins = change
	if change in coinValueList:
		return 1
	else:
		for i in [c for c in coinValueList if c <= change]:
			numCoins = 1 + recMC(coinValueList, change-i)
			if numCoins < minCoins:
				minCoins = numCoins
	return minCoins

recMC([1, 5, 10, 25], 63)

问题分解为：（change-i）的最小硬币数+1，其中i为一枚硬币的面值，故而循环多次直到遍历每一种可能。

该方法的问题在于有太多次对相同方案的遍历，如下图

![]image-20250317153318112.png)

相同的节点出现了多次，而每次出现都会进行完全一致而冗余的计算，这大大降低了算法的效率。

对此我们进行“针对性”的优化，即用knownResults储存每个节点所对应的数值，在计算时先查找这个节点是否已被计算过，以减少冗余的计算。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def recMC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        return 1
    elif knownResults[change] > 0:
        return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change-i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = numCoins
    return minCoins

recMC([1, 5, 10, 25], 63, [0]*64)

在这里介绍动态规划（dp），与上述算法不同，在这个问题上，递归采用了更为系统的储存方式，其会储存从1开始一直到change的每一个值对应的最少硬币数。

对于每一个值，其需要硬币的最小值，来自于这个值减去一个硬币的面值后所有情况的最小值+1。如对于（11）来说，为（1）+1，（6）+1，（10）+1，分别对应减去的硬币为10，5，1的情况，因此代码如下：

1
2
3
4
5
6
7
8
def dpMakeChange(coinValueList, change, minCoins):
    for cents in range(change+1):
        coinCount = cents
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
                coinCount = minCoins[cents - j]+1
            minCoins[cents] = coinCount
    return minCoins[change]

如果我们需要得到对于每一个值，在硬币数量最少的情况下所有硬币的面值，我们实际上只需要储存新增的硬币的面值即可递推得到所有的面值，修改代码如下； 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
    for cents in range(change + 1):
        coinCount = cents
        newcoin = 1
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newcoin = j
            minCoins[cents] = coinCount
            coinsUsed[cents] = newcoin
    return minCoins[change]


def printcoins(change, coinsUsed):
    while change > 0:
        print(coinsUsed[change],end = ' ')
        change -= coinsUsed[change]

coinsUsed = [0]*64
minCoins = [0]*64
dpMakeChange([1, 5, 10, 21, 25], 63, minCoins, coinsUsed)
printcoins(63,coinsUsed)

搜索

二分搜索

正常的搜索方法时间复杂度为O(n)，若列表为有序列表，那在不存在于列表中时时间消耗会减少。而使用二分搜索，时间复杂度可以降到O(logn)。（注意如果使用切片方法（如下）可能不严格遵守该事件复杂度，因为python的切片操作的时间复杂度为O(k)，可以用计算下标的方法减少这一操作的事件复杂度）

1
2
3
4
5
6
7
8
9
10
11
12
def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch(alist[:midpoint], item)
            else:
                return binarySearch(alist[midpoint+1:], item)

但问题是，排序可能造成更大的负担。

排序

冒泡排序

冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。

其代码如下

1
2
3
4
5
def bubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

其优势在于可以提前判断出是否已经有序（若一轮都没有发生交换），对于只需要交换少数次数的列表有优势，称短冒泡，但大部分时候是效率最低的排序方法。

选择排序

其与冒泡的区别是不再以交换将每一个值放到正确的位置，而是对于每一个位置，找到未排序的最大值放入。

代码如下

1
2
3
4
5
6
7
8
9
10
def selectionSort(alist):
    for fillslot in range(len(alist)-1, 0, -1):
        positionOfMax = 0
        for location in range(1, fillslot+1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location

        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp

由于减少了交换次数因此速度快于冒泡。

插入排序

最坏情况下的时间复杂度仍然为\(O(n^2)\)，最好情况下为\(O(n)\)，但采用了和冒泡以及选择不同的思路。通过不断地将新元素插入已排序列表实现排序。

代码如下

1
2
3
4
5
6
7
8
9
10
def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]#如果比该位置的数小就继续往前挪
            position = position-1

        alist[position] = currentvalue

可以看到，尽管时间复杂度一样，但该方法快于冒泡排序，因为移动所需要的时间短于交换（只需要进行一次赋值）。

希尔排序

类似于插入排序，但通过一定的步长将原列表划分为几个子列表，将子列表通过插入排序后再合并。不同的增量下时间复杂度不一样，但介于\(O(n)\)与\(O(n^2)\)之间。其关键在于找到合适的切分列表的方式。看似要多次排序增加了复杂度，但实际上，再后期的排序中，各个元素已经相当“接近“正确位置，需要的时间也大大降低。换言之，只有最后一步才是”真正“的排序，而前面的步骤只是预处理以减少最后排序的复杂度。

如对于增量为\(1,3,7,15,\dots,2^k-1\)的希尔排序来说，时间复杂度为\(O(n^\frac{3}{2})\)；而增量为\(1,2,3,4,6,8,9,\dots,2^p3^q\)（序列满足递增且\(p，q\)每次最多\(+1\)）来说，其时间复杂度为\(O(n\cdot\log n^2)\)，证明从略，参见希尔排序复杂度详细分析（翻译来源：Hans Werner Lang教授）_希尔排序时间复杂度-CSDN博客。对增量序列的取法来进行优化相当有趣，但现在没有能够在最坏情况下也能达到\(O(n\cdot\log n)\)的增量序列，甚至是否存在也不好说？

可以用另一种思想来理解：将数据存放在二维数组里，然后对每一列进行排序→直接合并在划分为列数更少的二维数组，并重复以上过程，当然，在实际实现中，仍然是一维数组。

通过代码来实现，举例：先划分为\(\frac{n}{2}\)个子列表，再划分为\(\frac{n}{4}\)个子列表……直到整个列表完成排序。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:

      for startposition in range(sublistcount):
        gapInsertionSort(alist,startposition,sublistcount)

      print("After increments of size",sublistcount,"The list is",alist)
      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap] 
            position = position-gap

        alist[position]=currentvalue

希尔排序是通过对插入的改良实现的，因此shellSort方法中调用了插入排序的内容。