這篇文章主要講解了“Python算法系列知識點有哪些”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Python算法系列知識點有哪些”吧！
主要思想
分治算法，即分而治之：把一個復雜問題分成兩個或更多的相同或相似子問題，直到最后子問題可以簡單地直接求解，最后將子問題的解合并為原問題的解。
歸并排序就是一個典型的分治算法。
三步走
和把大象塞進冰箱一樣，分治算法只要遵循三個步驟即可：分解 -> 解決 -> 合并。
1.分解：分解原問題為結(jié)構(gòu)相同的子問題（即尋找子問題）
2.解決：當分解到容易求解的邊界后，進行遞歸求解
3.合并：將子問題的解合并成原問題的解
這么一說似乎還是有點抽象？那我們通過經(jīng)典的排序算法歸并排序來體驗一下分治算法的核心思想。
歸并排序
思想
歸并排序的思想是：欲使序列有序，必先使其子序列有序。即先使得每個子序列有序，然后再將子序列合并成有序的列表。
因此，在歸并排序中的子問題就是：使子序列有序。
三步走
既然已經(jīng)找到了問題的子問題，是時候套用我們上述的三步走方法了。歸并排序的「三步走」如下：
1.分解：將序列劃分為兩部分
2.解決：遞歸地分別對兩個子序列進行歸并排序
3.合并：合并排序后的兩個子序列
舉例
來看一個具體的例子。
現(xiàn)在有一個待排序的序列：
10, 4, 6, 3, 8, 2, 5, 7
先對序列進行分解，把該序列一分為二，直到無法拆分為止。整個拆分過程如下：
然后對分解出的序列進行兩兩排序與合并：
10, 4 排序合并后：4, 10
6, 3 排序合并后：3, 6
8, 2 排序合并后：2, 8
5, 7 排序合并后：5, 7
……
整個歸并排序完整過程如下：
實現(xiàn)
def merge_sort(lst): # 從遞歸中返回長度為1的序列 if len(lst) <= 1: return lst middle = len(lst) / 2 # 1.分解：通過不斷遞歸，將原始序列拆分成 n 個小序列 left = merge_sort(lst[:middle]) right = merge_sort(lst[middle:]) # 進行排序與合并 return merge(left, right) def merge(left, right): i, j = 0, 0 result = [] # 2.解決：比較傳入的兩個子序列，對兩個子序列進行排序 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ōu)先級
題目描述
給定一個含有數(shù)字和運算符的字符串，為表達式添加括號，改變其運算優(yōu)先級以求出不同的結(jié)果。你需要給出所有可能的組合的結(jié)果。有效的運算符號包含 + , - 以及 *。
示例 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
思路
對于一個形如 x op y（op 為運算符，x 和 y 為數(shù)） 的算式而言，它的結(jié)果組合取決于 x 和 y 的結(jié)果組合數(shù)，而 x 和 y 又可以寫成形如 x op y 的算式。
因此，該問題的子問題就是 x op y 中的 x 和 y：以運算符分隔的左右兩側(cè)算式解。
然后我們來進行分治算法三步走：
1.分解：按運算符分成左右兩部分，分別求解
2.解決：實現(xiàn)一個遞歸函數(shù)，輸入算式，返回算式解
3.合并：根據(jù)運算符合并左右兩部分的解，得出最終解
其實算法相關(guān)的Python面試教程前面有跟大家講到，也可以找一下前面的內(nèi)容。
實現(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.分解：遇到運算符，計算左右兩側(cè)的結(jié)果集 # 2.解決：diffWaysToCompute 遞歸函數(shù)求出子問題的解 left = self.diffWaysToCompute(input[:i]) right = self.diffWaysToCompute(input[i+1:]) # 3.合并：根據(jù)運算符合并子問題的解 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算法系列知識點有哪些”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Python算法系列知識點有哪些這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！
重慶分公司
重慶分公司
