50。pow(x,n)实现pow(x,n)，即计算x的n次方函数。示例1：输入：2.00000,10输出：1024.00000示例2：输入：2.10000,3输出：9.26100示例3：输入：2.00000,-2输出：0.25000解释：2-2=1/22=1/4=0.25解释:-100.0float,n->int)->float:ifn==0:return1flag=1ifn>0else-1n=abs(n)defhelper(x,n):ifn==0:return1#如果它是奇数ifn%2:res=helper(x,(n-1)//2)returnres*res*x#如果是偶数res=helper(x,n//2)returnres*resreturnhelper(x,n)ifflag>0else1./helper(x,n)时间复杂度：$O(log(n))$，空间复杂度：$O(日志（n））$。思路2二分法+迭代defmyPow(x->float,n->int)->float:ifn==0:return1flag=1ifn>0else-1n=abs(n)res=1。ans=xwhilen>0:如果n%2:res*=ansans*=ansn//=2returnresifflag>0else1./res时间复杂度为$O(log(n))$，空间复杂度为$O(1)$相比第二个思路，我个人觉得第一种思路比较好理解，但是需要额外的空间复杂度方法2，想了半天还是不能完全理解。53.最大子序列和给定一个整数数组nums，找到一个具有最大和的连续子数组（该子数组至少包含一个元素），并返回它的最大和。示例：输入：[-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组[4,-1,2,1]的和最大，即6。进阶：如果你已经实现了一个复杂度为O(n)的解决方案，尝试用更复杂的分治法来解决它。这道题是一道典型的动态规划题。由于是动态规划问题，所以需要明确选择和状态：$f(n)$表示以nums[n-1]结尾的最大子序列和。Choice：是否选择元素作为最大连续子数组和的元素。状态转移方程：$$f(n)=\begin{cases}f(n-1)+nums[n-1],&if(f(n-1)+nums[n-1]>nums[n-1])\\nums[n-1],&else\end{cases}$$简单理解就是如果当前元素不能使最大子序列和变大，则现有子序列将被丢弃。根据状态转移方程，可以写出如下代码defmaxSubArray(nums):ifnotnums:returnn=len(nums)b=nums[0]res=bforiinrange(1,n):b=max(b+nums[i],nums[i])res=max(res,b)returnres思路2分治法最大子序列和可以有3种情况最大子序列和出现在数组的左半部分最子序列序和出现在数组的右半边最大子序和横跨数组的左右半边最后的最大值为左半边的最大值，右半边的最大值，横跨左半边和右半部分的最大值defmaxSubArray(nums):ifnotnums:returnn=len(nums)ifn==1:returnnums[0]#左半部分的最大值max_left=maxSubArray(nums[:n//2])#右半边的最大值max_right=maxSubArray(nums[n//2:])#计算中间的最大子序列和#计算左边的最大子序列和从右到左max_l=nums[len(nums)//2-1]tmp=0foriinrange(len(nums)//2-1,-1,-1):tmp+=nums[i]max_l=max(tmp,max_l)#从左到右计算右边的最大子序列和max_r=nums[len(nums)//2]tmp=0foriinrange(len(nums)//2,len(nums)):tmp+=nums[i]max_r=max(tmp,max_r)#返回三个中的最大值returnmax(max_right,max_left,max_l+max_r)的时间复杂度为$nlog(n)$，空间复杂度为$O(log(n))$169。给定一个包含大多数元素的大小为n的数组，找出最多元素多数元素是数组中出现次数超过?n/2?的元素。您可以假设数组是非空的，并且给定数组中的元素总是占多数。例子1：输入：[3,2,3]输出：3例子2：输入：[2,2,1,1,1,2,2]输出：2最简单直接的思路就是排序，去most中间的数就够了，对应的复杂度就是排序的复杂度。时间复杂度为$O(nlog(n))$，空间复杂度为$log(n)$思路1分而治之根据题中mode的定义，如果数组分为左右两部分，则数组的众数必须是其中一个部分的众数。defmajorityElement(nums):如果不是nums:returndefhelper(low,high):如果low==high:returnnums[low]mid=(low+high)//2left=helper(low,mid)right=helper(mid,high)ifleft==right:returnleft#统计左半部分模式出现的次数cnt_left=sum([1foriinrange(low,high+1)ifnums[i]==left])#计算模式在右半部分出现的次数cnt_right=sum([1foriinrange(low,high+1)ifnums[i]==right])#returnleftifcnt_left>cnt_rightelserihtreturnhelper(0,len(nums)-1)时间复杂度为$O(nlog(n))$，空间复杂度为$O(log(n))$思路2Voting维护一个modescore，仅当当前模式得分等于0时，修改模式defmajorityElement(nums):ifnotnums:returnscore=1candidate=nums[0]forninnums[1:]:ifscore==0:candidate=nifn==candidate:分数+=1else:score-=1returncandidate时间复杂度为$O(n)$，空间复杂度为$O(1)$
