茉莉Python

voidqueens@hotmail.com

0%

二叉堆

二叉堆是一种特殊的二叉树, 它总是保证一棵树的最小元素(最小堆)或者最大元素(最大堆)处于树根上, 常见的应用场景就是用于构建优先队列, 在jdk中Doug Lea所实现的ScheduledThreadPoolExecutor中就用到了最小堆;

1、最小堆

1.1 基本操作

BinaryHeap() 创建一个新的,空的二叉堆。
insert(k) 向堆添加一个新项。
findMin() 返回具有最小键值的项,并将项留在堆中。
delMin() 返回具有最小键值的项,从堆中删除该项。
如果堆是空的,isEmpty() 返回 true,否则返回 false。
size() 返回堆中的项数。
buildHeap(list) 从键列表构建一个新的堆。

注意,无论我们向堆中添加项的顺序是什么,每次都删除最小的。

1.2 实现

为了使我们的堆有效地工作,我们将利用二叉树的对数性质来表示我们的堆。 为了保证对数性能,我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点。 在我们的堆实现中,我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充,如图。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap1.png

完整二叉树的另一个有趣的属性是,我们可以使用单个列表来表示它。 我们不需要使用节点和引用,甚至列表的列表。因为树是完整的,父节点的左子节点(在位置 p 处)是在列表中位置 2p 中找到的节点。 类似地,父节点的右子节点在列表中的位置 2p + 1。为了找到树中任意节点的父节点,我们可以简单地使用Python 的整数除法。 假定节点在列表中的位置 n,则父节点在位置 n/2。如图,请注意父级和子级之间是 2p 和 2p+1 关系。 树的列表表示以及完整的结构属性允许我们仅使用几个简单的数学运算来高效地遍历一个完整的二叉树。 我们将看到,这也是我们的二叉堆的有效实现。

我们用于堆中存储项的方法依赖于维护堆的排序属性。 堆的排序属性如下:在堆中,对于具有父 p 的每个节点 x,p 中的键小于或等于 x 中的键。 下图展示了具有堆顺序属性的完整二叉树。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap2.png

我们将开始实现一个二叉堆的构造函数。由于整个二叉堆可以由单个列表表示,所以构造函数将初始化列表和一个 currentSize 属性来跟踪堆的当前大小。一个空的二叉堆有一个单一的零作为 heapList 的第一个元素,这个零只是放那里,用于以后简单的整数除法。

1
2
3
4
class BinHeap:
def __init__(self):
self.heapList=[0]
self.currentSize=0

将项添加到列表中最简单,最有效的方法是将项附加到列表的末尾。 它维护完整的树属性。但可能违反堆结构属性。可以编写一个方法,通过比较新添加的项与其父项,我们可以重新获得堆结构属性。 如果新添加的项小于其父项,则我们可以将项与其父项交换。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap3.png

注意,当我们完成一个项时,我们需要恢复新添加的项和父项之间的堆属性。 我们还需保留任何兄弟节点的堆属性。当然,如果新添加的项非常小,我们可能仍需要将其交换另一上层。事实上,我们可能需要交换到树的顶部。

percUp 方法,它在树中向上遍历一个新项,因为它需要去维护堆属性。注意,我们可以通过使用简单的整数除法来计算任意节点的父节点。 当前节点的父节点可以通过将当前节点的索引除以 2 来计算。

插入方法中的大部分工作都是由 percUp 完成的。 一旦一个新项被追加到树上,percUp 接管并正确定位新项。

