Skip to content

Commit 2c4afff

Browse files
chefyuanchefyuan
authored
Merge pull request chefyuan#28 from goodyong/add_python
添加了python版本代码
2 parents a503e97 + 7dd5ce1 commit 2c4afff

29 files changed

+1553
-90
lines changed

‎animation-simulation/数据结构和算法/BF算法.md

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,8 @@
6868

6969
#### 题目代码
7070

71+
Java Code:
72+
7173
```java
7274
class Solution {
7375
public int strStr(String haystack, String needle) {
@@ -101,10 +103,38 @@ class Solution {
101103
}
102104
```
103105

106+
Python Code:
107+
108+
```python
109+
from typing import List
110+
class Solution:
111+
def strStr(self, haystack: str, needle: str)->int:
112+
haylen = len(haystack)
113+
needlen = len(needle)
114+
# 特殊情况
115+
if haylen < needlen:
116+
return -1
117+
if needlen == 0:
118+
return 0
119+
# 主串
120+
for i in range(0, haylen - needlen + 1):
121+
# 模式串
122+
j = 0
123+
while j < needlen:
124+
if haystack[i + j] != needle[j]:
125+
break
126+
j += 1
127+
# 匹配成功
128+
if j == needlen:
129+
return i
130+
return -1
131+
```
104132

105133

106134
我们看一下BF算法的另一种算法（显示回退），其实原理一样，就是对代码进行了一下修改，只要是看完咱们的动图，这个也能够一下就能看懂，大家可以结合下面代码中的注释和动图进行理解。
107135

136+
Java Code:
137+
108138
```java
109139
class Solution {
110140
public int strStr(String haystack, String needle) {
@@ -132,3 +162,29 @@ class Solution {
132162
}
133163
```
134164

165+
Python Code:
166+
167+
```python
168+
from typing import List
169+
class Solution:
170+
def strStr(self, haystack: str, needle: str)->int:
171+
# i代表主串指针，j模式串
172+
i = 0
173+
j = 0
174+
# 主串长度和模式串长度
175+
halen = len(haystack)
176+
nelen = len(needle)
177+
# 循环条件，这里只有 i 增长
178+
while i < halen and j < nelen:
179+
# 相同时，则移动 j 指针
180+
if haystack[i] == needle[j]:
181+
j += 1
182+
else:
183+
# 不匹配时，将 j 重新只想模式串的头部，将 i 本次匹配的开始位置的下一字符
184+
i -= j
185+
j = 0
186+
i += 1
187+
# 查询成功时返回索引，查询失败时返回 -1
188+
renum = i - nelen if j == nelen else -1
189+
return renum
190+
```

‎animation-simulation/数据结构和算法/BM.md

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,8 @@ BM 算法是从右往左进行比较，发现坏字符的时候此时 cac 已
122122

123123
这破图画起来是真费劲啊。下面我们来看一下算法代码，代码有点长，我都标上了注释也在网站上 AC 了，如果各位感兴趣可以看一下，不感兴趣理解坏字符和好后缀规则即可。可以直接跳到 KMP 部分
124124

125+
Java Code:
126+
125127
```java
126128
class Solution {
127129
public int strStr(String haystack, String needle) {
@@ -215,6 +217,89 @@ class Solution {
215217
}
216218
```
217219

