Python算法系列知識(shí)點(diǎn)有哪些

這篇文章主要講解了“Python算法系列知識(shí)點(diǎn)有哪些”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Python算法系列知識(shí)點(diǎn)有哪些”吧！

主要思想

分治算法，即分而治之：把一個(gè)復(fù)雜問題分成兩個(gè)或更多的相同或相似子問題，直到最后子問題可以簡(jiǎn)單地直接求解，最后將子問題的解合并為原問題的解。

歸并排序就是一個(gè)典型的分治算法。

三步走

和把大象塞進(jìn)冰箱一樣，分治算法只要遵循三個(gè)步驟即可：分解 -> 解決 -> 合并。

1.分解：分解原問題為結(jié)構(gòu)相同的子問題（即尋找子問題）

2.解決：當(dāng)分解到容易求解的邊界后，進(jìn)行遞歸求解

3.合并：將子問題的解合并成原問題的解

這么一說似乎還是有點(diǎn)抽象？那我們通過經(jīng)典的排序算法歸并排序來體驗(yàn)一下分治算法的核心思想。

歸并排序

思想

歸并排序的思想是：欲使序列有序，必先使其子序列有序。即先使得每個(gè)子序列有序，然后再將子序列合并成有序的列表。

因此，在歸并排序中的子問題就是：使子序列有序。

三步走

既然已經(jīng)找到了問題的子問題，是時(shí)候套用我們上述的三步走方法了。歸并排序的「三步走」如下：

1.分解：將序列劃分為兩部分

2.解決：遞歸地分別對(duì)兩個(gè)子序列進(jìn)行歸并排序

3.合并：合并排序后的兩個(gè)子序列

舉例

來看一個(gè)具體的例子。

現(xiàn)在有一個(gè)待排序的序列：

10, 4, 6, 3, 8, 2, 5, 7

先對(duì)序列進(jìn)行分解，把該序列一分為二，直到無法拆分為止。整個(gè)拆分過程如下：

然后對(duì)分解出的序列進(jìn)行兩兩排序與合并：

10, 4 排序合并后：4, 10
6, 3 排序合并后：3, 6
8, 2 排序合并后：2, 8
5, 7 排序合并后：5, 7
……

整個(gè)歸并排序完整過程如下：

實(shí)現(xiàn)

def merge_sort(lst):
 # 從遞歸中返回長(zhǎng)度為1的序列
 if len(lst) <= 1:
 return lst 
 middle = len(lst) / 2
 # 1.分解：通過不斷遞歸，將原始序列拆分成 n 個(gè)小序列
 left = merge_sort(lst[:middle]) 
 right = merge_sort(lst[middle:])
 # 進(jìn)行排序與合并
 return merge(left, right)
def merge(left, right):
 i, j = 0, 0
 result = []
 # 2.解決：比較傳入的兩個(gè)子序列，對(duì)兩個(gè)子序列進(jìn)行排序
 while i < len(left) and j < len(right): 
 if left[i] <= right[j]:
 result.append(left[i])
 i += 1
 else:
 result.append(right[j])
 j += 1
 # 3.合并：將排好序的子序列合并
 result.extend(left[i:]) 
 result.extend(right[j:])
 return result

真題演練

為運(yùn)算表達(dá)式設(shè)計(jì)優(yōu)先級(jí)

題目描述

給定一個(gè)含有數(shù)字和運(yùn)算符的字符串，為表達(dá)式添加括號(hào)，改變其運(yùn)算優(yōu)先級(jí)以求出不同的結(jié)果。你需要給出所有可能的組合的結(jié)果。有效的運(yùn)算符號(hào)包含 + , - 以及 *。

示例 1:

輸入: "2-1-1"
輸出: [0, 2]
解釋: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

輸入: "2*3-4*5"
輸出: [-34, -14, -10, -10, 10]
解釋: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

思路

對(duì)于一個(gè)形如 x op y（op 為運(yùn)算符，x 和 y 為數(shù)） 的算式而言，它的結(jié)果組合取決于 x 和 y 的結(jié)果組合數(shù)，而 x 和 y 又可以寫成形如 x op y 的算式。

因此，該問題的子問題就是 x op y 中的 x 和 y：以運(yùn)算符分隔的左右兩側(cè)算式解。

然后我們來進(jìn)行分治算法三步走：

1.分解：按運(yùn)算符分成左右兩部分，分別求解

2.解決：實(shí)現(xiàn)一個(gè)遞歸函數(shù)，輸入算式，返回算式解

3.合并：根據(jù)運(yùn)算符合并左右兩部分的解，得出最終解

其實(shí)算法相關(guān)的Python面試教程前面有跟大家講到，也可以找一下前面的內(nèi)容。

實(shí)現(xiàn)

class Solution:
 def diffWaysToCompute(self, input: str) -> List[int]:
 # 如果只有數(shù)字，直接返回
 if input.isdigit():
 return [int(input)]
 res = []
 for i, char in enumerate(input):
 if char in ['+', '-', '*']:
 # 1.分解：遇到運(yùn)算符，計(jì)算左右兩側(cè)的結(jié)果集
 # 2.解決：diffWaysToCompute 遞歸函數(shù)求出子問題的解
 left = self.diffWaysToCompute(input[:i])
 right = self.diffWaysToCompute(input[i+1:])
 # 3.合并：根據(jù)運(yùn)算符合并子問題的解
 for l in left:
 for r in right:
 if char == '+':
 res.append(l + r)
 elif char == '-':
 res.append(l - r)
 else:
 res.append(l * r)
 return res

感謝各位的閱讀，以上就是“Python算法系列知識(shí)點(diǎn)有哪些”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)Python算法系列知識(shí)點(diǎn)有哪些這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！