leetcode53. 最大子序和
給定一個(gè)整數(shù)數(shù)組 nums?，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋:?連續(xù)子數(shù)組?[4,-1,2,1] 的和最大，為?6。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。
思路：
1、標(biāo)識(shí)前面的累加和和最大值
2、判斷累加和以及最大值的處理
代碼如下：
class?Solution:
????def?maxSubArray(self,?nums:?List[int])?->?int:??????
????????stmp=nums[0]
????????smax=nums[0]???????
????????for?i?in?range(1,len(nums)):
????????????if?stmp>0:
????????????????stmp=stmp+nums[i]
????????????????smax=max(stmp,smax)
????????????else:
????????????????stmp=nums[i]
????????????????smax=max(stmp,smax)
????????return?smax
leetcode121. 買賣股票的最佳時(shí)機(jī)
給定一個(gè)數(shù)組，它的第?i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。
注意：你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
? ? 注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
思路：
本質(zhì)上求序列的最小值和當(dāng)前值的差值，取最大，默認(rèn)值為0
代碼如下：
class?Solution:
????def?maxProfit(self,?prices:?List[int])?->?int:
???????if?len(prices)==0:
???????????return?0
???????smax=0
???????min1=prices[0]
???????for?i?in?range(1,len(prices)):
???????????min1=min(min1,prices[i])
???????????smax=max(smax,prices[i]-min1)
? ? ? ?return?smax
leetcode448. 找到所有數(shù)組中消失的數(shù)字
給定一個(gè)范圍在? 1 ≤ a[i] ≤ n (?n = 數(shù)組大小 ) 的 整型數(shù)組，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字。
您能在不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)。
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
思路：
修改數(shù)組，講出現(xiàn)過元素作為索引同時(shí)將值置為小于0的值，再判斷大于0的索引為未出現(xiàn)過的值
代碼如下：
class?Solution(object):
????def?findDisappearedNumbers(self,?nums):
????????"""
????????:type?nums:?List[int]
????????:rtype:?List[int]
????????"""
????????result=[]
????????for?i?in?range(len(nums)):
????????????newindex=abs(nums[i])-1
????????????if?nums[newindex]>0:
????????????????nums[newindex]*=-1
? ? ? ? for?j?in?range(len(nums)):
?????????????if?nums[j]>0:
?????????????????result.append(j+1)
????????return?result