1
2
3
4
5
6
7
8
9
10
11
12
def percUp(self,i):
while i//2>0:
if self.heapList[i] < self.heapList[i//2]:
tmp=self.heapList[i//2]
self.heapList[i//2]=self.heapList[i]
self.heapList[i]=tmp
i=i//2

def insert(self,k):
self.heapList.append(k)
self.currentSize+=1
self.percUp(self.currentSize)

因为堆属性要求树的根是树中的最小项,所以找到最小项很容易。delMin 的难点在根被删除后恢复堆结构和堆顺序属性。 我们可以分两步恢复我们的堆。首先,我们将通过获取列表中的最后一个项并将其移动到根位置来恢复根项,保持我们的堆结构属性。 但是,我们可能已经破坏了我们的二叉堆的堆顺序属性。 第二,我们通过将新的根节点沿着树向下推到其正确位置来恢复堆顺序属性。 下图展示了将新的根节点移动到堆中的正确位置所需的交换序列。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap4.png

为了维护堆顺序属性,我们所需要做的是将根节点和最小的子节点交换。在初始交换之后,我们可以将节点和其子节点重复交换,直到节点被交换到正确的位置,使它小于两个子节点。

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 percDown(self, i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc


def minChild(self, i):
'''
找到最小子节点:
如果右子节点不存在,那么最小子节点为左;
如果右子节点存在,判断左右的大小后再返回;
:param self:
:param i:
:return:
'''
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1


def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize -= 1
self.heapList.pop()
self.percDown(1)
return retval

为了完成我们对二叉堆的讨论,我们将看从一个列表构建整个堆的方法.如图,给定一个列表,通过一次插入一个键轻松地构建一个堆。由于你从一个项的列表开始,该列表是有序的,可以使用二分查找找到正确的位置,以大约 O(logn)O(logn) 操作的成本插入下一个键。 但是,请记住,在列表中间插入项可能需要 O(n)O(n) 操作来移动列表的其余部分,为新项腾出空间。 因此,要在堆中插入 n 个键,将需要总共 O(nlogn)O(nlogn) 操作。 然而,如果我们从整个列表开始,那么我们可以在 O(n)O(n) 操作中构建整个堆。Listing 6 展示了构建整个堆的代码。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap5.png

buildHeap 方法在 [9,6,5,2,3] 的初始树中的节点移动到其正确位置时所做的交换。虽然我们从树的中间开始,并以我们的方式回到根节点,percDown 方法确保最大的子节点总是沿着树向下移动。因为堆是一个完整的二叉树,超过中途点的任何节点都将是树叶,因此没有子节点。注意,当i = 1 时,我们从树的根节点向下交换,因此可能需要多次交换。正如你在上图最右边的两个树中可以看到的,首先 9 从根位置移出,但是 9 在树中向下移动一级之后,percDown 检查下一组子树,以确保它被推到下一层。在这种情况下,它与 3 进行第二次交换。现在 9 已经移动到树的最低层,不能进行进一步交换。将上图所示的这一系列交换的列表与树进行比较是有用的。

1
2
3
4
5
6
7
def buildHeap(self, alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while i > 0:
self.percDown(i)
i -= 1

完整代码:

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
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0


def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2

def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)

def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc

def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1

def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval

def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

我们可以在 O(n)中构建堆的断言可能看起来有点神秘,证明超出了范围。 然而,理解的关键是记住 logn 因子是从树的高度派生的。 对于buildHeap 中的大部分工作,树比 logn 短。
基于可以从 O(n) 时间构建堆的事实,你可以使用堆对列表在 O(nlogn)时间内排序,作为本章结尾的练习。

2、最大堆

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
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0

def percUp(self, i):
while i // 2 > 0:
if self.heapList[i] > self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2

def insert(self, k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)

def percDown(self, i):
while (i * 2) <= self.currentSize:
mc = self.maxChild(i)
if self.heapList[i] < self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc

def maxChild(self, i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2 + 1
else:
return i * 2

def delMax(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval

def buildHeap(self, alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1


bh = BinHeap()
bh.buildHeap([9, 5, 6, 2, 3])

print(bh.heapList)
print(bh.currentSize)
print(bh.delMax())
print(bh.heapList)
print(bh.delMax())

十四、database

优先顺序:where>group by>having>order by

182. 查找重复的电子邮箱

链接:https://leetcode-cn.com/problems/duplicate-emails/

SQL架构
编写一个 SQL 查询,查找 Person 表中所有重复的电子邮箱。

示例:

+----+---------+
| Id | Email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+
根据以上输入,你的查询应返回以下结果:

+---------+
| Email   |
+---------+
| a@b.com |
+---------+
说明:所有电子邮箱都是小写字母。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Write your MySQL query statement below
# 1.使用group by 和临时表
select Email from
(
select Email, count(Email) as nums
from Person
group by Email
) as tmp
where nums>1;
# 2.使用group by和having条件
select Email
from Person
group by Email
having count(Email) > 1;



十三、数学

172. 阶乘后的零

链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes/

给定一个整数 n,返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

题解一:

如果依靠算出阶乘结果,再计算有多少个0,很容易溢出。

思路:末尾有多少个0,只需要给当前数乘以一个10,就可以加一个0.

比如5!,也就是 5 * 4 * 3 * 2 * 1 = 120,我们发现结果会有一个 0,原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话,其实也只有 2 * 5 可以构成,所以我们只需要找有多少对 2/5。

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1

对于含有 2 的因子的话是 1 * 2, 2 * 2, 3 * 2, 4 * 2 …

对于含有 5 的因子的话是 1 * 5, 2 * 5…

含有 2 的因子每两个出现一次,含有 5 的因子每 5 个出现一次,所有 2 出现的个数远远多于 5,换言之找到一个 5,一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。

直接的,我们只需要判断每个累乘的数有多少个 5 的因子即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def trailingZeroes(self, n: int) -> int:
count=0
for i in range(n+1):
tmp=i
while tmp>0:
if tmp%5==0:
count+=1
tmp//=5
else:
break
return count

以上算法超时,继续优化。

对于一个数的阶乘,5 的因子一定是每隔 5 个数出现一次,也就是下边的样子。

n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) *... * n

因为每隔 5 个数出现一个 5,所以计算出现了多少个 5,我们只需要用 n/5 就可以算出来。

但还没有结束,继续分析。

... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ... * n

每隔 25 个数字,出现的是两个 5,所以除了每隔 5 个数算作一个 5,每隔 25 个数,还需要多算一个 5。

也就是我们需要再加上 n / 25 个 5。

同理我们还会发现每隔 5 * 5 * 5 = 125 个数字,会出现 3 个 5,所以我们还需要再加上 n / 125 。

综上,规律就是每隔 5 个数,出现一个 5,每隔 25 个数,出现 2 个 5,每隔 125 个数,出现 3 个 5,以此类推。

最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

写程序的话,如果直接按照上边的式子计算,分母可能会造成溢出。所以算 n / 25 的时候,我们先把 n 更新,n = n / 5,然后再计算 n / 5 即可,后边的同理。

1
2
3
4
5
6
7
8
class Solution:
def trailingZeroes(self, n: int) -> int:
count=0
while n>0:
count+=n//5
n//=5
return count

常用函数:

bin() # 十进制转二进制
oct() # 十进制转八进制
hex() # 十进制转十六进制

chr() # 数字转字符串(ascii)
ord() # 字符串(ascii)转数字

65--'A'
97--'a'

十二、字符串

?5.最长回文子串

链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:

输入: "cbbd"
输出: "bb"

题解一|暴力破解:
很明显,暴力法将选出所有子字符串可能的开始和结束位置,并检验它是不是回文。
时间复杂度:O(n^2),往往利用python的切片可以很好的缩减复杂度
如果不用切片,还需要遍历一次子字符串,时间复杂度就是O(n^3)
空间复杂度:O(1)

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
class Solution:
def longestPalindrome(self, s: str) -> str:
if s==s[::-1]:
return s

maxLen=1
ans=s[0]
for i in range(0,len(s)-1):
for j in range(i+1,len(s)):
if j-i+1 > maxLen and self.isPalindrome(s[i:j+1]):
maxLen=j-i+1
ans=s[i:j+1]
return ans

def isPalindrome(self, s: str) -> bool:
left,right=0,len(s)-1
while left<right:
while left<len(s) and not s[left].isalnum():
left+=1
while right >-1 and not s[right].isalnum():
right-=1
if left>right:
return True
if s[left].upper() != s[right].upper():
return False
else:
left+=1
right-=1
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestPalindrome(self, s: str) -> str:
if s==s[::-1]:
return s

maxLen=1
ans=s[0]
for i in range(0,len(s)-1):
for j in range(i+1,len(s)):
if j-i+1 > maxLen and s[i:j+1]==s[i:j+1][::-1]: # arr='abb',arr[0:1]='a',右边是开区间
maxLen=j-i+1
ans=s[i:j+1]
return ans

题解二:

每个字母当成回文串的中心
考虑两种情况:回文串的长度为奇数或者偶数情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
self.res=''
def helper(i,j):
while i>= 0 and j<n and s[i]==s[j]:
i-=1
j+=1
if len(self.res) < j-i-1:
self.res=s[i+1:j]
# print(i,self.res)

for i in range(n):
helper(i,i)
helper(i,i+1) # 解决case为"cbbd",即解决回文串为偶数的情况
return self.res

题解三:

把每个字母当成回文串的结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
max_len = 1
n = len(s)
start = 0
for i in range(1,n):
even = s[i-max_len:i+1]
odd = s[i - max_len-1:i+1]
#print(even,odd)
if i - max_len - 1 >= 0 and odd == odd[::-1]:
start = i - max_len - 1
max_len += 2
elif i - max_len >=0 and even == even[::-1]:
start = i - max_len
max_len += 1

#print(start,max_len)
return s[start: start+max_len]

题解二(动态规划):

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

1、定义数组的定义
    dp[i][j] 表示子串 s[i, j] 是否为回文子串。
2、找出数组的关系式
    dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
3、找到初始值

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/gao-hao-dong-tai-gui-hua-he-zhong-xin-tuo-zhan-zhu/

12.整数转罗马数字

链接:https://leetcode-cn.com/problems/integer-to-roman/

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: "III"
示例 2:

输入: 4
输出: "IV"
示例 3:

输入: 9
输出: "IX"
示例 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

题解一(贪心算法):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def intToRoman(self, num: int) -> str:
# dicts={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
dicts={1:'I',4:'IV',5:'V',9:'IX',10:'X',40:'XL',50:'L',90:'XC',100:'C',400:'CD',500:'D',900:'CM',1000:'M' }
ans=''
for key in sorted(dicts.keys())[::-1]:
if num==0:
break
tmp=num//key
if tmp==0:
continue
ans+=dicts[key]*tmp
num-=key*tmp
return ans

13.罗马数字转整数

链接:https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/rome.png

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3
示例 2:

输入: "IV"
输出: 4
示例 3:

输入: "IX"
输出: 9
示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

题解一(hash):
首先建立一个HashMap来映射符号和值,然后对字符串从左到右来,如果当前字符代表的值小于其右边,就减去该值;否则就加上该值,以此类推到最右边的数

1
2
3
4
5
6
7
8
9
10
class Solution:
def romanToInt(self, s: str) -> int:
arr={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
ans=0
for i in range(len(s)):
if i<len(s)-1 and arr[s[i]]<arr[s[i+1]]:
ans-=arr[s[i]]
else:
ans+=arr[s[i]]
return ans

题解二(hash):
# 构建一个字典记录所有罗马数字子串,注意长度为2的子串记录的值是(实际值 - 子串内左边罗马数字代表的数值)

# 然后,遍历整个 s 的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内,如果在就记录值,不在就说明当前位置不存在小数字在前面的情况,直接记录当前位置字符对应值

# 举个例子,遍历经过 IV 的时候先记录 I 的对应值 1,再往前移动一步记录 IV 的值 3,加起来正好是 IV 的真实值 4。max 函数在这里是为了防止遍历第一个字符的时候出现 [-1:0] 的情况,因为s[-1:0]为空。
1
2
3
4
class Solution:
def romanToInt(self, s: str) -> int:
arr={'I':1,'IV':3,'V':5,'IX':8,'X':10,'XL':30,'L':50,'XC':80,'C':100,'CD':300,'D':500,'CM':800,'M':1000}
return sum(arr.get(s[max(i-1,0):i+1],arr[v]) for i,v in enumerate(s))
1
2
3
4
5
6
7
class Solution:
def romanToInt(self, s: str) -> int:
arr={'I':1,'IV':3,'V':5,'IX':8,'X':10,'XL':30,'L':50,'XC':80,'C':100,'CD':300,'D':500,'CM':800,'M':1000}
ans=0
for i,v in enumerate(s):
ans+=arr.get(s[i-1:i+1],arr[v])
return ans

?### 14.最长公共前缀
链接:https://leetcode-cn.com/problems/longest-common-prefix/

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

https://blog.csdn.net/lz_901/article/details/89021210
题解一(水平扫描):

1、先找出 str1 和 str2(注:str1代表第一个字符串,str2代表第二个) 的公共字符串 s1。

2、然后再找出 s1 和 str3 的公共前缀 s2。

3、然后再找出 s2 和 str4 的公共前缀 s3。

4、一直这样遍历重复,用一个变量来保存两个两个字符串之间的公共前缀。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/lcp1.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# if not strs:
# return ''
# res=''
# for i in range(0,len(strs[0])):
# c=strs[0][i]
# for j in range(1,len(strs)):
# if i == len(str[j]) or c != strs[j][i]
# return res
# res+=c
if not strs:
return ''
prefix=strs[0]
for i in range(1,len(strs)):
while strs[i].find(prefix) != 0: # 此题是寻找最长公共前缀,所以需要找到开始索引是0.
prefix=prefix[0:len(prefix)-1]
if prefix=='':
return ''
return prefix

find()语法:

str.find(str, beg=0, end=len(string))

参数:
    str -- 指定检索的字符串
    beg -- 开始索引,默认为0。
    end -- 结束索引,默认为字符串的长度。

返回值:
    如果包含子字符串返回开始的索引值,否则返回-1。

题解二(水平扫描优化):

想象数组的末尾有一个非常短的字符串,使用上述方法仍旧会进行S次比较。
优化这类情况的方法是水平扫描,从前往后枚举字符串的每一列,先比较每个字符串相同列上的字符(即不同字符串相同下标的字符),然后再进行下一列的比较。

我们不横向一个一个字符串遍历,而是采用纵向的方式。例如对于这个["flower","flow","flight"],我们把它看成一个二维字符数组。

然后纵向遍历,一列一列遍历,只要发现某一列出现不同的字符,就遍历结束,例如上面这个例子中,第三列就出现不同了,所以遍历结束,把前两列返回。
1
2
3
4
5
6
7
8
9
10
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if(not strs):
return ""
for i in range(len(strs[0])):
c=strs[0][i]
for j in range(len(strs)):
if i==len(strs[j]) or strs[j][i] != c:
return strs[0][0:i]
return strs[0]

题解三(分治):

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/lcp2.png

复杂度:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/lcp3.png

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
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
def commonPrefix(l, r):
'''
治:从首位开始对比
:param l:
:param r:
:return:
'''
minlen = min(len(l), len(r))
for i in range(minlen):
if l[i] != r[i]:
return l[0:i]
return l[0:minlen]

def lcp(strs, l, r):
'''
分:分为小问题
:param strs:
:param l:
:param r:
:return:
'''

# 递归弹出
if l == r:
return strs[l]
# 继续分
else:
mid = (l + r) // 2
left = lcp(strs, l, mid)
right = lcp(strs, mid + 1, r)
return commonPrefix(left, right)

if not strs:
return ''
return lcp(strs, 0, len(strs) - 1)

题解四(zip):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# print(strs)
# print(*strs)
res=''
for i in zip(*strs):
# print(i)
if len(set(i))==1:
res+=i[0]
else:
break
return res

输出:
['flower', 'flow', 'flight']
flower flow flight
('f', 'f', 'f')
('l', 'l', 'l')
('o', 'o', 'i')

zip()语法:

zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表(python2)/对象(python3)。

如果各个迭代器的元素个数不一致,则返回列表长度与最短的对象相同,利用 * 号操作符,可以将元组解压为列表。

zip 方法在 Python 2 和 Python 3 中的不同:在 Python 3.x 中为了减少内存,zip() 返回的是一个对象。如需展示列表,需手动 list() 转换。在 Python 2.x zip() 返回的是一个列表。

zip([iterable, ...])

参数说明:
    iterabl -- 一个或多个迭代器;
返回值:
返回元组列表/一个对象。

题解五(max和min):

max()和min()在python字符串中是可以比较的,按照ascii值排序,比如abb,aba,abac,最大为abb,最小为aba。

1
2
3
4
5
6
7
8
9
10
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ''
s1=min(strs)
s2=max(strs)
for i,v in enumerate(s1):
if v != s2[i]:
return s1[:i]
return s1

28. 实现 strStr()

链接:https://leetcode-cn.com/problems/implement-strstr/

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

题解一(子串逐一比较 - 线性时间复杂度):

思路:沿着字符换逐步移动滑动窗口,将窗口内的子串与 needle 字符串比较。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/str1.png

时间复杂度:O((N - L)L),其中 N 为 haystack 字符串的长度,L 为 needle 字符串的长度。内循环中比较字符串的复杂度为 L,总共需要比较 (N - L) 次。
空间复杂度:O(1)

1
2
3
4
5
6
7
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n,length=len(haystack),len(needle)
for i in range(n-length+1):
if haystack[i:i+length]==needle:
return i
return -1

??题解二(双指针 - 线性时间复杂度):

题解一的缺陷是会将 haystack 所有长度为 L 的子串都与 needle 字符串比较,实际上是不需要这么做的。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/str.png

首先,只有子串的第一个字符跟 needle 字符串第一个字符相同的时候才需要比较。

其次,可以一个字符一个字符比较,一旦不匹配了就立刻终止。

比较到最后一位时发现不匹配,这时候开始回溯。需要注意的是,pn 指针是移动到 pn = pn - curr_len + 1 的位置,而 不是 pn = pn - curr_len 的位置。

这时候再比较一次,就找到了完整匹配的子串,直接返回子串的开始位置 pn - L。

思路:

移动 pn 指针,直到 pn 所指向位置的字符与 needle 字符串第一个字符相等。

通过 pn,pL,curr_len 计算匹配长度。

如果完全匹配(即 curr_len == L),返回匹配子串的起始坐标(即 pn - L)。

如果不完全匹配,回溯。使 pn = pn - curr_len + 1, pL = 0, curr_len = 0。

时间复杂度:最坏时间复杂度为 O((N - L)L),最优时间复杂度为 O(N)。
空间复杂度:O(1)

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
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
L, n = len(needle), len(haystack)
if L == 0:
return 0

pn = 0
while pn < n - L + 1:
# find the position of the first needle character
# in the haystack string
while pn < n - L + 1 and haystack[pn] != needle[0]:
pn += 1

# compute the max match string
curr_len = pL = 0
while pL < L and pn < n and haystack[pn] == needle[pL]:
pn += 1
pL += 1
curr_len += 1

# if the whole needle string is found,
# return its start position
if curr_len == L:
return pn - L

# otherwise, backtrack
pn = pn - curr_len + 1

return -1

???题解三(KMP):
https://leetcode-cn.com/problems/implement-strstr/solution/kmphua-48xiao-shi-kan-dong-liao-kmpxiang-rang-ni-z/

https://www.bilibili.com/video/BV1Px411z7Yo?from=search&seid=13225444196686531503
https://www.bilibili.com/video/BV1hW411a7ys/?spm_id_from=333.788.videocard.0

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
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
next=self.getNext(needle)
i=j=0
while i<len(haystack) and j<len(needle):
if j==-1 or haystack[i]==needle[j]:
i+=1
j+=1
else:
j=next[j]
if j==len(needle):
return i-j
else:
return -1
def getNext(self,needle):
next=[0]*len(needle)
next[0]=-1
print(next)
i=0
j=-1
while i<len(needle)-1:
if j==-1 or needle[i]==needle[j]:
i+=1
j+=1
next[i]=j
else:
j=next[j]
return next

题解四:

1
2
3
4
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
i=haystack.find(needle)
return i

20. 有效的括号

链接:https://leetcode-cn.com/problems/valid-parentheses/

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

题解一:

时间复杂度:O(N)。遍历了一遍字符串。
空间复杂度:O(N)。最坏情况下,假如输入是 (((((((,栈的大小将是输入字符串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def isValid(self, s: str) -> bool:
dict = {')':'(',']':'[','}':'{'}
stack=[]
for i in s:
if stack and i in dict:
if stack[-1] == dict[i]:
stack.pop()
else:
return False
else:
stack.append(i)
return not stack
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isValid(self, s: str) -> bool:
dicts={'(':1,')':-1,'{':2,'}':-2,'[':3,']':-3}
list=[]
for i in s:
if len(list)==0:
list.append(i)
elif dicts[i]+dicts[list[-1]]==0:
del list[-1]
else:
list.append(i)
return len(list)==0

38. 外观数列

链接:https://leetcode-cn.com/problems/count-and-say/

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"), 即 21。
21 被读作 "one 2",  "one 1" ("一个二" ,  "一个一") , 即 1211。

给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。

注意:整数序列中的每一项将表示为一个字符串。

示例 1:

输入: 1
输出: "1"
解释:这是一个基本样例。
示例 2:

输入: 4
输出: "1211"
解释:当 n = 3 时,序列是 "21",其中我们有 "2" 和 "1" 两组,"2" 可以读作 "12",也就是出现频次 = 1 而 值 = 2;类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起,也就是 "1211"。

https://zhuanlan.zhihu.com/p/106149461

题解一(递归):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def countAndSay(self, n: int) -> str:
# 初始条件
if n==1:
return '1'
print('调用前:',n)
pre=self.countAndSay(n-1) # 得到上一行的字符串
print('调用后:',n,pre)
res=''
count=1
length=len(pre)
for i in range(1,length):
if pre[i] != pre[i-1]:
res+=str(count)+pre[i-1]
count=1
else:
count+=1
print(pre[length-1])
res+=str(count)+pre[length-1]
return res

输出:

调用前: 5
调用前: 4
调用前: 3
调用前: 2
调用后: 2 1
1
调用后: 3 11
1
调用后: 4 21
1
调用后: 5 1211
1

题解二(迭代):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def countAndSay(self, n: int) -> str:
res='1'
while n-1>0:
tmp=''
pre=res[0]
count=0 # count=0
for i in range(len(res)): # 从0开始
if pre==res[i]:
count+=1
else:
tmp+=str(count)+pre
pre=res[i]
count=1
tmp+=str(count)+pre
res=tmp
n-=1
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def countAndSay(self, n: int) -> str:
res='1'
for i in range(n-1,0,-1):
tmp=''
pre=res[0]
count=1 # count=1
for j in range(1,len(res)): # 从1开始
if pre==res[j]:
count+=1
else:
tmp+=str(count)+pre
pre=res[j]
count=1
tmp+=str(count)+pre
res=tmp
return res

58. 最后一个单词的长度

链接:https://leetcode-cn.com/problems/length-of-last-word/

给定一个仅包含大小写字母和空格 ' ' 的字符串 s,返回其最后一个单词的长度。如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词,请返回 0 。

说明:一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

示例:

输入: "Hello World"
输出: 5

题解一(内置函数):

1
2
3
class Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.rstrip().split(' ')[-1])

题解二:

1
2
3
4
5
6
7
8
9
10
class Solution:
def lengthOfLastWord(self, s: str) -> int:
end=len(s)-1
while end>=0 and s[end]==' ':
end-=1
if end < 0: return 0
start=end
while start >=0 and s[start] !=' ':
start-=1
return end-start

67. 二进制求和

给你两个二进制字符串,返回它们的和(用二进制表示)。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"


提示:

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ,就都不含前导零。

题解一(内置函数):

时间复杂度为 O(N+M)

1
2
3
class Solution:
def addBinary(self, a: str, b: str) -> str:
return bin(int(a,2)+int(b,2))[2:]

题解二(逐位运算):

时间复杂度:O(max(N,M)),其中 N 和 M 是输入字符串 a 和 b 的长度。

空间复杂度:O(max(N,M)),存储求和结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def addBinary(self, a: str, b: str) -> str:
n=max(len(a),len(b))
a,b=a.zfill(n),b.zfill(n)
carry=0
res=[]
for i in range(n-1,-1,-1):
if a[i]=='1':
carry+=1
if b[i]=='1':
carry+=1
if carry%2==1:
res.append('1')
else:
res.append('0')

carry//=2

if carry==1:
res.append('1')
res.reverse()
return ''.join(res)

zfill()方法语法:
str.zfill(width)
参数:
width – 指定字符串的长度。原字符串右对齐,前面填充0。
返回值:
返回指定长度的字符串。

题解三(位操作):

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/bit.png

算法:

把 a 和 b 转换成整型数字 x 和 y,x 保存结果,y 保存进位。

当进位不为 0:y != 0:

    计算当前 x 和 y 的无进位相加结果:answer = x^y。

    计算当前 x 和 y 的进位:carry = (x & y) << 1。

    完成本次循环,更新 x = answer,y = carry。

返回 xx 的二进制形式。

时间复杂度:O(N+M),其中 N 和 M 是输入字符串 a 和 b 的长度。

空间复杂度:O(max(N,M)),存储计算结果。

1
2
3
4
5
6
7
8
9
class Solution:
def addBinary(self, a: str, b: str) -> str:
x,y=int(a,2),int(b,2)
while y:
res=x^y
carry=(x & y) << 1
x,y=res,carry
return bin(x)[2:]

1
2
3
4
5
6
7
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
x, y = x ^ y, (x & y) << 1
return bin(x)[2:]

125.验证回文串

链接:https://leetcode-cn.com/problems/valid-palindrome/

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:

输入: "race a car"
输出: false

题解一(双指针):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def isPalindrome(self, s: str) -> bool:
left,right=0,len(s)-1
while left<right:
while left<len(s) and not s[left].isalnum():
left+=1
while right >-1 and not s[right].isalnum():
right-=1
if left>right:
return True
if s[left].upper() != s[right].upper():
return False
else:
left+=1
right-=1
return True

isalnum():检测字符串是否由字母和数字组成。

题解二(正则):

1
2
3
4
5
6
class Solution:
def isPalindrome(self, s: str) -> bool:
import re
p=''.join(re.findall(r'[a-zA-Z0-9+]',s))
p=p.lower()
return True if p==p[::-1] else False

题解三(内置函数):

1
2
3
4
class Solution:
def isPalindrome(self, s: str) -> bool:
s = [*filter(str.isalnum, s.lower())]
return s == s[::-1]

168.Excel表列名称

链接:https://leetcode-cn.com/problems/excel-sheet-column-title/

给定一个正整数,返回它在 Excel 表中相对应的列名称。

例如,

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...
示例 1:

输入: 1
输出: "A"
示例 2:

输入: 28
输出: "AB"
示例 3:

输入: 701
输出: "ZY"

题解一(转26进制):

1
2
3
4
5
6
7
8
9
10
class Solution:
def convertToTitle(self, n: int) -> str:
res=''
while n:
n,y=divmod(n,26)
if y==0:
n-=1
y=26
res=chr(y+64)+res
return res
1
2
3
4
5
6
7
8
class Solution:
def convertToTitle(self, n: int) -> str:
res=''
while n:
n-=1
n,y=divmod(n,26)
res=chr(y+65)+res
return res

题解二(递归):

1
2
3
4
5
6
class Solution:
def convertToTitle(self, n: int) -> str:
if n==0:
return ''
else:
return self.convertToTitle((n-1)//26) + chr((n-1) % 26 + 65)

171.Excel表列序号

链接:https://leetcode-cn.com/problems/excel-sheet-column-number/

给定一个Excel表格中的列名称,返回其相应的列序号。

例如,

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...
示例 1:

输入: "A"
输出: 1
示例 2:

输入: "AB"
输出: 28
示例 3:

输入: "ZY"
输出: 701

题解一:

1
2
3
4
5
6
7
class Solution:
def titleToNumber(self, s: str) -> int:
res=0
for each in s:
num=(ord(each)-65)+1
res=res*26+num
return res

344.反转字符串

链接:https://leetcode-cn.com/problems/reverse-string/

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:

输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
示例 2:

输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

字符串逆序:

方法一:利用字符串的切片来实现逆序

def reverse1(str):
    return str[::-1]

方法二:将字符串转换为列表后再使用reverse()

def reverse2(str):
    str_list=list(str)
    str_list.reverse()  # 列表翻转
    return ''.join(str_list) # 将列表转换为字符串

def reverse2(str):
    str_list=[]
    for each in str:
        str_list.append(each)
    str_list.reverse()
    return ''.join(str_list)

方法三:新建列表,从后往前添加元素

def reverse3(str):
    str_list=[]
    for i in range(len(str)-1,-1,-1):
        str_list.append(str[i])
    return ''.join(str_list)    

方法四:递归

def reverse4(str):
    if len(str)<=1:
        return str
    return str[-1]+reverse4(str[:-1])

方法五:借助collections模块extendleft()

import collections

def reverse5(str):
    deque1 = collections.deque(str)
    deque2=collections.deque()
    for char in deque1:
        deque2.extendleft(char)
    return ''.join(deque2)

方法六:swap交换操作,以中间为基准,交换对称位置的字符

def reverse5(str):
str_list = list(str)
if len(str_list) == 0 or len(str_list) == 1:
    return str
i = 0
length = len(str_list)
while i < length / 2:
    str_list[i], str_list[length - i - 1] = str_list[length - i - 1], str_list[i]
    i += 1
return ''.join(str_list)

题解一(内置函数):

1
2
3
class Solution:
def reverseString(self, s):
s.reverse()

题解二(递归):

时间复杂度:O(N)。执行了 N/2 次的交换。
空间复杂度:O(N),递归过程中使用的堆栈空间。

1
2
3
4
5
6
7
8
9
10
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def helper(left,right):
if left<right:
s[left],s[right]=s[right],s[left]
helper(left+1,right-1)
helper(0,len(s)-1)

题解二(双指针):

时间复杂度:O(N)。执行了 N/2 次的交换。
空间复杂度:O(1),只使用了常数级空间。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left,right=0,len(s)-1
while left<right:
s[left],s[right]=s[right],s[left]
left+=1
right-=1
return s

345. 反转字符串中的元音字母

链接:https://leetcode-cn.com/problems/reverse-vowels-of-a-string/

编写一个函数,以字符串作为输入,反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"
示例 2:

输入: "leetcode"
输出: "leotcede"

题解一(栈):

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def reverseVowels(self, s: str) -> str:
stack=['a','e','i','o','u','A','E','I','O','U']
res=[]
tmp=[i for i in s if i in stack]
for i in s:
if i not in stack:
res.append(i)
else:
res.append(tmp.pop())
return ''.join(res)

题解二(双指针):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def reverseVowels(self, s: str) -> str:
if not s or len(s)==1:
return s
stack=['a','e','i','o','u','A','E','I','O','U']
s=list(s)
left,right=0,len(s)-1
while left<right:
if s[left] not in stack:
left+=1
if s[right] not in stack:
right-=1
if s[left] in stack and s[right] in stack:
s[left],s[right]=s[right],s[left]
left+=1
right-=1
return ''.join(s)

383. 赎金信

链接:https://leetcode-cn.com/problems/ransom-note/

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 

注意:

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

题解一(Counter):

1
2
3
4
5
6
7
8
9
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
from collections import Counter
r=Counter(ransomNote)
m=Counter(magazine)
if not r-m:
return True
else:
return False

题解二(双指针):

时间复杂度为O(nlog(n)+mlog(m))
空间复杂度为O(m + n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
sorted(ransomNote)
sorted(magazine)
i,j=0,0
while i<len(ransomNote) and j<len(magazine):
if ransomNote[i]>magazine[j]:
j+=1
elif ransomNote[i] < magazine[j]:
return False
else:
i+=1
j+=1
return i==len(ransomNote)

题解三(hash):

时间复杂度: O(N) - N(遍历magazine) + 1(字典检索为O(1))
空间复杂度: O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
hash={}
for i in magazine:
if i in hash:
hash[i]+=1
else:
hash[i]=1
for i in ransomNote:
if i in hash and hash[i]>0:
hash[i]-=1
else:
return False
return True

题解四(暴力):

时间复杂度: O(N^2) - N(遍历ransomNote) * N(replace最糟糕的情况是遍历整个magazine)
空间复杂度: O(1)

1
2
3
4
5
6
7
8
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
for i in ransomNote:
if i in magazine:
magazine=magazine.replace(i,'',1) # 可选字符串, 替换不超过 max 次
else:
return False
return True

387. 字符串中的第一个唯一字符

链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.


注意事项:您可以假定该字符串只包含小写字母。

题解一(切片):

1
2
3
4
5
6
7
8
class Solution:
def firstUniqChar(self, s: str) -> int:
if len(s)==1:
return 0
for k in range(len(s)):
if (s[k] not in s[k+1:]) and (s[k] not in s[:k]):
return k
return -1

题解二(内置函数):

时间复杂度: O(N),只遍历了两遍字符串,同时散列表中查找操作是常数时间复杂度的。
空间复杂度: O(N),用到了散列表来存储字符串中每个元素出现的次数。

1
2
3
4
5
6
7
8
class Solution:
def firstUniqChar(self, s: str) -> int:
from collections import Counter
count=Counter(s)
for k,v in enumerate(s):
if count[v]==1:
return k
return -1
1
2
3
4
5
6
import collections
class Solution:
def firstUniqChar(self, s: str) -> int:
for i,j in collections.Counter(s).items():
if j==1:return s.index(i)
return -1

题解三(find):

1.证明字母只出现了一次
如果一个字符串中的字符在字符串中从左边搜索和从右边搜索得到的index一样,那就证明只有一个了
2.循环每次是从第一个开始的,保证了执行的顺序

1
2
3
4
5
6
class Solution(object):
def firstUniqChar(self, s):
for i in s:
if s.find(i)== s.rfind(i):
return s.find(i)
return -1

415. 字符串相加

链接:https://leetcode-cn.com/problems/add-strings/

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

注意:

num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。

题解一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
n=max(len(num1),len(num2))
n1=num1.zfill(n)
n2=num2.zfill(n)
print(n1,n2)
carry=0
res=[]
for i in range(n-1,-1,-1):
tmp=int(n1[i])+int(n2[i])
carry+=tmp
res.append(carry%10)
carry//=10
if carry==1:
res.append(1)
res.reverse()
return ''.join([str(i) for i in res])

题解二(双指针):

时间复杂度:O(max(M,N)):其中 M,N 为 2 数字长度,按位遍历一遍数字(以较长的数字为准);
空间复杂度:O(1),指针与变量使用常数大小空间。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = ""
i, j, carry = len(num1) - 1, len(num2) - 1, 0
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
tmp = n1 + n2 + carry
carry = tmp // 10
res = str(tmp % 10) + res
i, j = i - 1, j - 1
return "1" + res if carry else res

434. 字符串中的单词数

链接:https://leetcode-cn.com/problems/number-of-segments-in-a-string/

统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。

请注意,你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符,所以 "Hello," 算作 1 个单词。

题解一(split):

时间复杂度 : O(n)。
这里用到的内置函数(无论是 Java 还是 Python)的时间复杂度或为 O(n),或为 O(1) ,故整个算法可以在线性复杂度内完成。

空间复杂度 : O(n)。
split 函数 (不管哪种语言) 返回长度为 O(n) 的数组/列表,故算法使用线性的额外空间。

1
2
3
4
5
class Solution:
def countSegments(self, s: str) -> int:
if not s:
return 0
return len(s.split(' ')) # 这段代码是错误的,并不能解决连续过个空格的case
1
2
3
class Solution:
def countSegments(self, s: str) -> int:
return len(s.split())

区别:

split()的时候,多个空格当成一个空格;
split(' ')的时候,多个空格也要分割,会分割出来空。

题解二:

时间复杂度 : O(n),对每个下标进行常数时间的检测。

空间复杂度 : O(1),只使用了额外的几个整数,因此使用的空间为常数。

1
2
3
4
5
6
7
8
class Solution:
def countSegments(self, s: str) -> int:
count=0
for i in range(len(s)):
if s[i] != ' ' and (s[i-1] ==' ' or i==0 ):
print(s[i])
count+=1
return count
### 520. 检测大写字母
链接:https://leetcode-cn.com/problems/detect-capital/

给定一个单词,你需要判断单词的大写使用是否正确。

我们定义,在以下情况时,单词的大写用法是正确的:

全部字母都是大写,比如"USA"。
单词中所有字母都不是大写,比如"leetcode"。
如果单词不只含有一个字母,只有首字母大写, 比如 "Google"。
否则,我们定义这个单词没有正确使用大写字母。

示例 1:

输入: "USA"
输出: True
示例 2:

输入: "FlaG"
输出: False
注意: 输入是由大写和小写拉丁字母组成的非空单词。

题解一(内置函数):

1
2
3
4
5
6
7
8
9
10
class Solution:
def detectCapitalUse(self, word: str) -> bool:
if word.isupper() or word.islower() or word.istitle():
return True
return False

class Solution:
def detectCapitalUse(self, word: str) -> bool:
return word.isupper() or word.islower() or word.istitle()

题解二:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def detectCapitalUse(self, word: str) -> bool:
c1=0
c2=0
for i in word:
if (i>='a'):
c1+=1
else:
c2+=1
if (c1==len(word)) | (c2==len(word)):
return True

return ((c2==1) & (word[0] < 'a' ))

二、栈

42. 接雨水

链接:https://leetcode-cn.com/problems/trapping-rain-water/

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/youdao/water2.png

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路: 求出每个柱子上面能够存多少水,然后将每根柱子的存水量相加便能得到总的存水量,为求出每根柱子上能够存多少水,就要求出每根柱子左边最高的和右边最高柱子,然后用两者的最小值减去当前柱子的高度。 例如图中从左到右第三根柱子的高度为0,它左边最高柱子的值为1,右边最高柱子的值为3,因此它的最大存水量为 Min(1,3)-0=1。

原文讲解:https://blog.csdn.net/u013309870/article/details/70978279

题解一|暴力:
利用上面的思路,从左到右遍历每根柱子,遍历的时候求出每根柱子左边最高和右边最高柱子的值,然后利用两者的最小值减去当前柱子的高度就行了。

时间复杂度O(n^2),空间复杂度O(1)。

注意:如果当前柱子大于它左右最大值的任何一个是存不了水的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0

left,right=0,0
for i in range(length):
left,right=0,0
for j in range(i):
left=max(left,height[j])
for j in range(length-1,i,-1):
right=max(right,height[j])

tmp=min(left,right)
if tmp>height[i]:
waters+=tmp-height[i]
else:
waters+=0

return waters

题解二|优化:

题解一时间复杂度为O(n^2)。原因是对于每个元素都要从左到右,和从右到最左遍历其两边最大值,假如使用两个数组 left[ ] , right[ ]来保存每个元素左边最大值,右边最大值的话,这样就不用每次都遍历了,因此时间复杂度可以减少到O(n),空间复杂度为O(n),典型的空间换时间算法。

对于数组[ 5, 2 , 6 , 2 , 4 ]
它的左数组:[5,5,6,6,6]
它的右数组:[6,6,6,4,4]

算法的流程:

从左到右遍历一次求出每个元素左边的最大值,保存在 left 数组中。 
从右到左遍历一次求出每个元素右边的最大值,保存在right数。
最后一次遍历求出每个元素(每根柱子)的存水量。
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
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0
leftLargest,rightLargest=0,0
left,right=[0]*length,[0]*length

for i in range(length):
leftLargest=max(leftLargest,height[i])
left[i]=leftLargest

for i in range(length-1,-1,-1):
rightLargest=max(rightLargest,height[i])
right[i]=rightLargest

for i in range(length):
tmp=min(left[i],right[i])
if tmp>height[i]:
waters+=tmp-height[i]
else:
waters+=0

return waters

题解三|优化:

优化题解二,分析上面算法发现其实没有必要使用 left 数组,因为当从左到右遍历求存水量的过程中可以利用一个变量来保存当前元素左边的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0
leftLargest,rightLargest=0,0
right=[0]*length

for i in range(length-1,-1,-1):
rightLargest=max(rightLargest,height[i])
right[i]=rightLargest

for i in range(length):
leftLargest=max(leftLargest,height[i])
tmp=min(leftLargest,right[i])
if tmp>height[i]:
waters+=tmp-height[i]
else:
waters+=0

return waters

题解四|双指针:

image

上面左右两边的黄色块分别表示当前元素左边最大值和右边最大值。

left ,right分别代表从左到右移动和从右到左移动的指针。

如果当前元素的左边最大值比右边最大值小,则left指针向右移动,否则right指针向左移动。

这种左右指针移动的目的是为了保证所求的左右最大值一定是当前元素的左右最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0
leftLargest,rightLargest=0,0
left,right=0,length-1

while left<right:
leftLargest=max(leftLargest,height[left])
rightLargest=max(rightLargest,height[right])

if leftLargest > rightLargest:
waters+=rightLargest-height[right]
right-=1
else:
waters+=leftLargest-height[left]
left+=1

return waters
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def trap(height):
if not height: return 0
left = 0
right = len(height) - 1
res = 0
# 记录左右边最大值
left_max = height[left]
right_max = height[right]
while left < right:
if height[left] < height[right]:
if left_max > height[left]:
res += left_max - height[left]
else:
left_max = height[left]
left += 1
else:
if right_max > height[right]:
res += right_max - height[right]
else:
right_max = height[right]
right -= 1
return res

58.最后一个单词的长度

链接:https://leetcode-cn.com/problems/length-of-last-word/

给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。

如果不存在最后一个单词,请返回 0 。

说明:一个单词是指由字母组成,但不包含任何空格的字符串。

示例:

输入: "Hello World"
输出: 5

题解一|内置函数:

1
2
3
class Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.rstrip().split(' ')[-1])

题解二:
思路:
从字符串末尾开始向前遍历,其中主要有两种情况
第一种情况,以字符串”Hello World”为例,从后向前遍历直到遍历到头或者遇到空格为止,即为最后一个单词”World”的长度5
第二种情况,以字符串”Hello World “为例,需要先将末尾的空格过滤掉,再进行第一种情况的操作,即认为最后一个单词为”World”,长度为5
所以完整过程为先从后过滤掉空格找到单词尾部,再从尾部向前遍历,找到单词头部,最后两者相减,即为单词的长度
时间复杂度:O(n),n为结尾空格和结尾单词总体长度

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def lengthOfLastWord(self, s: str) -> int:
# return len(s.rstrip().split(' ')[-1])
end=len(s)-1
while end>=0 and s[end]==' ':
end-=1
if end < 0: return 0
start=end
while start >=0 and s[start] !=' ':
start-=1
return end-start

136.只出现一次的数字

链接:https://leetcode-cn.com/problems/single-number/

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

题解一|list:

1
2
3
4
5
6
7
8
9
10
class Solution:
def singleNumber(self, nums: List[int]) -> int:
temp=[]
for i in nums:
if i not in temp:
temp.append(i)
else:
temp.remove(i)
# return temp[0]
return temp.pop()

题解二|hash:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def singleNumber(self, nums: List[int]) -> int:
temp={}
for i in nums:
if i not in temp:
temp[i]=1
else:
temp[i]+=1
for k,v in temp.items():
if v==1:
return k

题解三|位运算:

异或运算有以下三个性质。

任何数和 0 做异或运算,结果仍然是原来的数,即 a⊕0=a。
任何数和其自身做异或运算,结果是 0,即 a⊕a=0。
异或运算满足交换律和结合律,即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
1
2
3
4
5
6
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res=0
for i in nums:
res^=i
return res
1
2
3
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x,y:x^y,nums)

137.只出现一次的数字 II

链接:https://leetcode-cn.com/problems/single-number-ii/

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]
输出: 3
示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

题解一|hash:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hash={}
for i in nums:
if i not in hash:
hash[i]=1
else:
hash[i]+=1
for k,v in hash.items():
if v!=3:
return k

题解二|数学运算:

3×(a+b+c)−(a+a+a+b+b+b+c)=2c

时间复杂度:O(N),遍历输入数组。
空间复杂度:O(N),存储 N/3N/3 个元素的集合。
1
2
3
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return (3*sum(set(nums))-sum(nums))//2

???题解三|位运算:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/or.png

409.最长回文串

链接:https://leetcode-cn.com/problems/longest-palindrome/

给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。

在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

题解一|hash:

时间复杂度:O(N),其中 N 为字符串 s 的长度。我们需要遍历每个字符一次。

空间复杂度:O(S),其中 S 为字符集大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def longestPalindrome(self, s: str) -> int:
if not s:
return 0
hash={}
sum=0
for each in s:
if each not in hash:
hash[each]=1
else:
hash[each]+=1
for key,value in hash.items():
sum+=value//2*2
if sum%2==0 and value%2==1:
sum+=1
return sum
1
2
3
4
5
6
7
8
9
class Solution:
def longestPalindrome(self, s):
ans = 0
count = collections.Counter(s)
for v in count.values():
ans += v // 2 * 2
if ans % 2 == 0 and v % 2 == 1:
ans += 1
return ans

836.矩形重叠

链接:https://leetcode-cn.com/problems/rectangle-overlap/

矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。

如果相交的面积为正,则称两矩形重叠。需要明确的是,只在角或边接触的两个矩形不构成重叠。

给出两个矩形,判断它们是否重叠并返回结果。



示例 1:

输入:rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出:true
示例 2:

输入:rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出:false


提示:

两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
矩形中的所有坐标都处于 -10^9 和 10^9 之间。
x 轴默认指向右,y 轴默认指向上。
你可以仅考虑矩形是正放的情况。

题解一|检查位置:

思路:如果两个矩形不重叠,那么一个矩形肯定在另一个矩形的四周(即左右上下)

矩形 rec1 在矩形 rec2 的左侧;

矩形 rec1 在矩形 rec2 的右侧;

矩形 rec1 在矩形 rec2 的上方;

矩形 rec1 在矩形 rec2 的下方。

左侧:rec1[2] <= rec2[0];

右侧:rec1[0] >= rec2[2];

上方:rec1[1] >= rec2[3];

下方:rec1[3] <= rec2[1]。

时间复杂度:O(1)
空间复杂度:O(1),不需要额外的空间。

1
2
3
4
5
6
7
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
if rec1[0]>=rec2[2] or rec1[1]>=rec2[3]:
return False
if rec2[0]>=rec1[2] or rec2[1]>=rec1[3]: # 注意是or,不是and。
return False
return True
1
2
3
4
5
6
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
if rec1[2]<=rec2[0] or rec1[3]<=rec2[1] or rec1[0]>=rec2[2] or rec1[1]>=rec2[3]:
return False
else:
return True

题解二|检查区域:

思路:如果两个矩形重叠,那么它们重叠的区域一定也是一个矩形,那么这代表了两个矩形与 x 轴平行的边(水平边)投影到 x 轴上时会有交集,与 y 轴平行的边(竖直边)投影到 y 轴上时也会有交集。因此,我们可以将问题看作一维线段是否有交集的问题。

矩形 rec1 和 rec2 的水平边投影到 x 轴上的线段分别为 (rec1[0], rec1[2]) 和 (rec2[0], rec2[2])。根据数学知识我们可以知道,当 min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) 时,这两条线段有交集。对于矩形 rec1 和 rec2 的竖直边投影到 yy 轴上的线段,同理可以得到,当 min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]) 时,这两条线段有交集。(画图)

时间复杂度:O(1)
空间复杂度:O(1),不需要额外的空间。

1
2
3
4
5
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
def isIntersec(pLeft,pRight,qLeft,qRight):
return min(pRight,qRight)>max(pLeft,qLeft)
return isIntersec(rec1[0],rec1[2],rec2[0],rec2[2]) and isIntersec(rec1[1],rec1[3],rec2[1],rec2[3])

1160.拼写单词

链接:https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/

给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。

假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。

注意:
    每次拼写时,chars 中的每个字母都只能用一次。
    返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1:

输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释: 
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。
示例 2:

输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。

 
提示:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母

题解一(hash):

思路:对于一个单词 word,只要其中的每个字母的数量都不大于 chars 中对应的字母的数量,那么就可以用 chars 中的字母拼写出 word。所以我们只需要用一个哈希表存储 chars 中每个字母的数量,再用一个哈希表存储 word 中每个字母的数量,最后将这两个哈希表的键值对逐一进行比较即可。

时间复杂度:O(n),其中 n 为所有字符串的长度和。我们需要遍历每个字符串,包括 chars 以及数组 words 中的每个单词。

空间复杂度:O(S),其中 S 为字符集大小,在本题中 S 的值为 26(所有字符串仅包含小写字母)。程序运行过程中,最多同时存在两个哈希表,使用的空间均不超过字符集大小 S,因此空间复杂度为 O(S)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
from collections import Counter
hashChars={}
hashWords={}
hashChars=Counter(chars)
res=0
# print(hashChars)
for word in words:
hashWords=Counter(word)
# print(hashWords)
for key in hashWords:
if hashChars[key] < hashWords[key]:
break
else:
res+=len(word)
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
res=0
hash1={}
for each in chars:
if each not in hash1:
hash1[each]=1
else:
hash1[each]+=1
for word in words:
hash2={}
for w in word:
if w not in hash2:
hash2[w]=1
else:
hash2[w]+=1
for key in hash2:
if hash2.get(key,0) > hash1.get(key,0):
break
else:
res+=len(word)
return res

for-else用法:

如果for循环正常结束,else中语句执行;
如果for循环是break退出的,则else中语句不执行;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for i in range(5):
print(i)
else:
print('hello')

for i in range(5):
print(i)
if i==2:
break
else:
print('hello')

输出:
0
1
2
3
4
hello
------------
0
1
2

题解二|hash:

dict.get(key, default=None)
key -- 字典中要查找的键。
default -- 如果指定键的值不存在时,返回该默认值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
res=''
for word in words:
hash={}
for i in range(len(chars)):
hash[chars[i]]=hash.get(chars[i],0)+1
count=0
for w in word:
if hash.get(w,0)>=1:
hash[w]=hash.get(w,0)-1
count+=1
else:
break
if count == len(word):
res+=word
return len(res)

PyTorch 是一个基于 Python 的科学计算包,主要定位两类人群:

NumPy 的替代品,可以利用 GPU 的性能进行计算。
深度学习研究平台拥有足够的灵活性和速度。

一、张量Tensors

Tensors 类似于 NumPy 的 ndarrays ,同时 Tensors 可以使用 GPU 进行计算。

1
2
3
4
5
6
7
from __future__ import print_function
import torch
# x=torch.empty(5,3) # 构造一个5x3矩阵,不初始化
# x=torch.rand(5,3) # 构造一个随机初始化的矩阵
# x=torch.zeros(5,3,dtype=torch.long) # 构造一个全0的矩阵,数据类型为long
x=torch.tensor([5.5,3]) # 构造一个张量,直接使用数据
print(x)
1
2
3
4
5
x=x.new_ones(5,3,dtype=torch.double) # 创建一个 tensor 基于已经存在的 tensor
print(x)
x=torch.randn_like(x,dtype=torch.float)
print(x)
print(x.size()) # 获取x的维度信息

注意:torch.Size 是一个元组,所以它支持左右的元组操作。

1
2
3
4
5
6
7
8
9
# 加法
y=torch.rand(5,3)
print(x+y)
print(torch.add(x,y))
result=torch.empty(5,3)
torch.add(x,y,out=result) # 提供一个输出tensor为参数
print(result)
y.add_(x) # 加法in-place
print(x)

注意:任何使张量会发生变化的操作都有一个前缀 ‘’。例如:x.copy(y), x.t_(), 将会改变 x.

1
print(x[:,1]) # 使用标准的Numpy类似的索引操作
1
2
3
4
5
# 改变大小:如果你想改变一个 tensor 的大小或者形状,你可以使用 torch.view:
x=torch.randn(4,4)
y=x.view(16)
z=x.view(-1,8) # the size -1 is inferred from other dimensions
print(x.size(),y.size(),z.size())
1
2
3
x=torch.randn(1)
print(x)
print(x.item()) # 使用.item() 来获得tensor的value 。

二、自动微分

autograd 包是 PyTorch 中所有神经网络的核心。autograd 软件包为 Tensors 上的所有操作提供自动微分。它是一个由运行定义的框架,这意味着以代码运行方式定义你的后向传播,并且每次迭代都可以不同。我们从 tensor 和 gradients举例:

2.1 Tensor

torch.Tensor 是包的核心类。如果将其属性 .requires_grad 设置为 True,则会开始跟踪针对 tensor 的所有操作。完成计算后,您可以调用 .backward() 来自动计算所有梯度。该张量的梯度将累积到 .grad 属性中。

要停止 tensor 历史记录的跟踪,您可以调用 .detach(),它将其与计算历史记录分离,并防止将来的计算被跟踪。

要停止跟踪历史记录(和使用内存),您还可以将代码块使用 with torch.no_grad(): 包装起来。在评估模型时,这是特别有用,因为模型在训练阶段具有 requires_grad = True 的可训练参数有利于调参,但在评估阶段我们不需要梯度。

还有一个类对于 autograd 实现非常重要那就是 Function。Tensor 和 Function 互相连接并构建一个非循环图,它保存整个完整的计算过程的历史信息。每个张量都有一个 .grad_fn 属性保存着创建了张量的 Function 的引用,(如果用户自己创建张量,则g rad_fn 是 None )。

如果你想计算导数,你可以调用 Tensor.backward()。如果 Tensor 是标量(即它包含一个元素数据),则不需要指定任何参数backward(),但是如果它有更多元素,则需要指定一个gradient 参数来指定张量的形状。

1
2
3
4
5
6
7
8
import torch
x=torch.ones(2,2,requires_grad=True) # 创建一个张量,设置 requires_grad=True 来跟踪与它相关的计算
print(x)

y=x+2
print(y)

print(y.grad_fn) # y 作为操作的结果被创建,所以它有 grad_fn

输出:

tensor([[1., 1.],
        [1., 1.]], requires_grad=True)
tensor([[3., 3.],
        [3., 3.]], grad_fn=<AddBackward0>)
<AddBackward0 object at 0x7f95ccaa0810>
1
2
3
z=y*y*3
out=z.mean()
print(z,out)

输出:

tensor([[27., 27.],
    [27., 27.]], grad_fn=<MulBackward0>) tensor(27., grad_fn=<MeanBackward0>)

.requires_grad_( … ) 会改变张量的 requires_grad 标记。输入的标记默认为 False ,如果没有提供相应的参数。

1
2
3
4
5
6
7
a=torch.randn(2,2)
a=(a*3)/(a-1)
print(a.requires_grad)
a.requires_grad_(True)
print(a.requires_grad)
b=(a*a).sum()
print(b.grad_fn)

输出:

False
True
<SumBackward0 object at 0x7fe1db427dd8>

2.2 梯度

现在后向传播,因为输出包含了一个标量,out.backward() 等同于out.backward(torch.tensor(1.))。

1
2
3
out.backward()
# out.backward(retain_graph=True)
print(x.grad) # 打印梯度 d(out)/dx

输出:

tensor([[4.5000, 4.5000],
    [4.5000, 4.5000]])
1
2
3
4
5
x=torch.randn(3,requires_grad=True)
y=x*2
while y.data.norm() < 1000:
y=y*2
print(y)

在这种情况下,y 不再是一个标量。torch.autograd 不能够直接计算整个雅可比,但是如果我们只想要雅可比向量积,只需要简单的传递向量给 backward 作为参数。

1
2
3
4
v = torch.tensor([0.1, 1.0, 0.0001], dtype=torch.float)
y.backward(v)

print(x.grad)
1
2
3
4
5
6
# 将代码包裹在 with torch.no_grad(),来停止对从跟踪历史中 的 .requires_grad=True 的张量自动求导。
print(x.requires_grad)
print((x ** 2).requires_grad)

with torch.no_grad():
print((x ** 2).requires_grad)

三、神经网络

神经网络可以通过 torch.nn 包来构建。

现在对于自动梯度(autograd)有一些了解,神经网络是基于自动梯度 (autograd)来定义一些模型。一个 nn.Module 包括层和一个方法 forward(input) 它会返回输出(output)。

数字图片识别的网络:一个简单的前馈神经网络,它接收输入,让输入一个接着一个的通过一些层,最后给出输出。
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/nn.png

神经网络训练过程:

1.定义一个包含可训练参数的神经网络

2.迭代整个输入

3.通过神经网络处理输入

4.计算损失(loss)

5.反向传播梯度到神经网络的参数

6.更新网络的参数,典型的用一个简单的更新方法:weight = weight - learning_rate *gradient

一、简介

PyTorch是一个基于Torch的Python开源机器学习库,用于自然语言处理等应用程序。它主要由Facebook人工智能小组开发,不仅能够实现强大的GPU加速,同时还支持动态神经网络,这一点是现在很多主流框架如TensorFlow都不支持的。

PyTorch提供了两个高级功能:
1.具有强大的GPU加速的张量计算(如Numpy)
2.包含自动求导系统的深度神经网络

除了Facebook之外,Twitter、GMU和Salesforce等机构都采用了PyTorch。

PyTorch的前身是Torch,Torch是一个有大量机器学习算法支持的科学计算框架,是一个与Numpy类似的张量(Tensor) 操作库,其特点是特别灵活,但因其采用了小众的编程语言是Lua,所以流行度不高,这也就有了PyTorch的出现。所以其实Torch是 PyTorch的前身,它们的底层语言相同,只是使用了不同的上层包装语言。

TensorFlow和Caffe都是命令式的编程语言,而且是静态的,首先必须构建一个神经网络,然后一次又一次使用相同的结构,如果想要改变网络的结构,就必须从头开始。但是对于PyTorch,通过反向求导技术,可以让你零延迟地任意改变神经网络的行为,而且其实现速度 快。正是这一灵活性是PyTorch对比TensorFlow的最大优势。

另外,PyTorch的代码对比TensorFlow而言,更加简洁直观,底层代码也更容易看懂,这对于使用它的人来说理解底层肯定是一件令人激动的事。

所以,总结一下PyTorch的优点:

支持GPU;
灵活,支持动态神经网络;
底层代码易于理解;
命令式体验;
自定义扩展;

当然,现今任何一个深度学习框架都有其缺点,PyTorch也不例外,对比TensorFlow,其全面性处于劣势,目前PyTorch还不支持快速傅里叶、沿维翻转张量和检查无穷与非数值张量;针对移动端、嵌入式部署以及高性能服务器端的部署其性能表现有待提升;其次因为这个框 架较新,使得他的社区没有那么强大,在文档方面其C库大多数没有文档。

二、环境搭建

安装Anaconda;
安装PyTorch;

我们知道,目前的计算机都采用的是图灵机架构,其本质就是用一条无限长的纸带,对应今天的存储器。随后在工程学的推演中,逐渐出现了寄存器、易失性存储器(内存)以及永久性存储器(硬盘)等产品。由于不同的存储器,其速度越快,单位价格也就越昂贵,因此,妥善利用好每一寸告诉存储器的空间,永远是系统设计的一个核心。

Python 程序在运行时,需要在内存中开辟出一块空间,用于存放运行时产生的临时变量,计算完成后,再将结果输出到永久性存储器中。但是当数据量过大,或者内存空间管理不善,就很容易出现内存溢出的情况,程序可能会被操作系统终止。

而对于服务器这种用于永不中断的系统来说,内存管理就显得更为重要了,不然很容易引发内存泄漏。
这里的内存泄漏是指程序本身没有设计好,导致程序未能释放已不再使用的内存,或者直接失去了对某段内存的控制,造成了内存的浪费。

那么,对于不会再用到的内存空间,Python 是通过什么机制来管理的呢?就是引用计数机制。

一、Python引用计数机制

Python 中一切皆对象,也就是说,在 Python 中你用到的一切变量,本质上都是类对象。

那么,如何知道一个对象永远都不能再使用了呢?很简单,就是当这个对象的引用计数值为 0 时,说明这个对象永不再用,自然它就变成了垃圾,需要被回收。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import os
import psutil # 获取系统信息


def showMemoryInfo(hint):
pid = os.getpid()
p = psutil.Process(pid)

info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))


def func():
showMemoryInfo('initial')
a = [i for i in range(10000000)]
showMemoryInfo('after a created')


func()
showMemoryInfo('finished')

输出:

initial memory used: 6.3828125 MB
after a created memory used: 392.92578125 MB
finished memory used: 10.85546875 MB

可以看到,当调用函数 func() 且列表 a 被创建之后,内存占用迅速增加到了 392 MB,而在函数调用结束后,内存则返回正常。这是因为,函数内部声明的列表 a 是局部变量,在函数返回后,局部变量的引用会注销掉,此时列表 a 所指代对象的引用计数为 0,Python 便会执行垃圾回收,因此之前占用的大量内存就又回来了。

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
import os
import psutil


def showMemoryInfo(hint):
pid = os.getpid()
p = psutil.Process(pid)

info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))


def func():
showMemoryInfo('initial')
global a
a = [i for i in range(10000000)]
showMemoryInfo('after a created')


func()
showMemoryInfo('finished')

输出:
initial memory used: 6.37890625 MB
after a created memory used: 392.74609375 MB
finished memory used: 392.74609375 MB

global a 表示将 a 声明为全局变量,则即使函数返回后,列表的引用依然存在,于是 a 对象就不会被当做垃圾回收掉,依然占用大量内存。

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
import os
import psutil


def showMemoryInfo(hint):
pid = os.getpid()
p = psutil.Process(pid)

info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))


def func():
showMemoryInfo('initial')
a = [i for i in range(10000000)]
showMemoryInfo('after a created')
return a

a = func()
showMemoryInfo('finished')

输出:
initial memory used: 6.4140625 MB
after a created memory used: 392.86328125 MB
finished memory used: 392.86328125 MB

如果把生成的列表返回,然后在主程序中接收,那么引用依然存在,垃圾回收也不会被触发,大量内存仍然被占用着.

??Python 内部的引用计数机制:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys

a = []
print(sys.getrefcount(a)) # 两次引用,一次来自 a,一次来自 getrefcount


def func(a):
# 四次引用,a,python 的函数调用栈,函数参数,和 getrefcount
print(sys.getrefcount(a))


func(a)
# 两次引用,一次来自 a,一次来自 getrefcount,函数 func 调用已经不存在
print(sys.getrefcount(a))

输出:

2
4
2

注意:sys.getrefcount() 函数用于查看一个变量的引用次数,不过别忘了,getrefcount 本身也会引入一次计数。

注意:在函数调用发生的时候,会产生额外的两次引用,一次来自函数栈,另一个是函数参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
a = []
print(sys.getrefcount(a)) # 两次
b = a
print(sys.getrefcount(a)) # 三次
c = b
d = b
e = c
f = e
g = d
print(sys.getrefcount(a)) # 八次

输出:
2
3
8

分析:

a、b、c、d、e、f、g 这些变量全部指代的是同一个对象,而 sys.getrefcount() 函数并不是统计一个指针,而是要统计一个对象被引用的次数,所以最后一共会有 8 次引用。

理解引用这个概念后,引用释放是一种非常自然和清晰的思想。相比 C 语言中需要使用 free 去手动释放内存,Python 的垃圾回收在这里可以说是省心省力了。

不过,有读者还是会好奇,如果想手动释放内存,应该怎么做呢?方法同样很简单,只需要先调用 del a 来删除一个对象,然后强制调用 gc.collect() 即可手动启动垃圾回收。例如:

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
import psutil
import os
import gc

def show_memory_info(hint):
'''
显示当前 python 程序占用的内存大小
:param hint:
:return:
'''
pid = os.getpid()
p = psutil.Process(pid)

info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))

show_memory_info('initial')
a=[i for i in range(10000000)]
show_memory_info('after a created')
del a
gc.collect()
show_memory_info('finished')
print(a)

输出:
initial memory used: 6.3984375 MB
after a created memory used: 392.77734375 MB
finished memory used: 10.70703125 MB
Traceback (most recent call last):
File "/Users/apple/PycharmProjects/python-learning/test/Account.py", line 24, in <module>
print(a)
NameError: name 'a' is not defined

问题:引用次数为 0 是垃圾回收启动的充要条件吗?还有没有其他可能性呢?

引用计数是其中最简单的实现,引用计数并非充要条件,它只能算作充分非必要条件,至于其他的可能性,下面所讲的循环引用正是其中一种。

二、循环引用

问题:如果有两个对象,之间互相引用,且不再被别的对象所引用,那么它们应该被垃圾回收吗?

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
import psutil
import os
import gc


def show_memory_info(hint):
'''
显示当前 python 程序占用的内存大小
:param hint:
:return:
'''
pid = os.getpid()
p = psutil.Process(pid)

info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))


