当前位置:首页 > 开发语言/框架 > C++

LeetCode的medium题会合(C++实现)八

优良自学吧提供LeetCode的medium题会合(C++实现)八,LeetCode的medium题集合(C++实现)八1 Pow(x, n) 该题采用二分法进行递归 double myPow(double x, int n) { if(n==0) return 1; if(n<0)

LeetCode的medium题集合(C++实现)八

1 Pow(x, n)
该题采用二分法进行递归

double myPow(double x, int n) {
        if(n==0) return 1;
        if(n<0)
        {
            n=(-n);
            x=1/x;
        }
        double res=myPow(x,n/2);
        if(n%2==0)
        {
            return res*res;
        }
        else
        {
            return res*res*x;
        }

    }

2 Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
该题可以采用动态规划解决,dp[i]=dp[i1]>0?dp[i1]+nums[i]:nums[i]. 很显然,当当前的最大值小于0时,计算下一个值时将小于0的数丢弃。

int maxSubArray(vector<int>& nums) {
        int max=INT_MIN;
        int n=nums.size();
        int mid=0;
        for(int i=0;i<n;i++)
        {
        //这里用mid,max替代dp数组以节省空间
            mid=mid+nums[i];
            mid=(nums[i]>=mid?nums[i]:mid);
            if(mid>max)
            {
                max=mid;
            }
        }
        return max;
    }

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢

最近更新