1、貪心算法
貪心算法的指導(dǎo)思想是：每一步下的最優(yōu)兼犯，也就是局部最優(yōu)忍捡，一定情況下逼近全局最優(yōu)集漾。
對應(yīng)刷題：買賣股票的最佳時機
（1）給定一個數(shù)組，它的第?i 個元素是一支給定股票第 i 天的價格砸脊。
設(shè)計一個算法來計算你所能獲取的最大利潤具篇。你可以盡可能地完成更多的交易（多次買賣一支股票）。
class?Solution:
????def?maxProfit(self,?prices:?List[int])?->?int:
????????#貪心算法
????????max1=0
????????k=len(prices)
????????for?i?in?range(1,k):
????????????max1=max1+max((prices[i]-prices[i-1]),0)
????????return?max1
（2）給定一個數(shù)組凌埂，它的第?i 個元素是一支給定股票第 i 天的價格栽连。
如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設(shè)計一個算法來計算你所能獲取的最大利潤侨舆。
class?Solution:
????def?maxProfit(self,?prices:?List[int])?->?int:
? ? ? ?if?len(prices)<=1:
????????????return?0
???????else:
????????result=0
????????min1=prices[0]
????????for?i?in?range(1,len(prices)):
????????????if?prices[i]<min1:
????????????????min1=prices[i]
????????????result=max(result,prices[i]-min1)
????????return?result
（3）中等 跳躍游戲
給定一個非負(fù)整數(shù)數(shù)組秒紧，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度挨下。
判斷你是否能夠到達最后一個位置熔恢。
class?Solution:
????def?canJump(self,?nums:?List[int])?->?bool:
????????mostright=0
????????for?i?in?range(len(nums)):
???????????????if?i<=mostright:
???????????????????mostright=max(mostright,i+nums[i])
???????????????????if?mostright>=len(nums)-1:
???????????????????????return?True
????????return?False
2、動態(tài)規(guī)劃
用一句話解釋動態(tài)規(guī)劃就是 “記住你之前做過的事”臭笆，如果更準(zhǔn)確些叙淌，其實是 “記住你之前得到的答案”。
動態(tài)規(guī)劃解題四個步驟：
問題拆解愁铺，找到問題之間的具體聯(lián)系
狀態(tài)定義
遞推方程推導(dǎo)
實現(xiàn)（初始化）
典型例題1：爬樓梯LeetCode 第 70 號問題：爬樓梯鹰霍。
假設(shè)你正在爬樓梯。需要?n階你才能到達樓頂茵乱。
每次你可以爬 1 或 2 個臺階茂洒。你有多少種不同的方法可以爬到樓頂呢？
時間優(yōu)瓶竭，空間不優(yōu)督勺。
class?Solution:
????def?climbStairs(self,?n:?int)?->?int:
????????reslut=[]
????????reslut.append(1)
????????reslut.append(2)
????????for?i?in?range(2,n):
?????????????reslut.append(reslut[i-1]+reslut[i-2])
????????return?reslut[n-1]
典型例題2：LeetCode 第 53 號問題：最大子序和。
給定一個整數(shù)數(shù)組?nums?斤贰，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）智哀，返回其最大和。
class?Solution:
????def?maxSubArray(self,?nums:?List[int])?->?int:
????????smax=nums[0]
????????tmp=nums[0]
????????for?i?in?range(1,len(nums)):
????????????tmp=max(tmp,0)
????????????smax=max(nums[i]+tmp,smax)
????????????tmp=tmp+nums[i]
????????return?smax
典型例題3:
你是一個專業(yè)的小偷荧恍，計劃偷竊沿街的房屋瓷叫。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)送巡，如果兩間相鄰的房屋在同一晚上被小偷闖入摹菠，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組授艰，計算你 不觸動警報裝置的情況下 辨嗽，一夜之內(nèi)能夠偷竊到的最高金額世落。
class?Solution:
????def?rob(self,?nums:?List[int])?->?int:
???????if?len(nums)==0:
????????????return?0
???????else:
????????if?len(nums)<=2:
????????????return?max(nums)
????????else:
????????????first=nums[0]
????????????second=max(nums[0],nums[1])
????????????for?i?in?range(2,len(nums)):
????????????????nums[i]=max(first+nums[i],second)
????????????????first=second
????????????????second=max(first,nums[i])
????????????return?nums[len(nums)-1]
通過這幾個簡單的例子淮腾，相信你不難發(fā)現(xiàn)糟需，解動態(tài)規(guī)劃題目其實就是拆解問題，定義狀態(tài)的過程谷朝，嚴(yán)格說來洲押，動態(tài)規(guī)劃并不是一個具體的算法，而是凌駕于算法之上的一種 思想 圆凰。
這種思想強調(diào)的是從局部最優(yōu)解通過一定的策略推得全局最優(yōu)解杈帐，從子問題的答案一步步推出整個問題的答案，并且利用空間換取時間专钉。從很多算法之中你都可以看到動態(tài)規(guī)劃的影子挑童，所以，還是那句話 技術(shù)都是相通的跃须，找到背后的本質(zhì)思想是關(guān)鍵站叼。
參考網(wǎng)址：https://www.cxyxiaowu.com/6781.html
3、分治思想
分治策略：對于一個規(guī)模為 n 的問題菇民，將其分解為 k 個規(guī)模較小的子問題尽楔，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題第练，然后將各子問題的解合并得到原問題的解阔馋。
關(guān)鍵點：遞歸地解子問題，合并得到原問題的解娇掏，歸并排序的典型思路呕寝。
典型例題1：二分查找。
x 的平方根:實現(xiàn)?int sqrt(int x)?函數(shù)婴梧。計算并返回?x?的平方根壁涎，其中?x 是非負(fù)整數(shù)。由于返回類型是整數(shù)志秃，結(jié)果只保留整數(shù)的部分怔球，小數(shù)部分將被舍去。
class?Solution:
????def?mySqrt(self,?x:?int)?->?int:
????????????????l=0
????????????????r=x
????????????????ans=-1
????????????????while?l<=r:
????????????????????m=int((l+r)/2)
????????????????????if?m*m<=x:
????????????????????????ans=m
????????????????????????l=m+1
????????????????????else:
????????????????????????r=m-1
????????????????return?ans
典型例題2：歸并排序浮还。
歸并排序竟坛，兩路已經(jīng)有序，合并成一路钧舌，關(guān)鍵點：如果兩個數(shù)組是有序的担汤，則可以便捷地計算兩個數(shù)組的交集。
首先對兩個數(shù)組進行排序洼冻，然后使用兩個指針遍歷兩個數(shù)組崭歧。
初始時，兩個指針分別指向兩個數(shù)組的頭部撞牢。每次比較兩個指針指向的兩個數(shù)組中的數(shù)字率碾，如果兩個數(shù)字不相等叔营，則將指向較小數(shù)字的指針右移一位，如果兩個數(shù)字相等所宰，將該數(shù)字添加到答案绒尊，并將兩個指針都右移一位。當(dāng)至少有一個指針超出數(shù)組范圍時仔粥，遍歷結(jié)束婴谱。
給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集躯泰。
classSolution: defintersect(self, nums1: List[int], nums2: List[int])-> List[int]: nums1.sort()
? ? ? ? nums2.sort()
? ? ? ? result=[]
? ? ? ? length1=len(nums1)
? ? ? ? length2=len(nums2)
? ? ? ? index1=0? ? ? ? index2=0? ? ? ? while index1<length1 and index2<length2:
? ? ? ? ? ? if nums1[index1]<nums2[index2]:
? ? ? ? ? ? ? ? index1=index1+1? ? ? ? ? ??
? ? ? ? ? ? elif nums1[index1]>nums2[index2]:
? ? ? ? ? ? ? ? ? index2=index2+1? ? ? ? ? ??
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? result.append(nums1[index1])
? ? ? ? ? ? ? ? ? index1=index1+1? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ?index2=index2+1? ? ? ??
? ? ? ? ? return result
歸并排序：歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表谭羔，即把待排序序列分為若干個子序列，每個子序列是有序的麦向。然后再把有序子序列合并為整體有序序列口糕。即先劃分為兩個部分，最后進行合并磕蛇。
典型例題3:977. 有序數(shù)組的平方
給定一個按非遞減順序排序的整數(shù)數(shù)組?A景描，返回每個數(shù)字的平方組成的新數(shù)組，要求也按非遞減順序排序秀撇。
low一點的版本：
class?Solution:
????def?sortedSquares(self,?A:?List[int])?->?List[int]:
????????length=len(A)
????????if?length==0:
????????????return?A
????????else:
????????????result=[]
????????????l=0
????????????r=length-1
????????????while?l<=r:
????????????????tmp1=A[l]*A[l]
????????????????tmp2=A[r]*A[r]
????????????????if?tmp1<tmp2:
????????????????????result.insert(0,tmp2)
????????????????????r=r-1
????????????????elif?tmp1>tmp2:
????????????????????result.insert(0,tmp1)
????????????????????l=l+1
????????????????else:
????????????????????result.insert(0,tmp1)
????????????????????if?l!=r:
???????????????????????result.insert(0,tmp2)
????????????????????l=l+1
????????????????????r=r-1
????????return??result
優(yōu)化后的版本：
class?Solution:
????def?sortedSquares(self,?A:?List[int])?->?List[int]:
????????length=len(A)
????????if?length==0:
????????????return?A
????????else:
????????????result=[]
????????????l=0
????????????r=length-1
????????????while?l<=r:
????????????????tmp1=A[l]*A[l]
????????????????tmp2=A[r]*A[r]
????????????????if?tmp1<tmp2:
????????????????????result.insert(0,tmp2)
????????????????????r=r-1
????????????????else:
????????????????????result.insert(0,tmp1)
????????????????????l=l+1
????????return??result
典型例題3：快速排序超棺。
快速排序的基本思想：當(dāng)前待排序的無序區(qū)為 A[low..high] ，利用分治法可將快速排序的基本思想描述為：
（1）分解：
在A[low..high]中任選一個記錄作為基準(zhǔn)(pivot)呵燕，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左棠绘、右兩個較小的子區(qū)間R[low..pivotpos-1) 和 R[pivotpos+1..high] ，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字 pivot.key再扭，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key氧苍，而基準(zhǔn)記錄pivot則位于正確的位置( pivotpos )上，它無須參加后續(xù)的排序泛范。
（2）求解：
通過遞歸調(diào)用快速排序?qū)ψ笕门啊⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
因為當(dāng)"求解"步驟中的兩個遞歸調(diào)用結(jié)束時罢荡，其左赡突、右兩個子區(qū)間已有序。對快速排序而言区赵，"組合"步驟無須做什么惭缰，可看作是空操作。
總結(jié)分析：
分治法將規(guī)模為 n 的問題分成 k 個規(guī)模為 n／m 的子問題去解笼才。設(shè)分解閥值 n0 = 1 漱受，且 adhoc 解規(guī)模為 1 的問題耗費 1 個單位時間。再設(shè)將原問題分解為 k 個子問題以及用 merge 將 k 個子問題的解合并為原問題的解需用 f(n) 個單位時間骡送。用T(n)表示該分治法解規(guī)模為 |P| = n 的問題所需的計算時間昂羡，則有：
??T（n）= k T(n/m) + f(n)
4絮记、遞歸算法
先下定義：遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。
通俗來說紧憾，遞歸算法的實質(zhì)是把問題分解成規(guī)牡角В縮小的同類問題的子問題昌渤，然后遞歸調(diào)用方法來表示問題的解赴穗。它有如下特點：
1. 一個問題的解可以分解為幾個子問題的解
2. 這個問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同膀息，求解思路完全一樣
3. 存在遞歸終止條件般眉，即必須有一個明確的遞歸結(jié)束條件，稱之為遞歸出口潜支。
典型例題1:漢諾塔問題
5甸赃、回溯算法
待補充：
查找算法
排序算法
搜索算法
字符串匹配算法
接下來是各種數(shù)據(jù)結(jié)構(gòu)：
線性表、散列表冗酿、樹埠对、圖
參考資料：
內(nèi)容來自：https://zhuanlan.zhihu.com/p/137041568