def func():
show_memory_info('initial')
a = [i for i in range(10000000)]
b = [i for i in range(10000000)]
show_memory_info('after a,b created')
a.append(b)
b.append(a)


func()
show_memory_info('finished')

输出:
initial memory used: 6.4375 MB
after a,b created memory used: 779.69140625 MB
finished memory used: 779.69140625 MB

程序中,a 和 b 互相引用,并且作为局部变量在函数 func 调用结束后,a 和 b 这两个指针从程序意义上已经不存在,但从输出结果中看到,依然有内存占用,这是为什么呢?因为互相引用导致它们的引用数都不为 0。

试想一下,如果这段代码出现在生产环境中,哪怕 a 和 b 一开始占用的空间不是很大,但经过长时间运行后,Python 所占用的内存一定会变得越来越大,最终撑爆服务器,后果不堪设想。

有读者可能会说,互相引用还是很容易被发现的呀,问题不大。可是,更隐蔽的情况是出现一个引用环,在工程代码比较复杂的情况下,引用环真不一定能被轻易发现。那么应该怎么做呢?

Python 本身能够处理这种情况,可以通过显式调用 gc.collect() 来启动垃圾回收,例如:

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
import psutil
import os
import gc


def show_memory_info(hint):
'''
显示当前 python 程序占用的内存大小
:param hint:
:return:
'''
pid = os.getpid()
p = psutil.Process(pid)