220+
Python Code:
221+
222+
```python
223+
from typing import List
224+
class Solution:
225+
def strStr(self, haystack: str, needle: str)->int:
226+
haylen = len(haystack)
227+
needlen = len(needle)
228+
return self.bm(haystack, haylen, needle, needlen)
229+
230+
# 用来求坏字符情况下移动位数
231+
def badChar(self, b: str, m: int, bc: List[int]):
232+
# 初始化
233+
for i in range(0, 256):
234+
bc[i] = -1
235+
# m 代表模式串的长度，如果有两个 a，则后面那个会覆盖前面那个
236+
for i in range(0, m,):
237+
ascii = ord(b[i])
238+
bc[ascii] = i# 下标
239+
240+
# 用来求好后缀条件下的移动位数
241+
def goodSuffix(self, b: str, m: int, suffix: List[int], prefix: List[bool]):
242+
# 初始化
243+
for i in range(0, m):
244+
suffix[i] = -1
245+
prefix[i] = False
246+
for i in range(0, m - 1):
247+
j = i
248+
k = 0
249+
while j >= 0 and b[j] == b[m - 1 - k]:
250+
j -= 1
251+
k += 1
252+
suffix[k] = j + 1
253+
if j == -1:
254+
prefix[k] = True
255+
256+
def bm(self, a: str, n: int, b: str, m: int)->int:
257+
bc = [0] * 256# 创建一个数组用来保存最右边字符的下标
258+
self.badChar(b, m, bc)
259+
# 用来保存各种长度好后缀的最右位置的数组
260+
suffix_index = [0] * m
261+
# 判断是否是头部，如果是头部则True
262+
ispre = [False] * m
263+
self.goodSuffix(b, m, suffix_index, ispre)
264+
i = 0# 第一个匹配字符
265+
# 注意结束条件
266+
while i <= n - m:
267+
# 从后往前匹配，匹配失败，找到坏字符
268+
j = m - 1
269+
while j >= 0:
270+
if a[i + j] != b[j]:
271+
break
272+
j -= 1
273+
# 模式串遍历完毕，匹配成功
274+
if j < 0:
275+
return i
276+
# 下面为匹配失败时，如何处理
277+
# 求出坏字符规则下移动的位数，就是我们坏字符下标减最右边的下标
278+
x = j - bc[ord(a[i + j])]
279+
y = 0
280+
# 好后缀情况，求出好后缀情况下的移动位数,如果不含有好后缀的话，则按照坏字符来
281+
if y < m - 1 and m - 1 - j > 0:
282+
y = self.move(j, m, suffix_index, ispre)
283+
# 移动
284+
i += max(x, y)
285+
return -1
286+
287+
# j代表坏字符的下标
288+
def move(j: int, m: int, suffix_index: List[int], ispre: List[bool])->int:
289+
# 好后缀长度
290+
k = m - 1 - j
291+
# 如果含有长度为 k 的好后缀，返回移动位数
292+
if suffix_index[k] != -1:
293+
return j - suffix_index[k] + 1
294+
# 找头部为好后缀子串的最大长度，从长度最大的子串开始
295+
for r in range(j + 2, m):
296+
# //如果是头部
297+
if ispre[m - r] == True:
298+
return r
299+
# 如果没有发现好后缀匹配的串，或者头部为好后缀子串，则移动到 m 位，也就是匹配串的长度
300+
return m
301+
```
302+
218303
我们来理解一下我们代码中用到的两个数组，因为两个规则的移动位数，只与模式串有关，与主串无关，所以我们可以提前求出每种情况的移动情况，保存到数组中。
219304