info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))


def func():
show_memory_info('initial')
a = [i for i in range(10000000)]
b = [i for i in range(10000000)]
show_memory_info('after a,b created')
a.append(b)
b.append(a)


func()
gc.collect()
show_memory_info('finished')

输出:
initial memory used: 6.41015625 MB
after a,b created memory used: 779.81640625 MB
finished memory used: 11.4375 MB

事实上,Python 使用标记清除(mark-sweep)算法和分代收集(generational),来启用针对循环引用的自动垃圾回收。

1、标记清除算法:

先用图论来理解不可达的概念。对于一个有向图,如果从一个节点出发进行遍历,并标记其经过的所有节点;那么,在遍历结束后,所有没有被标记的节点,我们就称之为不可达节点。显而易见,这些节点的存在是没有任何意义的,自然的,我们就需要对它们进行垃圾回收。

当然,每次都遍历全图,对于 Python 而言是一种巨大的性能浪费。所以,在 Python 的垃圾回收实现中,标记清除算法使用双向链表维护了一个数据结构,并且只考虑容器类的对象(只有容器类对象才有可能产生循环引用)。

2、分代收集算法:

将 Python 中的所有对象分为三代。刚刚创立的对象是第 0 代;经过一次垃圾回收后,依然存在的对象,便会依次从上一代挪到下一代。而每一代启动自动垃圾回收的阈值,则是可以单独指定的。当垃圾回收器中新增对象减去删除对象达到相应的阈值时,就会对这一代对象启动垃圾回收。