220305
![头缀函数](https://cdn.jsdelivr.net/gh/tan45du/photobed@master/photo/头缀函数.145da63ig3s0.png)

‎animation-simulation/数据结构和算法/KMP.md

Lines changed: 59 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,7 @@ class Solution {
113113
k = next[k];
114114
}
115115
// 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
116-
//然后 k - 1 又和 i 相同，最长前后缀加1，即可
116+
//然后 k + 1 又和 i 相同，最长前后缀加1，即可
117117
if (needle[k+1] == needle[i]) {
118118
++k;
119119
}
@@ -125,5 +125,63 @@ class Solution {
125125
}
126126
```
127127

128+
Python Code:
129+
130+
```python
131+
from typing import List
132+
class Solution:
133+
def strStr(self, haystack: str, needle: str)->int:
134+
# 两种特殊情况
135+
if len(needle) == 0:
136+
return 0
137+
if len(haystack) == 0:
138+
return -1
139+
# 长度
140+
halen = len(haystack)
141+
nelen = len(needle)
142+
# 返回下标
143+
return self.kmp(haystack, halen, needle, nelen)
144+
145+
def kmp(self, hasyarr: str, halen: int, nearr: str, nelen: int)->int:
146+
# 获取next 数组
147+
next = self.next(nearr, nelen)
148+
j = 0
149+
for i in range(0, halen):
150+
# 发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
151+
# 前缀的后一位,和咱们移动模式串的含义相同
152+
while j > 0 and hasyarr[i] != nearr[j]:
153+
j = next[j - 1] + 1
154+
# 超出长度时，可以直接返回不存在
155+
if nelen - j + i > halen:
156+
return -1
157+
# 如果相同就将指针同时后移一下，比较下个字符
158+
if hasyarr[i] == nearr[j]:
159+
j += 1
160+
# 遍历完整个模式串，返回模式串的起点下标
161+
if j == nelen:
162+
return i - nelen + 1
163+
return -1
164+
165+
# 这一块比较难懂，不想看的同学可以忽略，了解大致含义即可，或者自己调试一下，看看运行情况
166+
# 我会每一步都写上注释
167+
def next(self, needle: str, len:int)->List[int]:
168+
# 定义 next 数组
169+
next = [0] * len
170+
# 初始化
171+
next[0] = -1
172+
k = -1
173+
for i in range(1, len):
174+
# 我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
175+
# 因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
176+
# 就要找 k+1前一个元素在next数组里的值,即next[k+1]
177+
while k != -1 and needle[k + 1] != needle[i]:
178+
k = next[k]
179+
# 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
180+
# 然后 k + 1 又和 i 相同，最长前后缀加1，即可
181+
if needle[k + 1] == needle[i]:
182+
k += 1
183+
next[i] = k
184+
return next
185+
```
128186

129187

‎animation-simulation/数据结构和算法/冒泡排序.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,8 @@
8080

8181
我们来看一下这段代码
8282

83+
Java Code:
84+
8385
```java
8486
class Solution {
8587
public int[] sortArray(int[] nums) {
@@ -102,6 +104,25 @@ class Solution {
102104
}
103105
```
104106

107+
Python Code:
108+
109+
```python
110+
from typing import List
111+
class Solution:
112+
def sortArray(self, nums: List[int])->List[int]:
113+
leng = len(nums)
114+
for i in range(0, leng):
115+
for j in range(i + 1, leng):
116+
if nums[i] > nums[j]:
117+
self.swap(nums, i, j)
118+
return nums
119+
120+
def swap(self, nums: List[int], i: int, j: int):
121+
temp = nums[i]
122+
nums[i] = nums[j]
123+
nums[j] = temp
124+
```
125+
105126
我们来思考一下上面的代码，每次让关键字 nums[i] 和 nums[j] 进行比较如果 nums[i] > nums[j] 时则进行交换，这样 nums[0] 在经过一次循环后一定为最小值。那么这段代码是冒泡排序吗？
106127

107128
显然不是，我们冒泡排序的思想是两两比较**相邻记录**的关键字，注意里面有相邻记录，所以这段代码不是我们的冒泡排序，下面我们用动图来模拟一下冒泡排序的执行过程，看完之后一定可以写出正宗的冒泡排序。
@@ -143,6 +164,8 @@ class Solution {
143164

144165
我们来对冒泡排序进行改进
145166

167+
Java Code:
168+
146169
```java
147170
class Solution {
148171
public int[] sortArray(int[] nums) {
@@ -172,6 +195,32 @@ class Solution {
172195
}
173196
```
174197

198+
Python Code:
199+
200+
```python
201+
from typing import List
202+
class Solution:
203+
def sortArray(self, nums: List[int])->List[int]:
204+
leng = len(nums)
205+
# 标志位
206+
flag = True
207+
for i in range(0, leng):
208+
if not flag:
209+
break
210+
flag = False
211+
for j in range(0, leng - i - 1):
212+
if nums[j] > nums[j + 1]:
213+
self.swap(nums, j, j + 1)
214+
# 发生交换，则变为true，下次继续判断
215+
flag = True
216+
return nums
217+
218+
def swap(self, nums: List[int], i: int, j: int):
219+
temp = nums[i]
220+
nums[i] = nums[j]
221+
nums[j] = temp
222+
```
223+
175224
这样我们就避免掉了已经有序的情况下无意义的循环判断。
176225

177226
**冒泡排序时间复杂度分析**

0 commit comments

Comments
 (0)