事实上,分代收集基于的思想是,新生的对象更有可能被垃圾回收,而存活更久的对象也有更高的概率继续存活。因此,通过这种做法,可以节约不少计算量,从而提高 Python 的性能。

GIL,中文译为全局解释器锁。

1
2
3
4
5
6
7
8
9
10
11
12
import time

start = time.clock()


def count(n):
while n > 0:
n -= 1


count(10000)
print('Time used:', (time.clock() - start))

输出:Time used: 0.0006330000000000016

使用多(适量)线程可以提升程序性能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import time
from threading import Thread

start = time.clock()


def count(n):
while n > 0:
n -= 1


t1 = Thread(target=count, args=[10000 // 2])
t2 = Thread(target=count, args=[10000 // 2])
t1.start()
t2.start()
t1.join()
t2.join()
print('Time used:', (time.clock() - start))

输出:Time used: 0.0007749999999999979

从输出结果看,多线程不但没有提高性能,反而降低了。

如果使用更多线程进行尝试,会发现其运行效率和 2 个线程效率几乎一样(本机器测试使用 4 个线程,其执行效率约为 0.001)。

事实上,得到这样的结果是肯定的,因为 GIL 限制了 Python 多线程的性能不会像我们预期的那样。

那么,什么是 GIL 呢?GIL 是最流程的 CPython 解释器(平常称为 Python)中的一个技术术语,中文译为全局解释器锁,其本质上类似操作系统的 Mutex。GIL 的功能是:在 CPython 解释器中执行的每一个 Python 线程,都会先锁住自己,以阻止别的线程执行。

当然,CPython 不可能容忍一个线程一直独占解释器,它会轮流执行 Python 线程。这样一来,用户看到的就是“伪”并行,即 Python 线程在交替执行,来模拟真正并行的线程。

有读者可能会问,既然 CPython 能控制线程伪并行,为什么还需要 GIL 呢?其实,这和 CPython 的底层内存管理有关。

CPython 使用引用计数来管理内容,所有 Python 脚本中创建的实例,都会配备一个引用计数,来记录有多少个指针来指向它。当实例的引用计数的值为 0 时,会自动释放其所占的内存。

1
2
3
4
5
>>> import sys
>>> a = []
>>> b = a
>>> sys.getrefcount(a)
3

a 的引用计数值为 3,因为有 a、b 和作为参数传递的 getrefcount 都引用了一个空列表。

假设有两个 Python 线程同时引用 a,那么双方就都会尝试操作该数据,很有可能造成引用计数的条件竞争,导致引用计数只增加 1(实际应增加 2),这造成的后果是,当第一个线程结束时,会把引用计数减少 1,此时可能已经达到释放内存的条件(引用计数为 0),当第 2 个线程再次视图访问 a 时,就无法找到有效的内存了。

所以,CPython 引进 GIL,可以最大程度上规避类似内存管理这样复杂的竞争风险问题。

一、GIL底层实现原理

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/GIL.gif

GIL 在 Python 程序的工作流程:

Thread 1、2、3 轮流执行,每一个线程在开始执行时,都会锁住 GIL,以阻止别的线程执行;同样的,每一个线程执行完一段后,会释放 GIL,以允许别的线程开始利用资源。

为什么 Python 线程会去主动释放 GIL 呢?毕竟,如果仅仅要求 Python 线程在开始执行时锁住 GIL,且永远不去释放 GIL,那别的线程就都没有运行的机会。其实,CPython 中还有另一个机制,叫做间隔式检查(check_interval),意思是 CPython 解释器会去轮询检查线程 GIL 的锁住情况,每隔一段时间,Python 解释器就会强制当前线程去释放 GIL,这样别的线程才能有执行的机会。

注意:不同版本的 Python,其间隔式检查的实现方式并不一样。早期的 Python 是 100 个刻度(大致对应了 1000 个字节码);而 Python 3 以后,间隔时间大致为 15 毫秒。当然,我们不必细究具体多久会强制释放 GIL,读者只需要明白,CPython 解释器会在一个“合理”的时间范围内释放 GIL 就可以了。

每一个 Python 线程都是类似这样循环的封装,来看下面这段代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
for (;;) {
if (--ticker < 0) {
ticker = check_interval;
/* Give another thread a chance */
PyThread_release_lock(interpreter_lock);
/* Other threads may run now */
PyThread_acquire_lock(interpreter_lock, 1);
}
bytecode = *next_instr++;
switch (bytecode) {
/* execute the next instruction ... */
}
}

每个 Python 线程都会先检查 ticker 计数。只有在 ticker 大于 0 的情况下,线程才会去执行自己的代码。

?二、GIL不能绝对保证线程安全

注意:有了 GIL,并不意味着 Python 程序员就不用去考虑线程安全了,因为即便 GIL 仅允许一个 Python 线程执行,但别忘了 Python 还有 check interval 这样的抢占机制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import threading

n = 0

def foo():
global n
n += 1

threads = []
for i in range(100):
t = threading.Thread(target=foo)
threads.append(t)

for i in threads:
i.start()

for i in threads:
i.join()
print(n)

执行此代码会发现,其大部分时候会打印 100,但有时也会打印 99 或者 98,原因在于 n+=1 这一句代码让线程并不安全。如果去翻译 foo 这个函数的字节码就会发现,它实际上是由下面四行字节码组成:

1
2
3
4
5
6
>>> import dis
>>> dis.dis(foo)
LOAD_GLOBAL 0 (n)
LOAD_CONST 1 (1)
INPLACE_ADD
STORE_GLOBAL 0 (n)

而这四行字节码中间都是有可能被打断的!所以,千万别以为有了 GIL 程序就不会产生线程问题,我们仍然需要注意线程安全。

多线程和普通的单线程相比,其运行效率会有极大的提高。但多线程也存在一定的局限性:

1、多线程运行过程中容易被打断,还可能出现多个线程同时竞争同一资源的情况;
2、多线程切换本身存在一定的损耗,线程数不能无线增加,因此如果I\O操作非常频繁,多线程很有可能满足不了高效率、高质量的需求。

同步:是指操作一个接一个地执行,下一个操作必须等上一个操作执行完成之后才能开始执行;
异步:是指不同操作间可以相互交替执行,如果其中地某个操作被堵塞,程序并不会等待,而是会找出可执行的操作继续执行。

例子(做一份报表,并以邮件的方式提交):

同步:应先向软件中输入各项数据,接下来等报表生成,再写邮件提交;
异步:向软件中输出各项数据后,会先写邮件,等待报表生成后,暂停写邮件的工作去查看生成的报表,确认无误后在写邮件直到发送完毕。

一、关于Asyncio

Asyncio 和其他 Python 程序一样,是单线程的,它只有一个主线程,但可以进行多个不同的任务。这里的任务,指的就是特殊的 future 对象,我们可以把它类比成多线程版本里的多个线程。

这些不同的任务,被一个叫做事件循环(Event Loop)的对象所控制。
所谓事件循环,是指主线程每次将执行序列中的任务清空后,就去事件队列中检查是否有等待执行的任务,如果有则每次取出一个推到执行序列中执行,这个过程是循环往复的。

为了简化讲解这个问题,可以假设任务只有两个状态:,分别是预备状态和等待状态:

预备状态是指任务目前空闲,但随时待命准备运行;
等待状态是指任务已经运行,但正在等待外部的操作完成,比如 I/O 操作。

在这种情况下,事件循环会维护两个任务列表,分别对应这两种状态,并且选取预备状态的一个任务(具体选取哪个任务,和其等待的时间长短、占用的资源等等相关)使其运行,一直到这个任务把控制权交还给事件循环为止。

当任务把控制权交还给事件循环对象时,它会根据其是否完成把任务放到预备或等待状态的列表,然后遍历等待状态列表的任务,查看他们是否完成:如果完成,则将其放到预备状态的列表;反之,则继续放在等待状态的列表。而原先在预备状态列表的任务位置仍旧不变,因为它们还未运行。

这样,当所有任务被重新放置在合适的列表后,新一轮的循环又开始了,事件循环对象继续从预备状态的列表中选取一个任务使其执行…如此周而复始,直到所有任务完成。

值得一提的是,对于 Asyncio 来说,它的任务在运行时不会被外部的一些因素打断,因此 Asyncio 内的操作不会出现竞争资源(多个线程同时使用同一资源)的情况,也就不需要担心线程安全的问题了。

二、Asyncio的使用

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
import asyncio
import aiohttp
import time


async def downloadOne(url):
async with aiohttp.ClientSession() as session:
async with session.get(url) as resp:
print('Read {} from {}'.format(resp.content_length, url))


async def downloadAll(urls):
tasks = [asyncio.ensure_future(downloadOne(url)) for url in urls]
await asyncio.gather(*tasks)


def main():
urls = [
'http://c.biancheng.net',
'http://c.biancheng.net/c',
'http://c.biancheng.net/python'
]
start = time.perf_counter()
loop = asyncio.get_event_loop()

try:
loop.run_until_complete(downloadAll(urls))
finally:
loop.close()

end = time.perf_counter()
print('Download {} urls in {} seconds'.format(len(urls), end - start))


if __name__ == '__main__':
main()

输出:

Read None from http://c.biancheng.net
Read None from http://c.biancheng.net/c
Read None from http://c.biancheng.net/python
Download 3 urls in 0.10918640485033393 seconds

注意:Async 和 await 关键字是 Asyncio 的最新写法,表示这个语句(函数)是非阻塞的,正好对应前面所讲的事件循环的概念,即如果任务执行的过程需要等待,则将其放入等待状态的列表中,然后继续执行预备状态列表里的任务。

1
2
3
4
5
loop = asyncio.get_event_loop()
try:
loop.run_until_complete(downloadll(sites))
finally:
loop.close()

上述代码表示拿到事件循环对象,并运行 downloadAll() 函数,直到其结束,最后关闭这个事件循环对象。

注意:如果读者使用 Python 3.7 及以上版本,上述代码可以直接用 asyncio.run(downloadAll(sites)) 来代替。

至于 Asyncio 版本的函数 downloadAll(),和之前多线程版本有很大的区别:

1、这里的 asyncio.ensure_future(coro) 表示对输入的协程 coro 创建一个任务,安排它的执行,并返回此任务对象。可以看到,这里对每一个网站的下载,都创建了一个对应的任务。

注意:Python 3.7+ 版本之后,可以使用 asyncio.create_task(coro) 等效替代 asyncio.ensure_future(coro)。

2、asyncio.gather() 表示在事件循环对象中运行 aws 序列的所有任务。

可以看到,其输出结果显示用时只有 0.11s,比之前的多线程版本效率更高,充分体现其优势。

Asyncio 还有很多其他的用法,可以查看 Python 事件循环官方文档进行了解。

三、Asyncio的缺陷

在学习多线程编程中使用的是 requests 库,但本节使用的是 aiohttp 库,原因在于 requests 库并不兼容 Asyncio,而 aiohttp 库兼容。Asyncio 软件库的兼容性问题,在 Python3 的早期一直是个大问题,但是随着技术的发展,这个问题正逐步得到解决。

使用 Asyncio 时,因为在任务调度方面有了更大的自主权,写代码时就得更加注意,不然很容易出错。